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