1 /**
2 This module implements an associative array.
3 @nogc associative array, replacement for std::map and std::set.
4 Implementation of Red Black Tree from Phobos.
5 
6 Copyright: Guillaume Piolat 2015-2016.
7 Copyright: Copyright (C) 2008- by Steven Schveighoffer. Other code
8 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
9 License:   $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
10 Authors:   Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu), Guillaume Piolat
11 */
12 module dplug.core.map;
13 
14 import std.functional: binaryFun;
15 
16 import dplug.core.nogc;
17 
18 nothrow:
19 @nogc:
20 
21 /// Creates a new empty `Map`.
22 Map!(K, V, less, allowDuplicates) makeMap(K, V, alias less = "a < b", bool allowDuplicates = false)()
23 {
24     return Map!(K, V, less, allowDuplicates)(42);
25 }
26 
27 /// Tree-map, designed to replace std::map usage.
28 /// The API should looks closely like the builtin associative arrays.
29 /// O(lg(n)) insertion, removal, and search time.
30 /// `Map` is designed to operate even without initialization through `makeMap`.
31 struct Map(K, V, alias less = "a < b", bool allowDuplicates = false)
32 {
33 public:
34 nothrow:
35 @nogc:
36 
37     this(int dummy)
38     {
39         lazyInitialize();
40     }
41 
42     @disable this(this);
43 
44     ~this()
45     {
46         if (_rbt !is null)
47         {
48             destroyFree(_rbt);
49             _rbt = null;
50         }
51     }
52 
53     /// Insert an element in the container, if the container doesn't already contain 
54     /// an element with equivalent key. 
55     /// Returns: `true` if the insertion took place.
56     bool insert(K key, V value)
57     {
58         lazyInitialize();
59 
60         auto kv = KeyValue(key, value);
61         assert(_rbt);
62         return _rbt.insert(kv) != 0;
63     }
64 
65     /// Removes an element from the container.
66     /// Returns: `true` if the removal took place.
67     bool remove(K key)
68     {
69         if (!isInitialized)
70             return false;
71 
72         auto kv = KeyValue(key, V.init);
73         return _rbt.removeKey(kv) != 0;
74     }
75 
76     /// Removes all elements from the map.
77     void clearContents()
78     {
79         if (!isInitialized)
80             return;
81 
82         while(_rbt.length > 0)
83             _rbt.removeBack();
84     }
85 
86     /// Returns: A pointer to the value corresponding to this key, or null if not available.
87     ///          Live builtin associative arrays.
88     inout(V)* opBinaryRight(string op)(K key) inout if (op == "in")
89     {
90         if (!isInitialized)
91             return null;
92 
93         auto kv = KeyValue(key, V.init);
94         auto node = _rbt._find(kv);
95         if (node is null)
96             return null;
97         else
98             return &node.value.value;
99     }
100 
101     /// Returns: A reference to the value corresponding to this key.
102     ref inout(V) opIndex(K key) inout
103     {
104         inout(V)* p = key in this;
105         return *p;
106     }
107 
108     /// Updates a value associated with a key, creates it if necessary.
109     void opIndexAssign(V value, K key)
110     {
111         // PERF: this could be faster
112         V* p = key in this;
113         if (p is null)
114             insert(key, value);
115         else
116             *p = value;
117     }
118 
119     /// Returns: `true` if this key is contained.
120     bool contains(K key) const
121     {
122          if (!isInitialized)
123             return false;
124         auto kv = KeyValue(key, V.init);
125         return (kv in _rbt);
126     }
127 
128     /// Returns: Number of elements in the map.
129     size_t length() const
130     {
131         if (!isInitialized)
132             return 0;
133 
134         return _rbt.length();
135     }
136 
137     /// Returns: `ttue` is the map has no element.
138     bool empty() const
139     {
140         if (!isInitialized)
141             return true;
142         return _rbt.length() == 0;
143     }
144 
145     // Iterate by value only
146 
147     /// Fetch a forward range on all values.
148     Range!(MapRangeType.value) byValue()
149     {
150         if (!isInitialized)
151             return Range!(MapRangeType.value).init;
152 
153         return Range!(MapRangeType.value)(_rbt[]);
154     }
155 
156     /// ditto
157     ConstRange!(MapRangeType.value) byValue() const
158     {
159         if (!isInitialized)
160             return ConstRange!(MapRangeType.value).init;
161 
162         return ConstRange!(MapRangeType.value)(_rbt[]);
163     }
164 
165     /// ditto
166     ImmutableRange!(MapRangeType.value) byValue() immutable
167     {
168         if (!isInitialized)
169             return ImmutableRange!(MapRangeType.value).init;
170         
171         return ImmutableRange!(MapRangeType.value)(_rbt[]);
172     }
173 
174     // default opSlice is like byValue for builtin associative arrays
175     alias opSlice = byValue;
176 
177     // Iterate by key only
178 
179     /// Fetch a forward range on all keys.
180     Range!(MapRangeType.key) byKey()
181     {
182         if (!isInitialized)
183             return Range!(MapRangeType.key).init;
184 
185         return Range!(MapRangeType.key)(_rbt[]);
186     }
187 
188     /// ditto
189     ConstRange!(MapRangeType.key) byKey() const
190     {
191         if (!isInitialized)
192             return ConstRange!(MapRangeType.key).init;
193 
194         return ConstRange!(MapRangeType.key)(_rbt[]);
195     }
196 
197     /// ditto
198     ImmutableRange!(MapRangeType.key) byKey() immutable
199     {
200         if (!isInitialized)
201             return ImmutableRange!(MapRangeType.key).init;
202 
203         return ImmutableRange!(MapRangeType.key)(_rbt[]);
204     }
205 
206     // Iterate by key-value
207 
208     /// Fetch a forward range on all keys.
209     Range!(MapRangeType.keyValue) byKeyValue()
210     {
211         if (!isInitialized)
212             return Range!(MapRangeType.keyValue).init;
213 
214         return Range!(MapRangeType.keyValue)(_rbt[]);
215     }
216 
217     /// ditto
218     ConstRange!(MapRangeType.keyValue) byKeyValue() const
219     {
220         if (!isInitialized)
221             return ConstRange!(MapRangeType.keyValue).init;
222 
223         return ConstRange!(MapRangeType.keyValue)(_rbt[]);
224     }
225 
226     /// ditto
227     ImmutableRange!(MapRangeType.keyValue) byKeyValue() immutable
228     {
229         if (!isInitialized)
230             return ImmutableRange!(MapRangeType.keyValue).init;
231 
232         return ImmutableRange!(MapRangeType.keyValue)(_rbt[]);
233     }
234 
235     // Iterate by single value (return a range where all elements have equal key)
236 
237     /// Fetch a forward range on all elements with given key.
238     Range!(MapRangeType.value) byGivenKey(K key)
239     {
240        if (!isInitialized)
241             return Range!(MapRangeType.value).init;
242 
243         auto kv = KeyValue(key, V.init);
244         return Range!(MapRangeType.value)(_rbt.range(kv));
245     }
246 
247     /// ditto
248     ConstRange!(MapRangeType.value) byGivenKey(K key) const
249     {
250         if (!isInitialized)
251             return ConstRange!(MapRangeType.value).init;
252 
253         auto kv = KeyValue(key, V.init);
254         return ConstRange!(MapRangeType.value)(_rbt.range(kv));
255     }
256 
257     /// ditto
258     ImmutableRange!(MapRangeType.value) byGivenKey(K key) immutable
259     {
260         if (!isInitialized)
261             return ImmutableRange!(MapRangeType.value).init;
262 
263         auto kv = KeyValue(key, V.init);
264         return ImmutableRange!(MapRangeType.value)(_rbt.range(kv));
265     }
266 
267 
268 private:
269 
270     alias Range(MapRangeType type) = MapRange!(RBNode!KeyValue*, type);
271     alias ConstRange(MapRangeType type) = MapRange!(const(RBNode!KeyValue)*, type); /// Ditto
272     alias ImmutableRange(MapRangeType type) = MapRange!(immutable(RBNode!KeyValue)*, type); /// Ditto
273 
274     alias _less = binaryFun!less;
275     static bool lessForAggregate(const(KeyValue) a, const(KeyValue) b)
276     {
277         return _less(a.key, b.key);
278     }
279 
280     alias InternalTree = RedBlackTree!(KeyValue, lessForAggregate, allowDuplicates);
281 
282     // we need a composite value to reuse Phobos RedBlackTree
283     static struct KeyValue
284     {
285     nothrow:
286     @nogc:
287         K key;
288         V value;
289     }
290 
291     InternalTree _rbt;
292 
293     bool isInitialized() const
294     {
295         return _rbt !is null;
296     }
297 
298     void lazyInitialize()
299     {
300         if (_rbt is null)
301         {
302             _rbt = mallocNew!InternalTree();
303         }
304     }
305 }
306 
307 unittest
308 {
309     // It should be possible to use most function of an uninitialized Map
310     // All except functions returning a range will work.
311     Map!(int, string) m;
312 
313     assert(m.length == 0);
314     assert(m.empty);
315     assert(!m.contains(7));
316 
317     auto range = m.byKey();
318     assert(range.empty);
319     foreach(e; range)
320     {        
321     }
322 
323     m[1] = "fun";
324 }
325 
326 unittest
327 {
328     void test(bool removeKeys) nothrow @nogc
329     {
330         {
331             auto test = makeMap!(int, string);
332             int N = 100;
333             foreach(i; 0..N)
334             {
335                 int key = (i * 69069) % 65536;
336                 test.insert(key, "this is a test");
337             }
338             foreach(i; 0..N)
339             {
340                 int key = (i * 69069) % 65536;
341                 assert(test.contains(key));
342             }
343         
344             if (removeKeys)
345             {
346                 foreach(i; 0..N)
347                 {
348                     int key = (i * 69069) % 65536;
349                     test.remove(key);
350                 }
351             }
352             foreach(i; 0..N)
353             {
354                 int key = (i * 69069) % 65536;
355                 assert(removeKeys ^ test.contains(key)); // either keys are here or removed
356             }            
357         }
358     }
359     test(true);
360     test(false);
361 }
362 
363 unittest
364 {
365     Map!(string, int) aa = makeMap!(string, int);   // Associative array of ints that are
366     // indexed by string keys.
367     // The KeyType is string.
368     aa["hello"] = 3;  // set value associated with key "hello" to 3
369     int value = aa["hello"];  // lookup value from a key
370     assert(value == 3);    
371 
372     int* p;
373 
374     p = ("hello" in aa);
375     if (p !is null)
376     {
377         *p = 4;  // update value associated with key
378         assert(aa["hello"] == 4);
379     }
380 
381     aa.remove("hello");
382 }
383 
384 /// Creates a new empty `Set`.
385 Set!(K, less) makeSet(K, alias less = "a < b", bool allowDuplicates = false)()
386 {
387     return Set!(K, less, allowDuplicates)(42);
388 }
389 
390 
391 /// Set, designed to replace std::set usage.
392 /// O(lg(n)) insertion, removal, and search time.
393 /// `Set` is designed to operate even without initialization through `makeSet`.
394 struct Set(K, alias less = "a < b", bool allowDuplicates = false)
395 {
396 public:
397 nothrow:
398 @nogc:
399 
400     this(int dummy)
401     {
402          lazyInitialize();
403     }
404 
405     @disable this(this);
406 
407     ~this()
408     {
409         if (isInitialized)
410         {
411             destroyFree(_rbt);
412             _rbt = null;
413         }
414     }
415 
416     /// Insert an element in the container. 
417     /// If allowDuplicates is false, this can fail and return `false` 
418     /// if the already contains an element with equivalent key. 
419     /// Returns: `true` if the insertion took place.
420     bool insert(K key)
421     {
422         lazyInitialize();
423         return _rbt.insert(key) != 0;
424     }
425 
426     /// Removes an element from the container.
427     /// Returns: `true` if the removal took place.
428     bool remove(K key)
429     {
430         if (!isInitialized)
431             return false;
432         return _rbt.removeKey(key) != 0;
433     }
434 
435     /// Removes all elements from the set.
436     void clearContents()
437     {
438         if (!isInitialized)
439             return;
440         while(_rbt.length > 0)
441             _rbt.removeBack();
442     }
443 
444     /// Returns: `true` if the element is present.
445     bool opBinaryRight(string op)(K key) inout if (op == "in")
446     {
447         if (!isInitialized)
448             return false;
449         return key in _rbt;
450     }
451 
452     /// Returns: `true` if the element is present.
453     bool opIndex(K key) const
454     {
455         if (!isInitialized)
456             return false;
457         return key in _rbt;
458     }
459 
460     /// Returns: `true` if the element is present.
461     bool contains(K key) const
462     {
463         if (!isInitialized)
464             return false;
465         return key in _rbt;
466     }
467 
468     /// Fetch a range that spans all the elements in the container.
469     auto opSlice() inout
470     {
471         if (!isInitialized)
472             return nullRange();
473         return _rbt[];
474     }
475 
476     /// Returns: Number of elements in the set.
477     size_t length() const
478     {
479         if (!isInitialized)
480             return 0;
481         return _rbt.length();
482     }
483 
484     /// Returns: `ttue` is the set has no element.
485     bool empty() const
486     {
487         if (!isInitialized)
488             return true;
489         return _rbt.length() == 0;
490     }
491 
492 private:
493     alias InternalTree = RedBlackTree!(K, less, allowDuplicates); 
494     InternalTree _rbt;
495 
496     bool isInitialized() const
497     {
498         return _rbt !is null;
499     }
500 
501     void lazyInitialize()
502     {
503         if (_rbt is null)
504         {
505             _rbt = mallocNew!InternalTree();
506         }
507     }
508 
509     /**
510     * Return a range without any items.
511     */
512     auto nullRange()
513     {
514         return InternalTree.Range.init;
515     }
516 
517     /// Ditto
518     auto nullRange() const
519     {
520         return InternalTree.ConstRange.init;
521     }
522 
523     /// Ditto
524     auto nullRange() immutable
525     {
526         return InternalTree.ImmutableRange.init;
527     }
528 }
529 
530 unittest
531 {
532     // It should be possible to use most function of an uninitialized Set
533     // All except functions returning a range will work.
534     Set!(string) set;
535 
536     assert(set.length == 0);
537     assert(set.empty);
538     set.clearContents();
539     assert(!set.contains("toto"));
540 
541     auto range = set[];
542     assert(range.empty);
543     foreach(e; range)
544     {        
545     }
546 
547     // Finally create the internal state
548     set.insert("titi");
549     assert(set.contains("titi"));
550 }
551 
552 
553 unittest
554 {
555     {
556         Set!(string) keywords = makeSet!string;
557 
558         assert(keywords.insert("public"));
559         assert(keywords.insert("private"));
560         assert(!keywords.insert("private"));
561 
562         assert(keywords.remove("public"));
563         assert(!keywords.remove("non-existent"));
564 
565         assert(keywords.contains("private"));
566         assert(!keywords.contains("public"));
567     }
568 
569 }
570 
571 private:
572 
573 
574 /*
575 * Implementation for a Red Black node for use in a Red Black Tree (see below)
576 *
577 * this implementation assumes we have a marker Node that is the parent of the
578 * root Node.  This marker Node is not a valid Node, but marks the end of the
579 * collection.  The root is the left child of the marker Node, so it is always
580 * last in the collection.  The marker Node is passed in to the setColor
581 * function, and the Node which has this Node as its parent is assumed to be
582 * the root Node.
583 *
584 * A Red Black tree should have O(lg(n)) insertion, removal, and search time.
585 */
586 struct RBNode(V)
587 {
588 nothrow:
589 @nogc:
590     /*
591     * Convenience alias
592     */
593     alias Node = RBNode*;
594 
595     private Node _left;
596     private Node _right;
597     private Node _parent;
598 
599     /**
600     * The value held by this node
601     */
602     V value;
603 
604     /**
605     * Enumeration determining what color the node is.  Null nodes are assumed
606     * to be black.
607     */
608     enum Color : byte
609     {
610         Red,
611         Black
612     }
613 
614     /**
615     * The color of the node.
616     */
617     Color color;
618 
619     /**
620     * Get the left child
621     */
622     @property inout(RBNode)* left() inout
623     {
624         return _left;
625     }
626 
627     /**
628     * Get the right child
629     */
630     @property inout(RBNode)* right() inout
631     {
632         return _right;
633     }
634 
635     /**
636     * Get the parent
637     */
638     @property inout(RBNode)* parent() inout
639     {
640         return _parent;
641     }
642 
643     void deallocate()
644     {
645         //import core.stdc.stdio;
646         //printf("deallocate %p\n", &this);
647         destroyFree(&this);
648     }
649 
650     /**
651     * Set the left child.  Also updates the new child's parent node.  This
652     * does not update the previous child.
653     *
654     * Returns newNode
655     */
656     @property Node left(Node newNode)
657     {
658         _left = newNode;
659         if (newNode !is null)
660             newNode._parent = &this;
661         return newNode;
662     }
663 
664     /**
665     * Set the right child.  Also updates the new child's parent node.  This
666     * does not update the previous child.
667     *
668     * Returns newNode
669     */
670     @property Node right(Node newNode)
671     {
672         _right = newNode;
673         if (newNode !is null)
674             newNode._parent = &this;
675         return newNode;
676     }
677 
678     // assume _left is not null
679     //
680     // performs rotate-right operation, where this is T, _right is R, _left is
681     // L, _parent is P:
682     //
683     //      P         P
684     //      |   ->    |
685     //      T         L
686     //     / \       / \
687     //    L   R     a   T
688     //   / \           / \
689     //  a   b         b   R
690     //
691     /**
692     * Rotate right.  This performs the following operations:
693     *  - The left child becomes the parent of this node.
694     *  - This node becomes the new parent's right child.
695     *  - The old right child of the new parent becomes the left child of this
696     *    node.
697     */
698     Node rotateR()
699     {
700         assert(_left !is null);
701 
702         // sets _left._parent also
703         if (isLeftNode)
704             parent.left = _left;
705         else
706             parent.right = _left;
707         Node tmp = _left._right;
708 
709         // sets _parent also
710         _left.right = &this;
711 
712         // sets tmp._parent also
713         left = tmp;
714 
715         return &this;
716     }
717 
718     // assumes _right is non null
719     //
720     // performs rotate-left operation, where this is T, _right is R, _left is
721     // L, _parent is P:
722     //
723     //      P           P
724     //      |    ->     |
725     //      T           R
726     //     / \         / \
727     //    L   R       T   b
728     //       / \     / \
729     //      a   b   L   a
730     //
731     /**
732     * Rotate left.  This performs the following operations:
733     *  - The right child becomes the parent of this node.
734     *  - This node becomes the new parent's left child.
735     *  - The old left child of the new parent becomes the right child of this
736     *    node.
737     */
738     Node rotateL()
739     {
740         assert(_right !is null);
741 
742         // sets _right._parent also
743         if (isLeftNode)
744             parent.left = _right;
745         else
746             parent.right = _right;
747         Node tmp = _right._left;
748 
749         // sets _parent also
750         _right.left = &this;
751 
752         // sets tmp._parent also
753         right = tmp;
754         return &this;
755     }
756 
757 
758     /**
759     * Returns true if this node is a left child.
760     *
761     * Note that this should always return a value because the root has a
762     * parent which is the marker node.
763     */
764     @property bool isLeftNode() const
765     {
766         assert(_parent !is null);
767         return _parent._left is &this;
768     }
769 
770     /**
771     * Set the color of the node after it is inserted.  This performs an
772     * update to the whole tree, possibly rotating nodes to keep the Red-Black
773     * properties correct.  This is an O(lg(n)) operation, where n is the
774     * number of nodes in the tree.
775     *
776     * end is the marker node, which is the parent of the topmost valid node.
777     */
778     void setColor(Node end)
779     {
780         // test against the marker node
781         if (_parent !is end)
782         {
783             if (_parent.color == Color.Red)
784             {
785                 Node cur = &this;
786                 while (true)
787                 {
788                     // because root is always black, _parent._parent always exists
789                     if (cur._parent.isLeftNode)
790                     {
791                         // parent is left node, y is 'uncle', could be null
792                         Node y = cur._parent._parent._right;
793                         if (y !is null && y.color == Color.Red)
794                         {
795                             cur._parent.color = Color.Black;
796                             y.color = Color.Black;
797                             cur = cur._parent._parent;
798                             if (cur._parent is end)
799                             {
800                                 // root node
801                                 cur.color = Color.Black;
802                                 break;
803                             }
804                             else
805                             {
806                                 // not root node
807                                 cur.color = Color.Red;
808                                 if (cur._parent.color == Color.Black)
809                                     // satisfied, exit the loop
810                                     break;
811                             }
812                         }
813                         else
814                         {
815                             if (!cur.isLeftNode)
816                                 cur = cur._parent.rotateL();
817                             cur._parent.color = Color.Black;
818                             cur = cur._parent._parent.rotateR();
819                             cur.color = Color.Red;
820                             // tree should be satisfied now
821                             break;
822                         }
823                     }
824                     else
825                     {
826                         // parent is right node, y is 'uncle'
827                         Node y = cur._parent._parent._left;
828                         if (y !is null && y.color == Color.Red)
829                         {
830                             cur._parent.color = Color.Black;
831                             y.color = Color.Black;
832                             cur = cur._parent._parent;
833                             if (cur._parent is end)
834                             {
835                                 // root node
836                                 cur.color = Color.Black;
837                                 break;
838                             }
839                             else
840                             {
841                                 // not root node
842                                 cur.color = Color.Red;
843                                 if (cur._parent.color == Color.Black)
844                                     // satisfied, exit the loop
845                                     break;
846                             }
847                         }
848                         else
849                         {
850                             if (cur.isLeftNode)
851                                 cur = cur._parent.rotateR();
852                             cur._parent.color = Color.Black;
853                             cur = cur._parent._parent.rotateL();
854                             cur.color = Color.Red;
855                             // tree should be satisfied now
856                             break;
857                         }
858                     }
859                 }
860 
861             }
862         }
863         else
864         {
865             //
866             // this is the root node, color it black
867             //
868             color = Color.Black;
869         }
870     }
871 
872     /**
873     * Remove this node from the tree.  The 'end' node is used as the marker
874     * which is root's parent.  Note that this cannot be null!
875     *
876     * Returns the next highest valued node in the tree after this one, or end
877     * if this was the highest-valued node.
878     */
879     Node remove(Node end)
880     {
881         //
882         // remove this node from the tree, fixing the color if necessary.
883         //
884         Node x;
885         Node ret = next;
886 
887         // if this node has 2 children
888         if (_left !is null && _right !is null)
889         {
890             //
891             // normally, we can just swap this node's and y's value, but
892             // because an iterator could be pointing to y and we don't want to
893             // disturb it, we swap this node and y's structure instead.  This
894             // can also be a benefit if the value of the tree is a large
895             // struct, which takes a long time to copy.
896             //
897             Node yp, yl, yr;
898             Node y = ret; // y = next
899             yp = y._parent;
900             yl = y._left;
901             yr = y._right;
902             auto yc = y.color;
903             auto isyleft = y.isLeftNode;
904 
905             //
906             // replace y's structure with structure of this node.
907             //
908             if (isLeftNode)
909                 _parent.left = y;
910             else
911                 _parent.right = y;
912             //
913             // need special case so y doesn't point back to itself
914             //
915             y.left = _left;
916             if (_right is y)
917                 y.right = &this;
918             else
919                 y.right = _right;
920             y.color = color;
921 
922             //
923             // replace this node's structure with structure of y.
924             //
925             left = yl;
926             right = yr;
927             if (_parent !is y)
928             {
929                 if (isyleft)
930                     yp.left = &this;
931                 else
932                     yp.right = &this;
933             }
934             color = yc;
935         }
936 
937         // if this has less than 2 children, remove it
938         if (_left !is null)
939             x = _left;
940         else
941             x = _right;
942 
943         bool deferedUnlink = false;
944         if (x is null)
945         {
946             // pretend this is a null node, defer unlinking the node
947             x = &this;
948             deferedUnlink = true;
949         }
950         else if (isLeftNode)
951             _parent.left = x;
952         else
953             _parent.right = x;
954 
955         // if the color of this is black, then it needs to be fixed
956         if (color == color.Black)
957         {
958             // need to recolor the tree.
959             while (x._parent !is end && x.color == Node.Color.Black)
960             {
961                 if (x.isLeftNode)
962                 {
963                     // left node
964                     Node w = x._parent._right;
965                     if (w.color == Node.Color.Red)
966                     {
967                         w.color = Node.Color.Black;
968                         x._parent.color = Node.Color.Red;
969                         x._parent.rotateL();
970                         w = x._parent._right;
971                     }
972                     Node wl = w.left;
973                     Node wr = w.right;
974                     if ((wl is null || wl.color == Node.Color.Black) &&
975                         (wr is null || wr.color == Node.Color.Black))
976                     {
977                         w.color = Node.Color.Red;
978                         x = x._parent;
979                     }
980                     else
981                     {
982                         if (wr is null || wr.color == Node.Color.Black)
983                         {
984                             // wl cannot be null here
985                             wl.color = Node.Color.Black;
986                             w.color = Node.Color.Red;
987                             w.rotateR();
988                             w = x._parent._right;
989                         }
990 
991                         w.color = x._parent.color;
992                         x._parent.color = Node.Color.Black;
993                         w._right.color = Node.Color.Black;
994                         x._parent.rotateL();
995                         x = end.left; // x = root
996                     }
997                 }
998                 else
999                 {
1000                     // right node
1001                     Node w = x._parent._left;
1002                     if (w.color == Node.Color.Red)
1003                     {
1004                         w.color = Node.Color.Black;
1005                         x._parent.color = Node.Color.Red;
1006                         x._parent.rotateR();
1007                         w = x._parent._left;
1008                     }
1009                     Node wl = w.left;
1010                     Node wr = w.right;
1011                     if ((wl is null || wl.color == Node.Color.Black) &&
1012                         (wr is null || wr.color == Node.Color.Black))
1013                     {
1014                         w.color = Node.Color.Red;
1015                         x = x._parent;
1016                     }
1017                     else
1018                     {
1019                         if (wl is null || wl.color == Node.Color.Black)
1020                         {
1021                             // wr cannot be null here
1022                             wr.color = Node.Color.Black;
1023                             w.color = Node.Color.Red;
1024                             w.rotateL();
1025                             w = x._parent._left;
1026                         }
1027 
1028                         w.color = x._parent.color;
1029                         x._parent.color = Node.Color.Black;
1030                         w._left.color = Node.Color.Black;
1031                         x._parent.rotateR();
1032                         x = end.left; // x = root
1033                     }
1034                 }
1035             }
1036             x.color = Node.Color.Black;
1037         }
1038 
1039         if (deferedUnlink)
1040         {
1041             //
1042             // unlink this node from the tree
1043             //
1044             if (isLeftNode)
1045                 _parent.left = null;
1046             else
1047                 _parent.right = null;
1048         }
1049 
1050         // clean references to help GC - Bugzilla 12915
1051         _left = _right = _parent = null;
1052 
1053         return ret;
1054     }
1055 
1056     /**
1057     * Return the leftmost descendant of this node.
1058     */
1059     @property inout(RBNode)* leftmost() inout
1060     {
1061         inout(RBNode)* result = &this;
1062         while (result._left !is null)
1063             result = result._left;
1064         return result;
1065     }
1066 
1067     /**
1068     * Return the rightmost descendant of this node
1069     */
1070     @property inout(RBNode)* rightmost() inout
1071     {
1072         inout(RBNode)* result = &this;
1073         while (result._right !is null)
1074             result = result._right;
1075         return result;
1076     }
1077 
1078     /**
1079     * Returns the next valued node in the tree.
1080     *
1081     * You should never call this on the marker node, as it is assumed that
1082     * there is a valid next node.
1083     */
1084     @property inout(RBNode)* next() inout
1085     {
1086         inout(RBNode)* n = &this;
1087         if (n.right is null)
1088         {
1089             while (!n.isLeftNode)
1090                 n = n._parent;
1091             return n._parent;
1092         }
1093         else
1094             return n.right.leftmost;
1095     }
1096 
1097     /**
1098     * Returns the previous valued node in the tree.
1099     *
1100     * You should never call this on the leftmost node of the tree as it is
1101     * assumed that there is a valid previous node.
1102     */
1103     @property inout(RBNode)* prev() inout
1104     {
1105         inout(RBNode)* n = &this;
1106         if (n.left is null)
1107         {
1108             while (n.isLeftNode)
1109                 n = n._parent;
1110             return n._parent;
1111         }
1112         else
1113             return n.left.rightmost;
1114     }
1115 }
1116 
1117 // Range type for RedBlackTree
1118 private struct RBRange(N)
1119 {
1120 nothrow:
1121 @nogc:
1122     alias Node = N;
1123     alias Elem = typeof(Node.value);
1124 
1125     private Node _begin = null;
1126     private Node _end = null;
1127 
1128     private this(Node b, Node e)
1129     {
1130         _begin = b;
1131         _end = e;
1132     }
1133 
1134     /**
1135     * Returns $(D true) if the range is _empty
1136     */
1137     @property bool empty() const
1138     {
1139         return _begin is _end;
1140     }
1141 
1142     /**
1143     * Returns the first element in the range
1144     */
1145     @property Elem front()
1146     {
1147         return _begin.value;
1148     }
1149 
1150     /**
1151     * Returns the last element in the range
1152     */
1153     @property Elem back()
1154     {
1155         return _end.prev.value;
1156     }
1157 
1158     /**
1159     * pop the front element from the range
1160     *
1161     * complexity: amortized $(BIGOH 1)
1162     */
1163     void popFront()
1164     {
1165         _begin = _begin.next;
1166     }
1167 
1168     /**
1169     * pop the back element from the range
1170     *
1171     * complexity: amortized $(BIGOH 1)
1172     */
1173     void popBack()
1174     {
1175         _end = _end.prev;
1176     }
1177 
1178     /**
1179     * Trivial _save implementation, needed for $(D isForwardRange).
1180     */
1181     @property RBRange save()
1182     {
1183         return this;
1184     }
1185 }
1186 
1187 unittest
1188 {
1189     // RBRange.init is supposed to be an empty valid range
1190     RBRange!(RBNode!int*) range;
1191     assert(range.empty);
1192     foreach(e; range)
1193     {        
1194     }
1195 }
1196 
1197 private enum MapRangeType
1198 {
1199     key,
1200     value,
1201     keyValue
1202 }
1203 
1204 // Range type for Dplug's Map, can iterate on keys or values
1205 private struct MapRange(N, MapRangeType type)
1206 {
1207 nothrow:
1208 @nogc:
1209 
1210     alias Node = N;
1211     alias InnerRange = RBRange!N;
1212 
1213     static if (type == MapRangeType.key)
1214         alias Elem = typeof(Node.value.key);
1215 
1216     else static if (type == MapRangeType.value)
1217         alias Elem = typeof(Node.value.value);
1218 
1219     else static if (type == MapRangeType.keyValue)
1220         alias Elem = typeof(Node.value);
1221 
1222     static Elem get(InnerRange.Elem pair)
1223     {
1224         static if (type == MapRangeType.key)
1225             return pair.key;
1226 
1227         else static if (type == MapRangeType.value)
1228             return pair.value;
1229 
1230         else static if (type == MapRangeType.keyValue)
1231             return pair;
1232     }
1233 
1234     // A Map range is just a wrapper around a RBRange
1235     private InnerRange _inner;
1236 
1237     private this(InnerRange inner)
1238     {
1239         _inner = inner;
1240     }
1241 
1242     /**
1243     * Returns $(D true) if the range is _empty
1244     */
1245     @property bool empty() const
1246     {
1247         return _inner.empty;
1248     }
1249 
1250     /**
1251     * Returns the first element in the range
1252     */
1253     @property Elem front()
1254     {
1255         return get(_inner.front);
1256     }
1257 
1258     /**
1259     * Returns the last element in the range
1260     */
1261     @property Elem back()
1262     {
1263         return get(_inner.back());
1264     }
1265 
1266     /**
1267     * pop the front element from the range
1268     *
1269     * complexity: amortized $(BIGOH 1)
1270     */
1271     void popFront()
1272     {
1273         _inner.popFront();
1274     }
1275 
1276     /**
1277     * pop the back element from the range
1278     *
1279     * complexity: amortized $(BIGOH 1)
1280     */
1281     void popBack()
1282     {
1283         _inner.popBack();
1284     }
1285 
1286     /**
1287     * Trivial _save implementation, needed for $(D isForwardRange).
1288     */
1289     @property MapRange save()
1290     {
1291         return this;
1292     }
1293 }
1294 
1295 /**
1296 * Implementation of a $(LINK2 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree,
1297 * red-black tree) container.
1298 *
1299 * All inserts, removes, searches, and any function in general has complexity
1300 * of $(BIGOH lg(n)).
1301 *
1302 * To use a different comparison than $(D "a < b"), pass a different operator string
1303 * that can be used by $(REF binaryFun, std,functional), or pass in a
1304 * function, delegate, functor, or any type where $(D less(a, b)) results in a $(D bool)
1305 * value.
1306 *
1307 * Note that less should produce a strict ordering.  That is, for two unequal
1308 * elements $(D a) and $(D b), $(D less(a, b) == !less(b, a)). $(D less(a, a)) should
1309 * always equal $(D false).
1310 *
1311 * If $(D allowDuplicates) is set to $(D true), then inserting the same element more than
1312 * once continues to add more elements.  If it is $(D false), duplicate elements are
1313 * ignored on insertion.  If duplicates are allowed, then new elements are
1314 * inserted after all existing duplicate elements.
1315 */
1316 
1317 final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
1318 {
1319 nothrow:
1320 @nogc:
1321     /**
1322     * Element type for the tree
1323     */
1324     alias Elem = T;
1325 
1326     alias _less = binaryFun!less;
1327 
1328     // used for convenience
1329     private alias RBNode = .RBNode!Elem;
1330     private alias Node = RBNode.Node;
1331 
1332     private Node   _end;
1333     private Node   _begin;
1334     private size_t _length;
1335 
1336     private void _setup()
1337     {
1338         assert(!_end); //Make sure that _setup isn't run more than once.
1339         _begin = _end = allocate();
1340     }
1341 
1342     static private Node allocate()
1343     {
1344         Node p = mallocNew!RBNode;
1345         //import core.stdc.stdio;
1346         //printf("allocate %p\n", p);
1347         return p;
1348     }
1349 
1350     static private Node allocate(Elem v)
1351     {
1352         auto result = allocate();
1353         result.value = v;
1354         return result;
1355     }
1356 
1357     /**
1358     * The range types for $(D RedBlackTree)
1359     */
1360     alias Range = RBRange!(RBNode*);
1361     alias ConstRange = RBRange!(const(RBNode)*); /// Ditto
1362     alias ImmutableRange = RBRange!(immutable(RBNode)*); /// Ditto
1363 
1364     // find a node based on an element value
1365     private inout(RBNode)* _find(Elem e) inout
1366     {
1367         static if (allowDuplicates)
1368         {
1369             inout(RBNode)* cur = _end.left;
1370             inout(RBNode)* result = null;
1371             while (cur)
1372             {
1373                 if (_less(cur.value, e))
1374                     cur = cur.right;
1375                 else if (_less(e, cur.value))
1376                     cur = cur.left;
1377                 else
1378                 {
1379                     // want to find the left-most element
1380                     result = cur;
1381                     cur = cur.left;
1382                 }
1383             }
1384             return result;
1385         }
1386         else
1387         {
1388             inout(RBNode)* cur = _end.left;
1389             while (cur)
1390             {
1391                 if (_less(cur.value, e))
1392                     cur = cur.right;
1393                 else if (_less(e, cur.value))
1394                     cur = cur.left;
1395                 else
1396                     return cur;
1397             }
1398             return null;
1399         }
1400     }
1401 
1402     // add an element to the tree, returns the node added, or the existing node
1403     // if it has already been added and allowDuplicates is false
1404     private auto _add(Elem n)
1405     {
1406         Node result;
1407         static if (!allowDuplicates)
1408             bool added = true;
1409 
1410         if (!_end.left)
1411         {
1412             _end.left = _begin = result = allocate(n);
1413         }
1414         else
1415         {
1416             Node newParent = _end.left;
1417             Node nxt;
1418             while (true)
1419             {
1420                 if (_less(n, newParent.value))
1421                 {
1422                     nxt = newParent.left;
1423                     if (nxt is null)
1424                     {
1425                         //
1426                         // add to right of new parent
1427                         //
1428                         newParent.left = result = allocate(n);
1429                         break;
1430                     }
1431                 }
1432                 else
1433                 {
1434                     static if (!allowDuplicates)
1435                     {
1436                         if (!(_less(newParent.value, n)))
1437                         {
1438                             result = newParent;
1439                             added = false;
1440                             break;
1441                         }
1442                     }
1443                     nxt = newParent.right;
1444                     if (nxt is null)
1445                     {
1446                         //
1447                         // add to right of new parent
1448                         //
1449                         newParent.right = result = allocate(n);
1450                         break;
1451                     }
1452                 }
1453                 newParent = nxt;
1454             }
1455             if (_begin.left)
1456                 _begin = _begin.left;
1457         }
1458 
1459         static if (allowDuplicates)
1460         {
1461             result.setColor(_end);
1462             ++_length;
1463             return result;
1464         }
1465         else
1466         {
1467             import std.typecons : Tuple;
1468 
1469             if (added)
1470             {
1471                 ++_length;
1472                 result.setColor(_end);
1473             }
1474             return Tuple!(bool, "added", Node, "n")(added, result);
1475         }
1476     }
1477 
1478 
1479     /**
1480     * Check if any elements exist in the container.  Returns $(D false) if at least
1481     * one element exists.
1482     */
1483     @property bool empty()
1484     {
1485         return _end.left is null;
1486     }
1487 
1488     /++
1489     Returns the number of elements in the container.
1490 
1491     Complexity: $(BIGOH 1).
1492     +/
1493     @property size_t length() const
1494     {
1495         return _length;
1496     }
1497 
1498     // Find the range for which every element is equal.
1499     private void findEnclosingRange(Elem e, inout(RBNode)** begin, inout(RBNode)** end) inout
1500     {
1501         *begin = _firstGreaterEqual(e);
1502         *end = _firstGreater(e);
1503     }
1504 
1505     /**
1506     * Fetch a range that spans all the elements in the container.
1507     *
1508     * Complexity: $(BIGOH 1)
1509     */
1510     Range opSlice()
1511     {
1512         return Range(_begin, _end);
1513     }
1514 
1515     /// Ditto
1516     ConstRange opSlice() const
1517     {
1518         return ConstRange(_begin, _end);
1519     }
1520 
1521     /// Ditto
1522     ImmutableRange opSlice() immutable
1523     {
1524         return ImmutableRange(_begin, _end);
1525     }
1526 
1527     /**
1528     * Fetch a range that spans all equal elements of a particular value.
1529     *
1530     * Complexity: $(BIGOH 1)
1531     */
1532     Range range(Elem e)
1533     {
1534         RBNode* begin, end;
1535         findEnclosingRange(e, &begin, &end);
1536         return Range(begin, end);
1537     }
1538 
1539     /// Ditto
1540     ConstRange range(Elem e) const
1541     {
1542         const(RBNode)* begin, end;
1543         findEnclosingRange(e, &begin, &end);
1544         return ConstRange(begin, end);
1545     }
1546 
1547     /// Ditto
1548     ImmutableRange range(Elem e) immutable
1549     {
1550         immutable(RBNode)* begin, end;
1551         findEnclosingRange(e, &begin, &end);
1552         return ImmutableRange(begin, end);
1553     }
1554 
1555     /**
1556     * The front element in the container
1557     *
1558     * Complexity: $(BIGOH 1)
1559     */
1560     Elem front()
1561     {
1562         return _begin.value;
1563     }
1564 
1565     /**
1566     * The last element in the container
1567     *
1568     * Complexity: $(BIGOH log(n))
1569     */
1570     Elem back()
1571     {
1572         return _end.prev.value;
1573     }
1574 
1575     /++
1576     $(D in) operator. Check to see if the given element exists in the
1577     container.
1578 
1579     Complexity: $(BIGOH log(n))
1580     +/
1581     bool opBinaryRight(string op)(Elem e) const if (op == "in")
1582     {
1583         return _find(e) !is null;
1584     }
1585 
1586     /**
1587     * Insert a single element in the container.  Note that this does not
1588     * invalidate any ranges currently iterating the container.
1589     *
1590     * Returns: The number of elements inserted.
1591     *
1592     * Complexity: $(BIGOH log(n))
1593     */
1594     size_t stableInsert(Elem elem)
1595     {
1596         static if (allowDuplicates)
1597         {
1598             _add(elem);
1599             return 1;
1600         }
1601         else
1602         {
1603             return(_add(elem).added ? 1 : 0);
1604         }
1605     }
1606 
1607     /// ditto
1608     alias insert = stableInsert;
1609 
1610     /**
1611     * Remove an element from the container and return its value.
1612     *
1613     * Complexity: $(BIGOH log(n))
1614     */
1615     Elem removeAny()
1616     {
1617         scope(success)
1618             --_length;
1619         auto n = _begin;
1620         auto result = n.value;
1621         _begin = n.remove(_end);
1622         n.deallocate();
1623         return result;
1624     }
1625 
1626     /**
1627     * Remove the front element from the container.
1628     *
1629     * Complexity: $(BIGOH log(n))
1630     */
1631     void removeFront()
1632     {
1633         scope(success)
1634             --_length;
1635         auto oldBegin = _begin;
1636         _begin = _begin.remove(_end);
1637         oldBegin.deallocate();
1638     }
1639 
1640     /**
1641     * Remove the back element from the container.
1642     *
1643     * Complexity: $(BIGOH log(n))
1644     */
1645     void removeBack()
1646     {
1647         scope(success)
1648             --_length;
1649         auto lastnode = _end.prev;
1650         if (lastnode is _begin)
1651         {
1652             auto oldBegin = _begin;
1653             _begin = _begin.remove(_end);
1654             oldBegin.deallocate();
1655         }
1656         else
1657         {
1658             lastnode.remove(_end);
1659             lastnode.deallocate();
1660         }
1661     }
1662 
1663     /++ Ditto +/
1664     size_t removeKey(Elem e)
1665     {
1666         immutable lenBefore = length;
1667 
1668         auto beg = _firstGreaterEqual(e);
1669         if (beg is _end || _less(e, beg.value))
1670             // no values are equal
1671             return 0;
1672         auto oldBeg = beg;
1673         immutable isBegin = (beg is _begin);
1674         beg = beg.remove(_end);
1675         if (isBegin)
1676             _begin = beg;
1677         --_length;
1678 
1679         oldBeg.deallocate();
1680 
1681         return lenBefore - length;
1682     }
1683 
1684     // find the first node where the value is > e
1685     private inout(RBNode)* _firstGreater(Elem e) inout
1686     {
1687         // can't use _find, because we cannot return null
1688         auto cur = _end.left;
1689         inout(RBNode)* result = _end;
1690         while (cur)
1691         {
1692             if (_less(e, cur.value))
1693             {
1694                 result = cur;
1695                 cur = cur.left;
1696             }
1697             else
1698                 cur = cur.right;
1699         }
1700         return result;
1701     }
1702 
1703 
1704     // find the first node where the value is >= e
1705     private inout(RBNode)* _firstGreaterEqual(Elem e) inout
1706     {
1707         // can't use _find, because we cannot return null.
1708         auto cur = _end.left;
1709         inout(RBNode)* result = _end;
1710         while (cur)
1711         {
1712             if (_less(cur.value, e))
1713                 cur = cur.right;
1714             else
1715             {
1716                 result = cur;
1717                 cur = cur.left;
1718             }
1719 
1720         }
1721         return result;
1722     }
1723 
1724     ///
1725     this()
1726     {
1727         _setup();
1728     }
1729 
1730     ~this()
1731     {
1732         while(length > 0)
1733             removeBack();
1734 
1735         // deallocate sentinel
1736         _end.deallocate();
1737     }
1738 }