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