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
17
18 *******************************************************************************/
19
20 module ocean.util.container.CircularList;
21
22 import ocean.util.container.Clink;
23
24 public import ocean.util.container.Container;
25
26 import ocean.util.container.model.IContainer;
27
28 version (unittest) import ocean.core.Test;
29
30 /*******************************************************************************
31
32 Circular linked list
33
34 ---
35 Iterator iterator ()
36 int opApply (int delegate(ref V value) dg)
37
38 CircularList add (V element)
39 CircularList addAt (size_t index, V element)
40 CircularList append (V element)
41 CircularList prepend (V element)
42 size_t addAt (size_t index, IContainer!(V) e)
43 size_t append (IContainer!(V) e)
44 size_t prepend (IContainer!(V) e)
45
46 bool take (ref V v)
47 bool contains (V element)
48 V get (size_t index)
49 size_t first (V element, size_t startingIndex = 0)
50 size_t last (V element, size_t startingIndex = 0)
51
52 V head ()
53 V tail ()
54 V head (V element)
55 V tail (V element)
56 V removeHead ()
57 V removeTail ()
58
59 bool removeAt (size_t index)
60 size_t remove (V element, bool all)
61 size_t removeRange (size_t fromIndex, size_t toIndex)
62
63 size_t replace (V oldElement, V newElement, bool all)
64 bool replaceAt (size_t index, V element)
65
66 size_t size ()
67 bool isEmpty ()
68 V[] toArray (V[] dst)
69 CircularList dup ()
70 CircularList subset (size_t from, size_t length)
71 CircularList clear ()
72 CircularList reset ()
73 CircularList check ()
74 ---
75
76 *******************************************************************************/
77
78 class CircularList (V, alias Reap = Container.reap,
79 alias Heap = Container.DefaultCollect)
80 : IContainer!(V)
81 {
82 import ocean.core.Verify;
83
84 // use this type for Allocator configuration
85 public alias Clink!(V) Type;
86
87 private alias Type *Ref;
88
89 private alias Heap!(Type) Alloc;
90
91 // number of elements contained
92 private size_t count;
93
94 // configured heap manager
95 private Alloc heap;
96
97 // mutation tag updates on each change
98 private size_t mutation;
99
100 // head of the list. Null if empty
101 private Ref list;
102
103
104 /***********************************************************************
105
106 Make an empty list
107
108 ***********************************************************************/
109
110 this ()
111 {
112 this (null, 0);
113 }
114
115 /***********************************************************************
116
117 Make an configured list
118
119 ***********************************************************************/
120
121 protected this (Ref h, size_t c)
122 {
123 list = h;
124 count = c;
125 }
126
127 /***********************************************************************
128
129 Clean up when deleted
130
131 ***********************************************************************/
132
133 ~this ()
134 {
135 reset;
136 }
137
138 /***********************************************************************
139
140 Return a generic iterator for contained elements
141
142 ***********************************************************************/
143
144 final Iterator iterator ()
145 {
146 // used to be Iterator i = void, but that doesn't initialize
147 // fields that are not initialized here.
148 Iterator i;
149 i.owner = this;
150 i.mutation = mutation;
151 i.cell = i.head = list;
152 i.count = count;
153 i.index = 0;
154 return i;
155 }
156
157 /***********************************************************************
158
159 Configure the assigned allocator with the size of each
160 allocation block (number of nodes allocated at one time)
161 and the number of nodes to pre-populate the cache with.
162
163 Time complexity: O(n)
164
165 ***********************************************************************/
166
167 final CircularList cache (size_t chunk, size_t count=0)
168 {
169 heap.config (chunk, count);
170 return this;
171 }
172
173 /***********************************************************************
174
175
176 ***********************************************************************/
177
178 final int opApply (scope int delegate(ref V value) dg)
179 {
180 return iterator.opApply (dg);
181 }
182
183 /***********************************************************************
184
185 Return the number of elements contained
186
187 ***********************************************************************/
188
189 final size_t size ()
190 {
191 return count;
192 }
193
194 /***********************************************************************
195
196 Make an independent copy of the list. Elements themselves
197 are not cloned
198
199 ***********************************************************************/
200
201 final CircularList dup ()
202 {
203 return new CircularList!(V, Reap, Heap) (list ? list.copyList(&heap.allocate) : null, count);
204 }
205
206 /***********************************************************************
207
208 Time complexity: O(n)
209
210 ***********************************************************************/
211
212 final bool contains (V element)
213 {
214 if (list)
215 return list.find (element) !is null;
216 return false;
217 }
218
219 /***********************************************************************
220
221 Time complexity: O(1)
222
223 ***********************************************************************/
224
225 final V head ()
226 {
227 return firstCell.value;
228 }
229
230 /***********************************************************************
231
232 Time complexity: O(1)
233
234 ***********************************************************************/
235
236 final V tail ()
237 {
238 return lastCell.value;
239 }
240
241 /***********************************************************************
242
243 Time complexity: O(n)
244
245 ***********************************************************************/
246
247 final V get (size_t index)
248 {
249 return cellAt(index).value;
250 }
251
252 /***********************************************************************
253
254 Time complexity: O(n)
255 Returns size_t.max if no element found.
256
257 ***********************************************************************/
258
259 final size_t first (V element, size_t startingIndex = 0)
260 {
261 if (startingIndex < 0)
262 startingIndex = 0;
263
264 auto p = list;
265 if (p is null)
266 return size_t.max;
267
268 for (size_t i = 0; true; ++i)
269 {
270 if (i >= startingIndex && element == p.value)
271 return i;
272
273 p = p.next;
274 if (p is list)
275 break;
276 }
277 return size_t.max;
278 }
279
280 /***********************************************************************
281
282 Time complexity: O(n)
283 Returns size_t.max if no element found.
284
285 ***********************************************************************/
286
287 final size_t last (V element, size_t startingIndex = 0)
288 {
289 if (count is 0)
290 return size_t.max;
291
292 if (startingIndex >= count)
293 startingIndex = count - 1;
294
295 if (startingIndex < 0)
296 startingIndex = 0;
297
298 auto p = cellAt (startingIndex);
299 size_t i = startingIndex;
300 for (;;)
301 {
302 if (element == p.value)
303 return i;
304 else
305 if (p is list)
306 break;
307 else
308 {
309 p = p.prev;
310 --i;
311 }
312 }
313 return size_t.max;
314 }
315
316 /***********************************************************************
317
318 Time complexity: O(length)
319
320 ***********************************************************************/
321
322 final CircularList subset (size_t from, size_t length)
323 {
324 Ref newlist = null;
325
326 if (length > 0)
327 {
328 checkIndex (from);
329 auto p = cellAt (from);
330 auto current = newlist = heap.allocate.set (p.value);
331
332 for (size_t i = 1; i < length; ++i)
333 {
334 p = p.next;
335 if (p is null)
336 length = i;
337 else
338 {
339 current.addNext (p.value, &heap.allocate);
340 current = current.next;
341 }
342 }
343 }
344
345 return new CircularList (newlist, length);
346 }
347
348 /***********************************************************************
349
350 Time complexity: O(1)
351
352 ***********************************************************************/
353
354 final CircularList clear ()
355 {
356 return clear (false);
357 }
358
359 /***********************************************************************
360
361 Reset the HashMap contents and optionally configure a new
362 heap manager. This releases more memory than clear() does
363
364 Time complexity: O(n)
365
366 ***********************************************************************/
367
368 final CircularList reset ()
369 {
370 return clear (true);
371 }
372
373 /***********************************************************************
374
375 Time complexity: O(n)
376
377 Takes the last element on the list
378
379 ***********************************************************************/
380
381 final bool take (ref V v)
382 {
383 if (count)
384 {
385 v = tail;
386 removeTail ();
387 return true;
388 }
389 return false;
390 }
391
392 /***********************************************************************
393
394 Time complexity: O(1)
395
396 ***********************************************************************/
397
398 final CircularList prepend (V element)
399 {
400 if (list is null)
401 list = heap.allocate.set (element);
402 else
403 list = list.addPrev (element, &heap.allocate);
404 increment;
405 return this;
406 }
407
408 /***********************************************************************
409
410 Time complexity: O(1)
411
412 ***********************************************************************/
413
414 final V head (V element)
415 {
416 auto p = firstCell;
417 auto v = p.value;
418 p.value = element;
419 mutate;
420 return v;
421 }
422
423 /***********************************************************************
424
425 Time complexity: O(1)
426
427 ***********************************************************************/
428
429 final V removeHead ()
430 {
431 auto p = firstCell;
432 if (p.singleton)
433 list = null;
434 else
435 {
436 auto n = p.next;
437 p.unlink;
438 list = n;
439 }
440
441 auto v = p.value;
442 decrement (p);
443 return v;
444 }
445
446 /***********************************************************************
447
448 Time complexity: O(1)
449
450 ***********************************************************************/
451
452 final CircularList add (V element)
453 {
454 return append (element);
455 }
456
457 /***********************************************************************
458
459 Time complexity: O(1)
460
461 ***********************************************************************/
462
463 final CircularList append (V element)
464 {
465 if (list is null)
466 prepend (element);
467 else
468 {
469 list.prev.addNext (element, &heap.allocate);
470 increment;
471 }
472 return this;
473 }
474
475 /***********************************************************************
476
477 Time complexity: O(1)
478
479 ***********************************************************************/
480
481 final V tail (V element)
482 {
483 auto p = lastCell;
484 auto v = p.value;
485 p.value = element;
486 mutate;
487 return v;
488 }
489
490 /***********************************************************************
491
492 Time complexity: O(1)
493
494 ***********************************************************************/
495
496 final V removeTail ()
497 {
498 auto p = lastCell;
499 if (p is list)
500 list = null;
501 else
502 p.unlink;
503
504 auto v = p.value;
505 decrement (p);
506 return v;
507 }
508
509 /***********************************************************************
510
511 Time complexity: O(n)
512
513 ***********************************************************************/
514
515 final CircularList addAt (size_t index, V element)
516 {
517 if (index is 0)
518 prepend (element);
519 else
520 {
521 cellAt(index - 1).addNext(element, &heap.allocate);
522 increment;
523 }
524 return this;
525 }
526
527 /***********************************************************************
528
529 Time complexity: O(n)
530
531 ***********************************************************************/
532
533 final CircularList replaceAt (size_t index, V element)
534 {
535 cellAt(index).value = element;
536 mutate;
537 return this;
538 }
539
540 /***********************************************************************
541
542 Time complexity: O(n)
543
544 ***********************************************************************/
545
546 final CircularList removeAt (size_t index)
547 {
548 if (index is 0)
549 removeHead;
550 else
551 {
552 auto p = cellAt(index);
553 p.unlink;
554 decrement (p);
555 }
556 return this;
557 }
558
559 /***********************************************************************
560
561 Time complexity: O(n)
562
563 ***********************************************************************/
564
565 final size_t remove (V element, bool all)
566 {
567 auto c = count;
568 if (list)
569 {
570 auto p = list;
571 for (;;)
572 {
573 auto n = p.next;
574 if (element == p.value)
575 {
576 p.unlink;
577 decrement (p);
578 if (p is list)
579 {
580 if (p is n)
581 {
582 list = null;
583 break;
584 }
585 else
586 list = n;
587 }
588
589 if (! all)
590 break;
591 else
592 p = n;
593 }
594 else
595 if (n is list)
596 break;
597 else
598 p = n;
599 }
600 }
601 return c - count;
602 }
603
604 /***********************************************************************
605
606 Time complexity: O(n)
607
608 ***********************************************************************/
609
610 final size_t replace (V oldElement, V newElement, bool all)
611 {
612 size_t c;
613 if (list)
614 {
615 auto p = list;
616 do {
617 if (oldElement == p.value)
618 {
619 ++c;
620 mutate;
621 p.value = newElement;
622 if (! all)
623 break;
624 }
625 p = p.next;
626 } while (p !is list);
627 }
628 return c;
629 }
630
631 /***********************************************************************
632
633 Time complexity: O(number of elements in e)
634
635 ***********************************************************************/
636
637 final size_t prepend (IContainer!(V) e)
638 {
639 Ref hd = null;
640 Ref current = null;
641 auto c = count;
642
643 foreach (element; e)
644 {
645 increment;
646
647 if (hd is null)
648 {
649 hd = heap.allocate.set(element);
650 current = hd;
651 }
652 else
653 {
654 current.addNext (element, &heap.allocate);
655 current = current.next;
656 }
657 }
658
659 if (list is null)
660 list = hd;
661 else
662 if (hd)
663 {
664 auto tl = list.prev;
665 current.next = list;
666 list.prev = current;
667 tl.next = hd;
668 hd.prev = tl;
669 list = hd;
670 }
671 return count - c;
672 }
673
674 /***********************************************************************
675
676 Time complexity: O(number of elements in e)
677
678 ***********************************************************************/
679
680 final size_t append (IContainer!(V) e)
681 {
682 auto c = count;
683 if (list is null)
684 prepend (e);
685 else
686 {
687 auto current = list.prev;
688 foreach (element; e)
689 {
690 increment;
691 current.addNext (element, &heap.allocate);
692 current = current.next;
693 }
694 }
695 return count - c;
696 }
697
698 /***********************************************************************
699
700 Time complexity: O(size() + number of elements in e)
701
702 ***********************************************************************/
703
704 final size_t addAt (size_t index, IContainer!(V) e)
705 {
706 auto c = count;
707 if (list is null || index is 0)
708 prepend (e);
709 else
710 {
711 auto current = cellAt (index - 1);
712 foreach (element; e)
713 {
714 increment;
715 current.addNext (element, &heap.allocate);
716 current = current.next;
717 }
718 }
719 return count - c;
720 }
721
722 /***********************************************************************
723
724 Time complexity: O(n)
725
726 ***********************************************************************/
727
728 final size_t removeRange (size_t fromIndex, size_t toIndex)
729 {
730 auto p = cellAt (fromIndex);
731 auto last = list.prev;
732 auto c = count;
733 for (size_t i = fromIndex; i <= toIndex; ++i)
734 {
735 auto n = p.next;
736 p.unlink;
737 decrement (p);
738 if (p is list)
739 {
740 if (p is last)
741 {
742 list = null;
743 break;
744 }
745 else
746 list = n;
747 }
748 p = n;
749 }
750 return c - count;
751 }
752
753 /***********************************************************************
754
755 Copy and return the contained set of values in an array,
756 using the optional dst as a recipient (which is resized
757 as necessary).
758
759 Returns a slice of dst representing the container values.
760
761 Time complexity: O(n)
762
763 ***********************************************************************/
764
765 final V[] toArray (V[] dst = null)
766 {
767 if (dst.length < count)
768 dst.length = count;
769
770 size_t i = 0;
771 foreach (v; this)
772 dst[i++] = v;
773 return dst [0 .. count];
774 }
775
776 /***********************************************************************
777
778 Is this container empty?
779
780 Time complexity: O(1)
781
782 ***********************************************************************/
783
784 final bool isEmpty ()
785 {
786 return count is 0;
787 }
788
789 /***********************************************************************
790
791
792 ***********************************************************************/
793
794 final CircularList check()
795 {
796 verify(((count is 0) is (list is null)));
797 verify((list is null || list.size is count));
798
799 if (list)
800 {
801 size_t c = 0;
802 auto p = list;
803 do {
804 verify(p.prev.next is p);
805 verify(p.next.prev is p);
806 verify(instances(p.value) > 0);
807 verify(contains(p.value));
808 p = p.next;
809 ++c;
810 } while (p !is list);
811 verify(c is size);
812 }
813 return this;
814 }
815
816 /***********************************************************************
817
818 Time complexity: O(n)
819
820 ***********************************************************************/
821
822 private size_t instances (V element)
823 {
824 if (list)
825 return list.count (element);
826 return 0;
827 }
828
829 /***********************************************************************
830
831
832 ***********************************************************************/
833
834 private void checkIndex (size_t i)
835 {
836 if (i >= count)
837 throw new Exception ("out of range");
838 }
839
840 /***********************************************************************
841
842 return the first cell, or throw exception if empty
843
844 ***********************************************************************/
845
846 private Ref firstCell ()
847 {
848 checkIndex (0);
849 return list;
850 }
851
852 /***********************************************************************
853
854 return the last cell, or throw exception if empty
855
856 ***********************************************************************/
857
858 private Ref lastCell ()
859 {
860 checkIndex (0);
861 return list.prev;
862 }
863
864 /***********************************************************************
865
866 return the index'th cell, or throw exception if bad index
867
868 ***********************************************************************/
869
870 private Ref cellAt (size_t index)
871 {
872 checkIndex (index);
873 return list.nth (index);
874 }
875
876 /***********************************************************************
877
878 Time complexity: O(1)
879
880 ***********************************************************************/
881
882 private CircularList clear (bool all)
883 {
884 mutate;
885
886 // collect each node if we can't collect all at once
887 if (heap.collect(all) is false && count)
888 {
889 auto p = list;
890 do {
891 auto n = p.next;
892 decrement (p);
893 p = n;
894 } while (p != list);
895 }
896
897 list = null;
898 count = 0;
899 return this;
900 }
901
902 /***********************************************************************
903
904 new element was added
905
906 ***********************************************************************/
907
908 private void increment ()
909 {
910 ++mutation;
911 ++count;
912 }
913
914 /***********************************************************************
915
916 element was removed
917
918 ***********************************************************************/
919
920 private void decrement (Ref p)
921 {
922 Reap (p.value);
923 heap.collect (p);
924 ++mutation;
925 --count;
926 }
927
928 /***********************************************************************
929
930 set was changed
931
932 ***********************************************************************/
933
934 private void mutate ()
935 {
936 ++mutation;
937 }
938
939 /***********************************************************************
940
941 Iterator with no filtering
942
943 ***********************************************************************/
944
945 private struct Iterator
946 {
947 bool rev;
948 Ref cell,
949 head,
950 prior;
951 CircularList owner;
952 size_t index,
953 count;
954 size_t mutation;
955
956 /***************************************************************
957
958 Did the container change underneath us?
959
960 ***************************************************************/
961
962 bool valid ()
963 {
964 return owner.mutation is mutation;
965 }
966
967 /***************************************************************
968
969 Accesses the next value, and returns false when
970 there are no further values to traverse
971
972 ***************************************************************/
973
974 bool next (ref V v)
975 {
976 if (auto n = next)
977 {
978 v = *n;
979 return true;
980 }
981 return false;
982 }
983
984 /***************************************************************
985
986 Return a pointer to the next value, or null when
987 there are no further values to traverse
988
989 ***************************************************************/
990
991 V* next ()
992 {
993 V* r;
994
995 if (index < count)
996 {
997 ++index;
998 prior = cell;
999 r = &cell.value;
1000 cell = (rev ? cell.prev : cell.next);
1001 }
1002 else
1003 cell = null;
1004 return r;
1005 }
1006
1007 /***************************************************************
1008
1009 Foreach support
1010
1011 ***************************************************************/
1012
1013 int opApply (scope int delegate(ref V value) dg)
1014 {
1015 int result;
1016 auto c = cell;
1017
1018 while (index < count)
1019 {
1020 ++index;
1021 prior = c;
1022 c = (rev ? c.prev : c.next);
1023 if ((result = dg(prior.value)) != 0)
1024 break;
1025 }
1026 cell = null;
1027 return result;
1028 }
1029
1030 /***************************************************************
1031
1032 Remove value that was just iterated.
1033
1034 ***************************************************************/
1035
1036 bool remove ()
1037 {
1038 if (prior)
1039 {
1040 auto next = (rev ? prior.prev : prior.next);
1041 if (prior is head)
1042 {
1043 if (prior is next)
1044 owner.list = null;
1045 else
1046 head = owner.list = next;
1047 }
1048
1049 prior.unlink;
1050 owner.decrement (prior);
1051 prior = null;
1052
1053 --count;
1054 // ignore this change
1055 ++mutation;
1056 return true;
1057 }
1058 return false;
1059 }
1060
1061 /***************************************************************
1062
1063 Insert a new value before the node about to be
1064 iterated (or after the node that was just iterated).
1065
1066 Returns: a copy of this iterator for chaining.
1067
1068 ***************************************************************/
1069
1070 Iterator insert (V value)
1071 {
1072 // Note: this needs some attention, not sure how
1073 // to handle when iterator is in reverse.
1074 if (cell is null)
1075 prior.addNext (value, &owner.heap.allocate);
1076 else
1077 cell.addPrev (value, &owner.heap.allocate);
1078 owner.increment;
1079
1080 ++count;
1081 // ignore this change
1082 ++mutation;
1083 return this;
1084 }
1085
1086 /***************************************************************
1087
1088 Flip the direction of next() and opApply(), and
1089 reset the termination point such that we can do
1090 another full traversal.
1091
1092 ***************************************************************/
1093
1094 Iterator reverse ()
1095 {
1096 rev ^= true;
1097 next;
1098 index = 0;
1099 return this;
1100 }
1101 }
1102 }
1103
1104 /*******************************************************************************
1105
1106 *******************************************************************************/
1107
1108 unittest
1109 {
1110 auto list = new CircularList!(int);
1111 list.add(1);
1112 list.add(2);
1113 list.add(3);
1114
1115 int i = 1;
1116 foreach(v; list)
1117 {
1118 test(v == i);
1119 i++;
1120 }
1121
1122 auto iter = list.iterator;
1123 iter.next();
1124 iter.remove(); // delete the first item
1125
1126 i = 2;
1127 foreach(v; list)
1128 {
1129 test(v == i);
1130 i++;
1131 }
1132
1133 // test insert functionality
1134 iter = list.iterator;
1135 iter.next;
1136 iter.insert(4);
1137
1138 int[] compareto = [2, 4, 3];
1139 i = 0;
1140 foreach(v; list)
1141 {
1142 test(v == compareto[i++]);
1143 }
1144 }
1145
1146 /*******************************************************************************
1147
1148 *******************************************************************************/
1149
1150 debug (CircularList)
1151 {
1152 import ocean.io.Stdout;
1153 import ocean.core.Thread;
1154 import ocean.time.StopWatch;
1155
1156 void main()
1157 {
1158 // usage examples ...
1159 auto list = new CircularList!(char[]);
1160 foreach (value; list)
1161 Stdout (value).newline;
1162
1163 list.add ("foo");
1164 list.add ("bar");
1165 list.add ("wumpus");
1166
1167 // implicit generic iteration
1168 foreach (value; list)
1169 Stdout (value).newline;
1170
1171 // explicit generic iteration
1172 foreach (value; list.iterator.reverse)
1173 Stdout.formatln ("> {}", value);
1174
1175 // generic iteration with optional remove
1176 auto s = list.iterator;
1177 foreach (value; s)
1178 {} //s.remove;
1179
1180 // incremental iteration, with optional remove
1181 char[] v;
1182 auto iterator = list.iterator;
1183 while (iterator.next(v))
1184 {}//iterator.remove;
1185
1186 // incremental iteration, with optional failfast
1187 auto it = list.iterator;
1188 while (it.valid && it.next(v))
1189 {}
1190
1191 // remove specific element
1192 list.remove ("wumpus", false);
1193
1194 // remove first element ...
1195 while (list.take(v))
1196 Stdout.formatln ("taking {}, {} left", v, list.size);
1197
1198
1199 // setup for benchmark, with a set of integers. We
1200 // use a chunk allocator, and presize the bucket[]
1201 auto test = new CircularList!(uint, Container.reap, Container.Chunk);
1202 test.cache (1000, 1_000_000);
1203 static immutable count = 1_000_000;
1204 StopWatch w;
1205
1206 // benchmark adding
1207 w.start;
1208 for (uint i=count; i--;)
1209 test.add(i);
1210 Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop);
1211
1212 // benchmark adding without allocation overhead
1213 test.clear;
1214 w.start;
1215 for (uint i=count; i--;)
1216 test.add(i);
1217 Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop);
1218
1219 // benchmark duplication
1220 w.start;
1221 auto dup = test.dup;
1222 Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop);
1223
1224 // benchmark iteration
1225 w.start;
1226 foreach (value; test) {}
1227 Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop);
1228
1229 test.check;
1230 }
1231 }