1 /**
2 This module implements a red-black tree container.
3 
4 This module is a submodule of $(MREF std, container).
5 
6 Source: $(PHOBOSSRC std/container/rbtree.d)
7 
8 Copyright: Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code
9 copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
10 
11 License: Distributed under the Boost Software License, Version 1.0.
12 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
13 boost.org/LICENSE_1_0.txt)).
14 
15 Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu)
16 */
17 module tagion.std.container.rbtree;
18 
19 ///
20 @safe pure unittest {
21     import std.algorithm.comparison : equal;
22     import std.container.rbtree;
23 
24     auto rbt = redBlackTree(3, 1, 4, 2, 5);
25     assert(rbt.front == 1);
26     assert(equal(rbt[], [1, 2, 3, 4, 5]));
27 
28     rbt.removeKey(1, 4);
29     assert(equal(rbt[], [2, 3, 5]));
30 
31     rbt.removeFront();
32     assert(equal(rbt[], [3, 5]));
33 
34     rbt.insert([1, 2, 4]);
35     assert(equal(rbt[], [1, 2, 3, 4, 5]));
36 
37     // Query bounds in O(log(n))
38     assert(rbt.lowerBound(3).equal([1, 2]));
39     assert(rbt.equalRange(3).equal([3]));
40     assert(rbt.upperBound(3).equal([4, 5]));
41 
42     // A Red Black tree with the highest element at front:
43     import std.range : iota;
44 
45     auto maxTree = redBlackTree!"a > b"(iota(5));
46     assert(equal(maxTree[], [4, 3, 2, 1, 0]));
47 
48     // adding duplicates will not add them, but return 0
49     auto rbt2 = redBlackTree(1, 3);
50     assert(rbt2.insert(1) == 0);
51     assert(equal(rbt2[], [1, 3]));
52     assert(rbt2.insert(2) == 1);
53 
54     // however you can allow duplicates
55     auto ubt = redBlackTree!true([0, 1, 0, 1]);
56     assert(equal(ubt[], [0, 0, 1, 1]));
57 }
58 
59 public import std.container.util;
60 import std.format;
61 import std.functional : binaryFun;
62 
63 version (StdUnittest) debug = RBDoChecks;
64 
65 //debug = RBDoChecks;
66 
67 /*
68  * Implementation for a Red Black node for use in a Red Black Tree (see below)
69  *
70  * this implementation assumes we have a marker Node that is the parent of the
71  * root Node.  This marker Node is not a valid Node, but marks the end of the
72  * collection.  The root is the left child of the marker Node, so it is always
73  * last in the collection.  The marker Node is passed in to the setColor
74  * function, and the Node which has this Node as its parent is assumed to be
75  * the root Node.
76  *
77  * A Red Black tree should have O(lg(n)) insertion, removal, and search time.
78  */
79 struct RBNode(V) {
80     /*
81      * Convenience alias
82      */
83     alias Node = RBNode*;
84 
85     private Node _left;
86     private Node _right;
87     private Node _parent;
88 
89     /**
90      * The value held by this node
91      */
92     V value;
93 
94     /**
95      * Enumeration determining what color the node is.  Null nodes are assumed
96      * to be black.
97      */
98     enum Color : byte {
99         Red,
100         Black
101     }
102 
103     /**
104      * The color of the node.
105      */
106     Color color;
107 
108     /**
109      * Get the left child
110      */
111     @property inout(RBNode)* left() inout return scope {
112         return _left;
113     }
114 
115     /**
116      * Get the right child
117      */
118     @property inout(RBNode)* right() inout return scope {
119         return _right;
120     }
121 
122     /**
123      * Get the parent
124      */
125     @property inout(RBNode)* parent() inout return scope {
126         return _parent;
127     }
128 
129     /**
130      * Set the left child.  Also updates the new child's parent node.  This
131      * does not update the previous child.
132      *
133      * $(RED Warning: If the node this is called on is a local variable, a stack pointer can be
134      * escaped through `newNode.parent`. It's marked `@trusted` only for backwards compatibility.)
135      *
136      * Returns newNode
137      */
138     @property Node left(return scope Node newNode) @trusted {
139         _left = newNode;
140         if (newNode !is null)
141             newNode._parent = &this;
142         return newNode;
143     }
144 
145     /**
146      * Set the right child.  Also updates the new child's parent node.  This
147      * does not update the previous child.
148      *
149      * $(RED Warning: If the node this is called on is a local variable, a stack pointer can be
150      * escaped through `newNode.parent`. It's marked `@trusted` only for backwards compatibility.)
151      *
152      * Returns newNode
153      */
154     @property Node right(return scope Node newNode) @trusted {
155         _right = newNode;
156         if (newNode !is null)
157             newNode._parent = &this;
158         return newNode;
159     }
160 
161     // assume _left is not null
162     //
163     // performs rotate-right operation, where this is T, _right is R, _left is
164     // L, _parent is P:
165     //
166     //      P         P
167     //      |   ->    |
168     //      T         L
169     //     / \       / \
170     //    L   R     a   T
171     //   / \           / \
172     //  a   b         b   R
173     //
174     /**
175      * Rotate right.  This performs the following operations:
176      *  - The left child becomes the parent of this node.
177      *  - This node becomes the new parent's right child.
178      *  - The old right child of the new parent becomes the left child of this
179      *    node.
180      */
181     Node rotateR()
182     in {
183         assert(_left !is null, "left node must not be null");
184     }
185     do {
186         // sets _left._parent also
187         if (isLeftNode)
188             parent.left = _left;
189         else
190             parent.right = _left;
191         Node tmp = _left._right;
192 
193         // sets _parent also
194         _left.right = &this;
195 
196         // sets tmp._parent also
197         left = tmp;
198 
199         return &this;
200     }
201 
202     // assumes _right is non null
203     //
204     // performs rotate-left operation, where this is T, _right is R, _left is
205     // L, _parent is P:
206     //
207     //      P           P
208     //      |    ->     |
209     //      T           R
210     //     / \         / \
211     //    L   R       T   b
212     //       / \     / \
213     //      a   b   L   a
214     //
215     /**
216      * Rotate left.  This performs the following operations:
217      *  - The right child becomes the parent of this node.
218      *  - This node becomes the new parent's left child.
219      *  - The old left child of the new parent becomes the right child of this
220      *    node.
221      */
222     Node rotateL()
223     in {
224         assert(_right !is null, "right node must not be null");
225     }
226     do {
227         // sets _right._parent also
228         if (isLeftNode)
229             parent.left = _right;
230         else
231             parent.right = _right;
232         Node tmp = _right._left;
233 
234         // sets _parent also
235         _right.left = &this;
236 
237         // sets tmp._parent also
238         right = tmp;
239         return &this;
240     }
241 
242     /**
243      * Returns true if this node is a left child.
244      *
245      * Note that this should always return a value because the root has a
246      * parent which is the marker node.
247      */
248     @property bool isLeftNode() const
249     in {
250         assert(_parent !is null, "parent must not be null");
251     }
252     do {
253         return _parent._left is &this;
254     }
255 
256     /**
257      * Set the color of the node after it is inserted.  This performs an
258      * update to the whole tree, possibly rotating nodes to keep the Red-Black
259      * properties correct.  This is an O(lg(n)) operation, where n is the
260      * number of nodes in the tree.
261      *
262      * end is the marker node, which is the parent of the topmost valid node.
263      */
264     void setColor(Node end) {
265         // test against the marker node
266         if (_parent !is end) {
267             if (_parent.color == Color.Red) {
268                 Node cur = &this;
269                 while (true) {
270                     // because root is always black, _parent._parent always exists
271                     if (cur._parent.isLeftNode) {
272                         // parent is left node, y is 'uncle', could be null
273                         Node y = cur._parent._parent._right;
274                         if (y !is null && y.color == Color.Red) {
275                             cur._parent.color = Color.Black;
276                             y.color = Color.Black;
277                             cur = cur._parent._parent;
278                             if (cur._parent is end) {
279                                 // root node
280                                 cur.color = Color.Black;
281                                 break;
282                             }
283                             else {
284                                 // not root node
285                                 cur.color = Color.Red;
286                                 if (cur._parent.color == Color.Black) // satisfied, exit the loop
287                                     break;
288                             }
289                         }
290                         else {
291                             if (!cur.isLeftNode)
292                                 cur = cur._parent.rotateL();
293                             cur._parent.color = Color.Black;
294                             cur = cur._parent._parent.rotateR();
295                             cur.color = Color.Red;
296                             // tree should be satisfied now
297                             break;
298                         }
299                     }
300                     else {
301                         // parent is right node, y is 'uncle'
302                         Node y = cur._parent._parent._left;
303                         if (y !is null && y.color == Color.Red) {
304                             cur._parent.color = Color.Black;
305                             y.color = Color.Black;
306                             cur = cur._parent._parent;
307                             if (cur._parent is end) {
308                                 // root node
309                                 cur.color = Color.Black;
310                                 break;
311                             }
312                             else {
313                                 // not root node
314                                 cur.color = Color.Red;
315                                 if (cur._parent.color == Color.Black) // satisfied, exit the loop
316                                     break;
317                             }
318                         }
319                         else {
320                             if (cur.isLeftNode)
321                                 cur = cur._parent.rotateR();
322                             cur._parent.color = Color.Black;
323                             cur = cur._parent._parent.rotateL();
324                             cur.color = Color.Red;
325                             // tree should be satisfied now
326                             break;
327                         }
328                     }
329                 }
330 
331             }
332         }
333         else {
334             //
335             // this is the root node, color it black
336             //
337             color = Color.Black;
338         }
339     }
340 
341     /**
342      * Remove this node from the tree.  The 'end' node is used as the marker
343      * which is root's parent.  Note that this cannot be null!
344      *
345      * Returns the next highest valued node in the tree after this one, or end
346      * if this was the highest-valued node.
347      */
348     Node remove(Node end) return {
349         //
350         // remove this node from the tree, fixing the color if necessary.
351         //
352         Node x;
353         Node ret = next;
354 
355         // if this node has 2 children
356         if (_left !is null && _right !is null) {
357             //
358             // normally, we can just swap this node's and y's value, but
359             // because an iterator could be pointing to y and we don't want to
360             // disturb it, we swap this node and y's structure instead.  This
361             // can also be a benefit if the value of the tree is a large
362             // struct, which takes a long time to copy.
363             //
364             Node yp, yl, yr;
365             Node y = ret; // y = next
366             yp = y._parent;
367             yl = y._left;
368             yr = y._right;
369             auto yc = y.color;
370             auto isyleft = y.isLeftNode;
371 
372             //
373             // replace y's structure with structure of this node.
374             //
375             if (isLeftNode)
376                 _parent.left = y;
377             else
378                 _parent.right = y;
379             //
380             // need special case so y doesn't point back to itself
381             //
382             y.left = _left;
383             if (_right is y)
384                 y.right = &this;
385             else
386                 y.right = _right;
387             y.color = color;
388 
389             //
390             // replace this node's structure with structure of y.
391             //
392             left = yl;
393             right = yr;
394             if (_parent !is y) {
395                 if (isyleft)
396                     yp.left = &this;
397                 else
398                     yp.right = &this;
399             }
400             color = yc;
401         }
402 
403         // if this has less than 2 children, remove it
404         if (_left !is null)
405             x = _left;
406         else
407             x = _right;
408 
409         bool deferedUnlink = false;
410         if (x is null) {
411             // pretend this is a null node, defer unlinking the node
412             x = &this;
413             deferedUnlink = true;
414         }
415         else if (isLeftNode)
416             _parent.left = x;
417         else
418             _parent.right = x;
419 
420         // if the color of this is black, then it needs to be fixed
421         if (color == color.Black) {
422             // need to recolor the tree.
423             while (x._parent !is end && x.color == Node.Color.Black) {
424                 if (x.isLeftNode) {
425                     // left node
426                     Node w = x._parent._right;
427                     if (w.color == Node.Color.Red) {
428                         w.color = Node.Color.Black;
429                         x._parent.color = Node.Color.Red;
430                         x._parent.rotateL();
431                         w = x._parent._right;
432                     }
433                     Node wl = w.left;
434                     Node wr = w.right;
435                     if ((wl is null || wl.color == Node.Color.Black) &&
436                             (wr is null || wr.color == Node.Color.Black)) {
437                         w.color = Node.Color.Red;
438                         x = x._parent;
439                     }
440                     else {
441                         if (wr is null || wr.color == Node.Color.Black) {
442                             // wl cannot be null here
443                             wl.color = Node.Color.Black;
444                             w.color = Node.Color.Red;
445                             w.rotateR();
446                             w = x._parent._right;
447                         }
448 
449                         w.color = x._parent.color;
450                         x._parent.color = Node.Color.Black;
451                         w._right.color = Node.Color.Black;
452                         x._parent.rotateL();
453                         x = end.left; // x = root
454                     }
455                 }
456                 else {
457                     // right node
458                     Node w = x._parent._left;
459                     if (w.color == Node.Color.Red) {
460                         w.color = Node.Color.Black;
461                         x._parent.color = Node.Color.Red;
462                         x._parent.rotateR();
463                         w = x._parent._left;
464                     }
465                     Node wl = w.left;
466                     Node wr = w.right;
467                     if ((wl is null || wl.color == Node.Color.Black) &&
468                             (wr is null || wr.color == Node.Color.Black)) {
469                         w.color = Node.Color.Red;
470                         x = x._parent;
471                     }
472                     else {
473                         if (wl is null || wl.color == Node.Color.Black) {
474                             // wr cannot be null here
475                             wr.color = Node.Color.Black;
476                             w.color = Node.Color.Red;
477                             w.rotateL();
478                             w = x._parent._left;
479                         }
480 
481                         w.color = x._parent.color;
482                         x._parent.color = Node.Color.Black;
483                         w._left.color = Node.Color.Black;
484                         x._parent.rotateR();
485                         x = end.left; // x = root
486                     }
487                 }
488             }
489             x.color = Node.Color.Black;
490         }
491 
492         if (deferedUnlink) {
493             //
494             // unlink this node from the tree
495             //
496             if (isLeftNode)
497                 _parent.left = null;
498             else
499                 _parent.right = null;
500         }
501 
502         // clean references to help GC
503         // https://issues.dlang.org/show_bug.cgi?id=12915
504         _left = _right = _parent = null;
505 
506         return ret;
507     }
508 
509     /**
510      * Return the leftmost descendant of this node.
511      */
512     @property inout(RBNode)* leftmost() inout return {
513         inout(RBNode)* result = &this;
514         while (result._left !is null)
515             result = result._left;
516         return result;
517     }
518 
519     /**
520      * Return the rightmost descendant of this node
521      */
522     @property inout(RBNode)* rightmost() inout return {
523         inout(RBNode)* result = &this;
524         while (result._right !is null)
525             result = result._right;
526         return result;
527     }
528 
529     /**
530      * Returns the next valued node in the tree.
531      *
532      * You should never call this on the marker node, as it is assumed that
533      * there is a valid next node.
534      */
535     @property inout(RBNode)* next() inout return {
536         inout(RBNode)* n = &this;
537         if (n.right is null) {
538             while (!n.isLeftNode)
539                 n = n._parent;
540             return n._parent;
541         }
542         else
543             return n.right.leftmost;
544     }
545 
546     /**
547      * Returns the previous valued node in the tree.
548      *
549      * You should never call this on the leftmost node of the tree as it is
550      * assumed that there is a valid previous node.
551      */
552     @property inout(RBNode)* prev() inout return {
553         inout(RBNode)* n = &this;
554         if (n.left is null) {
555             while (n.isLeftNode)
556                 n = n._parent;
557             return n._parent;
558         }
559         else
560             return n.left.rightmost;
561     }
562 
563     Node dup(scope Node delegate(V v) alloc) {
564         //
565         // duplicate this and all child nodes
566         //
567         // The recursion should be lg(n), so we shouldn't have to worry about
568         // stack size.
569         //
570         Node copy = alloc(value);
571         copy.color = color;
572         if (_left !is null)
573             copy.left = _left.dup(alloc);
574         if (_right !is null)
575             copy.right = _right.dup(alloc);
576         return copy;
577     }
578 
579     Node dup() {
580         Node copy = new RBNode!V(null, null, null, value);
581         copy.color = color;
582         if (_left !is null)
583             copy.left = _left.dup();
584         if (_right !is null)
585             copy.right = _right.dup();
586         return copy;
587     }
588 }
589 
590 //constness checks
591 @safe pure unittest {
592     const RBNode!int n;
593     static assert(is(typeof(n.leftmost)));
594     static assert(is(typeof(n.rightmost)));
595     static assert(is(typeof(n.next)));
596     static assert(is(typeof(n.prev)));
597 }
598 
599 private struct RBRange(N) {
600     alias Node = N;
601     alias Elem = typeof(Node.value);
602 
603     private Node _begin;
604     private Node _end;
605 
606     private this(Node b, Node e) {
607         _begin = b;
608         _end = e;
609     }
610 
611     /**
612      * Returns `true` if the range is _empty
613      */
614     @property bool empty() const {
615         return _begin is _end;
616     }
617 
618     /**
619      * Returns the first element in the range
620      */
621     @property Elem front() {
622         return _begin.value;
623     }
624 
625     /**
626      * Returns the last element in the range
627      */
628     @property Elem back() {
629         return _end.prev.value;
630     }
631 
632     /**
633      * pop the front element from the range
634      *
635      * Complexity: amortized $(BIGOH 1)
636      */
637     void popFront() {
638         _begin = _begin.next;
639     }
640 
641     /**
642      * pop the back element from the range
643      *
644      * Complexity: amortized $(BIGOH 1)
645      */
646     void popBack() {
647         _end = _end.prev;
648     }
649 
650     /**
651      * Trivial _save implementation, needed for `isForwardRange`.
652      */
653     @property RBRange save() {
654         return this;
655     }
656 }
657 
658 /**
659  * Implementation of a $(LINK2 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree,
660  * red-black tree) container.
661  *
662  * All inserts, removes, searches, and any function in general has complexity
663  * of $(BIGOH lg(n)).
664  *
665  * To use a different comparison than $(D "a < b"), pass a different operator string
666  * that can be used by $(REF binaryFun, std,functional), or pass in a
667  * function, delegate, functor, or any type where $(D less(a, b)) results in a `bool`
668  * value.
669  *
670  * Note that less should produce a strict ordering.  That is, for two unequal
671  * elements `a` and `b`, $(D less(a, b) == !less(b, a)). $(D less(a, a)) should
672  * always equal `false`.
673  *
674  * If `allowDuplicates` is set to `true`, then inserting the same element more than
675  * once continues to add more elements.  If it is `false`, duplicate elements are
676  * ignored on insertion.  If duplicates are allowed, then new elements are
677  * inserted after all existing duplicate elements.
678  */
679 final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
680         if (is(typeof(binaryFun!less(T.init, T.init)))) {
681     import std.meta : allSatisfy;
682     import std.range : Take;
683     import std.range.primitives : isInputRange, walkLength;
684     import std.traits : isDynamicArray, isImplicitlyConvertible, isIntegral;
685 
686     alias _less = binaryFun!less;
687 
688     version (StdUnittest) {
689         static if (is(typeof(less) == string)) {
690             private enum doUnittest = is(byte : T) && isIntegral!T && (less == "a < b" || less == "a > b");
691         }
692         else
693             enum doUnittest = false;
694 
695         // note, this must be final so it does not affect the vtable layout
696         bool arrayEqual(T[] arr) {
697             if (walkLength(this[]) == arr.length) {
698                 foreach (v; arr) {
699                     if (!(v in this))
700                         return false;
701                 }
702                 return true;
703             }
704             return false;
705         }
706     }
707     else {
708         private enum doUnittest = false;
709     }
710 
711     /**
712       * Element type for the tree
713       */
714     alias Elem = T;
715 
716     // used for convenience
717     private alias RBNode = .RBNode!Elem;
718     private alias Node = RBNode.Node;
719 
720     private Node _end;
721     private Node _begin;
722     private size_t _length;
723 
724     private void _setup() {
725         //Make sure that _setup isn't run more than once.
726         assert(!_end, "Setup must only be run once");
727         _begin = _end = allocate();
728     }
729 
730     static private Node allocate() {
731         return new RBNode;
732     }
733 
734     static private Node allocate(Elem v) {
735         return new RBNode(null, null, null, v);
736     }
737 
738     /**
739      * The range types for `RedBlackTree`
740      */
741     alias Range = RBRange!(RBNode*);
742     alias ConstRange = RBRange!(const(RBNode)*); /// Ditto
743     alias ImmutableRange = RBRange!(immutable(RBNode)*); /// Ditto
744 
745     static if (doUnittest)
746         @safe pure unittest {
747             import std.algorithm.comparison : equal;
748             import std.range.primitives;
749 
750             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
751             assert(ts.length == 5);
752             auto r = ts[];
753 
754             static if (less == "a < b")
755                 auto vals = [1, 2, 3, 4, 5];
756             else
757                 auto vals = [5, 4, 3, 2, 1];
758             assert(equal(r, vals));
759 
760             assert(r.front == vals.front);
761             assert(r.back != r.front);
762             auto oldfront = r.front;
763             auto oldback = r.back;
764             r.popFront();
765             r.popBack();
766             assert(r.front != r.back);
767             assert(r.front != oldfront);
768             assert(r.back != oldback);
769             assert(ts.length == 5);
770         }
771 
772     // find a node based on an element value
773     private inout(RBNode)* _find(Elem e) inout {
774         static if (allowDuplicates) {
775             inout(RBNode)* cur = _end.left;
776             inout(RBNode)* result = null;
777             while (cur) {
778                 if (_less(cur.value, e))
779                     cur = cur.right;
780                 else if (_less(e, cur.value))
781                     cur = cur.left;
782                 else {
783                     // want to find the left-most element
784                     result = cur;
785                     cur = cur.left;
786                 }
787             }
788             return result;
789         }
790         else {
791             inout(RBNode)* cur = _end.left;
792             while (cur) {
793                 if (_less(cur.value, e))
794                     cur = cur.right;
795                 else if (_less(e, cur.value))
796                     cur = cur.left;
797                 else
798                     return cur;
799             }
800             return null;
801         }
802     }
803 
804     /* add an element to the tree, returns the node added, or the existing node
805      * if it has already been added and allowDuplicates is false
806      * Returns:
807      *   true if node was added
808      */
809     private bool _add(Elem n) {
810         Node result;
811         static if (!allowDuplicates)
812             bool added = true;
813 
814         if (!_end.left) {
815             result = allocate(n);
816             (() @trusted { _end.left = _begin = result; })();
817         }
818         else {
819             Node newParent = _end.left;
820             Node nxt;
821             while (true) {
822                 if (_less(n, newParent.value)) {
823                     nxt = newParent.left;
824                     if (nxt is null) {
825                         //
826                         // add to right of new parent
827                         //
828                         result = allocate(n);
829                         (() @trusted { newParent.left = result; })();
830                         break;
831                     }
832                 }
833                 else {
834                     static if (!allowDuplicates) {
835                         if (!_less(newParent.value, n)) {
836                             result = newParent;
837                             added = false;
838                             break;
839                         }
840                     }
841                     nxt = newParent.right;
842                     if (nxt is null) {
843                         //
844                         // add to right of new parent
845                         //
846                         result = allocate(n);
847                         (() @trusted { newParent.right = result; })();
848                         break;
849                     }
850                 }
851                 newParent = nxt;
852             }
853             if (_begin.left)
854                 _begin = _begin.left;
855         }
856         static if (allowDuplicates) {
857             result.setColor(_end);
858             debug (RBDoChecks)
859                 check();
860             ++_length;
861             return true;
862         }
863         else {
864             if (added) {
865                 ++_length;
866                 result.setColor(_end);
867             }
868             debug (RBDoChecks)
869                 check();
870             return added;
871         }
872     }
873 
874     /**
875      * Check if any elements exist in the container.  Returns `false` if at least
876      * one element exists.
877      */
878     @property bool empty() const  // pure, nothrow, @safe, @nogc: are inferred
879     {
880         return _end.left is null;
881     }
882 
883     /++
884         Returns the number of elements in the container.
885 
886         Complexity: $(BIGOH 1).
887     +/
888     @property size_t length() const {
889         return _length;
890     }
891 
892     /**
893      * Duplicate this container.  The resulting container contains a shallow
894      * copy of the elements.
895      *
896      * Complexity: $(BIGOH n)
897      */
898     @property RedBlackTree dup() {
899         return new RedBlackTree(_end.dup(), _length);
900     }
901 
902     static if (doUnittest)
903         @safe pure unittest {
904             import std.algorithm.comparison : equal;
905 
906             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
907             assert(ts.length == 5);
908             auto ts2 = ts.dup;
909             assert(ts2.length == 5);
910             assert(equal(ts[], ts2[]));
911             ts2.insert(cast(Elem) 6);
912             assert(!equal(ts[], ts2[]));
913             assert(ts.length == 5 && ts2.length == 6);
914         }
915 
916     /**
917      * Fetch a range that spans all the elements in the container.
918      *
919      * Complexity: $(BIGOH 1)
920      */
921     Range opSlice() {
922         return Range(_begin, _end);
923     }
924 
925     /// Ditto
926     ConstRange opSlice() const {
927         return ConstRange(_begin, _end);
928     }
929 
930     /// Ditto
931     ImmutableRange opSlice() immutable {
932         return ImmutableRange(_begin, _end);
933     }
934 
935     /**
936      * The front element in the container
937      *
938      * Complexity: $(BIGOH 1)
939      */
940     inout(Elem) front() inout {
941         return _begin.value;
942     }
943 
944     /**
945      * The last element in the container
946      *
947      * Complexity: $(BIGOH log(n))
948      */
949     inout(Elem) back() inout {
950         return _end.prev.value;
951     }
952 
953     /++
954         `in` operator. Check to see if the given element exists in the
955         container.
956 
957        Complexity: $(BIGOH log(n))
958      +/
959     bool opBinaryRight(string op)(Elem e) const if (op == "in") {
960         return _find(e) !is null;
961     }
962 
963     static if (doUnittest)
964         @safe pure unittest {
965             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
966             assert(cast(Elem) 3 in ts);
967             assert(cast(Elem) 6 !in ts);
968         }
969 
970     /**
971      * Compares two trees for equality.
972      *
973      * Complexity: $(BIGOH n)
974      */
975     override bool opEquals(Object rhs) {
976         import std.algorithm.comparison : equal;
977 
978         RedBlackTree that = cast(RedBlackTree) rhs;
979         if (that is null)
980             return false;
981 
982         // If there aren't the same number of nodes, we can't be equal.
983         if (this._length != that._length)
984             return false;
985 
986         auto thisRange = this[];
987         auto thatRange = that[];
988         return equal!((Elem a, Elem b) => !_less(a, b) && !_less(b, a))(thisRange, thatRange);
989     }
990 
991     static if (doUnittest)
992         @system unittest {
993             auto t1 = new RedBlackTree(1, 2, 3, 4);
994             auto t2 = new RedBlackTree(1, 2, 3, 4);
995             auto t3 = new RedBlackTree(1, 2, 3, 5);
996             auto t4 = new RedBlackTree(1, 2, 3, 4, 5);
997             auto o = new Object();
998 
999             assert(t1 == t1);
1000             assert(t1 == t2);
1001             assert(t1 != t3);
1002             assert(t1 != t4);
1003             assert(t1 != o); // pathological case, must not crash
1004         }
1005 
1006     /**
1007      * Generates a hash for the tree. Note that with a custom comparison function
1008      * it may not hold that if two rbtrees are equal, the hashes of the trees
1009      * will be equal.
1010      */
1011     override size_t toHash() nothrow @safe {
1012         size_t hash = cast(size_t) 0x6b63_616c_4264_6552UL;
1013         foreach (ref e; this[]) // As in boost::hash_combine
1014             // https://www.boost.org/doc/libs/1_55_0/doc/html/hash/reference.html#boost.hash_combine
1015             hash += .hashOf(e) + 0x9e3779b9 + (hash << 6) + (hash >>> 2);
1016         return hash;
1017     }
1018 
1019     static if (doUnittest)
1020         @system unittest {
1021             auto t1 = new RedBlackTree(1, 2, 3, 4);
1022             auto t2 = new RedBlackTree(1, 2, 3, 4);
1023             auto t3 = new RedBlackTree(1, 2, 3, 5);
1024             auto t4 = new RedBlackTree(1, 2, 3, 4, 5);
1025 
1026             assert(t1.toHash() == t2.toHash);
1027 
1028             assert(t1.toHash() != t3.toHash);
1029             assert(t2.toHash() != t3.toHash);
1030 
1031             assert(t3.toHash() != t4.toHash);
1032             assert(t1.toHash() != t4.toHash);
1033 
1034             // empty tree
1035             auto t5 = new RedBlackTree();
1036             auto t6 = new RedBlackTree();
1037 
1038             assert(t5.toHash() == t6.toHash());
1039 
1040             auto t7 = new RedBlackTree!string("red", "black");
1041             auto t8 = new RedBlackTree!string("white", "black");
1042             auto t9 = new RedBlackTree!string("red", "black");
1043 
1044             assert(t7.toHash() == t9.toHash());
1045             assert(t7.toHash() != t8.toHash());
1046 
1047             static struct MyInt {
1048                 int x;
1049 
1050             @safe:
1051 
1052                 this(int init_x) {
1053                     x = init_x;
1054                 }
1055 
1056                 size_t toHash() const nothrow {
1057                     return typeid(x).getHash(&x) ^ 0xF0F0_F0F0;
1058                 }
1059 
1060                 int opCmp(const MyInt that) const {
1061                     return (x > that.x) - (x < that.x);
1062                 }
1063 
1064                 bool opEquals(const MyInt that) const {
1065                     return (this.x == that.x);
1066                 }
1067             }
1068 
1069             auto rbt1 = new RedBlackTree!MyInt(MyInt(1), MyInt(2), MyInt(3), MyInt(4));
1070             auto rbt2 = new RedBlackTree!MyInt(MyInt(1), MyInt(2), MyInt(3), MyInt(4));
1071 
1072             assert(rbt1.toHash() == rbt2.toHash());
1073             assert(rbt1.toHash() != t1.toHash());
1074 
1075             auto rbt3 = new RedBlackTree!MyInt(MyInt(4), MyInt(2), MyInt(3), MyInt(4));
1076 
1077             assert(rbt1.toHash() != rbt3.toHash());
1078 
1079             class MyInt2 {
1080                 int x;
1081 
1082                 this(int init_x) {
1083                     x = init_x;
1084                 }
1085 
1086                 override size_t toHash() const @safe nothrow {
1087                     return typeid(x).getHash(&x) ^ 0xF0F0_F0F0;
1088                 }
1089 
1090                 int opCmp(const MyInt2 that) const {
1091                     return (x > that.x) - (x < that.x);
1092                 }
1093 
1094                 bool opEquals(const MyInt2 that) const {
1095                     return (this.x == that.x);
1096                 }
1097             }
1098 
1099             static bool nullSafeLess(scope const MyInt2 a, scope const MyInt2 b) {
1100                 return a is null ? b !is null : (b !is null && a < b);
1101             }
1102 
1103             auto rbt4 = new RedBlackTree!MyInt2(new MyInt2(1), new MyInt2(9), new MyInt2(3), new MyInt2(42));
1104             auto rbt5 = new RedBlackTree!MyInt2(new MyInt2(1), new MyInt2(9), new MyInt2(3), new MyInt2(42));
1105             auto rbt6 = new RedBlackTree!(MyInt2, nullSafeLess)(new MyInt2(9), new MyInt2(3), new MyInt2(42));
1106             auto rbt7 = new RedBlackTree!(MyInt2, nullSafeLess)(null);
1107 
1108             assert(rbt6.toHash() != rbt5.toHash());
1109             assert(rbt6.toHash() != rbt4.toHash());
1110             assert(rbt6.toHash() != rbt7.toHash());
1111             assert(rbt4.toHash() == rbt5.toHash());
1112 
1113             auto rbt8 = new RedBlackTree!(MyInt2, nullSafeLess)(null, new MyInt2(9), null, new MyInt2(42));
1114             auto rbt9 = new RedBlackTree!(MyInt2, nullSafeLess)(null, new MyInt2(9), null, new MyInt2(42));
1115             auto rbt10 = new RedBlackTree!(MyInt2, nullSafeLess)(new MyInt2(94), null, new MyInt2(147));
1116 
1117             assert(rbt8.toHash() == rbt9.toHash());
1118             assert(rbt8.toHash() != rbt10.toHash());
1119         }
1120 
1121     /**
1122      * Removes all elements from the container.
1123      *
1124      * Complexity: $(BIGOH 1)
1125      */
1126     void clear() {
1127         _end.left = null;
1128         _begin = _end;
1129         _length = 0;
1130     }
1131 
1132     static if (doUnittest)
1133         @safe pure unittest {
1134             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1135             assert(ts.length == 5);
1136             ts.clear();
1137             assert(ts.empty && ts.length == 0);
1138         }
1139 
1140     /**
1141      * Insert a single element in the container.  Note that this does not
1142      * invalidate any ranges currently iterating the container.
1143      *
1144      * Returns: The number of elements inserted.
1145      *
1146      * Complexity: $(BIGOH log(n))
1147      */
1148     size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem)) {
1149         static if (allowDuplicates) {
1150             _add(stuff);
1151             return 1;
1152         }
1153         else {
1154             return _add(stuff);
1155         }
1156     }
1157 
1158     /**
1159      * Insert a range of elements in the container.  Note that this does not
1160      * invalidate any ranges currently iterating the container.
1161      *
1162      * Returns: The number of elements inserted.
1163      *
1164      * Complexity: $(BIGOH m * log(n))
1165      */
1166     size_t stableInsert(Stuff)(Stuff stuff) if (isInputRange!Stuff &&
1167             isImplicitlyConvertible!(ElementType!Stuff, Elem)) {
1168         size_t result = 0;
1169         static if (allowDuplicates) {
1170             foreach (e; stuff) {
1171                 ++result;
1172                 _add(e);
1173             }
1174         }
1175         else {
1176             foreach (e; stuff) {
1177                 result += _add(e);
1178             }
1179         }
1180         return result;
1181     }
1182 
1183     /// ditto
1184     alias insert = stableInsert;
1185 
1186     static if (doUnittest)
1187         @safe pure unittest {
1188             auto ts = new RedBlackTree(2, 1, 3, 4, 5, 2, 5);
1189             static if (allowDuplicates) {
1190                 assert(ts.length == 7);
1191                 assert(ts.stableInsert(cast(Elem[])[7, 8, 6, 9, 10, 8]) == 6);
1192                 assert(ts.length == 13);
1193                 assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 14);
1194                 assert(ts.stableInsert(cast(Elem) 7) == 1 && ts.length == 15);
1195 
1196                 static if (less == "a < b")
1197                     assert(ts.arrayEqual([1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 10, 11]));
1198                 else
1199                     assert(ts.arrayEqual([11, 10, 9, 8, 8, 7, 7, 6, 5, 5, 4, 3, 2, 2, 1]));
1200             }
1201             else {
1202                 assert(ts.length == 5);
1203                 Elem[] elems = [7, 8, 6, 9, 10, 8];
1204                 assert(ts.stableInsert(elems) == 5);
1205                 assert(ts.length == 10);
1206                 assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 11);
1207                 assert(ts.stableInsert(cast(Elem) 7) == 0 && ts.length == 11);
1208 
1209                 static if (less == "a < b")
1210                     assert(ts.arrayEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]));
1211                 else
1212                     assert(ts.arrayEqual([11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]));
1213             }
1214         }
1215 
1216     /**
1217      * Remove an element from the container and return its value.
1218      *
1219      * Complexity: $(BIGOH log(n))
1220      */
1221     Elem removeAny() {
1222         scope (success)
1223             --_length;
1224         auto n = _begin;
1225         auto result = n.value;
1226         _begin = n.remove(_end);
1227         debug (RBDoChecks)
1228             check();
1229         return result;
1230     }
1231 
1232     static if (doUnittest)
1233         @safe pure unittest {
1234             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1235             assert(ts.length == 5);
1236             auto x = ts.removeAny();
1237             assert(ts.length == 4);
1238             Elem[] arr;
1239             foreach (Elem i; 1 .. 6)
1240                 if (i != x)
1241                     arr ~= i;
1242             assert(ts.arrayEqual(arr));
1243         }
1244 
1245     /**
1246      * Remove the front element from the container.
1247      *
1248      * Complexity: $(BIGOH log(n))
1249      */
1250     void removeFront() {
1251         scope (success)
1252             --_length;
1253         _begin = _begin.remove(_end);
1254         debug (RBDoChecks)
1255             check();
1256     }
1257 
1258     /**
1259      * Remove the back element from the container.
1260      *
1261      * Complexity: $(BIGOH log(n))
1262      */
1263     void removeBack() {
1264         scope (success)
1265             --_length;
1266         auto lastnode = _end.prev;
1267         if (lastnode is _begin)
1268             _begin = _begin.remove(_end);
1269         else
1270             lastnode.remove(_end);
1271         debug (RBDoChecks)
1272             check();
1273     }
1274 
1275     static if (doUnittest)
1276         @safe pure unittest {
1277             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1278             assert(ts.length == 5);
1279             ts.removeBack();
1280             assert(ts.length == 4);
1281 
1282             static if (less == "a < b")
1283                 assert(ts.arrayEqual([1, 2, 3, 4]));
1284             else
1285                 assert(ts.arrayEqual([2, 3, 4, 5]));
1286 
1287             ts.removeFront();
1288             assert(ts.arrayEqual([2, 3, 4]) && ts.length == 3);
1289         }
1290 
1291     /++
1292         Removes the given range from the container.
1293 
1294         Returns: A range containing all of the elements that were after the
1295                  given range.
1296 
1297         Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
1298                     the range)
1299      +/
1300     Range remove(Range r) {
1301         auto b = r._begin;
1302         auto e = r._end;
1303         if (_begin is b)
1304             _begin = e;
1305         while (b !is e) {
1306             b = b.remove(_end);
1307             --_length;
1308         }
1309         debug (RBDoChecks)
1310             check();
1311         return Range(e, _end);
1312     }
1313 
1314     static if (doUnittest)
1315         @safe pure unittest {
1316             import std.algorithm.comparison : equal;
1317 
1318             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1319             assert(ts.length == 5);
1320             auto r = ts[];
1321             r.popFront();
1322             r.popBack();
1323             assert(ts.length == 5);
1324             auto r2 = ts.remove(r);
1325             assert(ts.length == 2);
1326             assert(ts.arrayEqual([1, 5]));
1327 
1328             static if (less == "a < b")
1329                 assert(equal(r2, [5]));
1330             else
1331                 assert(equal(r2, [1]));
1332         }
1333 
1334     /++
1335         Removes the given `Take!Range` from the container
1336 
1337         Returns: A range containing all of the elements that were after the
1338                  given range.
1339 
1340         Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
1341                     the range)
1342      +/
1343     Range remove(Take!Range r) {
1344         immutable isBegin = (r.source._begin is _begin);
1345         auto b = r.source._begin;
1346 
1347         while (!r.empty) {
1348             r.popFront();
1349             b = b.remove(_end);
1350             --_length;
1351         }
1352 
1353         if (isBegin)
1354             _begin = b;
1355 
1356         return Range(b, _end);
1357     }
1358 
1359     static if (doUnittest)
1360         @safe pure unittest {
1361             import std.algorithm.comparison : equal;
1362             import std.range : take;
1363 
1364             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1365             auto r = ts[];
1366             r.popFront();
1367             assert(ts.length == 5);
1368             auto r2 = ts.remove(take(r, 0));
1369 
1370             static if (less == "a < b") {
1371                 assert(equal(r2, [2, 3, 4, 5]));
1372                 auto r3 = ts.remove(take(r, 2));
1373                 assert(ts.arrayEqual([1, 4, 5]) && ts.length == 3);
1374                 assert(equal(r3, [4, 5]));
1375             }
1376             else {
1377                 assert(equal(r2, [4, 3, 2, 1]));
1378                 auto r3 = ts.remove(take(r, 2));
1379                 assert(ts.arrayEqual([5, 2, 1]) && ts.length == 3);
1380                 assert(equal(r3, [2, 1]));
1381             }
1382         }
1383 
1384     /++
1385        Removes elements from the container that are equal to the given values
1386        according to the less comparator. One element is removed for each value
1387        given which is in the container. If `allowDuplicates` is true,
1388        duplicates are removed only if duplicate values are given.
1389 
1390        Returns: The number of elements removed.
1391 
1392        Complexity: $(BIGOH m log(n)) (where m is the number of elements to remove)
1393 
1394        Example:
1395 --------------------
1396 auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);
1397 rbt.removeKey(1, 4, 7);
1398 assert(equal(rbt[], [0, 1, 1, 5]));
1399 rbt.removeKey(1, 1, 0);
1400 assert(equal(rbt[], [5]));
1401 --------------------
1402       +/
1403     size_t removeKey(U...)(U elems) if (allSatisfy!(isImplicitlyConvertibleToElem, U)) {
1404         Elem[U.length] toRemove = [elems];
1405         return removeKey(toRemove[]);
1406     }
1407 
1408     /++ Ditto +/
1409     size_t removeKey(U)(scope U[] elems) if (isImplicitlyConvertible!(U, Elem)) {
1410         immutable lenBefore = length;
1411 
1412         foreach (e; elems) {
1413             auto beg = _firstGreaterEqual(e);
1414             if (beg is _end || _less(e, beg.value)) // no values are equal
1415                 continue;
1416             immutable isBegin = (beg is _begin);
1417             beg = beg.remove(_end);
1418             if (isBegin)
1419                 _begin = beg;
1420             --_length;
1421         }
1422 
1423         return lenBefore - length;
1424     }
1425 
1426     /++ Ditto +/
1427     size_t removeKey(Stuff)(Stuff stuff)
1428             if (isInputRange!Stuff &&
1429                 isImplicitlyConvertible!(ElementType!Stuff, Elem) &&
1430                 !isDynamicArray!Stuff) {
1431         import std.array : array;
1432 
1433         //We use array in case stuff is a Range from this RedBlackTree - either
1434         //directly or indirectly.
1435         return removeKey(array(stuff));
1436     }
1437 
1438     //Helper for removeKey.
1439     private template isImplicitlyConvertibleToElem(U) {
1440         enum isImplicitlyConvertibleToElem = isImplicitlyConvertible!(U, Elem);
1441     }
1442 
1443     static if (doUnittest)
1444         @safe pure unittest {
1445             import std.algorithm.comparison : equal;
1446             import std.range : take;
1447 
1448             auto rbt = new RedBlackTree(5, 4, 3, 7, 2, 1, 7, 6, 2, 19, 45);
1449 
1450             //The cast(Elem) is because these tests are instantiated with a variety
1451             //of numeric types, and the literals are all int, which is not always
1452             //implicitly convertible to Elem (e.g. short).
1453             static if (allowDuplicates) {
1454                 assert(rbt.length == 11);
1455                 assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 10);
1456                 assert(rbt.arrayEqual([1, 2, 2, 3, 5, 6, 7, 7, 19, 45]) && rbt.length == 10);
1457 
1458                 assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3);
1459                 assert(rbt.arrayEqual([2, 3, 5, 7, 7, 19, 45]) && rbt.length == 7);
1460 
1461                 assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 7);
1462                 assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 4);
1463 
1464                 static if (less == "a < b")
1465                     assert(equal(rbt[], [7, 7, 19, 45]));
1466                 else
1467                     assert(equal(rbt[], [7, 5, 3, 2]));
1468             }
1469             else {
1470                 assert(rbt.length == 9);
1471                 assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 8);
1472                 assert(rbt.arrayEqual([1, 2, 3, 5, 6, 7, 19, 45]));
1473 
1474                 assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3);
1475                 assert(rbt.arrayEqual([3, 5, 7, 19, 45]) && rbt.length == 5);
1476 
1477                 assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 5);
1478                 assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 2);
1479 
1480                 static if (less == "a < b")
1481                     assert(equal(rbt[], [19, 45]));
1482                 else
1483                     assert(equal(rbt[], [5, 3]));
1484             }
1485         }
1486 
1487     // find the first node where the value is > e
1488     private inout(RBNode)* _firstGreater(Elem e) inout {
1489         // can't use _find, because we cannot return null
1490         auto cur = _end.left;
1491         inout(RBNode)* result = _end;
1492         while (cur) {
1493             if (_less(e, cur.value)) {
1494                 result = cur;
1495                 cur = cur.left;
1496             }
1497             else
1498                 cur = cur.right;
1499         }
1500         return result;
1501     }
1502 
1503     // find the first node where the value is >= e
1504     private inout(RBNode)* _firstGreaterEqual(Elem e) inout {
1505         // can't use _find, because we cannot return null.
1506         auto cur = _end.left;
1507         inout(RBNode)* result = _end;
1508         while (cur) {
1509             if (_less(cur.value, e))
1510                 cur = cur.right;
1511             else {
1512                 result = cur;
1513                 cur = cur.left;
1514             }
1515 
1516         }
1517         return result;
1518     }
1519 
1520     /**
1521      * Get a range from the container with all elements that are > e according
1522      * to the less comparator
1523      *
1524      * Complexity: $(BIGOH log(n))
1525      */
1526     Range upperBound(Elem e) {
1527         return Range(_firstGreater(e), _end);
1528     }
1529 
1530     /// Ditto
1531     ConstRange upperBound(Elem e) const {
1532         return ConstRange(_firstGreater(e), _end);
1533     }
1534 
1535     /// Ditto
1536     ImmutableRange upperBound(Elem e) immutable {
1537         return ImmutableRange(_firstGreater(e), _end);
1538     }
1539 
1540     /**
1541      * Get a range from the container with all elements that are < e according
1542      * to the less comparator
1543      *
1544      * Complexity: $(BIGOH log(n))
1545      */
1546     Range lowerBound(Elem e) {
1547         return Range(_begin, _firstGreaterEqual(e));
1548     }
1549 
1550     /// Ditto
1551     ConstRange lowerBound(Elem e) const {
1552         return ConstRange(_begin, _firstGreaterEqual(e));
1553     }
1554 
1555     /// Ditto
1556     ImmutableRange lowerBound(Elem e) immutable {
1557         return ImmutableRange(_begin, _firstGreaterEqual(e));
1558     }
1559 
1560     /**
1561      * Get a range from the container with all elements that are == e according
1562      * to the less comparator
1563      *
1564      * Complexity: $(BIGOH log(n))
1565      */
1566     auto equalRange(this This)(Elem e) {
1567         auto beg = _firstGreaterEqual(e);
1568         alias RangeType = RBRange!(typeof(beg));
1569         if (beg is _end || _less(e, beg.value)) // no values are equal
1570             return RangeType(beg, beg);
1571         static if (allowDuplicates) {
1572             return RangeType(beg, _firstGreater(e));
1573         }
1574         else {
1575             // no sense in doing a full search, no duplicates are allowed,
1576             // so we just get the next node.
1577             return RangeType(beg, beg.next);
1578         }
1579     }
1580 
1581     static if (doUnittest)
1582         @safe pure unittest {
1583             import std.algorithm.comparison : equal;
1584 
1585             auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1586             auto rl = ts.lowerBound(3);
1587             auto ru = ts.upperBound(3);
1588             auto re = ts.equalRange(3);
1589 
1590             static if (less == "a < b") {
1591                 assert(equal(rl, [1, 2]));
1592                 assert(equal(ru, [4, 5]));
1593             }
1594             else {
1595                 assert(equal(rl, [5, 4]));
1596                 assert(equal(ru, [2, 1]));
1597             }
1598 
1599             assert(equal(re, [3]));
1600         }
1601 
1602     debug (RBDoChecks) {
1603         /*
1604          * Print the tree.  This prints a sideways view of the tree in ASCII form,
1605          * with the number of indentations representing the level of the nodes.
1606          * It does not print values, only the tree structure and color of nodes.
1607          */
1608         void printTree(Node n, int indent = 0) {
1609             import std.stdio : write, writeln;
1610 
1611             if (n !is null) {
1612                 printTree(n.right, indent + 2);
1613                 for (int i = 0; i < indent; i++)
1614                     write(".");
1615                 writeln(n.color == n.color.Black ? "B" : "R");
1616                 printTree(n.left, indent + 2);
1617             }
1618             else {
1619                 for (int i = 0; i < indent; i++)
1620                     write(".");
1621                 writeln("N");
1622             }
1623             if (indent is 0)
1624                 writeln();
1625         }
1626 
1627         /*
1628          * Check the tree for validity.  This is called after every add or remove.
1629          * This should only be enabled to debug the implementation of the RB Tree.
1630          */
1631         void check() @trusted {
1632             //
1633             // check implementation of the tree
1634             //
1635             int recurse(Node n, string path) {
1636                 import std.stdio : writeln;
1637 
1638                 if (n is null)
1639                     return 1;
1640                 if (n.parent.left !is n && n.parent.right !is n)
1641                     throw new Exception("Node at path " ~ path ~ " has inconsistent pointers");
1642                 Node next = n.next;
1643                 static if (allowDuplicates) {
1644                     if (next !is _end && _less(next.value, n.value))
1645                         throw new Exception("ordering invalid at path " ~ path);
1646                 }
1647                 else {
1648                     if (next !is _end && !_less(n.value, next.value))
1649                         throw new Exception("ordering invalid at path " ~ path);
1650                 }
1651                 if (n.color == n.color.Red) {
1652                     if ((n.left !is null && n.left.color == n.color.Red) ||
1653                             (n.right !is null && n.right.color == n.color.Red))
1654                         throw new Exception("Node at path " ~ path ~ " is red with a red child");
1655                 }
1656 
1657                 int l = recurse(n.left, path ~ "L");
1658                 int r = recurse(n.right, path ~ "R");
1659                 if (l != r) {
1660                     writeln("bad tree at:");
1661                     debug printTree(n);
1662                     throw new Exception(
1663                             "Node at path " ~ path ~ " has different number of black nodes on left and right paths"
1664                     );
1665                 }
1666                 return l + (n.color == n.color.Black ? 1 : 0);
1667             }
1668 
1669             try {
1670                 recurse(_end.left, "");
1671             }
1672             catch (Exception e) {
1673                 debug printTree(_end.left, 0);
1674                 throw e;
1675             }
1676         }
1677     }
1678 
1679     /**
1680       Formats the RedBlackTree into a sink function. For more info see $(D
1681       std.format.formatValue). Note that this only is available when the
1682       element type can be formatted. Otherwise, the default toString from
1683       Object is used.
1684      */
1685     static if (is(typeof(() { FormatSpec!(char) fmt; formatValue((const(char)[]) {}, ConstRange.init, fmt); }))) {
1686         void toString(scope void delegate(const(char)[]) sink, scope const ref FormatSpec!char fmt) const {
1687             sink("RedBlackTree(");
1688             sink.formatValue(this[], fmt);
1689             sink(")");
1690         }
1691     }
1692 
1693     /**
1694      * Constructor. Pass in an array of elements, or individual elements to
1695      * initialize the tree with.
1696      */
1697     this(Elem[] elems...) {
1698         _setup();
1699         stableInsert(elems);
1700     }
1701 
1702     /**
1703      * Constructor. Pass in a range of elements to initialize the tree with.
1704      */
1705     this(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem)) {
1706         _setup();
1707         stableInsert(stuff);
1708     }
1709 
1710     ///
1711     this() {
1712         _setup();
1713     }
1714 
1715     private this(Node end, size_t length) {
1716         _end = end;
1717         _begin = end.leftmost;
1718         _length = length;
1719     }
1720 }
1721 
1722 //Verify Example for removeKey.
1723 @safe pure unittest {
1724     import std.algorithm.comparison : equal;
1725 
1726     auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);
1727     rbt.removeKey(1, 4, 7);
1728     assert(equal(rbt[], [0, 1, 1, 5]));
1729     rbt.removeKey(1, 1, 0);
1730     assert(equal(rbt[], [5]));
1731 }
1732 
1733 //Tests for removeKey
1734 @safe pure unittest {
1735     import std.algorithm.comparison : equal;
1736 
1737     {
1738         auto rbt = redBlackTree(["hello", "world", "foo", "bar"]);
1739         assert(equal(rbt[], ["bar", "foo", "hello", "world"]));
1740         assert(rbt.removeKey("hello") == 1);
1741         assert(equal(rbt[], ["bar", "foo", "world"]));
1742         assert(rbt.removeKey("hello") == 0);
1743         assert(equal(rbt[], ["bar", "foo", "world"]));
1744         assert(rbt.removeKey("hello", "foo", "bar") == 2);
1745         assert(equal(rbt[], ["world"]));
1746         assert(rbt.removeKey(["", "world", "hello"]) == 1);
1747         assert(rbt.empty);
1748     }
1749 
1750     {
1751         auto rbt = redBlackTree([1, 2, 12, 27, 4, 500]);
1752         assert(equal(rbt[], [1, 2, 4, 12, 27, 500]));
1753         assert(rbt.removeKey(1u) == 1);
1754         assert(equal(rbt[], [2, 4, 12, 27, 500]));
1755         assert(rbt.removeKey(cast(byte) 1) == 0);
1756         assert(equal(rbt[], [2, 4, 12, 27, 500]));
1757         assert(rbt.removeKey(1, 12u, cast(byte) 27) == 2);
1758         assert(equal(rbt[], [2, 4, 500]));
1759         assert(rbt.removeKey([cast(short) 0, cast(short) 500, cast(short) 1]) == 1);
1760         assert(equal(rbt[], [2, 4]));
1761     }
1762 }
1763 
1764 @safe pure unittest {
1765     void test(T)() {
1766         auto rt1 = new RedBlackTree!(T, "a < b", false)();
1767         auto rt2 = new RedBlackTree!(T, "a < b", true)();
1768         auto rt3 = new RedBlackTree!(T, "a > b", false)();
1769         auto rt4 = new RedBlackTree!(T, "a > b", true)();
1770     }
1771 
1772     test!long();
1773     test!ulong();
1774     test!int();
1775     test!uint();
1776     test!short();
1777     test!ushort();
1778     test!byte();
1779     test!byte();
1780 }
1781 
1782 // https://issues.dlang.org/show_bug.cgi?id=19626
1783 @safe pure unittest {
1784     enum T {
1785         a,
1786         b
1787     }
1788 
1789     alias t = RedBlackTree!T;
1790 }
1791 
1792 import std.range.primitives : ElementType, isInputRange;
1793 import std.traits : isArray, isSomeString;
1794 
1795 /++
1796     Convenience function for creating a `RedBlackTree!E` from a list of
1797     values.
1798 
1799     Params:
1800         allowDuplicates =  Whether duplicates should be allowed (optional, default: false)
1801         less = predicate to sort by (optional)
1802         elems = elements to insert into the rbtree (variadic arguments)
1803         range = range elements to insert into the rbtree (alternative to elems)
1804   +/
1805 auto redBlackTree(E)(E[] elems...) {
1806     return new RedBlackTree!E(elems);
1807 }
1808 
1809 /++ Ditto +/
1810 auto redBlackTree(bool allowDuplicates, E)(E[] elems...) {
1811     return new RedBlackTree!(E, "a < b", allowDuplicates)(elems);
1812 }
1813 
1814 /++ Ditto +/
1815 auto redBlackTree(alias less, E)(E[] elems...) if (is(typeof(binaryFun!less(E.init, E.init)))) {
1816     return new RedBlackTree!(E, less)(elems);
1817 }
1818 
1819 /++ Ditto +/
1820 auto redBlackTree(alias less, bool allowDuplicates, E)(E[] elems...) if (is(typeof(binaryFun!less(E.init, E.init)))) {
1821     //We shouldn't need to instantiate less here, but for some reason,
1822     //dmd can't handle it if we don't (even though the template which
1823     //takes less but not allowDuplicates works just fine).
1824     return new RedBlackTree!(E, binaryFun!less, allowDuplicates)(elems);
1825 }
1826 
1827 /++ Ditto +/
1828 auto redBlackTree(Stuff)(Stuff range) if (isInputRange!Stuff && !isArray!(Stuff)) {
1829     return new RedBlackTree!(ElementType!Stuff)(range);
1830 }
1831 
1832 /++ Ditto +/
1833 auto redBlackTree(bool allowDuplicates, Stuff)(Stuff range) if (isInputRange!Stuff && !isArray!(Stuff)) {
1834     return new RedBlackTree!(ElementType!Stuff, "a < b", allowDuplicates)(range);
1835 }
1836 
1837 /++ Ditto +/
1838 auto redBlackTree(alias less, Stuff)(Stuff range)
1839         if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
1840             && isInputRange!Stuff && !isArray!(Stuff)) {
1841     return new RedBlackTree!(ElementType!Stuff, less)(range);
1842 }
1843 
1844 /++ Ditto +/
1845 auto redBlackTree(alias less, bool allowDuplicates, Stuff)(Stuff range)
1846         if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
1847             && isInputRange!Stuff && !isArray!(Stuff)) {
1848     //We shouldn't need to instantiate less here, but for some reason,
1849     //dmd can't handle it if we don't (even though the template which
1850     //takes less but not allowDuplicates works just fine).
1851     return new RedBlackTree!(ElementType!Stuff, binaryFun!less, allowDuplicates)(range);
1852 }
1853 
1854 ///
1855 @safe pure unittest {
1856     import std.range : iota;
1857 
1858     auto rbt1 = redBlackTree(0, 1, 5, 7);
1859     auto rbt2 = redBlackTree!string("hello", "world");
1860     auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5);
1861     auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7);
1862     auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9);
1863 
1864     // also works with ranges
1865     auto rbt6 = redBlackTree(iota(3));
1866     auto rbt7 = redBlackTree!true(iota(3));
1867     auto rbt8 = redBlackTree!"a > b"(iota(3));
1868     auto rbt9 = redBlackTree!("a > b", true)(iota(3));
1869 }
1870 
1871 //Combinations not in examples.
1872 @system pure unittest {
1873     auto rbt1 = redBlackTree!(true, string)("hello", "hello");
1874     auto rbt2 = redBlackTree!((a, b) { return a < b; }, double)(5.1, 2.3);
1875     auto rbt3 = redBlackTree!("a > b", true, string)("hello", "world");
1876 }
1877 
1878 //Range construction.
1879 @safe pure unittest {
1880     import std.algorithm.comparison : equal;
1881     import std.range : iota;
1882 
1883     auto rbt = new RedBlackTree!(int, "a > b")(iota(5));
1884     assert(equal(rbt[], [4, 3, 2, 1, 0]));
1885 }
1886 
1887 // construction with arrays
1888 @safe pure unittest {
1889     import std.algorithm.comparison : equal;
1890 
1891     auto rbt = redBlackTree!"a > b"([0, 1, 2, 3, 4]);
1892     assert(equal(rbt[], [4, 3, 2, 1, 0]));
1893 
1894     auto rbt2 = redBlackTree!"a > b"(["a", "b"]);
1895     assert(equal(rbt2[], ["b", "a"]));
1896 
1897     auto rbt3 = redBlackTree!"a > b"([1, 2]);
1898     assert(equal(rbt3[], [2, 1]));
1899 
1900     auto rbt4 = redBlackTree([0, 1, 7, 5]);
1901     assert(equal(rbt4[], [0, 1, 5, 7]));
1902 
1903     auto rbt5 = redBlackTree(["hello", "world"]);
1904     assert(equal(rbt5[], ["hello", "world"]));
1905 
1906     auto rbt6 = redBlackTree!true([0, 1, 5, 7, 5]);
1907     assert(equal(rbt6[], [0, 1, 5, 5, 7]));
1908 
1909     auto rbt7 = redBlackTree!"a > b"([0, 1, 5, 7]);
1910     assert(equal(rbt7[], [7, 5, 1, 0]));
1911 
1912     auto rbt8 = redBlackTree!("a > b", true)([0.1, 1.3, 5.9, 7.2, 5.9]);
1913     assert(equal(rbt8[], [7.2, 5.9, 5.9, 1.3, 0.1]));
1914 }
1915 
1916 // convenience wrapper range construction
1917 @safe pure unittest {
1918     import std.algorithm.comparison : equal;
1919     import std.range : chain, iota;
1920 
1921     auto rbt = redBlackTree(iota(3));
1922     assert(equal(rbt[], [0, 1, 2]));
1923 
1924     auto rbt2 = redBlackTree!"a > b"(iota(2));
1925     assert(equal(rbt2[], [1, 0]));
1926 
1927     auto rbt3 = redBlackTree(chain([0, 1], [7, 5]));
1928     assert(equal(rbt3[], [0, 1, 5, 7]));
1929 
1930     auto rbt4 = redBlackTree(chain(["hello"].idup, ["world"].idup));
1931     assert(equal(rbt4[], ["hello", "world"]));
1932 
1933     auto rbt5 = redBlackTree!true(chain([0, 1], [5, 7, 5]));
1934     assert(equal(rbt5[], [0, 1, 5, 5, 7]));
1935 
1936     auto rbt6 = redBlackTree!("a > b", true)(chain([0.1, 1.3], [5.9, 7.2, 5.9]));
1937     assert(equal(rbt6[], [7.2, 5.9, 5.9, 1.3, 0.1]));
1938 }
1939 
1940 @safe pure unittest {
1941     import std.array : array;
1942 
1943     auto rt1 = redBlackTree(5, 4, 3, 2, 1);
1944     assert(rt1.length == 5);
1945     assert(array(rt1[]) == [1, 2, 3, 4, 5]);
1946 
1947     auto rt2 = redBlackTree!"a > b"(1.1, 2.1);
1948     assert(rt2.length == 2);
1949     assert(array(rt2[]) == [2.1, 1.1]);
1950 
1951     auto rt3 = redBlackTree!true(5, 5, 4);
1952     assert(rt3.length == 3);
1953     assert(array(rt3[]) == [4, 5, 5]);
1954 
1955     auto rt4 = redBlackTree!string("hello", "hello");
1956     assert(rt4.length == 1);
1957     assert(array(rt4[]) == ["hello"]);
1958 }
1959 
1960 @system unittest {
1961     import std.conv : to;
1962 
1963     auto rt1 = redBlackTree!string();
1964     assert(rt1.to!string == "RedBlackTree([])");
1965 
1966     auto rt2 = redBlackTree!string("hello");
1967     assert(rt2.to!string == "RedBlackTree([\"hello\"])");
1968 
1969     auto rt3 = redBlackTree!string("hello", "world", "!");
1970     assert(rt3.to!string == "RedBlackTree([\"!\", \"hello\", \"world\"])");
1971 
1972     // type deduction can be done automatically
1973     auto rt4 = redBlackTree(["hello"]);
1974     assert(rt4.to!string == "RedBlackTree([\"hello\"])");
1975 }
1976 
1977 //constness checks
1978 @safe pure unittest {
1979     const rt1 = redBlackTree(5, 4, 3, 2, 1);
1980     void allQualifiers() pure nothrow @safe @nogc {
1981         assert(!rt1.empty);
1982         assert(rt1.length == 5);
1983         assert(5 in rt1);
1984     }
1985 
1986     allQualifiers();
1987 
1988     static assert(is(typeof(rt1.upperBound(3).front) == const(int)));
1989     import std.algorithm.comparison : equal;
1990 
1991     assert(rt1.upperBound(3).equal([4, 5]));
1992     assert(rt1.lowerBound(3).equal([1, 2]));
1993     assert(rt1.equalRange(3).equal([3]));
1994     assert(rt1[].equal([1, 2, 3, 4, 5]));
1995 }
1996 
1997 //immutable checks
1998 @safe pure unittest {
1999     immutable rt1 = redBlackTree(5, 4, 3, 2, 1);
2000     static assert(is(typeof(rt1.empty)));
2001     static assert(is(typeof(rt1.length)));
2002     static assert(is(typeof(5 in rt1)));
2003 
2004     static assert(is(typeof(rt1.upperBound(3).front) == immutable(int)));
2005     import std.algorithm.comparison : equal;
2006 
2007     assert(rt1.upperBound(2).equal([3, 4, 5]));
2008 }
2009 
2010 // https://issues.dlang.org/show_bug.cgi?id=15941
2011 @safe pure unittest {
2012     class C {
2013     }
2014 
2015     RedBlackTree!(C, "cast(void*)a < cast(void*) b") tree;
2016 }
2017 
2018 // const/immutable elements (https://issues.dlang.org/show_bug.cgi?id=17519)
2019 @safe pure unittest {
2020     RedBlackTree!(immutable int) t1;
2021     RedBlackTree!(const int) t2;
2022 
2023     import std.algorithm.iteration : map;
2024 
2025     static struct S {
2026         int* p;
2027     }
2028 
2029     auto t3 = new RedBlackTree!(immutable S, (a, b) => *a.p < *b.p);
2030     t3.insert([1, 2, 3].map!(x => immutable S(new int(x))));
2031     static assert(!__traits(compiles, *t3.front.p = 4));
2032     assert(*t3.front.p == 1);
2033 }
2034 
2035 // make sure the comparator can be a delegate
2036 @safe pure unittest {
2037     import std.algorithm.comparison : equal;
2038 
2039     auto t = new RedBlackTree!(int, delegate(a, b) => a > b);
2040     t.insert([1, 3, 5, 4, 2]);
2041     assert(t[].equal([5, 4, 3, 2, 1]));
2042 }