1 /** 2 This module implements an associative array. 3 @nogc associative array, replacement for std::map and std::set. 4 Implementation of Red Black Tree from Phobos. 5 6 Copyright: Guillaume Piolat 2015-2016. 7 Copyright: Copyright (C) 2008- by Steven Schveighoffer. Other code 8 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. 9 License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 10 Authors: Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu), Guillaume Piolat 11 */ 12 module dplug.core.map; 13 14 import std.functional: binaryFun; 15 16 import dplug.core.nogc; 17 18 nothrow: 19 @nogc: 20 21 /// Creates a new empty `Map`. 22 Map!(K, V, less, allowDuplicates) makeMap(K, V, alias less = "a < b", bool allowDuplicates = false)() 23 { 24 return Map!(K, V, less, allowDuplicates)(42); 25 } 26 27 /// Tree-map, designed to replace std::map usage. 28 /// The API should looks closely like the builtin associative arrays. 29 /// O(lg(n)) insertion, removal, and search time. 30 /// `Map` is designed to operate even without initialization through `makeMap`. 31 struct Map(K, V, alias less = "a < b", bool allowDuplicates = false) 32 { 33 public: 34 nothrow: 35 @nogc: 36 37 this(int dummy) 38 { 39 lazyInitialize(); 40 } 41 42 @disable this(this); 43 44 ~this() 45 { 46 if (_rbt !is null) 47 { 48 destroyFree(_rbt); 49 _rbt = null; 50 } 51 } 52 53 /// Insert an element in the container, if the container doesn't already contain 54 /// an element with equivalent key. 55 /// Returns: `true` if the insertion took place. 56 bool insert(K key, V value) 57 { 58 lazyInitialize(); 59 60 auto kv = KeyValue(key, value); 61 assert(_rbt); 62 return _rbt.insert(kv) != 0; 63 } 64 65 /// Removes an element from the container. 66 /// Returns: `true` if the removal took place. 67 bool remove(K key) 68 { 69 if (!isInitialized) 70 return false; 71 72 auto kv = KeyValue(key, V.init); 73 return _rbt.removeKey(kv) != 0; 74 } 75 76 /// Removes all elements from the map. 77 void clearContents() 78 { 79 if (!isInitialized) 80 return; 81 82 while(_rbt.length > 0) 83 _rbt.removeBack(); 84 } 85 86 /// Returns: A pointer to the value corresponding to this key, or null if not available. 87 /// Live builtin associative arrays. 88 inout(V)* opBinaryRight(string op)(K key) inout if (op == "in") 89 { 90 if (!isInitialized) 91 return null; 92 93 auto kv = KeyValue(key, V.init); 94 auto node = _rbt._find(kv); 95 if (node is null) 96 return null; 97 else 98 return &node.value.value; 99 } 100 101 /// Returns: A reference to the value corresponding to this key. 102 ref inout(V) opIndex(K key) inout 103 { 104 inout(V)* p = key in this; 105 return *p; 106 } 107 108 /// Updates a value associated with a key, creates it if necessary. 109 void opIndexAssign(V value, K key) 110 { 111 // PERF: this could be faster 112 V* p = key in this; 113 if (p is null) 114 insert(key, value); 115 else 116 *p = value; 117 } 118 119 /// Returns: `true` if this key is contained. 120 bool contains(K key) const 121 { 122 if (!isInitialized) 123 return false; 124 auto kv = KeyValue(key, V.init); 125 return (kv in _rbt); 126 } 127 128 /// Returns: Number of elements in the map. 129 size_t length() const 130 { 131 if (!isInitialized) 132 return 0; 133 134 return _rbt.length(); 135 } 136 137 /// Returns: `ttue` is the map has no element. 138 bool empty() const 139 { 140 if (!isInitialized) 141 return true; 142 return _rbt.length() == 0; 143 } 144 145 // Iterate by value only 146 147 /// Fetch a forward range on all values. 148 Range!(MapRangeType.value) byValue() 149 { 150 if (!isInitialized) 151 return Range!(MapRangeType.value).init; 152 153 return Range!(MapRangeType.value)(_rbt[]); 154 } 155 156 /// ditto 157 ConstRange!(MapRangeType.value) byValue() const 158 { 159 if (!isInitialized) 160 return ConstRange!(MapRangeType.value).init; 161 162 return ConstRange!(MapRangeType.value)(_rbt[]); 163 } 164 165 /// ditto 166 ImmutableRange!(MapRangeType.value) byValue() immutable 167 { 168 if (!isInitialized) 169 return ImmutableRange!(MapRangeType.value).init; 170 171 return ImmutableRange!(MapRangeType.value)(_rbt[]); 172 } 173 174 // default opSlice is like byValue for builtin associative arrays 175 alias opSlice = byValue; 176 177 // Iterate by key only 178 179 /// Fetch a forward range on all keys. 180 Range!(MapRangeType.key) byKey() 181 { 182 if (!isInitialized) 183 return Range!(MapRangeType.key).init; 184 185 return Range!(MapRangeType.key)(_rbt[]); 186 } 187 188 /// ditto 189 ConstRange!(MapRangeType.key) byKey() const 190 { 191 if (!isInitialized) 192 return ConstRange!(MapRangeType.key).init; 193 194 return ConstRange!(MapRangeType.key)(_rbt[]); 195 } 196 197 /// ditto 198 ImmutableRange!(MapRangeType.key) byKey() immutable 199 { 200 if (!isInitialized) 201 return ImmutableRange!(MapRangeType.key).init; 202 203 return ImmutableRange!(MapRangeType.key)(_rbt[]); 204 } 205 206 // Iterate by key-value 207 208 /// Fetch a forward range on all keys. 209 Range!(MapRangeType.keyValue) byKeyValue() 210 { 211 if (!isInitialized) 212 return Range!(MapRangeType.keyValue).init; 213 214 return Range!(MapRangeType.keyValue)(_rbt[]); 215 } 216 217 /// ditto 218 ConstRange!(MapRangeType.keyValue) byKeyValue() const 219 { 220 if (!isInitialized) 221 return ConstRange!(MapRangeType.keyValue).init; 222 223 return ConstRange!(MapRangeType.keyValue)(_rbt[]); 224 } 225 226 /// ditto 227 ImmutableRange!(MapRangeType.keyValue) byKeyValue() immutable 228 { 229 if (!isInitialized) 230 return ImmutableRange!(MapRangeType.keyValue).init; 231 232 return ImmutableRange!(MapRangeType.keyValue)(_rbt[]); 233 } 234 235 // Iterate by single value (return a range where all elements have equal key) 236 237 /// Fetch a forward range on all elements with given key. 238 Range!(MapRangeType.value) byGivenKey(K key) 239 { 240 if (!isInitialized) 241 return Range!(MapRangeType.value).init; 242 243 auto kv = KeyValue(key, V.init); 244 return Range!(MapRangeType.value)(_rbt.range(kv)); 245 } 246 247 /// ditto 248 ConstRange!(MapRangeType.value) byGivenKey(K key) const 249 { 250 if (!isInitialized) 251 return ConstRange!(MapRangeType.value).init; 252 253 auto kv = KeyValue(key, V.init); 254 return ConstRange!(MapRangeType.value)(_rbt.range(kv)); 255 } 256 257 /// ditto 258 ImmutableRange!(MapRangeType.value) byGivenKey(K key) immutable 259 { 260 if (!isInitialized) 261 return ImmutableRange!(MapRangeType.value).init; 262 263 auto kv = KeyValue(key, V.init); 264 return ImmutableRange!(MapRangeType.value)(_rbt.range(kv)); 265 } 266 267 268 private: 269 270 alias Range(MapRangeType type) = MapRange!(RBNode!KeyValue*, type); 271 alias ConstRange(MapRangeType type) = MapRange!(const(RBNode!KeyValue)*, type); /// Ditto 272 alias ImmutableRange(MapRangeType type) = MapRange!(immutable(RBNode!KeyValue)*, type); /// Ditto 273 274 alias _less = binaryFun!less; 275 static bool lessForAggregate(const(KeyValue) a, const(KeyValue) b) 276 { 277 return _less(a.key, b.key); 278 } 279 280 alias InternalTree = RedBlackTree!(KeyValue, lessForAggregate, allowDuplicates); 281 282 // we need a composite value to reuse Phobos RedBlackTree 283 static struct KeyValue 284 { 285 nothrow: 286 @nogc: 287 K key; 288 V value; 289 } 290 291 InternalTree _rbt; 292 293 bool isInitialized() const 294 { 295 return _rbt !is null; 296 } 297 298 void lazyInitialize() 299 { 300 if (_rbt is null) 301 { 302 _rbt = mallocNew!InternalTree(); 303 } 304 } 305 } 306 307 unittest 308 { 309 // It should be possible to use most function of an uninitialized Map 310 // All except functions returning a range will work. 311 Map!(int, string) m; 312 313 assert(m.length == 0); 314 assert(m.empty); 315 assert(!m.contains(7)); 316 317 auto range = m.byKey(); 318 assert(range.empty); 319 foreach(e; range) 320 { 321 } 322 323 m[1] = "fun"; 324 } 325 326 unittest 327 { 328 void test(bool removeKeys) nothrow @nogc 329 { 330 { 331 auto test = makeMap!(int, string); 332 int N = 100; 333 foreach(i; 0..N) 334 { 335 int key = (i * 69069) % 65536; 336 test.insert(key, "this is a test"); 337 } 338 foreach(i; 0..N) 339 { 340 int key = (i * 69069) % 65536; 341 assert(test.contains(key)); 342 } 343 344 if (removeKeys) 345 { 346 foreach(i; 0..N) 347 { 348 int key = (i * 69069) % 65536; 349 test.remove(key); 350 } 351 } 352 foreach(i; 0..N) 353 { 354 int key = (i * 69069) % 65536; 355 assert(removeKeys ^ test.contains(key)); // either keys are here or removed 356 } 357 } 358 } 359 test(true); 360 test(false); 361 } 362 363 unittest 364 { 365 Map!(string, int) aa = makeMap!(string, int); // Associative array of ints that are 366 // indexed by string keys. 367 // The KeyType is string. 368 aa["hello"] = 3; // set value associated with key "hello" to 3 369 int value = aa["hello"]; // lookup value from a key 370 assert(value == 3); 371 372 int* p; 373 374 p = ("hello" in aa); 375 if (p !is null) 376 { 377 *p = 4; // update value associated with key 378 assert(aa["hello"] == 4); 379 } 380 381 aa.remove("hello"); 382 } 383 384 /// Creates a new empty `Set`. 385 Set!(K, less) makeSet(K, alias less = "a < b", bool allowDuplicates = false)() 386 { 387 return Set!(K, less, allowDuplicates)(42); 388 } 389 390 391 /// Set, designed to replace std::set usage. 392 /// O(lg(n)) insertion, removal, and search time. 393 /// `Set` is designed to operate even without initialization through `makeSet`. 394 struct Set(K, alias less = "a < b", bool allowDuplicates = false) 395 { 396 public: 397 nothrow: 398 @nogc: 399 400 this(int dummy) 401 { 402 lazyInitialize(); 403 } 404 405 @disable this(this); 406 407 ~this() 408 { 409 if (isInitialized) 410 { 411 destroyFree(_rbt); 412 _rbt = null; 413 } 414 } 415 416 /// Insert an element in the container. 417 /// If allowDuplicates is false, this can fail and return `false` 418 /// if the already contains an element with equivalent key. 419 /// Returns: `true` if the insertion took place. 420 bool insert(K key) 421 { 422 lazyInitialize(); 423 return _rbt.insert(key) != 0; 424 } 425 426 /// Removes an element from the container. 427 /// Returns: `true` if the removal took place. 428 bool remove(K key) 429 { 430 if (!isInitialized) 431 return false; 432 return _rbt.removeKey(key) != 0; 433 } 434 435 /// Removes all elements from the set. 436 void clearContents() 437 { 438 if (!isInitialized) 439 return; 440 while(_rbt.length > 0) 441 _rbt.removeBack(); 442 } 443 444 /// Returns: `true` if the element is present. 445 bool opBinaryRight(string op)(K key) inout if (op == "in") 446 { 447 if (!isInitialized) 448 return false; 449 return key in _rbt; 450 } 451 452 /// Returns: `true` if the element is present. 453 bool opIndex(K key) const 454 { 455 if (!isInitialized) 456 return false; 457 return key in _rbt; 458 } 459 460 /// Returns: `true` if the element is present. 461 bool contains(K key) const 462 { 463 if (!isInitialized) 464 return false; 465 return key in _rbt; 466 } 467 468 /// Fetch a range that spans all the elements in the container. 469 auto opSlice() inout 470 { 471 if (!isInitialized) 472 return nullRange(); 473 return _rbt[]; 474 } 475 476 /// Returns: Number of elements in the set. 477 size_t length() const 478 { 479 if (!isInitialized) 480 return 0; 481 return _rbt.length(); 482 } 483 484 /// Returns: `ttue` is the set has no element. 485 bool empty() const 486 { 487 if (!isInitialized) 488 return true; 489 return _rbt.length() == 0; 490 } 491 492 private: 493 alias InternalTree = RedBlackTree!(K, less, allowDuplicates); 494 InternalTree _rbt; 495 496 bool isInitialized() const 497 { 498 return _rbt !is null; 499 } 500 501 void lazyInitialize() 502 { 503 if (_rbt is null) 504 { 505 _rbt = mallocNew!InternalTree(); 506 } 507 } 508 509 /** 510 * Return a range without any items. 511 */ 512 auto nullRange() 513 { 514 return InternalTree.Range.init; 515 } 516 517 /// Ditto 518 auto nullRange() const 519 { 520 return InternalTree.ConstRange.init; 521 } 522 523 /// Ditto 524 auto nullRange() immutable 525 { 526 return InternalTree.ImmutableRange.init; 527 } 528 } 529 530 unittest 531 { 532 // It should be possible to use most function of an uninitialized Set 533 // All except functions returning a range will work. 534 Set!(string) set; 535 536 assert(set.length == 0); 537 assert(set.empty); 538 set.clearContents(); 539 assert(!set.contains("toto")); 540 541 auto range = set[]; 542 assert(range.empty); 543 foreach(e; range) 544 { 545 } 546 547 // Finally create the internal state 548 set.insert("titi"); 549 assert(set.contains("titi")); 550 } 551 552 553 unittest 554 { 555 { 556 Set!(string) keywords = makeSet!string; 557 558 assert(keywords.insert("public")); 559 assert(keywords.insert("private")); 560 assert(!keywords.insert("private")); 561 562 assert(keywords.remove("public")); 563 assert(!keywords.remove("non-existent")); 564 565 assert(keywords.contains("private")); 566 assert(!keywords.contains("public")); 567 } 568 569 } 570 571 private: 572 573 574 /* 575 * Implementation for a Red Black node for use in a Red Black Tree (see below) 576 * 577 * this implementation assumes we have a marker Node that is the parent of the 578 * root Node. This marker Node is not a valid Node, but marks the end of the 579 * collection. The root is the left child of the marker Node, so it is always 580 * last in the collection. The marker Node is passed in to the setColor 581 * function, and the Node which has this Node as its parent is assumed to be 582 * the root Node. 583 * 584 * A Red Black tree should have O(lg(n)) insertion, removal, and search time. 585 */ 586 struct RBNode(V) 587 { 588 nothrow: 589 @nogc: 590 /* 591 * Convenience alias 592 */ 593 alias Node = RBNode*; 594 595 private Node _left; 596 private Node _right; 597 private Node _parent; 598 599 /** 600 * The value held by this node 601 */ 602 V value; 603 604 /** 605 * Enumeration determining what color the node is. Null nodes are assumed 606 * to be black. 607 */ 608 enum Color : byte 609 { 610 Red, 611 Black 612 } 613 614 /** 615 * The color of the node. 616 */ 617 Color color; 618 619 /** 620 * Get the left child 621 */ 622 @property inout(RBNode)* left() inout 623 { 624 return _left; 625 } 626 627 /** 628 * Get the right child 629 */ 630 @property inout(RBNode)* right() inout 631 { 632 return _right; 633 } 634 635 /** 636 * Get the parent 637 */ 638 @property inout(RBNode)* parent() inout 639 { 640 return _parent; 641 } 642 643 void deallocate() 644 { 645 //import core.stdc.stdio; 646 //printf("deallocate %p\n", &this); 647 destroyFree(&this); 648 } 649 650 /** 651 * Set the left child. Also updates the new child's parent node. This 652 * does not update the previous child. 653 * 654 * Returns newNode 655 */ 656 @property Node left(Node newNode) 657 { 658 _left = newNode; 659 if (newNode !is null) 660 newNode._parent = &this; 661 return newNode; 662 } 663 664 /** 665 * Set the right child. Also updates the new child's parent node. This 666 * does not update the previous child. 667 * 668 * Returns newNode 669 */ 670 @property Node right(Node newNode) 671 { 672 _right = newNode; 673 if (newNode !is null) 674 newNode._parent = &this; 675 return newNode; 676 } 677 678 // assume _left is not null 679 // 680 // performs rotate-right operation, where this is T, _right is R, _left is 681 // L, _parent is P: 682 // 683 // P P 684 // | -> | 685 // T L 686 // / \ / \ 687 // L R a T 688 // / \ / \ 689 // a b b R 690 // 691 /** 692 * Rotate right. This performs the following operations: 693 * - The left child becomes the parent of this node. 694 * - This node becomes the new parent's right child. 695 * - The old right child of the new parent becomes the left child of this 696 * node. 697 */ 698 Node rotateR() 699 { 700 assert(_left !is null); 701 702 // sets _left._parent also 703 if (isLeftNode) 704 parent.left = _left; 705 else 706 parent.right = _left; 707 Node tmp = _left._right; 708 709 // sets _parent also 710 _left.right = &this; 711 712 // sets tmp._parent also 713 left = tmp; 714 715 return &this; 716 } 717 718 // assumes _right is non null 719 // 720 // performs rotate-left operation, where this is T, _right is R, _left is 721 // L, _parent is P: 722 // 723 // P P 724 // | -> | 725 // T R 726 // / \ / \ 727 // L R T b 728 // / \ / \ 729 // a b L a 730 // 731 /** 732 * Rotate left. This performs the following operations: 733 * - The right child becomes the parent of this node. 734 * - This node becomes the new parent's left child. 735 * - The old left child of the new parent becomes the right child of this 736 * node. 737 */ 738 Node rotateL() 739 { 740 assert(_right !is null); 741 742 // sets _right._parent also 743 if (isLeftNode) 744 parent.left = _right; 745 else 746 parent.right = _right; 747 Node tmp = _right._left; 748 749 // sets _parent also 750 _right.left = &this; 751 752 // sets tmp._parent also 753 right = tmp; 754 return &this; 755 } 756 757 758 /** 759 * Returns true if this node is a left child. 760 * 761 * Note that this should always return a value because the root has a 762 * parent which is the marker node. 763 */ 764 @property bool isLeftNode() const 765 { 766 assert(_parent !is null); 767 return _parent._left is &this; 768 } 769 770 /** 771 * Set the color of the node after it is inserted. This performs an 772 * update to the whole tree, possibly rotating nodes to keep the Red-Black 773 * properties correct. This is an O(lg(n)) operation, where n is the 774 * number of nodes in the tree. 775 * 776 * end is the marker node, which is the parent of the topmost valid node. 777 */ 778 void setColor(Node end) 779 { 780 // test against the marker node 781 if (_parent !is end) 782 { 783 if (_parent.color == Color.Red) 784 { 785 Node cur = &this; 786 while (true) 787 { 788 // because root is always black, _parent._parent always exists 789 if (cur._parent.isLeftNode) 790 { 791 // parent is left node, y is 'uncle', could be null 792 Node y = cur._parent._parent._right; 793 if (y !is null && y.color == Color.Red) 794 { 795 cur._parent.color = Color.Black; 796 y.color = Color.Black; 797 cur = cur._parent._parent; 798 if (cur._parent is end) 799 { 800 // root node 801 cur.color = Color.Black; 802 break; 803 } 804 else 805 { 806 // not root node 807 cur.color = Color.Red; 808 if (cur._parent.color == Color.Black) 809 // satisfied, exit the loop 810 break; 811 } 812 } 813 else 814 { 815 if (!cur.isLeftNode) 816 cur = cur._parent.rotateL(); 817 cur._parent.color = Color.Black; 818 cur = cur._parent._parent.rotateR(); 819 cur.color = Color.Red; 820 // tree should be satisfied now 821 break; 822 } 823 } 824 else 825 { 826 // parent is right node, y is 'uncle' 827 Node y = cur._parent._parent._left; 828 if (y !is null && y.color == Color.Red) 829 { 830 cur._parent.color = Color.Black; 831 y.color = Color.Black; 832 cur = cur._parent._parent; 833 if (cur._parent is end) 834 { 835 // root node 836 cur.color = Color.Black; 837 break; 838 } 839 else 840 { 841 // not root node 842 cur.color = Color.Red; 843 if (cur._parent.color == Color.Black) 844 // satisfied, exit the loop 845 break; 846 } 847 } 848 else 849 { 850 if (cur.isLeftNode) 851 cur = cur._parent.rotateR(); 852 cur._parent.color = Color.Black; 853 cur = cur._parent._parent.rotateL(); 854 cur.color = Color.Red; 855 // tree should be satisfied now 856 break; 857 } 858 } 859 } 860 861 } 862 } 863 else 864 { 865 // 866 // this is the root node, color it black 867 // 868 color = Color.Black; 869 } 870 } 871 872 /** 873 * Remove this node from the tree. The 'end' node is used as the marker 874 * which is root's parent. Note that this cannot be null! 875 * 876 * Returns the next highest valued node in the tree after this one, or end 877 * if this was the highest-valued node. 878 */ 879 Node remove(Node end) 880 { 881 // 882 // remove this node from the tree, fixing the color if necessary. 883 // 884 Node x; 885 Node ret = next; 886 887 // if this node has 2 children 888 if (_left !is null && _right !is null) 889 { 890 // 891 // normally, we can just swap this node's and y's value, but 892 // because an iterator could be pointing to y and we don't want to 893 // disturb it, we swap this node and y's structure instead. This 894 // can also be a benefit if the value of the tree is a large 895 // struct, which takes a long time to copy. 896 // 897 Node yp, yl, yr; 898 Node y = ret; // y = next 899 yp = y._parent; 900 yl = y._left; 901 yr = y._right; 902 auto yc = y.color; 903 auto isyleft = y.isLeftNode; 904 905 // 906 // replace y's structure with structure of this node. 907 // 908 if (isLeftNode) 909 _parent.left = y; 910 else 911 _parent.right = y; 912 // 913 // need special case so y doesn't point back to itself 914 // 915 y.left = _left; 916 if (_right is y) 917 y.right = &this; 918 else 919 y.right = _right; 920 y.color = color; 921 922 // 923 // replace this node's structure with structure of y. 924 // 925 left = yl; 926 right = yr; 927 if (_parent !is y) 928 { 929 if (isyleft) 930 yp.left = &this; 931 else 932 yp.right = &this; 933 } 934 color = yc; 935 } 936 937 // if this has less than 2 children, remove it 938 if (_left !is null) 939 x = _left; 940 else 941 x = _right; 942 943 bool deferedUnlink = false; 944 if (x is null) 945 { 946 // pretend this is a null node, defer unlinking the node 947 x = &this; 948 deferedUnlink = true; 949 } 950 else if (isLeftNode) 951 _parent.left = x; 952 else 953 _parent.right = x; 954 955 // if the color of this is black, then it needs to be fixed 956 if (color == color.Black) 957 { 958 // need to recolor the tree. 959 while (x._parent !is end && x.color == Node.Color.Black) 960 { 961 if (x.isLeftNode) 962 { 963 // left node 964 Node w = x._parent._right; 965 if (w.color == Node.Color.Red) 966 { 967 w.color = Node.Color.Black; 968 x._parent.color = Node.Color.Red; 969 x._parent.rotateL(); 970 w = x._parent._right; 971 } 972 Node wl = w.left; 973 Node wr = w.right; 974 if ((wl is null || wl.color == Node.Color.Black) && 975 (wr is null || wr.color == Node.Color.Black)) 976 { 977 w.color = Node.Color.Red; 978 x = x._parent; 979 } 980 else 981 { 982 if (wr is null || wr.color == Node.Color.Black) 983 { 984 // wl cannot be null here 985 wl.color = Node.Color.Black; 986 w.color = Node.Color.Red; 987 w.rotateR(); 988 w = x._parent._right; 989 } 990 991 w.color = x._parent.color; 992 x._parent.color = Node.Color.Black; 993 w._right.color = Node.Color.Black; 994 x._parent.rotateL(); 995 x = end.left; // x = root 996 } 997 } 998 else 999 { 1000 // right node 1001 Node w = x._parent._left; 1002 if (w.color == Node.Color.Red) 1003 { 1004 w.color = Node.Color.Black; 1005 x._parent.color = Node.Color.Red; 1006 x._parent.rotateR(); 1007 w = x._parent._left; 1008 } 1009 Node wl = w.left; 1010 Node wr = w.right; 1011 if ((wl is null || wl.color == Node.Color.Black) && 1012 (wr is null || wr.color == Node.Color.Black)) 1013 { 1014 w.color = Node.Color.Red; 1015 x = x._parent; 1016 } 1017 else 1018 { 1019 if (wl is null || wl.color == Node.Color.Black) 1020 { 1021 // wr cannot be null here 1022 wr.color = Node.Color.Black; 1023 w.color = Node.Color.Red; 1024 w.rotateL(); 1025 w = x._parent._left; 1026 } 1027 1028 w.color = x._parent.color; 1029 x._parent.color = Node.Color.Black; 1030 w._left.color = Node.Color.Black; 1031 x._parent.rotateR(); 1032 x = end.left; // x = root 1033 } 1034 } 1035 } 1036 x.color = Node.Color.Black; 1037 } 1038 1039 if (deferedUnlink) 1040 { 1041 // 1042 // unlink this node from the tree 1043 // 1044 if (isLeftNode) 1045 _parent.left = null; 1046 else 1047 _parent.right = null; 1048 } 1049 1050 // clean references to help GC - Bugzilla 12915 1051 _left = _right = _parent = null; 1052 1053 return ret; 1054 } 1055 1056 /** 1057 * Return the leftmost descendant of this node. 1058 */ 1059 @property inout(RBNode)* leftmost() inout 1060 { 1061 inout(RBNode)* result = &this; 1062 while (result._left !is null) 1063 result = result._left; 1064 return result; 1065 } 1066 1067 /** 1068 * Return the rightmost descendant of this node 1069 */ 1070 @property inout(RBNode)* rightmost() inout 1071 { 1072 inout(RBNode)* result = &this; 1073 while (result._right !is null) 1074 result = result._right; 1075 return result; 1076 } 1077 1078 /** 1079 * Returns the next valued node in the tree. 1080 * 1081 * You should never call this on the marker node, as it is assumed that 1082 * there is a valid next node. 1083 */ 1084 @property inout(RBNode)* next() inout 1085 { 1086 inout(RBNode)* n = &this; 1087 if (n.right is null) 1088 { 1089 while (!n.isLeftNode) 1090 n = n._parent; 1091 return n._parent; 1092 } 1093 else 1094 return n.right.leftmost; 1095 } 1096 1097 /** 1098 * Returns the previous valued node in the tree. 1099 * 1100 * You should never call this on the leftmost node of the tree as it is 1101 * assumed that there is a valid previous node. 1102 */ 1103 @property inout(RBNode)* prev() inout 1104 { 1105 inout(RBNode)* n = &this; 1106 if (n.left is null) 1107 { 1108 while (n.isLeftNode) 1109 n = n._parent; 1110 return n._parent; 1111 } 1112 else 1113 return n.left.rightmost; 1114 } 1115 } 1116 1117 // Range type for RedBlackTree 1118 private struct RBRange(N) 1119 { 1120 nothrow: 1121 @nogc: 1122 alias Node = N; 1123 alias Elem = typeof(Node.value); 1124 1125 private Node _begin = null; 1126 private Node _end = null; 1127 1128 private this(Node b, Node e) 1129 { 1130 _begin = b; 1131 _end = e; 1132 } 1133 1134 /** 1135 * Returns $(D true) if the range is _empty 1136 */ 1137 @property bool empty() const 1138 { 1139 return _begin is _end; 1140 } 1141 1142 /** 1143 * Returns the first element in the range 1144 */ 1145 @property Elem front() 1146 { 1147 return _begin.value; 1148 } 1149 1150 /** 1151 * Returns the last element in the range 1152 */ 1153 @property Elem back() 1154 { 1155 return _end.prev.value; 1156 } 1157 1158 /** 1159 * pop the front element from the range 1160 * 1161 * complexity: amortized $(BIGOH 1) 1162 */ 1163 void popFront() 1164 { 1165 _begin = _begin.next; 1166 } 1167 1168 /** 1169 * pop the back element from the range 1170 * 1171 * complexity: amortized $(BIGOH 1) 1172 */ 1173 void popBack() 1174 { 1175 _end = _end.prev; 1176 } 1177 1178 /** 1179 * Trivial _save implementation, needed for $(D isForwardRange). 1180 */ 1181 @property RBRange save() 1182 { 1183 return this; 1184 } 1185 } 1186 1187 unittest 1188 { 1189 // RBRange.init is supposed to be an empty valid range 1190 RBRange!(RBNode!int*) range; 1191 assert(range.empty); 1192 foreach(e; range) 1193 { 1194 } 1195 } 1196 1197 private enum MapRangeType 1198 { 1199 key, 1200 value, 1201 keyValue 1202 } 1203 1204 // Range type for Dplug's Map, can iterate on keys or values 1205 private struct MapRange(N, MapRangeType type) 1206 { 1207 nothrow: 1208 @nogc: 1209 1210 alias Node = N; 1211 alias InnerRange = RBRange!N; 1212 1213 static if (type == MapRangeType.key) 1214 alias Elem = typeof(Node.value.key); 1215 1216 else static if (type == MapRangeType.value) 1217 alias Elem = typeof(Node.value.value); 1218 1219 else static if (type == MapRangeType.keyValue) 1220 alias Elem = typeof(Node.value); 1221 1222 static Elem get(InnerRange.Elem pair) 1223 { 1224 static if (type == MapRangeType.key) 1225 return pair.key; 1226 1227 else static if (type == MapRangeType.value) 1228 return pair.value; 1229 1230 else static if (type == MapRangeType.keyValue) 1231 return pair; 1232 } 1233 1234 // A Map range is just a wrapper around a RBRange 1235 private InnerRange _inner; 1236 1237 private this(InnerRange inner) 1238 { 1239 _inner = inner; 1240 } 1241 1242 /** 1243 * Returns $(D true) if the range is _empty 1244 */ 1245 @property bool empty() const 1246 { 1247 return _inner.empty; 1248 } 1249 1250 /** 1251 * Returns the first element in the range 1252 */ 1253 @property Elem front() 1254 { 1255 return get(_inner.front); 1256 } 1257 1258 /** 1259 * Returns the last element in the range 1260 */ 1261 @property Elem back() 1262 { 1263 return get(_inner.back()); 1264 } 1265 1266 /** 1267 * pop the front element from the range 1268 * 1269 * complexity: amortized $(BIGOH 1) 1270 */ 1271 void popFront() 1272 { 1273 _inner.popFront(); 1274 } 1275 1276 /** 1277 * pop the back element from the range 1278 * 1279 * complexity: amortized $(BIGOH 1) 1280 */ 1281 void popBack() 1282 { 1283 _inner.popBack(); 1284 } 1285 1286 /** 1287 * Trivial _save implementation, needed for $(D isForwardRange). 1288 */ 1289 @property MapRange save() 1290 { 1291 return this; 1292 } 1293 } 1294 1295 /** 1296 * Implementation of a $(LINK2 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree, 1297 * red-black tree) container. 1298 * 1299 * All inserts, removes, searches, and any function in general has complexity 1300 * of $(BIGOH lg(n)). 1301 * 1302 * To use a different comparison than $(D "a < b"), pass a different operator string 1303 * that can be used by $(REF binaryFun, std,functional), or pass in a 1304 * function, delegate, functor, or any type where $(D less(a, b)) results in a $(D bool) 1305 * value. 1306 * 1307 * Note that less should produce a strict ordering. That is, for two unequal 1308 * elements $(D a) and $(D b), $(D less(a, b) == !less(b, a)). $(D less(a, a)) should 1309 * always equal $(D false). 1310 * 1311 * If $(D allowDuplicates) is set to $(D true), then inserting the same element more than 1312 * once continues to add more elements. If it is $(D false), duplicate elements are 1313 * ignored on insertion. If duplicates are allowed, then new elements are 1314 * inserted after all existing duplicate elements. 1315 */ 1316 1317 final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) 1318 { 1319 nothrow: 1320 @nogc: 1321 /** 1322 * Element type for the tree 1323 */ 1324 alias Elem = T; 1325 1326 alias _less = binaryFun!less; 1327 1328 // used for convenience 1329 private alias RBNode = .RBNode!Elem; 1330 private alias Node = RBNode.Node; 1331 1332 private Node _end; 1333 private Node _begin; 1334 private size_t _length; 1335 1336 private void _setup() 1337 { 1338 assert(!_end); //Make sure that _setup isn't run more than once. 1339 _begin = _end = allocate(); 1340 } 1341 1342 static private Node allocate() 1343 { 1344 Node p = mallocNew!RBNode; 1345 //import core.stdc.stdio; 1346 //printf("allocate %p\n", p); 1347 return p; 1348 } 1349 1350 static private Node allocate(Elem v) 1351 { 1352 auto result = allocate(); 1353 result.value = v; 1354 return result; 1355 } 1356 1357 /** 1358 * The range types for $(D RedBlackTree) 1359 */ 1360 alias Range = RBRange!(RBNode*); 1361 alias ConstRange = RBRange!(const(RBNode)*); /// Ditto 1362 alias ImmutableRange = RBRange!(immutable(RBNode)*); /// Ditto 1363 1364 // find a node based on an element value 1365 private inout(RBNode)* _find(Elem e) inout 1366 { 1367 static if (allowDuplicates) 1368 { 1369 inout(RBNode)* cur = _end.left; 1370 inout(RBNode)* result = null; 1371 while (cur) 1372 { 1373 if (_less(cur.value, e)) 1374 cur = cur.right; 1375 else if (_less(e, cur.value)) 1376 cur = cur.left; 1377 else 1378 { 1379 // want to find the left-most element 1380 result = cur; 1381 cur = cur.left; 1382 } 1383 } 1384 return result; 1385 } 1386 else 1387 { 1388 inout(RBNode)* cur = _end.left; 1389 while (cur) 1390 { 1391 if (_less(cur.value, e)) 1392 cur = cur.right; 1393 else if (_less(e, cur.value)) 1394 cur = cur.left; 1395 else 1396 return cur; 1397 } 1398 return null; 1399 } 1400 } 1401 1402 // add an element to the tree, returns the node added, or the existing node 1403 // if it has already been added and allowDuplicates is false 1404 private auto _add(Elem n) 1405 { 1406 Node result; 1407 static if (!allowDuplicates) 1408 bool added = true; 1409 1410 if (!_end.left) 1411 { 1412 _end.left = _begin = result = allocate(n); 1413 } 1414 else 1415 { 1416 Node newParent = _end.left; 1417 Node nxt; 1418 while (true) 1419 { 1420 if (_less(n, newParent.value)) 1421 { 1422 nxt = newParent.left; 1423 if (nxt is null) 1424 { 1425 // 1426 // add to right of new parent 1427 // 1428 newParent.left = result = allocate(n); 1429 break; 1430 } 1431 } 1432 else 1433 { 1434 static if (!allowDuplicates) 1435 { 1436 if (!(_less(newParent.value, n))) 1437 { 1438 result = newParent; 1439 added = false; 1440 break; 1441 } 1442 } 1443 nxt = newParent.right; 1444 if (nxt is null) 1445 { 1446 // 1447 // add to right of new parent 1448 // 1449 newParent.right = result = allocate(n); 1450 break; 1451 } 1452 } 1453 newParent = nxt; 1454 } 1455 if (_begin.left) 1456 _begin = _begin.left; 1457 } 1458 1459 static if (allowDuplicates) 1460 { 1461 result.setColor(_end); 1462 ++_length; 1463 return result; 1464 } 1465 else 1466 { 1467 import std.typecons : Tuple; 1468 1469 if (added) 1470 { 1471 ++_length; 1472 result.setColor(_end); 1473 } 1474 return Tuple!(bool, "added", Node, "n")(added, result); 1475 } 1476 } 1477 1478 1479 /** 1480 * Check if any elements exist in the container. Returns $(D false) if at least 1481 * one element exists. 1482 */ 1483 @property bool empty() 1484 { 1485 return _end.left is null; 1486 } 1487 1488 /++ 1489 Returns the number of elements in the container. 1490 1491 Complexity: $(BIGOH 1). 1492 +/ 1493 @property size_t length() const 1494 { 1495 return _length; 1496 } 1497 1498 // Find the range for which every element is equal. 1499 private void findEnclosingRange(Elem e, inout(RBNode)** begin, inout(RBNode)** end) inout 1500 { 1501 *begin = _firstGreaterEqual(e); 1502 *end = _firstGreater(e); 1503 } 1504 1505 /** 1506 * Fetch a range that spans all the elements in the container. 1507 * 1508 * Complexity: $(BIGOH 1) 1509 */ 1510 Range opSlice() 1511 { 1512 return Range(_begin, _end); 1513 } 1514 1515 /// Ditto 1516 ConstRange opSlice() const 1517 { 1518 return ConstRange(_begin, _end); 1519 } 1520 1521 /// Ditto 1522 ImmutableRange opSlice() immutable 1523 { 1524 return ImmutableRange(_begin, _end); 1525 } 1526 1527 /** 1528 * Fetch a range that spans all equal elements of a particular value. 1529 * 1530 * Complexity: $(BIGOH 1) 1531 */ 1532 Range range(Elem e) 1533 { 1534 RBNode* begin, end; 1535 findEnclosingRange(e, &begin, &end); 1536 return Range(begin, end); 1537 } 1538 1539 /// Ditto 1540 ConstRange range(Elem e) const 1541 { 1542 const(RBNode)* begin, end; 1543 findEnclosingRange(e, &begin, &end); 1544 return ConstRange(begin, end); 1545 } 1546 1547 /// Ditto 1548 ImmutableRange range(Elem e) immutable 1549 { 1550 immutable(RBNode)* begin, end; 1551 findEnclosingRange(e, &begin, &end); 1552 return ImmutableRange(begin, end); 1553 } 1554 1555 /** 1556 * The front element in the container 1557 * 1558 * Complexity: $(BIGOH 1) 1559 */ 1560 Elem front() 1561 { 1562 return _begin.value; 1563 } 1564 1565 /** 1566 * The last element in the container 1567 * 1568 * Complexity: $(BIGOH log(n)) 1569 */ 1570 Elem back() 1571 { 1572 return _end.prev.value; 1573 } 1574 1575 /++ 1576 $(D in) operator. Check to see if the given element exists in the 1577 container. 1578 1579 Complexity: $(BIGOH log(n)) 1580 +/ 1581 bool opBinaryRight(string op)(Elem e) const if (op == "in") 1582 { 1583 return _find(e) !is null; 1584 } 1585 1586 /** 1587 * Insert a single element in the container. Note that this does not 1588 * invalidate any ranges currently iterating the container. 1589 * 1590 * Returns: The number of elements inserted. 1591 * 1592 * Complexity: $(BIGOH log(n)) 1593 */ 1594 size_t stableInsert(Elem elem) 1595 { 1596 static if (allowDuplicates) 1597 { 1598 _add(elem); 1599 return 1; 1600 } 1601 else 1602 { 1603 return(_add(elem).added ? 1 : 0); 1604 } 1605 } 1606 1607 /// ditto 1608 alias insert = stableInsert; 1609 1610 /** 1611 * Remove an element from the container and return its value. 1612 * 1613 * Complexity: $(BIGOH log(n)) 1614 */ 1615 Elem removeAny() 1616 { 1617 scope(success) 1618 --_length; 1619 auto n = _begin; 1620 auto result = n.value; 1621 _begin = n.remove(_end); 1622 n.deallocate(); 1623 return result; 1624 } 1625 1626 /** 1627 * Remove the front element from the container. 1628 * 1629 * Complexity: $(BIGOH log(n)) 1630 */ 1631 void removeFront() 1632 { 1633 scope(success) 1634 --_length; 1635 auto oldBegin = _begin; 1636 _begin = _begin.remove(_end); 1637 oldBegin.deallocate(); 1638 } 1639 1640 /** 1641 * Remove the back element from the container. 1642 * 1643 * Complexity: $(BIGOH log(n)) 1644 */ 1645 void removeBack() 1646 { 1647 scope(success) 1648 --_length; 1649 auto lastnode = _end.prev; 1650 if (lastnode is _begin) 1651 { 1652 auto oldBegin = _begin; 1653 _begin = _begin.remove(_end); 1654 oldBegin.deallocate(); 1655 } 1656 else 1657 { 1658 lastnode.remove(_end); 1659 lastnode.deallocate(); 1660 } 1661 } 1662 1663 /++ Ditto +/ 1664 size_t removeKey(Elem e) 1665 { 1666 immutable lenBefore = length; 1667 1668 auto beg = _firstGreaterEqual(e); 1669 if (beg is _end || _less(e, beg.value)) 1670 // no values are equal 1671 return 0; 1672 auto oldBeg = beg; 1673 immutable isBegin = (beg is _begin); 1674 beg = beg.remove(_end); 1675 if (isBegin) 1676 _begin = beg; 1677 --_length; 1678 1679 oldBeg.deallocate(); 1680 1681 return lenBefore - length; 1682 } 1683 1684 // find the first node where the value is > e 1685 private inout(RBNode)* _firstGreater(Elem e) inout 1686 { 1687 // can't use _find, because we cannot return null 1688 auto cur = _end.left; 1689 inout(RBNode)* result = _end; 1690 while (cur) 1691 { 1692 if (_less(e, cur.value)) 1693 { 1694 result = cur; 1695 cur = cur.left; 1696 } 1697 else 1698 cur = cur.right; 1699 } 1700 return result; 1701 } 1702 1703 1704 // find the first node where the value is >= e 1705 private inout(RBNode)* _firstGreaterEqual(Elem e) inout 1706 { 1707 // can't use _find, because we cannot return null. 1708 auto cur = _end.left; 1709 inout(RBNode)* result = _end; 1710 while (cur) 1711 { 1712 if (_less(cur.value, e)) 1713 cur = cur.right; 1714 else 1715 { 1716 result = cur; 1717 cur = cur.left; 1718 } 1719 1720 } 1721 return result; 1722 } 1723 1724 /// 1725 this() 1726 { 1727 _setup(); 1728 } 1729 1730 ~this() 1731 { 1732 while(length > 0) 1733 removeBack(); 1734 1735 // deallocate sentinel 1736 _end.deallocate(); 1737 } 1738 }