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