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