2 This module implements a red-black tree container.
4 This module is a submodule of $(MREF std, container).
6 Source: $(PHOBOSSRC std/container/rbtree.d)
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.
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)).
15 Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu)
17 module std.container.rbtree;
22 import std.algorithm.comparison : equal;
23 import std.container.rbtree;
25 auto rbt = redBlackTree(3, 1, 4, 2, 5);
26 assert(rbt.front == 1);
27 assert(equal(rbt[], [1, 2, 3, 4, 5]));
30 assert(equal(rbt[], [2, 3, 5]));
33 assert(equal(rbt[], [3, 5]));
35 rbt.insert([1, 2, 4]);
36 assert(equal(rbt[], [1, 2, 3, 4, 5]));
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]));
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]));
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);
54 // however you can allow duplicates
55 auto ubt = redBlackTree!true([0, 1, 0, 1]);
56 assert(equal(ubt[], [0, 0, 1, 1]));
60 import std.functional : binaryFun;
62 public import std.container.util;
64 version (StdUnittest) debug = RBDoChecks;
69 * Implementation for a Red Black node for use in a Red Black Tree (see below)
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
78 * A Red Black tree should have O(lg(n)) insertion, removal, and search time.
92 * The value held by this node
97 * Enumeration determining what color the node is. Null nodes are assumed
107 * The color of the node.
114 @property inout(RBNode)* left() inout
120 * Get the right child
122 @property inout(RBNode)* right() inout
130 @property inout(RBNode)* parent() inout
136 * Set the left child. Also updates the new child's parent node. This
137 * does not update the previous child.
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.)
144 @property Node left(return scope Node newNode) @trusted
147 if (newNode !is null)
148 newNode._parent = &this;
153 * Set the right child. Also updates the new child's parent node. This
154 * does not update the previous child.
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.)
161 @property Node right(return scope Node newNode) @trusted
164 if (newNode !is null)
165 newNode._parent = &this;
169 // assume _left is not null
171 // performs rotate-right operation, where this is T, _right is R, _left is
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
192 assert(_left !is null, "left node must not be null");
196 // sets _left._parent also
200 parent.right = _left;
201 Node tmp = _left._right;
206 // sets tmp._parent also
212 // assumes _right is non null
214 // performs rotate-left operation, where this is T, _right is R, _left is
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
235 assert(_right !is null, "right node must not be null");
239 // sets _right._parent also
241 parent.left = _right;
243 parent.right = _right;
244 Node tmp = _right._left;
249 // sets tmp._parent also
256 * Returns true if this node is a left child.
258 * Note that this should always return a value because the root has a
259 * parent which is the marker node.
261 @property bool isLeftNode() const
264 assert(_parent !is null, "parent must not be null");
268 return _parent._left is &this;
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.
277 * end is the marker node, which is the parent of the topmost valid node.
279 void setColor(Node end)
281 // test against the marker node
284 if (_parent.color == Color.Red)
289 // because root is always black, _parent._parent always exists
290 if (cur._parent.isLeftNode)
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)
296 cur._parent.color = Color.Black;
297 y.color = Color.Black;
298 cur = cur._parent._parent;
299 if (cur._parent is end)
302 cur.color = Color.Black;
308 cur.color = Color.Red;
309 if (cur._parent.color == Color.Black)
310 // satisfied, exit the loop
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
327 // parent is right node, y is 'uncle'
328 Node y = cur._parent._parent._left;
329 if (y !is null && y.color == Color.Red)
331 cur._parent.color = Color.Black;
332 y.color = Color.Black;
333 cur = cur._parent._parent;
334 if (cur._parent is end)
337 cur.color = Color.Black;
343 cur.color = Color.Red;
344 if (cur._parent.color == Color.Black)
345 // satisfied, exit the loop
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
367 // this is the root node, color it black
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!
377 * Returns the next highest valued node in the tree after this one, or end
378 * if this was the highest-valued node.
380 Node remove(Node end)
383 // remove this node from the tree, fixing the color if necessary.
388 // if this node has 2 children
389 if (_left !is null && _right !is null)
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.
399 Node y = ret; // y = next
404 auto isyleft = y.isLeftNode;
407 // replace y's structure with structure of this node.
414 // need special case so y doesn't point back to itself
424 // replace this node's structure with structure of y.
438 // if this has less than 2 children, remove it
444 bool deferedUnlink = false;
447 // pretend this is a null node, defer unlinking the node
449 deferedUnlink = true;
456 // if the color of this is black, then it needs to be fixed
457 if (color == color.Black)
459 // need to recolor the tree.
460 while (x._parent !is end && x.color == Node.Color.Black)
465 Node w = x._parent._right;
466 if (w.color == Node.Color.Red)
468 w.color = Node.Color.Black;
469 x._parent.color = Node.Color.Red;
471 w = x._parent._right;
475 if ((wl is null || wl.color == Node.Color.Black) &&
476 (wr is null || wr.color == Node.Color.Black))
478 w.color = Node.Color.Red;
483 if (wr is null || wr.color == Node.Color.Black)
485 // wl cannot be null here
486 wl.color = Node.Color.Black;
487 w.color = Node.Color.Red;
489 w = x._parent._right;
492 w.color = x._parent.color;
493 x._parent.color = Node.Color.Black;
494 w._right.color = Node.Color.Black;
496 x = end.left; // x = root
502 Node w = x._parent._left;
503 if (w.color == Node.Color.Red)
505 w.color = Node.Color.Black;
506 x._parent.color = Node.Color.Red;
512 if ((wl is null || wl.color == Node.Color.Black) &&
513 (wr is null || wr.color == Node.Color.Black))
515 w.color = Node.Color.Red;
520 if (wl is null || wl.color == Node.Color.Black)
522 // wr cannot be null here
523 wr.color = Node.Color.Black;
524 w.color = Node.Color.Red;
529 w.color = x._parent.color;
530 x._parent.color = Node.Color.Black;
531 w._left.color = Node.Color.Black;
533 x = end.left; // x = root
537 x.color = Node.Color.Black;
543 // unlink this node from the tree
548 _parent.right = null;
551 // clean references to help GC
552 // https://issues.dlang.org/show_bug.cgi?id=12915
553 _left = _right = _parent = null;
559 * Return the leftmost descendant of this node.
561 @property inout(RBNode)* leftmost() inout
563 inout(RBNode)* result = &this;
564 while (result._left !is null)
565 result = result._left;
570 * Return the rightmost descendant of this node
572 @property inout(RBNode)* rightmost() inout
574 inout(RBNode)* result = &this;
575 while (result._right !is null)
576 result = result._right;
581 * Returns the next valued node in the tree.
583 * You should never call this on the marker node, as it is assumed that
584 * there is a valid next node.
586 @property inout(RBNode)* next() inout
588 inout(RBNode)* n = &this;
591 while (!n.isLeftNode)
596 return n.right.leftmost;
600 * Returns the previous valued node in the tree.
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.
605 @property inout(RBNode)* prev() inout
607 inout(RBNode)* n = &this;
615 return n.left.rightmost;
618 Node dup(scope Node delegate(V v) alloc)
621 // duplicate this and all child nodes
623 // The recursion should be lg(n), so we shouldn't have to worry about
626 Node copy = alloc(value);
629 copy.left = _left.dup(alloc);
631 copy.right = _right.dup(alloc);
637 Node copy = new RBNode!V(null, null, null, value);
640 copy.left = _left.dup();
642 copy.right = _right.dup();
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)));
657 private struct RBRange(N)
660 alias Elem = typeof(Node.value);
665 private this(Node b, Node e)
672 * Returns `true` if the range is _empty
674 @property bool empty() const
676 return _begin is _end;
680 * Returns the first element in the range
682 @property Elem front()
688 * Returns the last element in the range
690 @property Elem back()
692 return _end.prev.value;
696 * pop the front element from the range
698 * Complexity: amortized $(BIGOH 1)
702 _begin = _begin.next;
706 * pop the back element from the range
708 * Complexity: amortized $(BIGOH 1)
716 * Trivial _save implementation, needed for `isForwardRange`.
718 @property RBRange save()
725 * Implementation of a $(LINK2 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree,
726 * red-black tree) container.
728 * All inserts, removes, searches, and any function in general has complexity
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`
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`.
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.
745 final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
746 if (is(typeof(binaryFun!less(T.init, T.init))))
748 import std.meta : allSatisfy;
749 import std.range : Take;
750 import std.range.primitives : isInputRange, walkLength;
751 import std.traits : isIntegral, isDynamicArray, isImplicitlyConvertible;
753 alias _less = binaryFun!less;
755 version (StdUnittest)
757 static if (is(typeof(less) == string))
759 private enum doUnittest = is(byte : T) && isIntegral!T && (less == "a < b" || less == "a > b");
762 enum doUnittest = false;
764 // note, this must be final so it does not affect the vtable layout
765 bool arrayEqual(T[] arr)
767 if (walkLength(this[]) == arr.length)
781 private enum doUnittest = false;
785 * Element type for the tree
789 // used for convenience
790 private alias RBNode = .RBNode!Elem;
791 private alias Node = RBNode.Node;
795 private size_t _length;
797 private void _setup()
799 //Make sure that _setup isn't run more than once.
800 assert(!_end, "Setup must only be run once");
801 _begin = _end = allocate();
804 static private Node allocate()
809 static private Node allocate(Elem v)
811 return new RBNode(null, null, null, v);
815 * The range types for `RedBlackTree`
817 alias Range = RBRange!(RBNode*);
818 alias ConstRange = RBRange!(const(RBNode)*); /// Ditto
819 alias ImmutableRange = RBRange!(immutable(RBNode)*); /// Ditto
821 static if (doUnittest) @safe pure unittest
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);
829 static if (less == "a < b")
830 auto vals = [1, 2, 3, 4, 5];
832 auto vals = [5, 4, 3, 2, 1];
833 assert(equal(r, vals));
835 assert(r.front == vals.front);
836 assert(r.back != r.front);
837 auto oldfront = r.front;
838 auto oldback = r.back;
841 assert(r.front != r.back);
842 assert(r.front != oldfront);
843 assert(r.back != oldback);
844 assert(ts.length == 5);
847 // find a node based on an element value
848 private inout(RBNode)* _find(Elem e) inout
850 static if (allowDuplicates)
852 inout(RBNode)* cur = _end.left;
853 inout(RBNode)* result = null;
856 if (_less(cur.value, e))
858 else if (_less(e, cur.value))
862 // want to find the left-most element
871 inout(RBNode)* cur = _end.left;
874 if (_less(cur.value, e))
876 else if (_less(e, cur.value))
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
888 * true if node was added
890 private bool _add(return scope Elem n)
893 static if (!allowDuplicates)
898 result = allocate(n);
899 (() @trusted { _end.left = _begin = result; }) ();
903 Node newParent = _end.left;
907 if (_less(n, newParent.value))
909 nxt = newParent.left;
913 // add to right of new parent
915 result = allocate(n);
916 (() @trusted { newParent.left = result; }) ();
922 static if (!allowDuplicates)
924 if (!_less(newParent.value, n))
931 nxt = newParent.right;
935 // add to right of new parent
937 result = allocate(n);
938 (() @trusted { newParent.right = result; }) ();
945 _begin = _begin.left;
947 static if (allowDuplicates)
949 result.setColor(_end);
960 result.setColor(_end);
970 * Check if any elements exist in the container. Returns `false` if at least
971 * one element exists.
973 @property bool empty() const // pure, nothrow, @safe, @nogc: are inferred
975 return _end.left is null;
979 Returns the number of elements in the container.
981 Complexity: $(BIGOH 1).
983 @property size_t length() const
989 * Duplicate this container. The resulting container contains a shallow
990 * copy of the elements.
992 * Complexity: $(BIGOH n)
994 @property RedBlackTree dup()
996 return new RedBlackTree(_end.dup(), _length);
999 static if (doUnittest) @safe pure unittest
1001 import std.algorithm.comparison : equal;
1002 auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1003 assert(ts.length == 5);
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);
1013 * Fetch a range that spans all the elements in the container.
1015 * Complexity: $(BIGOH 1)
1019 return Range(_begin, _end);
1023 ConstRange opSlice() const
1025 return ConstRange(_begin, _end);
1029 ImmutableRange opSlice() immutable
1031 return ImmutableRange(_begin, _end);
1035 * The front element in the container
1037 * Complexity: $(BIGOH 1)
1039 inout(Elem) front() inout
1041 return _begin.value;
1045 * The last element in the container
1047 * Complexity: $(BIGOH log(n))
1049 inout(Elem) back() inout
1051 return _end.prev.value;
1055 `in` operator. Check to see if the given element exists in the
1058 Complexity: $(BIGOH log(n))
1060 bool opBinaryRight(string op)(Elem e) const if (op == "in")
1062 return _find(e) !is null;
1065 static if (doUnittest) @safe pure unittest
1067 auto ts = new RedBlackTree(1, 2, 3, 4, 5);
1068 assert(cast(Elem) 3 in ts);
1069 assert(cast(Elem) 6 !in ts);
1073 * Compares two trees for equality.
1075 * Complexity: $(BIGOH n)
1077 override bool opEquals(Object rhs)
1079 import std.algorithm.comparison : equal;
1081 RedBlackTree that = cast(RedBlackTree) rhs;
1082 if (that is null) return false;
1084 // If there aren't the same number of nodes, we can't be equal.
1085 if (this._length != that._length) return false;
1087 auto thisRange = this[];
1088 auto thatRange = that[];
1089 return equal!((Elem a, Elem b) => !_less(a,b) && !_less(b,a))
1090 (thisRange, thatRange);
1093 static if (doUnittest) @system unittest
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();
1105 assert(t1 != o); // pathological case, must not crash
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
1113 override size_t toHash() nothrow @safe
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);
1123 static if (doUnittest) @system unittest
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);
1130 assert(t1.toHash() == t2.toHash);
1132 assert(t1.toHash() != t3.toHash);
1133 assert(t2.toHash() != t3.toHash);
1135 assert(t3.toHash() != t4.toHash);
1136 assert(t1.toHash() != t4.toHash);
1139 auto t5 = new RedBlackTree();
1140 auto t6 = new RedBlackTree();
1142 assert(t5.toHash() == t6.toHash());
1144 auto t7 = new RedBlackTree!string("red", "black");
1145 auto t8 = new RedBlackTree!string("white", "black");
1146 auto t9 = new RedBlackTree!string("red", "black");
1148 assert(t7.toHash() == t9.toHash());
1149 assert(t7.toHash() != t8.toHash());
1162 size_t toHash() const nothrow
1164 return typeid(x).getHash(&x) ^ 0xF0F0_F0F0;
1167 int opCmp(const MyInt that) const
1169 return (x > that.x) - (x < that.x);
1172 bool opEquals(const MyInt that) const
1174 return (this.x == that.x);
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));
1181 assert(rbt1.toHash() == rbt2.toHash());
1182 assert(rbt1.toHash() != t1.toHash());
1184 auto rbt3 = new RedBlackTree!MyInt(MyInt(4), MyInt(2), MyInt(3), MyInt(4));
1186 assert(rbt1.toHash() != rbt3.toHash());
1197 override size_t toHash() const @safe nothrow
1199 return typeid(x).getHash(&x) ^ 0xF0F0_F0F0;
1202 int opCmp(const MyInt2 that) const
1204 return (x > that.x) - (x < that.x);
1207 bool opEquals(const MyInt2 that) const
1209 return (this.x == that.x);
1213 static bool nullSafeLess(scope const MyInt2 a, scope const MyInt2 b)
1215 return a is null ? b !is null : (b !is null && a < b);
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);
1223 assert(rbt6.toHash() != rbt5.toHash());
1224 assert(rbt6.toHash() != rbt4.toHash());
1225 assert(rbt6.toHash() != rbt7.toHash());
1226 assert(rbt4.toHash() == rbt5.toHash());
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));
1232 assert(rbt8.toHash() == rbt9.toHash());
1233 assert(rbt8.toHash() != rbt10.toHash());
1237 * Removes all elements from the container.
1239 * Complexity: $(BIGOH 1)
1248 static if (doUnittest) @safe pure unittest
1250 auto ts = new RedBlackTree(1,2,3,4,5);
1251 assert(ts.length == 5);
1253 assert(ts.empty && ts.length == 0);
1257 * Insert a single element in the container. Note that this does not
1258 * invalidate any ranges currently iterating the container.
1260 * Returns: The number of elements inserted.
1262 * Complexity: $(BIGOH log(n))
1264 size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem))
1266 static if (allowDuplicates)
1278 * Insert a range of elements in the container. Note that this does not
1279 * invalidate any ranges currently iterating the container.
1281 * Returns: The number of elements inserted.
1283 * Complexity: $(BIGOH m * log(n))
1285 size_t stableInsert(Stuff)(scope Stuff stuff)
1286 if (isInputRange!Stuff &&
1287 isImplicitlyConvertible!(ElementType!Stuff, Elem))
1290 static if (allowDuplicates)
1309 alias insert = stableInsert;
1311 static if (doUnittest) @safe pure unittest
1313 auto ts = new RedBlackTree(2,1,3,4,5,2,5);
1314 static if (allowDuplicates)
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);
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]));
1325 assert(ts.arrayEqual([11,10,9,8,8,7,7,6,5,5,4,3,2,2,1]));
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);
1336 static if (less == "a < b")
1337 assert(ts.arrayEqual([1,2,3,4,5,6,7,8,9,10,11]));
1339 assert(ts.arrayEqual([11,10,9,8,7,6,5,4,3,2,1]));
1344 * Remove an element from the container and return its value.
1346 * Complexity: $(BIGOH log(n))
1353 auto result = n.value;
1354 _begin = n.remove(_end);
1360 static if (doUnittest) @safe pure unittest
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);
1367 foreach (Elem i; 1 .. 6)
1368 if (i != x) arr ~= i;
1369 assert(ts.arrayEqual(arr));
1373 * Remove the front element from the container.
1375 * Complexity: $(BIGOH log(n))
1381 _begin = _begin.remove(_end);
1387 * Remove the back element from the container.
1389 * Complexity: $(BIGOH log(n))
1395 auto lastnode = _end.prev;
1396 if (lastnode is _begin)
1397 _begin = _begin.remove(_end);
1399 lastnode.remove(_end);
1404 static if (doUnittest) @safe pure unittest
1406 auto ts = new RedBlackTree(1,2,3,4,5);
1407 assert(ts.length == 5);
1409 assert(ts.length == 4);
1411 static if (less == "a < b")
1412 assert(ts.arrayEqual([1,2,3,4]));
1414 assert(ts.arrayEqual([2,3,4,5]));
1417 assert(ts.arrayEqual([2,3,4]) && ts.length == 3);
1421 Removes the given range from the container.
1423 Returns: A range containing all of the elements that were after the
1426 Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
1429 Range remove(Range r)
1442 return Range(e, _end);
1445 static if (doUnittest) @safe pure unittest
1447 import std.algorithm.comparison : equal;
1448 auto ts = new RedBlackTree(1,2,3,4,5);
1449 assert(ts.length == 5);
1453 assert(ts.length == 5);
1454 auto r2 = ts.remove(r);
1455 assert(ts.length == 2);
1456 assert(ts.arrayEqual([1,5]));
1458 static if (less == "a < b")
1459 assert(equal(r2, [5]));
1461 assert(equal(r2, [1]));
1465 Removes the given `Take!Range` from the container
1467 Returns: A range containing all of the elements that were after the
1470 Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
1473 Range remove(Take!Range r)
1475 immutable isBegin = (r.source._begin is _begin);
1476 auto b = r.source._begin;
1488 return Range(b, _end);
1491 static if (doUnittest) @safe pure unittest
1493 import std.algorithm.comparison : equal;
1494 import std.range : take;
1495 auto ts = new RedBlackTree(1,2,3,4,5);
1498 assert(ts.length == 5);
1499 auto r2 = ts.remove(take(r, 0));
1501 static if (less == "a < b")
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]));
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]));
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.
1523 Returns: The number of elements removed.
1525 Complexity: $(BIGOH m log(n)) (where m is the number of elements to remove)
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 --------------------
1536 size_t removeKey(U...)(U elems)
1537 if (allSatisfy!(isImplicitlyConvertibleToElem, U))
1539 Elem[U.length] toRemove = [elems];
1540 return removeKey(toRemove[]);
1544 size_t removeKey(U)(scope U[] elems)
1545 if (isImplicitlyConvertible!(U, Elem))
1547 immutable lenBefore = length;
1551 auto beg = _firstGreaterEqual(e);
1552 if (beg is _end || _less(e, beg.value))
1553 // no values are equal
1555 immutable isBegin = (beg is _begin);
1556 beg = beg.remove(_end);
1562 return lenBefore - length;
1566 size_t removeKey(Stuff)(Stuff stuff)
1567 if (isInputRange!Stuff &&
1568 isImplicitlyConvertible!(ElementType!Stuff, Elem) &&
1569 !isDynamicArray!Stuff)
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));
1577 //Helper for removeKey.
1578 private template isImplicitlyConvertibleToElem(U)
1580 enum isImplicitlyConvertibleToElem = isImplicitlyConvertible!(U, Elem);
1583 static if (doUnittest) @safe pure unittest
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);
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)
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);
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);
1601 assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 7);
1602 assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 4);
1604 static if (less == "a < b")
1605 assert(equal(rbt[], [7,7,19,45]));
1607 assert(equal(rbt[], [7,5,3,2]));
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]));
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);
1618 assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 5);
1619 assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 2);
1621 static if (less == "a < b")
1622 assert(equal(rbt[], [19,45]));
1624 assert(equal(rbt[], [5,3]));
1628 // find the first node where the value is > e
1629 private inout(RBNode)* _firstGreater(Elem e) inout
1631 // can't use _find, because we cannot return null
1632 auto cur = _end.left;
1633 inout(RBNode)* result = _end;
1636 if (_less(e, cur.value))
1647 // find the first node where the value is >= e
1648 private inout(RBNode)* _firstGreaterEqual(Elem e) inout
1650 // can't use _find, because we cannot return null.
1651 auto cur = _end.left;
1652 inout(RBNode)* result = _end;
1655 if (_less(cur.value, e))
1668 * Get a range from the container with all elements that are > e according
1669 * to the less comparator
1671 * Complexity: $(BIGOH log(n))
1673 Range upperBound(Elem e)
1675 return Range(_firstGreater(e), _end);
1679 ConstRange upperBound(Elem e) const
1681 return ConstRange(_firstGreater(e), _end);
1685 ImmutableRange upperBound(Elem e) immutable
1687 return ImmutableRange(_firstGreater(e), _end);
1691 * Get a range from the container with all elements that are < e according
1692 * to the less comparator
1694 * Complexity: $(BIGOH log(n))
1696 Range lowerBound(Elem e)
1698 return Range(_begin, _firstGreaterEqual(e));
1702 ConstRange lowerBound(Elem e) const
1704 return ConstRange(_begin, _firstGreaterEqual(e));
1708 ImmutableRange lowerBound(Elem e) immutable
1710 return ImmutableRange(_begin, _firstGreaterEqual(e));
1714 * Get a range from the container with all elements that are == e according
1715 * to the less comparator
1717 * Complexity: $(BIGOH log(n))
1719 auto equalRange(this This)(Elem e)
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)
1728 return RangeType(beg, _firstGreater(e));
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);
1738 static if (doUnittest) @safe pure unittest
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);
1746 static if (less == "a < b")
1748 assert(equal(rl, [1,2]));
1749 assert(equal(ru, [4,5]));
1753 assert(equal(rl, [5,4]));
1754 assert(equal(ru, [2,1]));
1757 assert(equal(re, [3]));
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.
1767 void printTree(Node n, int indent = 0)
1769 import std.stdio : write, writeln;
1772 printTree(n.right, indent + 2);
1773 for (int i = 0; i < indent; i++)
1775 writeln(n.color == n.color.Black ? "B" : "R");
1776 printTree(n.left, indent + 2);
1780 for (int i = 0; i < indent; i++)
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.
1792 void check() @trusted
1795 // check implementation of the tree
1797 int recurse(Node n, string path)
1799 import std.stdio : writeln;
1802 if (n.parent.left !is n && n.parent.right !is n)
1803 throw new Exception("Node at path " ~ path ~ " has inconsistent pointers");
1805 static if (allowDuplicates)
1807 if (next !is _end && _less(next.value, n.value))
1808 throw new Exception("ordering invalid at path " ~ path);
1812 if (next !is _end && !_less(n.value, next.value))
1813 throw new Exception("ordering invalid at path " ~ path);
1815 if (n.color == n.color.Red)
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");
1822 int l = recurse(n.left, path ~ "L");
1823 int r = recurse(n.right, path ~ "R");
1826 writeln("bad tree at:");
1828 throw new Exception(
1829 "Node at path " ~ path ~ " has different number of black nodes on left and right paths"
1832 return l + (n.color == n.color.Black ? 1 : 0);
1837 recurse(_end.left, "");
1841 debug printTree(_end.left, 0);
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
1853 static if (is(typeof((){FormatSpec!(char) fmt; formatValue((const(char)[]) {}, ConstRange.init, fmt);})))
1855 void toString(scope void delegate(const(char)[]) sink, scope const ref FormatSpec!char fmt) const
1857 sink("RedBlackTree(");
1858 sink.formatValue(this[], fmt);
1864 * Constructor. Pass in an array of elements, or individual elements to
1865 * initialize the tree with.
1867 this(Elem[] elems...)
1870 stableInsert(elems);
1874 * Constructor. Pass in a range of elements to initialize the tree with.
1876 this(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem))
1879 stableInsert(stuff);
1888 private this(Node end, size_t length)
1891 _begin = end.leftmost;
1896 //Verify Example for removeKey.
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]));
1907 //Tests for removeKey
1910 import std.algorithm.comparison : equal;
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);
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]));
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)();
1958 // https://issues.dlang.org/show_bug.cgi?id=19626
1962 alias t = RedBlackTree!T;
1965 import std.range.primitives : isInputRange, ElementType;
1966 import std.traits : isArray, isSomeString;
1969 Convenience function for creating a `RedBlackTree!E` from a list of
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)
1978 auto redBlackTree(E)(E[] elems...)
1980 return new RedBlackTree!E(elems);
1984 auto redBlackTree(bool allowDuplicates, E)(E[] elems...)
1986 return new RedBlackTree!(E, "a < b", allowDuplicates)(elems);
1990 auto redBlackTree(alias less, E)(E[] elems...)
1991 if (is(typeof(binaryFun!less(E.init, E.init))))
1993 return new RedBlackTree!(E, less)(elems);
1997 auto redBlackTree(alias less, bool allowDuplicates, E)(E[] elems...)
1998 if (is(typeof(binaryFun!less(E.init, E.init))))
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);
2007 auto redBlackTree(Stuff)(Stuff range)
2008 if (isInputRange!Stuff && !isArray!(Stuff))
2010 return new RedBlackTree!(ElementType!Stuff)(range);
2014 auto redBlackTree(bool allowDuplicates, Stuff)(Stuff range)
2015 if (isInputRange!Stuff && !isArray!(Stuff))
2017 return new RedBlackTree!(ElementType!Stuff, "a < b", allowDuplicates)(range);
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))
2025 return new RedBlackTree!(ElementType!Stuff, less)(range);
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))
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);
2042 import std.range : iota;
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);
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));
2057 //Combinations not in examples.
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");
2065 //Range construction.
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]));
2075 // construction with arrays
2078 import std.algorithm.comparison : equal;
2080 auto rbt = redBlackTree!"a > b"([0, 1, 2, 3, 4]);
2081 assert(equal(rbt[], [4, 3, 2, 1, 0]));
2083 auto rbt2 = redBlackTree!"a > b"(["a", "b"]);
2084 assert(equal(rbt2[], ["b", "a"]));
2086 auto rbt3 = redBlackTree!"a > b"([1, 2]);
2087 assert(equal(rbt3[], [2, 1]));
2089 auto rbt4 = redBlackTree([0, 1, 7, 5]);
2090 assert(equal(rbt4[], [0, 1, 5, 7]));
2092 auto rbt5 = redBlackTree(["hello", "world"]);
2093 assert(equal(rbt5[], ["hello", "world"]));
2095 auto rbt6 = redBlackTree!true([0, 1, 5, 7, 5]);
2096 assert(equal(rbt6[], [0, 1, 5, 5, 7]));
2098 auto rbt7 = redBlackTree!"a > b"([0, 1, 5, 7]);
2099 assert(equal(rbt7[], [7, 5, 1, 0]));
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]));
2105 // convenience wrapper range construction
2108 import std.algorithm.comparison : equal;
2109 import std.range : chain, iota;
2111 auto rbt = redBlackTree(iota(3));
2112 assert(equal(rbt[], [0, 1, 2]));
2114 auto rbt2 = redBlackTree!"a > b"(iota(2));
2115 assert(equal(rbt2[], [1, 0]));
2117 auto rbt3 = redBlackTree(chain([0, 1], [7, 5]));
2118 assert(equal(rbt3[], [0, 1, 5, 7]));
2120 auto rbt4 = redBlackTree(chain(["hello"], ["world"]));
2121 assert(equal(rbt4[], ["hello", "world"]));
2123 auto rbt5 = redBlackTree!true(chain([0, 1], [5, 7, 5]));
2124 assert(equal(rbt5[], [0, 1, 5, 5, 7]));
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]));
2132 import std.array : array;
2134 auto rt1 = redBlackTree(5, 4, 3, 2, 1);
2135 assert(rt1.length == 5);
2136 assert(array(rt1[]) == [1, 2, 3, 4, 5]);
2138 auto rt2 = redBlackTree!"a > b"(1.1, 2.1);
2139 assert(rt2.length == 2);
2140 assert(array(rt2[]) == [2.1, 1.1]);
2142 auto rt3 = redBlackTree!true(5, 5, 4);
2143 assert(rt3.length == 3);
2144 assert(array(rt3[]) == [4, 5, 5]);
2146 auto rt4 = redBlackTree!string("hello", "hello");
2147 assert(rt4.length == 1);
2148 assert(array(rt4[]) == ["hello"]);
2153 import std.conv : to;
2155 auto rt1 = redBlackTree!string();
2156 assert(rt1.to!string == "RedBlackTree([])");
2158 auto rt2 = redBlackTree!string("hello");
2159 assert(rt2.to!string == "RedBlackTree([\"hello\"])");
2161 auto rt3 = redBlackTree!string("hello", "world", "!");
2162 assert(rt3.to!string == "RedBlackTree([\"!\", \"hello\", \"world\"])");
2164 // type deduction can be done automatically
2165 auto rt4 = redBlackTree(["hello"]);
2166 assert(rt4.to!string == "RedBlackTree([\"hello\"])");
2172 const rt1 = redBlackTree(5,4,3,2,1);
2173 void allQualifiers() pure nothrow @safe @nogc {
2175 assert(rt1.length == 5);
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]));
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)));
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]));
2201 // https://issues.dlang.org/show_bug.cgi?id=15941
2205 RedBlackTree!(C, "cast(void*)a < cast(void*) b") tree;
2208 // const/immutable elements (https://issues.dlang.org/show_bug.cgi?id=17519)
2211 RedBlackTree!(immutable int) t1;
2212 RedBlackTree!(const int) t2;
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);
2222 // make sure the comparator can be a delegate
2225 import std.algorithm.comparison : equal;
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]));