1 /// \file RBTree.d
2 
3 module tagion.betterC.utils.RBTree;
4 /*
5  * [PROG]               : Red Black Tree
6  * [AUTHOR]             : Ashfaqur Rahman <sajib.finix@gmail.com>
7  * [PURPOSE]            : Red-Black tree is an algorithm for creating a balanced
8  *                        binary search tree data structure. Implementing a red-balck tree
9  *                        data structure is the purpose of this program.
10  *
11  * [DESCRIPTION]        : Its almost like the normal binary search tree data structure. But
12  *                        for keeping the tree balanced an extra color field is introduced to each node.
13  *                        This tree will mantain bellow properties.
14  *                                1. Nodes can be either RED or BLACK.
15  *                                2. root is BLACK.
16  *                                3. Leaves of this tree are null nodes. Here null is represented bya special node null.
17  *                                   Each null nodes are BLACK. So each leave is BLACK.
18  *                                4. Each RED node's parent is BLACK
19  *                                5. Each simple path taken from a node to descendent leaf has same number of black height.
20  *                                   That means each path contains same number of BLACK nodes.
21 
22  */
23 
24 @nogc:
25 import tagion.betterC.utils.Memory;
26 import tagion.betterC.utils.Stack;
27 
28 //import hibon.HiBONBase : Key;
29 import std.traits : isPointer;
30 
31 //import core.stdc.stdio;
32 
33 RBTreeT!(K) RBTree(K)(const bool owns = true) {
34     RBTreeT!(K) result;
35     with (result) {
36         nill = &NILL;
37         root = nill;
38     }
39     result.owns = owns;
40     return result;
41 }
42 
43 struct RBTreeT(K) {
44 @nogc:
45     enum Color {
46         RED,
47         BLACK
48     }
49 
50     static this() {
51         NILL.color = Color.BLACK;
52     }
53 
54     struct Node {
55     @nogc:
56         K item;
57         Color color;
58         Node* parent;
59         Node* left;
60         Node* right;
61     }
62 
63     private {
64         static Node NILL;
65         Node* nill;
66         Node* root;
67         bool owns;
68     }
69 
70     RBTreeT expropriate() {
71         auto result = RBTree!K(owns);
72         result.root = root;
73         root = nill;
74         return result;
75     }
76 
77     void surrender() {
78         root = nill;
79         owns = false;
80     }
81 
82     ~this() {
83         dispose;
84     }
85 
86     void dispose() {
87         void _dispose(Node* current) {
88             if (current !is nill) {
89                 _dispose(current.left);
90                 _dispose(current.right);
91                 if (owns) {
92                     static if (isPointer!K) {
93 
94                         
95 
96                             .dispose(current.item);
97                     }
98                     else static if (__traits(compiles, current.item.dispose)) {
99                         current.item.dispose;
100                     }
101                 }
102                 current.dispose;
103             }
104         }
105 
106         _dispose(root);
107         root = nill;
108     }
109 
110     /* Print tree items by inorder tree walk */
111 
112     @property empty() const pure {
113         return root is nill;
114     }
115 
116     protected Node* _search(const(K) item) {
117         Node* x = root;
118         while ((x !is nill) && (compare(x.item, item) != 0)) {
119             if (compare(x.item, item) > 0) {
120                 x = x.left;
121             }
122             else {
123                 x = x.right;
124             }
125         }
126         return x;
127     }
128 
129     static int compare(K)(scope const(K) a, scope const(K) b) pure {
130         static if (__traits(compiles, a.opCmp(b))) {
131             return a.opCmp(b);
132         }
133         else {
134             if (a < b) {
135                 return -1;
136             }
137             else if (a == b) {
138                 return 0;
139             }
140             return 1;
141         }
142     }
143 
144     version (WebAssembly) {
145         void dump(int iter_max = 20) const {
146             // empty
147         }
148     }
149     else {
150         void dump(int iter_max = 20) const {
151             import core.stdc.stdio;
152 
153             const(char[4]) INDENT = "  ->";
154             void _dump(const(Node*) current, const uint level = 1) @nogc {
155                 if (current !is nill) {
156                     _dump(current.left, level + 1);
157                     foreach (i; 0 .. level) {
158                         printf("%s", INDENT.ptr);
159                     }
160                     printf("%p\n", current);
161                     iter_max--;
162                     assert(iter_max > 0);
163                     _dump(current.right, level + 1);
164                 }
165             }
166 
167             printf("DUMP %p %p\n", root, nill);
168             _dump(root);
169         }
170     }
171 
172     const(Node*) search(const(K) item) const pure {
173         const(Node*) _search(const(Node*) current) pure {
174             if (current !is nill) {
175                 import std.traits;
176 
177                 const cmp = compare(current.item, item);
178                 if (cmp == 0) {
179                     return current;
180                 }
181                 else if (cmp > 0) {
182                     return _search(current.left);
183                 }
184                 else {
185                     return _search(current.right);
186                 }
187             }
188             return nill;
189         }
190 
191         auto result = _search(root);
192         if (result !is nill) {
193             return result;
194         }
195         return null;
196     }
197 
198     bool exists(K item) const {
199         //        const result=search(item);
200         return search(item) !is null;
201     }
202 
203     @property size_t length() const {
204         size_t count;
205         foreach (m; this[]) {
206             count++;
207         }
208         return count;
209     }
210 
211     protected Node* tree_minimum(Node* x) {
212         while (x.left !is nill) {
213             x = x.left;
214         }
215         return x;
216     }
217 
218     /*
219      * Insertion is done by the same procedure for BST Insert. Except new node is colored
220      * RED. As it is coloured RED it may violate property 2 or 4. For this reason an
221      * auxilary procedure called insert_fixup is called to fix these violation.
222      */
223 
224     bool insert(K item) {
225         bool result;
226         Node* z = create!Node;
227         scope (exit) {
228             if (!result) {
229                 z.dispose;
230             }
231         }
232         z.item = item;
233         return result = insert(z);
234     }
235 
236     const(K) get(const(K) item) const {
237         alias _K = const(K);
238         auto result = search(item);
239         if (result !is null) {
240             return result.item;
241         }
242         return K.init;
243     }
244 
245     private bool insert(Node* z) {
246         Node* x, y;
247         z.color = Color.RED;
248         z.left = nill;
249         z.right = nill;
250 
251         x = root;
252         y = nill;
253 
254         /*
255          * Go through the tree untill a leaf(null) is reached. y is used for keeping
256          * track of the last non-null node which will be z's parent.
257          */
258         while (x !is nill) {
259             y = x;
260             const cmp = compare(z.item, x.item);
261             if (cmp < 0) {
262                 x = x.left;
263             }
264             else if (cmp == 0) {
265                 // Item already exists
266                 return false;
267             }
268             else {
269                 x = x.right;
270             }
271         }
272 
273         if (y is nill) {
274             root = z;
275         }
276         else if (compare(z.item, y.item) <= 0) {
277             y.left = z;
278         }
279         else {
280             y.right = z;
281         }
282 
283         z.parent = y;
284 
285         insert_fixup(z);
286         return true;
287     }
288 
289     /*
290      * Here is the psudocode for fixing violations.
291      *
292      * while (z's parent is RED)
293      *              if (z's parent is z's grand parent's left child) then
294      *                      if (z's right uncle or grand parent's right child is RED) then
295      *                              make z's parent and uncle BLACK
296      *                              make z's grand parent RED
297      *                              make z's grand parent new z as it may violate property 2 & 4
298      *                              (so while loop will contineue)
299      *
300      *                      else(z's right uncle is not RED)
301      *                              if (z is z's parents right child) then
302      *                                      make z's parent z
303      *                                      left rotate z
304      *                              make z's parent's color BLACK
305      *                              make z's grand parent's color RED
306      *                              right rotate z's grand parent
307      *                              ( while loop won't pass next iteration as no violation)
308      *
309      *              else(z's parent is z's grand parent's right child)
310      *                      do exact same thing above just swap left with right and vice-varsa
311      *
312      * At this point only property 2 can be violated so make root BLACK
313      */
314 
315     protected void insert_fixup(Node* z) {
316         while (z.parent.color is Color.RED) {
317 
318             /* z's parent is left child of z's grand parent*/
319             if (z.parent is z.parent.parent.left) {
320 
321                 /* z's grand parent's right child is RED */
322                 if ((z.parent.parent.right !is nill) && (z.parent.parent.right.color is Color.RED)) {
323                     z.parent.color = Color.BLACK;
324                     z.parent.parent.right.color = Color.BLACK;
325                     z.parent.parent.color = Color.RED;
326                     z = z.parent.parent;
327                 }
328 
329                 /* z's grand parent's right child is not RED */
330             else {
331 
332                     /* z is z's parent's right child */
333                     if (z is z.parent.right) {
334                         z = z.parent;
335                         left_rotate(z);
336                     }
337 
338                     z.parent.color = Color.BLACK;
339                     z.parent.parent.color = Color.RED;
340                     right_rotate(z.parent.parent);
341                 }
342             }
343 
344             /* z's parent is z's grand parent's right child */
345             else {
346 
347                 /* z's left uncle or z's grand parent's left child is also RED */
348                 if (z.parent.parent.left.color is Color.RED) {
349                     z.parent.color = Color.BLACK;
350                     z.parent.parent.left.color = Color.BLACK;
351                     z.parent.parent.color = Color.RED;
352                     z = z.parent.parent;
353                 }
354 
355                 /* z's left uncle is not RED */
356                 else {
357                     /* z is z's parents left child */
358                     if (z is z.parent.left) {
359                         z = z.parent;
360                         right_rotate(z);
361                     }
362 
363                     z.parent.color = Color.BLACK;
364                     z.parent.parent.color = Color.RED;
365                     left_rotate(z.parent.parent);
366                 }
367             }
368         }
369 
370         root.color = Color.BLACK;
371     }
372 
373     /*
374      * Lets say y is x's right child. Left rotate x by making y, x's parent and x, y's
375      * left child. y's left child becomes x's right child.
376      *
377      *         x                            y
378      *        / \                          /  \
379      *      STA  y     ----------->       x   STC
380      *      / \                          /      \
381      *   STB   STC                      STA    STB
382      */
383 
384     void left_rotate(Node* x) {
385         Node* y;
386 
387         /* Make y's left child x's right child */
388         y = x.right;
389         x.right = y.left;
390         if (y.left !is nill) {
391             y.left.parent = x;
392         }
393 
394         /* Make x's parent y's parent and y, x's parent's child */
395         y.parent = x.parent;
396         if (y.parent is nill) {
397             root = y;
398         }
399         else if (x is x.parent.left) {
400             x.parent.left = y;
401         }
402         else {
403             x.parent.right = y;
404         }
405 
406         /* Make x, y's left child & y, x's parent */
407         y.left = x;
408         x.parent = y;
409     }
410 
411     /*
412      * Lets say y is x's left child. Right rotate x by making x, y's right child and y
413      * x's parent. y's right child becomes x's left child.
414      *
415      *          |                                                |
416      *          y
417      *         / \                                              / \
418      *        y   STA               ---------------->        STB   x
419      *       / \                                             / \
420      *    STB   STC                                       STC   STA
421      */
422 
423     protected void right_rotate(Node* x) {
424         Node* y;
425 
426         /* Make y's right child x's left child */
427         y = x.left;
428         x.left = y.right;
429         if (y.right !is nill) {
430             y.right.parent = x;
431         }
432 
433         /* Make x's parent y's parent and y, x's parent's child */
434         y.parent = x.parent;
435         if (y.parent is nill) {
436             root = y;
437         }
438         else if (x is x.parent.left) {
439             x.parent.left = y;
440         }
441         else {
442             x.parent.right = y;
443         }
444 
445         /* Make y, x's parent and x, y's child */
446         y.right = x;
447         x.parent = y;
448     }
449 
450     /*
451      * Deletion is done by the same mechanism as BST deletion. If z has no child, z is
452      * removed. If z has single child, z is replaced by its child. Else z is replaced by
453      * its successor. If successor is not z's own child, successor is replaced by its
454      * own child first. then z is replaced by the successor.
455      *
456      * A pointer y is used to keep track. In first two case y is z. 3rd case y is z's
457      * successor. So in first two case y is removed. In 3rd case y is moved.
458      *
459      *Another pointer x is used to keep track of the node which replace y.
460      *
461      * As removing or moving y can harm red-black tree properties a variable
462      * yOriginalColor is used to keep track of the original colour. If its BLACK then
463      * removing or moving y harm red-black tree properties. In that case an auxilary
464      * procedure remove_fixup(x) is called to recover this.
465      */
466 
467     bool remove(K item) {
468         auto remove_node = _search(item);
469         if (remove_node !is nill) {
470             remove(remove_node);
471             return true;
472         }
473         return false;
474     }
475 
476     protected void remove(ref Node* z) {
477         scope (exit) {
478             if (owns) {
479                 static if (isPointer!K) {
480 
481                     
482 
483                         .dispose(z.item);
484                 }
485                 else static if (__traits(compiles, z.item.dispose)) {
486                     z.item.dispose;
487                 }
488             }
489             z.dispose;
490         }
491         Node* y, x;
492         Color yOriginalColor;
493 
494         y = z;
495         yOriginalColor = y.color;
496 
497         if (z.left is nill) {
498             x = z.right;
499             transplant(z, z.right);
500         }
501         else if (z.right is nill) {
502             x = z.left;
503             transplant(z, z.left);
504         }
505         else {
506             y = tree_minimum(z.right);
507             yOriginalColor = y.color;
508 
509             x = y.right;
510 
511             if (y.parent == z) {
512                 x.parent = y;
513             }
514             else {
515                 transplant(y, y.right);
516                 y.right = z.right;
517                 y.right.parent = y;
518             }
519 
520             transplant(z, y);
521             y.left = z.left;
522             y.left.parent = y;
523             y.color = z.color;
524         }
525 
526         if (yOriginalColor is Color.BLACK) {
527             remove_fixup(x);
528         }
529     }
530 
531     /*
532      * As y was black and removed x gains y's extra blackness.
533      * Move the extra blackness of x until
534      *              1. x becomes root. In that case just remove extra blackness
535      *              2. x becomes a RED and BLACK node. in that case just make x BLACK
536      *
537      * First check if x is x's parents left or right child. Say x is left child
538      *
539      * There are 4 cases.
540      *
541      * Case 1: x's sibling w is red. transform case 1 into case 2 by recoloring
542      * w and x's parent. Then left rotate x's parent.
543      *
544      * Case 2: x's sibling w is black, w's both children is black. Move x and w's
545      * blackness to x's parent by coloring w to RED and x's parent to BLACK.
546      * Make x's parent new x.Notice if case 2 come through case 1 x's parent becomes
547      * RED and BLACK as it became RED in case 1. So loop will stop in next iteration.
548      *
549      * Case 3: w is black, w's left child is red and right child is black. Transform
550      * case 3 into case 4 by recoloring w and w's left child, then right rotate w.
551      *
552      * Case 4: w is black, w's right child is red. recolor w with x's parent's color.
553      * make x's parent BLACK, w's right child black. Now left rotate x's parent. Make x
554      * point to root. So loop will be stopped in next iteration.
555      *
556      * If x is right child of it's parent do exact same thing swapping left<->right
557      */
558 
559     protected void remove_fixup(Node* x) {
560         Node* w;
561 
562         while (x !is root && x.color is Color.BLACK) {
563             if (x is x.parent.left) {
564                 w = x.parent.right;
565 
566                 if (w.color is Color.RED) {
567                     w.color = Color.BLACK;
568                     x.parent.color = Color.RED;
569                     left_rotate(x.parent);
570                     w = x.parent.right;
571                 }
572 
573                 if (w.left.color is Color.BLACK && w.right.color is Color.BLACK) {
574                     w.color = Color.RED;
575                     x.parent.color = Color.BLACK;
576                     x = x.parent;
577                 }
578                 else {
579 
580                     if (w.right.color is Color.BLACK) {
581                         w.color = Color.RED;
582                         w.left.color = Color.BLACK;
583                         right_rotate(w);
584                         w = x.parent.right;
585                     }
586 
587                     w.color = x.parent.color;
588                     x.parent.color = Color.BLACK;
589                     x.right.color = Color.BLACK;
590                     left_rotate(x.parent);
591                     x = root;
592 
593                 }
594 
595             }
596             else {
597                 w = x.parent.left;
598 
599                 if (w.color is Color.RED) {
600                     w.color = Color.BLACK;
601                     x.parent.color = Color.BLACK;
602                     right_rotate(x.parent);
603                     w = x.parent.left;
604                 }
605 
606                 if (w.left.color is Color.BLACK && w.right.color is Color.BLACK) {
607                     w.color = Color.RED;
608                     x.parent.color = Color.BLACK;
609                     x = x.parent;
610                 }
611                 else {
612 
613                     if (w.left.color is Color.BLACK) {
614                         w.color = Color.RED;
615                         w.right.color = Color.BLACK;
616                         left_rotate(w);
617                         w = x.parent.left;
618                     }
619 
620                     w.color = x.parent.color;
621                     x.parent.color = Color.BLACK;
622                     w.left.color = Color.BLACK;
623                     right_rotate(x.parent);
624                     x = root;
625 
626                 }
627             }
628 
629         }
630 
631         x.color = Color.BLACK;
632     }
633 
634     /* replace node u with node v */
635     protected void transplant(Node* u, Node* v) {
636         if (u.parent is nill) {
637             root = v;
638         }
639         else if (u is u.parent.left) {
640             u.parent.left = v;
641         }
642         else {
643             u.parent.right = v;
644         }
645 
646         v.parent = u.parent;
647     }
648 
649     Range opSlice() const {
650         // In betterC the descructor of RBTree is call if the argument is passed to the Range struct
651         // This is the reason why the pointer to RBTree is used
652         auto range = Range(root);
653         return range;
654     }
655 
656     struct Range {
657         import std.traits;
658 
659         private {
660             Node* nill;
661             Node* current;
662             Node* walker;
663             Stack!(Node*) stack;
664         }
665 
666         this(const(Node*) root) {
667             this.nill = &RBTreeT.NILL;
668             walker = current = cast(Node*) root;
669             popFront;
670         }
671 
672         ~this() {
673             dispose;
674         }
675 
676         void dispose() {
677             stack.dispose;
678             walker = current = null;
679         }
680 
681         private void push(Node* node) {
682             stack.push(node);
683         }
684 
685         private Node* pop() {
686             if (stack.empty) {
687                 return nill;
688             }
689             return stack.pop;
690         }
691 
692         @property bool empty() const pure {
693             return (current is nill);
694         }
695 
696         @property const(K) front() const pure {
697             if (current is nill) {
698                 return K.init;
699             }
700             return current.item;
701         }
702 
703         void popFront() {
704             while (walker !is nill) {
705                 push(walker);
706                 walker = walker.left;
707             }
708 
709             if (!stack.empty) {
710                 walker = current = pop;
711                 walker = walker.right;
712             }
713             else {
714                 current = nill;
715             }
716         }
717     }
718 }
719 
720 unittest {
721 
722     enum tcase = [
723             60, 140, 20, 130, 30, 160, 110, 170, 40, 120, 50, 70, 100, 10, 150, 80,
724             90
725         ];
726     const(int[17]) result = [
727         10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170
728     ];
729 
730     assert(tcase.length == result.length);
731 
732     auto tree = RBTree!int(false);
733 
734     foreach (item; tcase) {
735         tree.insert(item);
736     }
737 
738     // Check that all the elements has been added
739     uint count;
740 
741     foreach (n; tree[]) {
742         const item = result[count++];
743         assert(n == item);
744     }
745 
746     // Check the size of the check lists
747     assert(tcase.length == count);
748 
749     enum indices = [5, 3, 14, 0, tcase.length - 1];
750 
751     // Check exists
752     foreach (i; indices) {
753         const item = result[i];
754         assert(tree.exists(item));
755     }
756 
757     // Check search
758     foreach (i; indices) {
759         const item = result[i];
760         const n = tree.search(item);
761         assert(n !is null);
762         assert(item == n.item);
763     }
764 
765     // Check remove
766     foreach (i; indices) {
767         const item = result[i];
768         const n_exists = tree.search(item);
769         assert(n_exists !is null);
770         tree.remove(item);
771         assert(!tree.exists(item));
772         const n = tree.search(item);
773         assert(n is null);
774         count--;
775         assert(tree.length == count);
776     }
777 }
778 
779 // unittest {
780 //     import hibon.HiBON;
781 //     auto tree=RBTree!(char[])(true);
782 //     import std.typecons : Tuple;
783 //     Tuple!(char[2], char[2], char[2], char[1], char[1], char[1]) check_list=[
784 //         "07", "17", "42", "a", "b", "c"
785 //         ];
786 
787 //     char[][check_list.length] key_list;
788 //     foreach(i, k; check_list) {
789 //         create(key_list[i], k);
790 //     }
791 
792 //     tree.insert(key_list[4]);
793 //     tree.insert(key_list[1]);
794 //     tree.insert(key_list[2]);
795 //     tree.insert(key_list[3]);
796 //     tree.insert(key_list[0]);
797 //     tree.insert(key_list[5]);
798 
799 //     {
800 //         auto range=tree[];
801 //         foreach(k; check_list) {
802 //             assert(k == range.front);
803 //             range.popFront;
804 //         }
805 //     }
806 
807 //     tree.remove(key_list[2]);
808 
809 //     {
810 //         auto range=tree[];
811 //         foreach(i, k; check_list) {
812 //             if (i !is 2) {
813 //                 assert(k == range.front);
814 //                 range.popFront;
815 //             }
816 //         }
817 //     }
818 // }
819 
820 unittest {
821     auto tree = RBTree!int(false);
822     tree.insert(42);
823     assert(tree.length is 1);
824     tree.insert(42);
825     assert(tree.length is 1);
826     //    assert(0);
827 }