The OpenD Programming Language

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