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