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