1 /******************************************************************************* 2 3 copyright: Copyright (c) 2008 Kris Bell. All rights reserved 4 5 license: BSD style: $(LICENSE) 6 7 version: Apr 2008: Initial release 8 9 authors: Kris 10 11 Since: 0.99.7 12 13 Based upon Doug Lea's Java collection package 14 15 *******************************************************************************/ 16 17 module tango.util.container.SortedMap; 18 19 public import tango.util.container.Container; 20 21 private import tango.util.container.RedBlack; 22 23 private import tango.util.container.model.IContainer; 24 25 private import tango.core.Exception : NoSuchElementException; 26 27 /******************************************************************************* 28 29 RedBlack trees of (key, value) pairs 30 31 --- 32 Iterator iterator (bool forward) 33 Iterator iterator (K key, bool forward) 34 int opApply (scope int delegate (ref V value) dg) 35 int opApply (scope int delegate (ref K key, ref V value) dg) 36 37 bool contains (V value) 38 bool containsKey (K key) 39 bool containsPair (K key, V value) 40 bool keyOf (V value, ref K key) 41 bool get (K key, ref V value) 42 43 bool take (ref V v) 44 bool take (K key, ref V v) 45 bool removeKey (K key) 46 size_t remove (V value, bool all) 47 size_t remove (IContainer!(V) e, bool all) 48 49 bool add (K key, V value) 50 size_t replace (V oldElement, V newElement, bool all) 51 bool replacePair (K key, V oldElement, V newElement) 52 bool opIndexAssign (V element, K key) 53 K nearbyKey (K key, bool greater) 54 V opIndex (K key) 55 V* opIn_r (K key) 56 57 size_t size () 58 bool isEmpty () 59 V[] toArray (V[] dst) 60 SortedMap dup () 61 SortedMap clear () 62 SortedMap reset () 63 SortedMap comparator (Comparator c) 64 --- 65 66 *******************************************************************************/ 67 68 class SortedMap (K, V, alias Reap = Container.reap, 69 alias Heap = Container.DefaultCollect) 70 : IContainer!(V) 71 { 72 // use this type for Allocator configuration 73 public alias RedBlack!(K, V) Type; 74 private alias Type *Ref; 75 76 private alias Heap!(Type) Alloc; 77 private alias Compare!(K) Comparator; 78 79 // root of the tree. Null if empty. 80 package Ref tree; 81 82 // configured heap manager 83 private Alloc heap; 84 85 // Comparators used for ordering 86 private Comparator cmp; 87 private Compare!(V) cmpElem; 88 89 private size_t count, 90 mutation; 91 92 93 /*********************************************************************** 94 95 Make an empty tree, using given Comparator for ordering 96 97 ***********************************************************************/ 98 99 public this (Comparator c = null) 100 { 101 this (c, 0); 102 } 103 104 /*********************************************************************** 105 106 Special version of constructor needed by dup() 107 108 ***********************************************************************/ 109 110 private this (Comparator c, size_t n) 111 { 112 count = n; 113 cmpElem = &compareElem; 114 cmp = (c is null) ? &compareKey : c; 115 } 116 117 /*********************************************************************** 118 119 Clean up when deleted 120 121 ***********************************************************************/ 122 123 ~this () 124 { 125 reset; 126 } 127 128 /*********************************************************************** 129 130 Return a generic iterator for contained elements 131 132 ***********************************************************************/ 133 134 final Iterator iterator (bool forward = true) 135 { 136 Iterator i = void; 137 i.node = count ? (forward ? tree.leftmost : tree.rightmost) : null; 138 i.bump = forward ? &Iterator.fore : &Iterator.back; 139 i.mutation = mutation; 140 i.owner = this; 141 i.prior = null; 142 return i; 143 } 144 145 /*********************************************************************** 146 147 Return an iterator which return all elements matching 148 or greater/lesser than the key in argument. The second 149 argument dictates traversal direction. 150 151 Return a generic iterator for contained elements 152 153 ***********************************************************************/ 154 155 final Iterator iterator (K key, bool forward) 156 { 157 Iterator i = iterator (forward); 158 i.node = count ? tree.findFirst(key, cmp, forward) : null; 159 return i; 160 } 161 162 /*********************************************************************** 163 164 Configure the assigned allocator with the size of each 165 allocation block (number of nodes allocated at one time) 166 and the number of nodes to pre-populate the cache with. 167 168 Time complexity: O(n) 169 170 ***********************************************************************/ 171 172 final SortedMap cache (size_t chunk, size_t count=0) 173 { 174 heap.config (chunk, count); 175 return this; 176 } 177 178 /*********************************************************************** 179 180 Return the number of elements contained 181 182 ***********************************************************************/ 183 184 @property final const size_t size () 185 { 186 return count; 187 } 188 189 /*********************************************************************** 190 191 Create an independent copy. Does not clone elements 192 193 ***********************************************************************/ 194 195 @property final SortedMap dup () 196 { 197 auto clone = new SortedMap!(K, V, Reap, Heap) (cmp, count); 198 if (count) 199 clone.tree = tree.copyTree (&clone.heap.allocate); 200 201 return clone; 202 } 203 204 /*********************************************************************** 205 206 Time complexity: O(log n) 207 208 ***********************************************************************/ 209 210 final bool contains (V value) 211 { 212 if (count is 0) 213 return false; 214 return tree.findAttribute (value, cmpElem) !is null; 215 } 216 217 /*********************************************************************** 218 219 ***********************************************************************/ 220 221 final int opApply (scope int delegate (ref V value) dg) 222 { 223 return iterator.opApply ((ref K k, ref V v) {return dg(v);}); 224 } 225 226 227 /*********************************************************************** 228 229 ***********************************************************************/ 230 231 final int opApply (scope int delegate (ref K key, ref V value) dg) 232 { 233 return iterator.opApply (dg); 234 } 235 236 /*********************************************************************** 237 238 Use a new Comparator. Causes a reorganization 239 240 ***********************************************************************/ 241 242 final SortedMap comparator (Comparator c) 243 { 244 if (cmp !is c) 245 { 246 cmp = (c is null) ? &compareKey : c; 247 248 if (count !is 0) 249 { 250 // must rebuild tree! 251 mutate; 252 auto t = tree.leftmost; 253 tree = null; 254 count = 0; 255 256 while (t) 257 { 258 add_ (t.value, t.attribute, false); 259 t = t.successor; 260 } 261 } 262 } 263 return this; 264 } 265 266 /*********************************************************************** 267 268 Time complexity: O(log n) 269 270 ***********************************************************************/ 271 272 final bool containsKey (K key) 273 { 274 if (count is 0) 275 return false; 276 277 return tree.find (key, cmp) !is null; 278 } 279 280 /*********************************************************************** 281 282 Time complexity: O(n) 283 284 ***********************************************************************/ 285 286 final bool containsPair (K key, V value) 287 { 288 if (count is 0) 289 return false; 290 291 return tree.find (key, value, cmp) !is null; 292 } 293 294 /*********************************************************************** 295 296 Return the value associated with Key key. 297 298 param: key a key 299 Returns: whether the key is contained or not 300 301 ***********************************************************************/ 302 303 final bool get (K key, ref V value) 304 { 305 if (count) 306 { 307 auto p = tree.find (key, cmp); 308 if (p) 309 { 310 value = p.attribute; 311 return true; 312 } 313 } 314 return false; 315 } 316 317 /*********************************************************************** 318 319 Return the value of the key exactly matching the provided 320 key or, if none, the key just after/before it based on the 321 setting of the second argument 322 323 param: key a key 324 param: after indicates whether to look beyond or before 325 the given key, where there is no exact match 326 throws: NoSuchElementException if none found 327 returns: a pointer to the value, or null if not present 328 329 ***********************************************************************/ 330 331 K nearbyKey (K key, bool after) 332 { 333 if (count) 334 { 335 auto p = tree.findFirst (key, cmp, after); 336 if (p) 337 return p.value; 338 } 339 340 noSuchElement ("no such key"); 341 assert (0); 342 } 343 344 /*********************************************************************** 345 346 Return the first key of the map 347 348 throws: NoSuchElementException where the map is empty 349 350 ***********************************************************************/ 351 352 K firstKey () 353 { 354 if (count) 355 return tree.leftmost.value; 356 357 noSuchElement ("no such key"); 358 assert (0); 359 } 360 361 /*********************************************************************** 362 363 Return the last key of the map 364 365 throws: NoSuchElementException where the map is empty 366 367 ***********************************************************************/ 368 369 K lastKey () 370 { 371 if (count) 372 return tree.rightmost.value; 373 374 noSuchElement ("no such key"); 375 assert (0); 376 } 377 378 /*********************************************************************** 379 380 Return the value associated with Key key. 381 382 param: key a key 383 Returns: a pointer to the value, or null if not present 384 385 ***********************************************************************/ 386 387 final V* opIn_r (K key) 388 { 389 if (count) 390 { 391 auto p = tree.find (key, cmp); 392 if (p) 393 return &p.attribute; 394 } 395 return null; 396 } 397 398 /*********************************************************************** 399 400 Time complexity: O(n) 401 402 ***********************************************************************/ 403 404 final bool keyOf (V value, ref K key) 405 { 406 if (count is 0) 407 return false; 408 409 auto p = tree.findAttribute (value, cmpElem); 410 if (p is null) 411 return false; 412 413 key = p.value; 414 return true; 415 } 416 417 /*********************************************************************** 418 419 Time complexity: O(n) 420 421 ***********************************************************************/ 422 423 final SortedMap clear () 424 { 425 return clear (false); 426 } 427 428 /*********************************************************************** 429 430 Reset the SortedMap contents. This releases more memory 431 than clear() does 432 433 Time complexity: O(n) 434 435 ***********************************************************************/ 436 437 final SortedMap reset () 438 { 439 return clear (true); 440 } 441 442 /*********************************************************************** 443 444 ************************************************************************/ 445 446 final size_t remove (IContainer!(V) e, bool all) 447 { 448 auto c = count; 449 foreach (v; e) 450 remove (v, all); 451 return c - count; 452 } 453 454 /*********************************************************************** 455 456 Time complexity: O(n 457 458 ***********************************************************************/ 459 460 final size_t remove (V value, bool all = false) 461 { 462 size_t i = count; 463 if (count) 464 { 465 auto p = tree.findAttribute (value, cmpElem); 466 while (p) 467 { 468 tree = p.remove (tree); 469 decrement (p); 470 if (!all || count is 0) 471 break; 472 p = tree.findAttribute (value, cmpElem); 473 } 474 } 475 return i - count; 476 } 477 478 /*********************************************************************** 479 480 Time complexity: O(n) 481 482 ***********************************************************************/ 483 484 final size_t replace (V oldElement, V newElement, bool all = false) 485 { 486 size_t c; 487 488 if (count) 489 { 490 auto p = tree.findAttribute (oldElement, cmpElem); 491 while (p) 492 { 493 ++c; 494 mutate; 495 p.attribute = newElement; 496 if (!all) 497 break; 498 p = tree.findAttribute (oldElement, cmpElem); 499 } 500 } 501 return c; 502 } 503 504 /*********************************************************************** 505 506 Time complexity: O(log n) 507 508 Takes the value associated with the least key. 509 510 ***********************************************************************/ 511 512 final bool take (ref V v) 513 { 514 if (count) 515 { 516 auto p = tree.leftmost; 517 v = p.attribute; 518 tree = p.remove (tree); 519 decrement (p); 520 return true; 521 } 522 return false; 523 } 524 525 /*********************************************************************** 526 527 Time complexity: O(log n) 528 529 ***********************************************************************/ 530 531 final bool take (K key, ref V value) 532 { 533 if (count) 534 { 535 auto p = tree.find (key, cmp); 536 if (p) 537 { 538 value = p.attribute; 539 tree = p.remove (tree); 540 decrement (p); 541 return true; 542 } 543 } 544 return false; 545 } 546 547 /*********************************************************************** 548 549 Time complexity: O(log n) 550 551 Returns true if inserted, false where an existing key 552 exists and was updated instead 553 554 ***********************************************************************/ 555 556 final bool add (K key, V value) 557 { 558 return add_ (key, value, true); 559 } 560 561 /*********************************************************************** 562 563 Time complexity: O(log n) 564 565 Returns true if inserted, false where an existing key 566 exists and was updated instead 567 568 ***********************************************************************/ 569 570 final bool opIndexAssign (V element, K key) 571 { 572 return add (key, element); 573 } 574 575 /*********************************************************************** 576 577 Operator retreival function 578 579 Throws NoSuchElementException where key is missing 580 581 ***********************************************************************/ 582 583 final V opIndex (K key) 584 { 585 auto p = opIn_r (key); 586 if (p) 587 return *p; 588 589 noSuchElement ("missing or invalid key"); 590 assert (0); 591 } 592 593 /*********************************************************************** 594 595 Time complexity: O(log n) 596 597 ***********************************************************************/ 598 599 final bool removeKey (K key) 600 { 601 V value; 602 603 return take (key, value); 604 } 605 606 /*********************************************************************** 607 608 Time complexity: O(log n) 609 610 ***********************************************************************/ 611 612 final bool replacePair (K key, V oldElement, V newElement) 613 { 614 if (count) 615 { 616 auto p = tree.find (key, oldElement, cmp); 617 if (p) 618 { 619 p.attribute = newElement; 620 mutate; 621 return true; 622 } 623 } 624 return false; 625 } 626 627 /*********************************************************************** 628 629 Copy and return the contained set of values in an array, 630 using the optional dst as a recipient (which is resized 631 as necessary). 632 633 Returns a slice of dst representing the container values. 634 635 Time complexity: O(n) 636 637 ***********************************************************************/ 638 639 final V[] toArray (V[] dst = null) 640 { 641 if (dst.length < count) 642 dst.length = count; 643 644 size_t i = 0; 645 foreach (k, v; this) 646 dst[i++] = v; 647 return dst [0 .. count]; 648 } 649 650 /*********************************************************************** 651 652 Is this container empty? 653 654 Time complexity: O(1) 655 656 ***********************************************************************/ 657 658 final const bool isEmpty () 659 { 660 return count is 0; 661 } 662 663 /*********************************************************************** 664 665 666 ***********************************************************************/ 667 668 final SortedMap check () 669 { 670 assert(cmp !is null); 671 assert(((count is 0) is (tree is null))); 672 assert((tree is null || tree.size() is count)); 673 674 if (tree) 675 { 676 tree.checkImplementation; 677 auto t = tree.leftmost; 678 K last = K.init; 679 680 while (t) 681 { 682 auto v = t.value; 683 assert((last is K.init || cmp(last, v) <= 0)); 684 last = v; 685 t = t.successor; 686 } 687 } 688 return this; 689 } 690 691 692 /*********************************************************************** 693 694 695 ***********************************************************************/ 696 697 private void noSuchElement (immutable(char)[] msg) 698 { 699 throw new NoSuchElementException (msg); 700 } 701 702 /*********************************************************************** 703 704 Time complexity: O(log n) 705 706 ***********************************************************************/ 707 708 private size_t instances (V value) 709 { 710 if (count is 0) 711 return 0; 712 return tree.countAttribute (value, cmpElem); 713 } 714 715 /*********************************************************************** 716 717 Returns true where an element is added, false where an 718 existing key is found 719 720 ***********************************************************************/ 721 722 private final bool add_ (K key, V value, bool checkOccurrence) 723 { 724 if (tree is null) 725 { 726 tree = heap.allocate.set (key, value); 727 increment; 728 } 729 else 730 { 731 auto t = tree; 732 for (;;) 733 { 734 int diff = cmp (key, t.value); 735 if (diff is 0 && checkOccurrence) 736 { 737 if (t.attribute != value) 738 { 739 t.attribute = value; 740 mutate; 741 } 742 return false; 743 } 744 else 745 if (diff <= 0) 746 { 747 if (t.left) 748 t = t.left; 749 else 750 { 751 tree = t.insertLeft (heap.allocate.set(key, value), tree); 752 increment; 753 break; 754 } 755 } 756 else 757 { 758 if (t.right) 759 t = t.right; 760 else 761 { 762 tree = t.insertRight (heap.allocate.set(key, value), tree); 763 increment; 764 break; 765 } 766 } 767 } 768 } 769 770 return true; 771 } 772 773 /*********************************************************************** 774 775 Time complexity: O(n) 776 777 ***********************************************************************/ 778 779 private SortedMap clear (bool all) 780 { 781 mutate; 782 783 // collect each node if we can't collect all at once 784 if ((heap.collect(all) is false) & count) 785 { 786 auto node = tree.leftmost; 787 while (node) 788 { 789 auto next = node.successor; 790 decrement (node); 791 node = next; 792 } 793 } 794 795 count = 0; 796 tree = null; 797 return this; 798 } 799 800 /*********************************************************************** 801 802 Time complexity: O(log n) 803 804 ***********************************************************************/ 805 806 private void remove (Ref node) 807 { 808 tree = node.remove (tree); 809 decrement (node); 810 } 811 812 /*********************************************************************** 813 814 new element was added 815 816 ***********************************************************************/ 817 818 private void increment () 819 { 820 ++mutation; 821 ++count; 822 } 823 824 /*********************************************************************** 825 826 element was removed 827 828 ***********************************************************************/ 829 830 private void decrement (Ref p) 831 { 832 Reap (p.value, p.attribute); 833 heap.collect (p); 834 ++mutation; 835 --count; 836 } 837 838 /*********************************************************************** 839 840 set was changed 841 842 ***********************************************************************/ 843 844 private void mutate () 845 { 846 ++mutation; 847 } 848 849 /*********************************************************************** 850 851 The default key comparator 852 853 @param fst first argument 854 @param snd second argument 855 856 Returns: a negative number if fst is less than snd; a 857 positive number if fst is greater than snd; else 0 858 859 ***********************************************************************/ 860 861 private static int compareKey (ref K fst, ref K snd) 862 { 863 if (fst is snd) 864 return 0; 865 866 return typeid(K).compare (&fst, &snd); 867 } 868 869 870 /*********************************************************************** 871 872 The default value comparator 873 874 @param fst first argument 875 @param snd second argument 876 877 Returns: a negative number if fst is less than snd; a 878 positive number if fst is greater than snd; else 0 879 880 ***********************************************************************/ 881 882 private static int compareElem(ref V fst, ref V snd) 883 { 884 if (fst is snd) 885 return 0; 886 887 return typeid(V).compare (&fst, &snd); 888 } 889 890 /*********************************************************************** 891 892 Iterator with no filtering 893 894 ***********************************************************************/ 895 896 private struct Iterator 897 { 898 Ref function(Ref) bump; 899 Ref node, 900 prior; 901 SortedMap owner; 902 size_t mutation; 903 904 /*************************************************************** 905 906 Did the container change underneath us? 907 908 ***************************************************************/ 909 910 bool valid () 911 { 912 return owner.mutation is mutation; 913 } 914 915 /*************************************************************** 916 917 Accesses the next value, and returns false when 918 there are no further values to traverse 919 920 ***************************************************************/ 921 922 bool next (ref K k, ref V v) 923 { 924 auto n = next (k); 925 return (n) ? v = *n, true : false; 926 } 927 928 /*************************************************************** 929 930 Return a pointer to the next value, or null when 931 there are no further values to traverse 932 933 ***************************************************************/ 934 935 V* next (ref K k) 936 { 937 V* r; 938 939 if (node) 940 { 941 prior = node; 942 k = node.value; 943 r = &node.attribute; 944 node = bump (node); 945 } 946 return r; 947 } 948 949 /*************************************************************** 950 951 Foreach support 952 953 ***************************************************************/ 954 955 int opApply (scope int delegate(ref K key, ref V value) dg) 956 { 957 int result; 958 959 auto n = node; 960 while (n) 961 { 962 prior = n; 963 auto next = bump (n); 964 if ((result = dg(n.value, n.attribute)) != 0) 965 break; 966 n = next; 967 } 968 node = n; 969 return result; 970 } 971 972 /*************************************************************** 973 974 Remove value at the current iterator location 975 976 ***************************************************************/ 977 978 bool remove () 979 { 980 if (prior) 981 { 982 owner.remove (prior); 983 984 // ignore this change 985 ++mutation; 986 return true; 987 } 988 989 prior = null; 990 return false; 991 } 992 993 /*************************************************************** 994 995 ***************************************************************/ 996 997 Iterator reverse () 998 { 999 if (bump is &fore) 1000 bump = &back; 1001 else 1002 bump = &fore; 1003 return this; 1004 } 1005 1006 /*************************************************************** 1007 1008 ***************************************************************/ 1009 1010 private static Ref fore (Ref p) 1011 { 1012 return p.successor; 1013 } 1014 1015 /*************************************************************** 1016 1017 ***************************************************************/ 1018 1019 private static Ref back (Ref p) 1020 { 1021 return p.predecessor; 1022 } 1023 } 1024 } 1025 1026 1027 1028 /******************************************************************************* 1029 1030 *******************************************************************************/ 1031 1032 debug (SortedMap) 1033 { 1034 import tango.io.Stdout; 1035 import tango.core.Thread; 1036 import tango.time.StopWatch; 1037 import tango.math.random.Kiss; 1038 1039 void main() 1040 { 1041 // usage examples ... 1042 auto map = new SortedMap!(char[], int); 1043 map.add ("foo", 1); 1044 map.add ("bar", 2); 1045 map.add ("wumpus", 3); 1046 1047 // implicit generic iteration 1048 foreach (key, value; map) 1049 Stdout.formatln ("{}:{}", key, value); 1050 1051 // explicit iteration 1052 foreach (key, value; map.iterator("foo", false)) 1053 Stdout.formatln ("{}:{}", key, value); 1054 1055 // generic iteration with optional remove 1056 auto s = map.iterator; 1057 foreach (key, value; s) 1058 {} // s.remove; 1059 1060 // incremental iteration, with optional remove 1061 char[] k; 1062 int v; 1063 auto iterator = map.iterator; 1064 while (iterator.next(k, v)) 1065 {} //iterator.remove; 1066 1067 // incremental iteration, with optional failfast 1068 auto it = map.iterator; 1069 while (it.valid && it.next(k, v)) 1070 {} 1071 1072 // remove specific element 1073 map.removeKey ("wumpus"); 1074 1075 // remove first element ... 1076 while (map.take(v)) 1077 Stdout.formatln ("taking {}, {} left", v, map.size); 1078 1079 1080 // setup for benchmark, with a set of integers. We 1081 // use a chunk allocator, and presize the bucket[] 1082 auto test = new SortedMap!(int, int, Container.reap, Container.Chunk); 1083 test.cache (1000, 500_000); 1084 const count = 500_000; 1085 StopWatch w; 1086 1087 auto keys = new int[count]; 1088 foreach (ref vv; keys) 1089 vv = Kiss.instance.toInt(int.max); 1090 1091 // benchmark adding 1092 w.start; 1093 for (int i=count; i--;) 1094 test.add(keys[i], i); 1095 Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop); 1096 1097 // benchmark reading 1098 w.start; 1099 for (int i=count; i--;) 1100 test.get(keys[i], v); 1101 Stdout.formatln ("{} lookups: {}/s", test.size, test.size/w.stop); 1102 1103 // benchmark adding without allocation overhead 1104 test.clear; 1105 w.start; 1106 for (int i=count; i--;) 1107 test.add(keys[i], i); 1108 Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop); 1109 1110 // benchmark duplication 1111 w.start; 1112 auto dup = test.dup; 1113 Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop); 1114 1115 // benchmark iteration 1116 w.start; 1117 foreach (key, value; test) {} 1118 Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop); 1119 1120 test.check; 1121 } 1122 }