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 }