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 }