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