1 /**
2  * Several implementations of standard containers.
3  */
4 module iz.containers;
5 
6 import
7     core.exception, core.stdc..string;
8 import
9     std.exception, std..string, std.traits, std.conv, std.range.primitives,
10     std.typecons;
11 import
12     iz.memory, iz.types, iz.streams;
13 version(unittest) import
14     std.stdio: writeln, write, stdout;
15 
16 version(X86_64)
17     version(linux) version = Nux64;
18 
19 /**
20  * Generic, manually managed, array.
21  *
22  * Array(T) implements a single-dimension array of uncollected memory.
23  * It internally allocates memory blocks to minimize the reallocation fingerprints,
24  * allowing insertions to be 2 times faster than built-in arrays.
25  *
26  * Its layout differs from built-in D's dynamic arrays and they cannot be cast as T[]
27  * however, most of the slicing operations are possible.
28  *
29  * Manual management implies that $(D destruct()) must be called on the array when
30  * it goes out of scope. $(D destruct()) is only called on the content when the
31  * specialization is a $(D struct()) or a $(D union)). Classes and pointers must
32  * be freed by hand.
33  */
34 struct Array(T)
35 {
36 
37 private:
38 
39     size_t _length;
40     @NoGc Ptr _elems;
41     uint _granularity = 4096;
42     size_t _blockCount;
43 
44     pragma(inline, true)
45     void setLength(size_t value) @nogc
46     {
47         assert(_granularity != 0);
48 
49         const size_t newBlockCount = ((value * T.sizeof) / _granularity) + 1;
50         if (_blockCount != newBlockCount)
51         {
52             _blockCount = newBlockCount;
53             _elems = reallocMem(_elems, _granularity * _blockCount);
54         }
55         _length = value;
56     }
57 
58     pragma(inline, true)
59     void grow() @nogc
60     {
61         length(_length + 1);
62     }
63 
64     pragma(inline, true)
65     void shrink() @nogc
66     {
67         length(_length - 1);
68     }
69 
70     pragma(inline, true)
71     Unqual!T* rwPtr(size_t index) pure const nothrow @nogc
72     {
73         return cast(Unqual!T*) (_elems + index * T.sizeof);
74     }
75 
76     struct Range
77     {
78         private size_t _i;
79         private Array!T* _a;
80         ///
81         this(ref Array!T array, size_t index = 0) @nogc @trusted
82         {
83             _a = &array;
84             _i = index;
85         }
86         ///
87         ref T front() @nogc
88         {
89             return _a.opIndex(_i);
90         }
91         ///
92         void popFront() @nogc @safe
93         {
94             ++_i;
95         }
96         ///
97         bool empty() @nogc @safe
98         {
99             return _i >= _a._length;
100         }
101     }
102 
103     pragma(inline, true)
104     void postblitElements()()
105     {
106         static if (is(T == struct) && hasMember!(T, "__postblit") && isCopyable!T )
107         {
108             foreach(i; 0.._length)
109                 (*rwPtr(i)).__postblit();
110         }
111     }
112 
113 public:
114 
115     /// Constructs the array with a list of T.
116     this(E...)(E elements) @nogc
117     if (is(Unqual!E == T) || is(T == E))
118     {
119         opAssign(elements);
120     }
121 
122     /// Constructs the array with a D array of T.
123     this(E)(E[] elements...) @nogc
124     if (is(Unqual!E == T) || is(T == E))
125     {
126         opAssign(elements);
127     }
128 
129     /// Constructs by dispatching to the existing opAssign overloads.
130     this(E)(auto ref E value) @nogc
131     {
132         opAssign(value);
133     }
134 
135     this(this)
136     {
137         Ptr old = _elems;
138         const size_t sz = _granularity * _blockCount;
139         _elems = getMem(sz);
140         moveMem(_elems, old, sz);
141         postblitElements;
142     }
143 
144     ~this()
145     {
146         length(0);
147         if (_elems)
148             freeMem(_elems);
149         _elems = null;
150     }
151 
152     /**
153      * Indicates the memory allocation block-size.
154      */
155     uint granurality() const pure nothrow @safe @nogc
156     {
157         return _granularity;
158     }
159 
160     /**
161      * Sets the memory allocation block-size.
162      * value should be set to 16 or 4096 (the default).
163      */
164     void granularity(uint value) @nogc
165     {
166         if (_granularity == value)
167             return;
168         if (value < T.sizeof)
169         {
170             value = 16 * T.sizeof;
171         }
172         else if (value < 16)
173         {
174             value = 16;
175         }
176         else while (_granularity % 16 != 0)
177         {
178             value--;
179         }
180         _granularity = value;
181         setLength(_length);
182     }
183 
184     /**
185      * Indicates how many block the array is made of.
186      */
187     pragma(inline, true)
188     size_t blockCount() const pure nothrow @safe @nogc
189     {
190         return _blockCount;
191     }
192 
193     /// Sets or gets the element count.
194     pragma(inline, true)
195     size_t length() const pure nothrow @safe @nogc
196     {
197         return _length;
198     }
199 
200     /// ditto
201     void length(V)(V value)
202     if (isIntegral!V)
203     {
204         if (value == _length)
205             return;
206         size_t oldLen = _length;
207         static if (is(T == struct) && !isTuple!T)
208         {
209             if (value < _length)
210             {
211                 foreach (i; value.._length)
212                     destruct(opIndex(i));
213             }
214         }
215         setLength(value);
216         static if (is(T == struct))
217         {
218             if (value > oldLen)
219                 foreach (i; oldLen.._length)
220                     emplace(rwPtr(i));
221         }
222     }
223 
224     /**
225      * Pointer to the first element.
226      * As it's always assigned It cannot be used to determine if the array is empty.
227      */
228     pragma(inline, true)
229     Ptr ptr() pure nothrow @nogc
230     {
231         return _elems;
232     }
233 
234     /**
235      * Typed pointer to the first element.
236      */
237     pragma(inline, true)
238     T* typedPtr() pure nothrow @nogc
239     {
240         return cast(T*) _elems;
241     }
242 
243     /**
244      * Returns the string representation of the array.
245      *
246      * Throw:
247      *      A ConvException if T is not converitble to string.
248      */
249     static if (__traits(compiles, to!string(opSlice())))
250     string toString()
251     {
252         if (_length == 0)
253             return "[]";
254         else
255         {
256             auto r = opSlice();
257             return to!string(r);
258         }
259     }
260 
261     /// Returns a mutable (deep) copy of the array.
262     Array!T dup()()
263     {
264         Array!T result = this;
265         return result;
266     }
267 
268     /// Support for associative arrays.
269     size_t toHash() nothrow @trusted
270     {
271         return opSlice().hashOf;
272     }
273 
274     /// Support for equality tests.
275     bool opEquals(A)(auto ref A array) const pure @nogc @trusted
276     if ((is(Unqual!A == Unqual!(Array!T)) || is(Unqual!(ElementEncodingType!A) == T)))
277     {
278         if (_length != array.length)
279             return false;
280         else if (_length == 0 && array.length == 0)
281             return true;
282         static if (is(Unqual!A == Unqual!(Array!T)))
283             return _elems[0.._length * T.sizeof] ==
284               array._elems[0..array._length * T.sizeof];
285         else
286             return _elems[0.._length * T.sizeof] ==
287               array.ptr[0..array.length];
288     }
289 
290     /// Support for the array syntax.
291     pragma(inline, true)
292     ref T opIndex(size_t i) const pure @nogc
293     {
294         return *rwPtr(i);
295     }
296 
297     /// Support for the array syntax.
298     void opIndexAssign()(ref T item, size_t i) @nogc
299     {
300         *rwPtr(i) = item;
301     }
302 
303     /// Ditto
304     void opIndexAssign()(T item, size_t i) @nogc
305     {
306         *rwPtr(i) = item;
307     }
308 
309     /// ditto
310     static if (isTemplateInstance!(T) && __traits(isSame, TemplateOf!T, TemplateOf!(typeof(this))))
311     void opIndexAssign()(TemplateArgsOf!(T)[0][] item, size_t i) @nogc
312     {
313         *rwPtr(i) = item;
314     }
315 
316     /// Support for the foreach operator.
317     int opApply(scope int delegate(ref T) dg)
318     {
319         int result;
320         foreach (immutable i; 0 .. _length)
321         {
322             result = dg(*rwPtr(i));
323             if (result) break;
324         }
325         return result;
326     }
327 
328     /// Support for the foreach_reverse operator.
329     int opApplyReverse(scope int delegate(ref T) dg)
330     {
331         int result;
332         foreach_reverse (immutable i; 0 .. _length)
333         {
334             result = dg(*rwPtr(i));
335             if (result) break;
336         }
337         return result;
338     }
339 
340     /// Support for the dollar operator.
341     size_t opDollar() const pure nothrow @safe @nogc
342     {
343         return _length;
344     }
345 
346     /// Assign another Array!T.
347     void opAssign(E)(auto ref Array!E elements) @nogc
348     if (is(Unqual!E == T) || is(E == T))
349     {
350         setLength(elements._length);
351         moveMem(_elems, elements._elems, T.sizeof * _length);
352         /*setLength(0);
353         _granularity = elements._granularity;
354         _length = elements.length;
355         _elems = elements._elems;
356         _blockCount = elements._blockCount;
357         __postblit();*/
358     }
359 
360     /// Assigns a D array.
361     void opAssign(E)(auto ref E[] elements) @nogc
362     if (is(Unqual!E == T) || is(E == T))
363     {
364         setLength(elements.length);
365         foreach (i, element; elements)
366             *rwPtr(i) = cast(T) element;
367     }
368 
369     /// Assigns an inpunt range.
370     void opAssign(E)(auto ref E elements) @nogc
371     if (isInputRange!E && is(Unqual!(ElementType!E) == T) && !isRandomAccessRange!E)
372     {
373         const len = walkLength(elements);
374         setLength(len);
375         foreach (immutable i; 0..len)
376         {
377             opAssign(elements.front);
378             elements.popFront;
379         }
380     }
381 
382     /// Support for the cat operator
383     auto ref typeof(this) opBinary(string op : "~", R)(auto ref R rhs) return @nogc
384     if (__traits(hasMember, R, "length") && __traits(hasMember, R, "ptr"))
385     {
386         typeof(this) result;
387         result.length = _length + rhs.length;
388         moveMem(result.rwPtr(0), _elems , T.sizeof * _length);
389         moveMem(result.rwPtr(_length), rhs._elems , T.sizeof * rhs.length);
390         return result;
391     }
392 
393     /// Support for the cat operator.
394     ref typeof(this) opOpAssign(string op, E = T)(auto ref E[] elements) @nogc
395     if (is(Unqual!E == T) || is(E == T))
396     {
397         static if (op == "~")
398         {
399             const old = _length;
400             setLength(_length + elements.length);
401             moveMem( rwPtr(old), elements.ptr , T.sizeof * elements.length);
402             return this;
403         }
404         else static assert(0, "operator not implemented");
405     }
406 
407     /// Support for the cat operator.
408     ref typeof(this)  opOpAssign(string op)(T aElement) @nogc
409     {
410         static if (op == "~")
411         {
412             grow;
413             opIndexAssign(aElement, _length-1);
414             return this;
415         }
416         else static assert(0, "operator not implemented");
417     }
418 
419     /// Support for output ranges.
420     alias put = opOpAssign!"~";
421 
422     /// ditto
423     void put(E)(auto ref E[] elements) @nogc
424     if (is(Unqual!E == T) || is(E == T))
425     {
426         const old = _length;
427         setLength(_length + elements.length);
428         moveMem( rwPtr(old), elements.ptr , T.sizeof * elements.length);
429     }
430 
431     /// Returns a slice of the array. The memory is not duplicated.
432     auto ref opSlice(bool dSlice = false)(size_t lo, size_t hi) return @nogc
433     {
434         static if (dSlice)
435         {
436             return (cast(T*) _elems)[lo..hi];
437         }
438         else
439         {
440             Array!T result;
441             result.length = hi - lo;
442             moveMem(result.rwPtr(0), rwPtr(lo), (hi - lo) * T.sizeof);
443             return result;
444         }
445     }
446 
447     /// Returns the array as a D slice. The memory is not duplicated.
448     T[] opSlice() const
449     {
450         return (cast(T*) _elems)[0.._length];
451     }
452 
453     /// Support for filling the array with a single element.
454     void opSliceAssign()(T value) @nogc
455     {
456         rwPtr(0)[0.._length] = value;
457     }
458 
459     /// ditto
460     void opSliceAssign()(T value, size_t lo, size_t hi) @nogc
461     {
462         foreach (immutable i; lo .. hi)
463             *rwPtr(i) = value;
464     }
465 
466     /// Returns an input range with an assignable front.
467     auto range()
468     {
469         return Range(this, 0);
470     }
471 
472     /// Allows to use the array as a D built-in array.
473     alias opSlice this;
474 }
475 ///
476 unittest
477 {
478     Array!int a;
479     a.length = 2;
480     a[] = 1;
481     assert(a[0] == 1);
482     assert(a[1] == 1);
483 }
484 
485 unittest
486 {
487     import std.range.primitives;
488     static assert(isOutputRange!(Array!int, int));
489     Array!(char) a;
490     a.put("someString");
491 }
492 
493 
494 unittest
495 {
496     alias Key = string;
497     alias A = Array!int;
498     A[Key] x;
499     //x["a"] = [0];
500 }
501 
502 unittest
503 {
504     // init-index
505     Array!size_t a;
506     a.length = 2;
507     a[0] = 8;
508     a[1] = 9;
509     assert( a[0] == 8);
510     assert( a[1] == 9);
511     assert( a[$-1] == 9);
512 
513     Array!int b = Array!int(0,1,2,3,4,5,6);
514     assert( b.length == 7);
515     assert( b[$-1] == 6);
516 
517     Array!float floatarr = Array!float ([0.0f, 0.1f, 0.2f, 0.3f, 0.4f]);
518     assert( floatarr.length == 5);
519     assert( floatarr[0] == 0.0f);
520     assert( floatarr[1] == 0.1f);
521     assert( floatarr[2] == 0.2f);
522     assert( floatarr[3] == 0.3f);
523     assert( floatarr[4] == 0.4f);
524 
525     // loops
526     int i;
527     foreach (float aflt; floatarr)
528     {
529         float v = i * 0.1f;
530         assert( aflt == v);
531         i++;
532     }
533     foreach_reverse(float aflt; floatarr)
534     {
535         i--;
536         float v = i * 0.1f;
537         assert( aflt == v);
538     }
539 
540     // opEquals
541     auto nativeArr = [111u, 222u, 333u, 444u, 555u];
542     auto arrcpy1 = Array!uint(111u, 222u, 333u, 444u, 555u);
543     auto arrcpy2 = Array!uint(111u, 222u, 333u, 444u, 555u);
544     assert( arrcpy1 == nativeArr );
545     assert( arrcpy2 == nativeArr );
546     assert( arrcpy1 == arrcpy2 );
547     arrcpy2[0] = 0;
548     assert( arrcpy1 != arrcpy2 );
549     arrcpy1.length = 3;
550     assert( nativeArr != arrcpy1 );
551     arrcpy1.length = 0;
552     arrcpy2.length = 0;
553     assert( arrcpy1 == arrcpy2 );
554 
555     // opSlice
556     Array!float g0 = floatarr[1..4];
557     assert( g0[0] ==  floatarr[1]);
558     assert( g0[2] ==  floatarr[3]);
559     Array!float g1 = floatarr;
560     assert( g1[0] ==  floatarr[0]);
561     assert( g1[4] ==  floatarr[4]);
562 
563     // opSliceAssign
564     g1[] = 0.123456f;
565     assert( g1[0] == 0.123456f);
566     assert( g1[3] == 0.123456f);
567     g1[0..1] = 0.654321f;
568     assert( g1[0] == 0.654321f);
569     assert( g1[1] == 0.123456f);
570     assert( g1[2] == 0.123456f);
571 
572     // huge
573     a.length = 10_000_000;
574     a[$-1] = a.length-1;
575     assert(a[a.length-1] == a.length-1);
576     a.length = 10;
577     a.length = 10_000_000;
578     a[$-1] = a.length-1;
579     assert(a[$-1] == a.length-1);
580 }
581 
582 unittest
583 {
584     Array!char a = "123456";
585     Array!char b = a;
586     assert(b.length == 6);
587     assert(b == "123456");
588     destructEach(a,b);
589 }
590 
591 unittest
592 {
593     static int c;
594     static struct S{int i = 1; ~this() @nogc {c = 1;}}
595     Array!S array;
596     assert(array.toString == "[]");
597     array.length = 1;
598     assert(array[0].i == 1);
599     array.length = 0;
600     assert(c);
601 }
602 
603 unittest
604 {
605     int[] source = [0,1,2];
606     Array!int a = source;
607     assert(a == source);
608     assert(a.dup == source);
609     destruct(a);
610 }
611 
612 @nogc unittest
613 {
614     static int[] source = [0,1,2,3];
615     static int[] r = [0,2,3];
616     Array!int a = source;
617     assert(a == source);
618     a = a[0..1] ~ a[2..$];
619     assert(a == r);
620     destruct(a);
621 }
622 
623 @nogc unittest
624 {
625     static int[] aa = [0,1];
626     static int[] bb = [2,3];
627     static int[] r0 = [0,1,2,3];
628     static int[] r1 = [0,1,2,3,0,1,2,3];
629     Array!int a = aa;
630     Array!int b = bb;
631     Array!int c = a ~ b;
632     assert(c  == r0);
633     assert(c ~ c == r1);
634     destructEach(a, b, c);
635 }
636 
637 unittest
638 {
639     Array!(Array!(const(char))) a;
640     a.length = 2;
641     a[0] = "first";
642     a[1] = "second".dup;
643     destruct(a);
644 }
645 
646 private mixin template ListHelpers(T)
647 {
648     static if (is (T == class))
649     {
650         final public T addNewItem(A...)(A a)
651         {
652             T result = construct!T(a);
653             add(result);
654             return result;
655         }
656     }
657     else static if (is (T == struct))
658     {
659         final public T * addNewItem(A...)(A a)
660         {
661             T * result = construct!T(a);
662             add(result);
663             return result;
664         }
665     }
666     else static if (isPointer!T)
667     {
668         final public T addNewItem(A...)(A a)
669         {
670             T result = newPtr!(PointerTarget!T)(a);
671             add(result);
672             return result;
673         }
674     }
675 
676     alias opDollar = count;
677 }
678 
679 
680 /**
681  * A list, fast to be iterated, slow to be reorganized.
682  * Encapsulates an Array!T and interfaces it as a list.
683  */
684 class ContiguousList(T)
685 {
686     mixin ListHelpers!T;
687     mixin inheritedDtor;
688 
689 private:
690 
691         @NoGc Array!T _items;
692 
693 
694 public:
695 
696     ///
697     this(A...)(A elements)
698     {
699         _items = Array!T(elements);
700     }
701 
702     ~this()
703     {
704         _items.length = 0;
705     }
706 
707     /// Support for the array syntax.
708     ref T opIndex(ptrdiff_t i)
709     {
710         return _items[i];
711     }
712 
713     /// Support for the array syntax.
714     void opIndexAssign(T item, size_t i)
715     {
716         _items[i] = item;
717     }
718 
719     /// Support for the foreach operator.
720     int opApply(scope int delegate(ref T) dg)
721     {
722         int result;
723         foreach (immutable i; 0 .. _items.length)
724         {
725             result = dg(_items[i]);
726             if (result) break;
727         }
728         return result;
729     }
730 
731     /// Support for the foreach_reverse operator.
732     int opApplyReverse(scope int delegate(ref T) dg)
733     {
734         int result;
735         foreach_reverse(immutable i; 0 .. _items.length)
736         {
737             result = dg(_items[i]);
738             if (result) break;
739         }
740         return result;
741     }
742 
743     /// Replaces the items with the content of a D T[].
744     void opAssign(T[] items)
745     {
746         _items.opAssign(items);
747     }
748 
749     /// Replaces the items with the content of an Array!T.
750     void opAssign(Array!T items)
751     {
752         _items.opAssign(items);
753     }
754 
755     deprecated("formerly implemented for the List interface")
756     T last()
757     {
758         return _items[$-1];
759     }
760 
761     deprecated("formerly implemented for the List interface")
762     T first()
763     {
764         return _items[0];
765     }
766 
767     /**
768      * Tries to find an item in the list.
769      *
770      * Params:
771      *      item = the item to find.
772      * Returns:
773      *      -1 if item is not present otherwise its index.
774      */
775     ptrdiff_t find(T item)
776     {
777         ptrdiff_t result = -1;
778         foreach (immutable i; 0 .. _items.length)
779         {
780             if (_items[i] == item)
781             {
782                 result = i;
783                 break;
784             }
785         }
786         return result;
787     }
788 
789     /**
790      * Adds an item at the end of the list and returns its index.
791      *
792      * Returns:
793      *      The last item index.
794      */
795     ptrdiff_t add(T item)
796     {
797         _items.grow;
798         _items[$-1] = item;
799         return _items.length - 1;
800     }
801 
802     /**
803      * Adds items at the end of the list.
804      *
805      * Returns:
806      *      The last item index.
807      */
808     ptrdiff_t add(I)(I items)
809     {
810         _items ~= items;
811         return _items.length - 1;
812     }
813 
814     /**
815      * Inserts an item at the beginning of the list.
816      *
817      * In a Contiguous list, add() should be preferred over insert().
818      *
819      * Returns:
820      *      Always 0.
821      */
822     ptrdiff_t insert(T item)
823     {
824         _items.grow;
825         memmove(_items.ptr + T.sizeof, _items.ptr, (_items.length - 1) * T.sizeof);
826         _items[0] = item;
827         return 0;
828     }
829 
830     /**
831      * Inserts an item at a given position.
832      *
833      * In a Contiguous list, add() should ne preferred over insert().
834      *
835      * Params:
836      *      position = The position where to insert.
837      *      item = The item to insert.
838      * Returns:
839      *      The item index, position if it was valid.
840      */
841     ptrdiff_t insert(size_t position, T item)
842     {
843         if (position == 0)
844             return insert(item);
845         else if (position >= _items.length)
846             return add(item);
847         else
848         {
849             _items.grow;
850             memmove(_items.ptr + T.sizeof * position + 1,
851                     _items.ptr + T.sizeof * position,
852                     (_items.length - 1 - position) * T.sizeof);
853             _items[position] = item;
854             return position;
855         }
856     }
857 
858     /**
859      * Exchanges the positions of two items.
860      *
861      * Params:
862      *      item1 = The first item.
863      *      item2 = The second item.
864      */
865     void swapItems(T item1, T item2)
866     in
867     {
868         assert(item1 != item2);
869     }
870     body
871     {
872         ptrdiff_t i1 = find(item1);
873         ptrdiff_t i2 = find(item2);
874         if (i1 != -1 && i2 != -1)
875         {
876             _items[i1] = _items[i2];
877             _items[i2] = item1;
878         }
879     }
880 
881     /**
882      * Exchanges the positions of two items.
883      *
884      * Params:
885      *      index1 = The first item index.
886      *      index2 = The second item index.
887      */
888     void swapIndexes(size_t index1, size_t index2)
889     {
890         if (index1 == index2) return;
891         if ((index1 >= _items.length) | (index2 >= _items.length)) return;
892 
893         auto old = _items[index1];
894         _items[index1] = _items[index2];
895         _items[index2] = old;
896     }
897 
898     /**
899      * Removes an item from the list.
900      *
901      * Params:
902      *      item = The item to remove.
903      * Returns:
904      *      true if the item wasin the list, false otherwise.
905      */
906     bool remove(T item)
907     {
908         auto i = find(item);
909         auto result = (i != -1);
910         if (result)
911             extract(i);
912         return result;
913     }
914 
915     /**
916      * Removes an item from the list.
917      *
918      * Params:
919      *      index = The index of the item to remove.
920      * Returns:
921      *      The item that's been removed.
922      */
923     T extract(size_t index)
924     {
925         T result = _items[index];
926         if (index == _items.length-1)
927         {
928             _items.shrink;
929         }
930         else if (index == 0)
931         {
932             memmove(_items.ptr, _items.ptr + T.sizeof, (_items.length - 1) * T.sizeof);
933             _items.shrink;
934         }
935         else
936         {
937             Ptr fromPtr = _items.ptr + T.sizeof * index;
938             memmove(fromPtr, fromPtr + T.sizeof, (_items.length - index) * T.sizeof);
939             _items.shrink;
940         }
941         return result;
942     }
943 
944     /**
945      * Empties the list.
946      */
947     void clear()
948     {
949         _items.length = 0;
950     }
951 
952     /**
953      * Returns the items count.
954      */
955     final size_t count() const pure nothrow @safe
956     {
957         return _items.opDollar();
958     }
959 
960     /**
961      * Returns the internal array.
962      *
963      * ContiguousList doesn't contain any other hidden field
964      * and the container can be modified without altering the
965      * state of the list.
966      */
967     final ref Array!T array() nothrow @safe
968     {
969         return _items;
970     }
971 }
972 
973 
974 /**
975  * Payload for the dynamic list.
976  */
977 private template dlistPayload(T)
978 {
979     private static const prevOffs = 0;
980     private static const nextOffs = size_t.sizeof;
981     private static const dataOffs = size_t.sizeof + size_t.sizeof;
982 
983     @nogc nothrow private:
984 
985     void* newPld(void* aPrevious, void* aNext, ref T aData) @trusted
986     {
987         auto result = getMem( 2 * size_t.sizeof + T.sizeof);
988         if (result)
989         {
990             *cast(size_t*)  (result + prevOffs) = cast(size_t) aPrevious;
991             *cast(size_t*)  (result + nextOffs) = cast(size_t) aNext;
992             static if (is(T == struct))
993             {
994                 static T init;
995                 copyMem(result + dataOffs, &init, T.sizeof);
996             }
997             *cast(T*) (result + dataOffs) = aData;
998         }
999         return result;
1000     }
1001     void freePld(void* aPayload) @trusted
1002     in
1003     {
1004         assert(aPayload);
1005     }
1006     body
1007     {
1008         static if (is(T==struct))
1009         {
1010             destruct(getData(aPayload));
1011         }
1012         freeMem(aPayload);
1013     }
1014 
1015     void setPrev(void* aPayload, void* aPrevious) @trusted
1016     in
1017     {
1018         assert(aPayload);
1019     }
1020     body
1021     {
1022         *cast(void**) (aPayload + prevOffs) = aPrevious;
1023     }
1024 
1025     void setNext(void* aPayload, void* aNext) @trusted
1026     in
1027     {
1028         assert(aPayload);
1029     }
1030     body
1031     {
1032         *cast(void**) (aPayload + nextOffs) = aNext;
1033     }
1034 
1035     void setData(void* aPayload, ref T aData) @trusted
1036     in
1037     {
1038         assert(aPayload);
1039     }
1040     body
1041     {
1042         *cast(T*) (aPayload + dataOffs) = aData;
1043         static if (is(T == struct) && hasMember!(T, "__postblit") && isCopyable!T )
1044         {
1045             (cast(T*) (aPayload + dataOffs)).__postblit();
1046         }
1047     }
1048 
1049     void* getPrev(void* aPayload) @trusted
1050     {
1051         version(X86) asm @nogc nothrow
1052         {
1053             naked;
1054             mov     EAX, [EAX + prevOffs];
1055             ret;
1056         }
1057         else version(Win64) asm @nogc nothrow
1058         {
1059             naked;
1060             mov     RAX, [RCX + prevOffs];
1061             ret;
1062         }
1063         else version(Nux64) asm @nogc nothrow
1064         {
1065             naked;
1066             mov     RAX, [RDI + prevOffs];
1067             ret;
1068         }
1069         else return *cast(void**) (aPayload + prevOffs);
1070     }
1071 
1072     void* getNext(void* aPayload) @trusted
1073     {
1074         version(X86) asm @nogc nothrow
1075         {
1076             naked;
1077             mov     EAX, [EAX + nextOffs];
1078             ret;
1079         }
1080         else version(Win64) asm @nogc nothrow
1081         {
1082             naked;
1083             mov     RAX, [RCX + nextOffs];
1084             ret;
1085         }
1086         else version(Nux64) asm @nogc nothrow
1087         {
1088             naked;
1089             mov     RAX, [RDI + nextOffs];
1090             ret;
1091         }
1092         else return *cast(void**) (aPayload + nextOffs);
1093     }
1094 
1095     ref T getData(void* aPayload) @trusted
1096     {
1097         /*version(X86) asm @nogc nothrow
1098         {
1099             naked;
1100             mov     EAX, [EAX + dataOffs];
1101             ret;
1102         }
1103         else version(Win64) asm @nogc nothrow
1104         {
1105             naked;
1106             mov     RAX, [RCX + dataOffs];
1107             ret;
1108         }
1109         else version(Nux64) asm @nogc nothrow
1110         {
1111             naked;
1112             mov     RAX, [RDI + dataOffs];
1113             ret;
1114         }
1115         else*/ return *cast(T*) (aPayload + dataOffs);
1116     }
1117 }
1118 
1119 
1120 /**
1121  * A List implementation, slow to be iterated, fast to be reorganized.
1122  * This is a standard doubly linked list, with GC-free heap allocations.
1123  */
1124 class DynamicList(T)
1125 {
1126     mixin ListHelpers!T;
1127     mixin inheritedDtor;
1128 
1129 private:
1130 
1131     size_t _count;
1132     void* _last;
1133     void* _first;
1134     alias payload = dlistPayload!T;
1135 
1136     void* getPayloadFromIx(size_t index) @safe @nogc nothrow
1137     {
1138         void* current = _first;
1139         foreach (immutable i; 0 .. index)
1140             current = payload.getNext(current);
1141         return current;
1142     }
1143 
1144     void* getPayloadFromDt(ref T item) @trusted
1145     {
1146         void* current = _first;
1147         while (current)
1148         {
1149             if (payload.getData(current) == item)
1150                 break;
1151             current = payload.getNext(current);
1152         }
1153         return current;
1154     }
1155 
1156 public:
1157 
1158     ///
1159     this(A...)(A elements)
1160     {
1161         foreach (elem; elements)
1162             add(elem);
1163     }
1164 
1165     ~this()
1166     {
1167         clear;
1168     }
1169 
1170     /// Support for the array syntax.
1171     ref T opIndex(ptrdiff_t i) @safe @nogc nothrow
1172     {
1173         void* _pld = getPayloadFromIx(i);
1174         return payload.getData(_pld);
1175     }
1176 
1177     /// Support for the array syntax.
1178     void opIndexAssign(ref T item, size_t i) @safe @nogc nothrow
1179     {
1180         void* _pld = getPayloadFromIx(i);
1181         payload.setData(_pld, item);
1182     }
1183 
1184     /// Support for the foreach operator.
1185     int opApply(int delegate(ref T) dg) @trusted
1186     {
1187         int result;
1188         void* current = _first;
1189         while (current)
1190         {
1191             result = dg(payload.getData(current));
1192             if (result) break;
1193             current = payload.getNext(current);
1194         }
1195         return result;
1196     }
1197 
1198     /// Support for the foreach_reverse operator.
1199     int opApplyReverse(int delegate(ref T) dg) @trusted
1200     {
1201         int result;
1202         void* current = _last;
1203         while (current)
1204         {
1205             result = dg(payload.getData(current));
1206             if (result) break;
1207             current = payload.getPrev(current);
1208         }
1209         return result;
1210     }
1211 
1212     /// Replaces the items with the content of a D T[].
1213     void opAssign(T[] elems) @trusted @nogc
1214     {
1215         clear;
1216         foreach (elem; elems)
1217             add(elem);
1218     }
1219 
1220     /// Returns the first element.
1221     T last() @safe @nogc nothrow
1222     {
1223         return payload.getData(_last);
1224     }
1225 
1226     /// Returns the last element.
1227     T first() @safe @nogc nothrow
1228     {
1229         return payload.getData(_first);
1230     }
1231 
1232     /**
1233      * Tries to find an item in the list.
1234      *
1235      * Params:
1236      *      item = the item to find.
1237      * Returns:
1238      *      -1 if item is not present otherwise its index.
1239      */
1240     ptrdiff_t find(T item) @trusted
1241     {
1242         void* current = _first;
1243         ptrdiff_t result = -1;
1244         while (current)
1245         {
1246             result++;
1247             if (payload.getData(current) == item)
1248                 return result++;
1249             current = payload.getNext(current);
1250         }
1251         return -1;
1252     }
1253 
1254     /**
1255      * Adds an item at the end of the list and returns its index.
1256      */
1257     ptrdiff_t add(ref T item) @trusted @nogc
1258     {
1259         if (!_first)
1260             return insert(item);
1261         else
1262         {
1263             void* _pld = payload.newPld(_last, null, item);
1264             payload.setNext(_last, _pld);
1265             _last = _pld;
1266             return _count++;
1267         }
1268     }
1269 
1270     /// ditto
1271     ptrdiff_t add(T item) @trusted @nogc
1272     {
1273         return add(item);
1274     }
1275 
1276     /**
1277      * Adds items at the end of the list and returns the last item index.
1278      */
1279     ptrdiff_t add(T[] items) @trusted @nogc
1280     {
1281         foreach (item; items)
1282             add(item);
1283         return _count - 1;
1284     }
1285 
1286     /**
1287      * Inserts an item at the beginning of the list.
1288      */
1289     ptrdiff_t insert(ref T item) @trusted @nogc
1290     {
1291         void* _pld = payload.newPld(null, _first, item);
1292         if (_first) payload.setPrev(_first, _pld);
1293         else _last = _pld;
1294         _first = _pld;
1295         ++_count;
1296         return 0;
1297     }
1298 
1299     /// ditto
1300     ptrdiff_t insert(T item) @trusted @nogc
1301     {
1302         return insert(item);
1303     }
1304 
1305     /**
1306      * Inserts an item at a given position.
1307      *
1308      * Params:
1309      *      position = The position where to insert.
1310      *      item = The item to insert.
1311      * Returns:
1312      *      The item index, position if it was valid.
1313      */
1314     ptrdiff_t insert(size_t position, ref T item) @trusted @nogc
1315     {
1316         if (!_first || position == 0)
1317         {
1318             return insert(item);
1319         }
1320         else if (position >= _count)
1321         {
1322             return add(item);
1323         }
1324         else
1325         {
1326             void* old = getPayloadFromIx(position);
1327             void* prev = payload.getPrev(old);
1328             void* _pld = payload.newPld(prev, old, item);
1329             payload.setPrev(old, _pld);
1330             payload.setNext(prev, _pld);
1331             _count++;
1332             return position;
1333         }
1334     }
1335 
1336     /// ditto
1337     ptrdiff_t insert(size_t position, T item) @trusted @nogc
1338     {
1339         return insert(position, item);
1340     }
1341 
1342     /**
1343      * Exchanges the positions of two items.
1344      *
1345      * Params:
1346      *      item1 = The first item.
1347      *      item2 = The second item.
1348      */
1349     void swapItems(T item1, T item2) @trusted
1350     {
1351         void* _pld1 = getPayloadFromDt(item1);
1352         if (_pld1 == null) return;
1353         void* _pld2 = getPayloadFromDt(item2);
1354         if (_pld2 == null) return;
1355 
1356         T _data1 = payload.getData(_pld1);
1357         T _data2 = payload.getData(_pld2);
1358 
1359         payload.setData(_pld1, _data2);
1360         payload.setData(_pld2, _data1);
1361     }
1362 
1363     /**
1364      * Exchanges the positions of two items.
1365      *
1366      * Params:
1367      *      index1 = The first item index.
1368      *      index2 = The second item index.
1369      */
1370     void swapIndexes(size_t index1, size_t index2) @trusted
1371     {
1372         void* _pld1 = getPayloadFromIx(index1);
1373         if (_pld1 == null) return;
1374         void* _pld2 = getPayloadFromIx(index2);
1375         if (_pld2 == null) return;
1376 
1377         T _data1 = payload.getData(_pld1);
1378         T _data2 = payload.getData(_pld2);
1379 
1380         payload.setData(_pld1, _data2);
1381         payload.setData(_pld2, _data1);
1382     }
1383 
1384     /**
1385      * Removes an item from the list.
1386      *
1387      * Params:
1388      *      item = The item to remove.
1389      * Returns:
1390      *      true if the item wasin the list, false otherwise.
1391      */
1392     bool remove(T item) @trusted
1393     {
1394         void* _pld = getPayloadFromDt(item);
1395         if (!_pld) return false;
1396 
1397         void* _prev = payload.getPrev(_pld);
1398         void* _next = payload.getNext(_pld);
1399         if (_last == _pld && _prev)
1400         {
1401             _last = _prev;
1402             payload.setNext(_last, null);
1403             _next = null;
1404         }
1405         else if (_first == _pld && _next)
1406         {
1407             _first = _next;
1408             payload.setPrev(_first, null);
1409             _prev = null;
1410         }
1411         else if (_prev && _next)
1412         {
1413             if (_prev) payload.setNext(_prev, _next);
1414             if (_next) payload.setPrev(_next, _prev);
1415         }
1416         payload.freePld(_pld);
1417         if (_last == _first && _last == _pld)
1418         {
1419             _last = null;
1420             _first = null;
1421         }
1422         --_count;
1423         return true;
1424     }
1425 
1426     /**
1427      * Removes an item from the list.
1428      *
1429      * Params:
1430      *      index = The index of the item to remove.
1431      * Returns:
1432      *      The item that's been removed.
1433      */
1434     T extract(size_t index) @trusted
1435     {
1436         T result;
1437         void* _pld = getPayloadFromIx(index);
1438         if (!_pld) return result;
1439         result = payload.getData(_pld);
1440 
1441         void* _prev = payload.getPrev(_pld);
1442         void* _next = payload.getNext(_pld);
1443         if (_last == _pld && _prev)
1444         {
1445             _last = _prev;
1446             payload.setNext(_prev, null);
1447             _next = null;
1448         }
1449         else if (_first == _pld && _next)
1450         {
1451             _first = _next;
1452             payload.setPrev(_next, null);
1453             _prev = null;
1454         }
1455         else if (_prev && _next)
1456         {
1457             payload.setNext(_prev, _next);
1458             payload.setPrev(_next, _prev);
1459         }
1460         payload.freePld(_pld);
1461         if (_last == _first && _last == _pld)
1462         {
1463             _last = null;
1464             _first = null;
1465         }
1466         --_count;
1467         return result;
1468     }
1469 
1470     /**
1471      * Empties the list.
1472      */
1473     void clear() @trusted @nogc
1474     {
1475         void* current = _first;
1476         while (current)
1477         {
1478             void* _old = current;
1479             current = payload.getNext(current);
1480             payload.freePld(_old);
1481         }
1482         _count = 0;
1483         _first = null;
1484         _last = null;
1485     }
1486 
1487     /**
1488      * Returns the items count.
1489      */
1490     size_t count() @trusted @nogc
1491     {
1492         return _count;
1493     }
1494 
1495     Range opSlice()
1496     {
1497         return Range(_first, _last);
1498     }
1499 
1500     Range opSlice(size_t lo, size_t hi) @trusted
1501     {
1502         return Range(getPayloadFromIx(lo), getPayloadFromIx(hi));
1503     }
1504 
1505     alias length = count;
1506 
1507     alias put = add;
1508 
1509     private struct Range
1510     {
1511         private void* _begin;
1512         private void* _end;
1513 
1514         private this(void* b, void* e)
1515         {
1516             _begin = b;
1517             _end = e;
1518         }
1519 
1520         /**
1521          * Returns $(D true) if the range is _empty
1522          */
1523         bool empty() const @property
1524         {
1525             return _begin is null;
1526         }
1527 
1528         /**
1529          * Returns the first element in the range
1530          */
1531         T front() @safe @nogc
1532         {
1533             return payload.getData(_begin);
1534         }
1535 
1536         /**
1537          * Returns the last element in the range
1538          */
1539         T back() @safe @nogc
1540         {
1541             return payload.getData(_end);
1542         }
1543 
1544         /**
1545          * pop the front element from the range
1546          *
1547          * complexity: amortized $(BIGOH 1)
1548          */
1549         void popFront() @safe @nogc
1550         {
1551             _begin = payload.getNext(_begin);
1552         }
1553 
1554         /**
1555          * pop the back element from the range
1556          *
1557          * complexity: amortized $(BIGOH 1)
1558          */
1559         void popBack() @safe @nogc
1560         {
1561             _end = payload.getPrev(_end);
1562         }
1563 
1564         /**
1565          * Trivial _save implementation, needed for $(D isForwardRange).
1566          */
1567         Range save() @safe @nogc
1568         {
1569             return this;
1570         }
1571 
1572         size_t length() @safe @nogc
1573         {
1574             size_t result;
1575             auto cur = _begin;
1576             while (cur)
1577             {
1578                 cur = payload.getNext(cur);
1579                 ++result;
1580             }
1581             return result;
1582         }
1583     }
1584 }
1585 
1586 unittest
1587 {
1588     struct  S{int a,b; int notPod(){return a;}}
1589     class   C{int a,b; int notPod(){return a;}}
1590 
1591     void test(alias T )()
1592     {
1593         // struct as ptr
1594         alias SList = T!(S*);
1595         S[200] arrayOfS;
1596         SList sList = construct!SList;
1597         scope(exit) sList.destruct;
1598 
1599         for (auto i = 0; i < arrayOfS.length; i++)
1600         {
1601             arrayOfS[i].a = i;
1602             sList.add( &arrayOfS[i] );
1603             assert( sList[i] == &arrayOfS[i]);
1604             assert( sList.count == i + 1);
1605             assert( sList.find( &arrayOfS[i] ) == i);
1606         }
1607 
1608         sList.swapIndexes(0,1);
1609         assert( sList.find(&arrayOfS[0]) == 1 );
1610         assert( sList.find(&arrayOfS[1]) == 0 );
1611         sList.swapIndexes(0,1);
1612         assert( sList.find(&arrayOfS[0]) == 0 );
1613         assert( sList.find(&arrayOfS[1]) == 1 );
1614         sList.remove(sList.last);
1615         assert( sList.count == arrayOfS.length -1 );
1616         sList.clear;
1617         assert( sList.count == 0 );
1618         for (auto i = 0; i < arrayOfS.length; i++)
1619         {
1620             sList.add( &arrayOfS[i] );
1621         }
1622         sList.extract(50);
1623         assert( sList.find(&arrayOfS[50]) == -1 );
1624         sList.insert(50,&arrayOfS[50]);
1625         assert( sList.find(&arrayOfS[50]) == 50 );
1626         sList.extract(50);
1627         sList.insert(&arrayOfS[50]);
1628         assert( sList.find(&arrayOfS[50]) == 0 );
1629         sList.clear;
1630         assert( sList.count == 0 );
1631         for (auto i = 0; i < arrayOfS.length; i++)
1632         {
1633             sList.add( &arrayOfS[i] );
1634         }
1635 
1636         // class as ref
1637         alias CList = T!C;
1638         C[200] arrayOfC;
1639         CList cList = construct!CList;
1640         scope(exit) cList.destruct;
1641 
1642         for (auto i = 0; i < arrayOfC.length; i++)
1643         {
1644             arrayOfC[i] = construct!C;
1645             arrayOfC[i].a = i;
1646             cList.add( arrayOfC[i] );
1647             assert( cList[i] is arrayOfC[i]);
1648             assert( cList.count == i + 1);
1649             assert( cList.find( arrayOfC[i] ) == i);
1650         }
1651         cList.swapIndexes(0,1);
1652         assert( cList.find(arrayOfC[0]) == 1 );
1653         assert( cList.find(arrayOfC[1]) == 0 );
1654         cList.swapIndexes(0,1);
1655         assert( cList.find(arrayOfC[0]) == 0 );
1656         assert( cList.find(arrayOfC[1]) == 1 );
1657         cList.remove(cList.last);
1658         assert( cList.count == arrayOfC.length -1 );
1659         cList.clear;
1660         assert( cList.count == 0 );
1661         for (auto i = 0; i < arrayOfC.length; i++)
1662         {
1663             cList.add( arrayOfC[i] );
1664         }
1665         cList.extract(50);
1666         assert( cList.find(arrayOfC[50]) == -1 );
1667         cList.insert(50,arrayOfC[50]);
1668         assert( cList.find(arrayOfC[50]) == 50 );
1669         cList.extract(50);
1670         cList.insert(arrayOfC[50]);
1671         assert( cList.find(arrayOfC[50]) == 0 );
1672         cList.clear;
1673         assert( cList.count == 0 );
1674         for (auto i = 0; i < arrayOfC.length; i++)
1675         {
1676             cList.add( arrayOfC[i] );
1677         }
1678 
1679         // cleanup of internally allocated items.
1680         C itm;
1681         cList.clear;
1682         assert(cList.count == 0);
1683         cList.addNewItem;
1684         cList.addNewItem;
1685         assert(cList.count == 2);
1686 
1687         itm = cList.extract(0);
1688         assert(itm);
1689         itm.destruct;
1690         assert(cList.count == 1);
1691         itm = cList.extract(0);
1692         assert(itm);
1693         itm.destruct;
1694         assert(cList.count == 0);
1695 
1696         cList.add(arrayOfC[0]);
1697         cList[0] = arrayOfC[1];
1698         assert(cList.find(arrayOfC[0]) == -1);
1699         assert(cList.find(arrayOfC[1]) == 0);
1700         cList.clear;
1701 
1702         cList = arrayOfC[10..20];
1703         assert(cList.count == 10);
1704         assert(cList[0] == arrayOfC[10]);
1705         assert(cList[9] == arrayOfC[19]);
1706 
1707         cList.clear;
1708         cList.insert(0, arrayOfC[24]);
1709         assert(cList[0] == arrayOfC[24]);
1710         cList.insert(123456, arrayOfC[25]);
1711         assert(cList.count == 2);
1712         assert(cList[1] == arrayOfC[25]);
1713         cList.swapItems(arrayOfC[24],arrayOfC[25]);
1714         assert(cList[0] == arrayOfC[25]);
1715         assert(cList[1] == arrayOfC[24]);
1716         cList.swapIndexes(0,1);
1717         assert(cList[0] == arrayOfC[24]);
1718         assert(cList[1] == arrayOfC[25]);
1719         C elem = cList.extract(1);
1720         assert(elem is arrayOfC[25]);
1721         assert(cList.count == 1);
1722 
1723         size_t i;
1724         cList = arrayOfC[0..10];
1725         foreach (C c; cList)
1726         {
1727             assert(c is arrayOfC[i]);
1728             ++i;
1729         }
1730         foreach_reverse(C c; cList)
1731         {
1732             --i;
1733             assert(c is arrayOfC[i]);
1734         }
1735         assert(cList.first == arrayOfC[0]);
1736         assert(cList.last == arrayOfC[9]);
1737 
1738         cList.clear;
1739         cList.add(arrayOfC[0..10]);
1740         assert(cList.count == 10);
1741         assert(cList.first == arrayOfC[0]);
1742         assert(cList.last == arrayOfC[9]);
1743 
1744         foreach(o; arrayOfC)
1745             destruct(o);
1746     }
1747 
1748     test!(ContiguousList);
1749     test!(DynamicList);
1750 }
1751 
1752 unittest
1753 {
1754     alias List = DynamicList!(Array!int);
1755     Array!int a;
1756     Array!int b = [2,3];
1757     List lst = construct!List();
1758     lst.add(a);
1759     lst.add(b);
1760     assert(lst[0].ptr !is a.ptr);
1761     destructEach(a,b, lst);
1762 }
1763 
1764 /**
1765  * TreeItemSiblings is an input range that allows to
1766  * iterate the children of a TreeItem.
1767  */
1768 struct TreeItemChildren(T)
1769 {
1770 
1771 private:
1772 
1773     T _front;
1774 
1775 public:
1776 
1777     /// See $(D initialize()).
1778     this(TT)(auto ref TT t)
1779     if (is(TT == T))
1780     {
1781         initialize(t);
1782     }
1783 
1784     /// Initializes the range from a parent.
1785     void initialize(TT)(auto ref TT t)
1786     if (is(TT == T))
1787     {
1788         _front = t.firstChild;
1789     }
1790 
1791     ///
1792     ref T front()
1793     {
1794         return _front;
1795     }
1796 
1797     ///
1798     void popFront()
1799     {
1800         _front = _front.nextSibling;
1801     }
1802 
1803     ///
1804     bool empty()
1805     {
1806         return _front is null;
1807     }
1808 
1809     /**
1810      * Support for the array syntax.
1811      * Should be avoided in for() loops.
1812      */
1813     T opIndex(ptrdiff_t index)
1814     in
1815     {
1816         assert(_front);
1817     }
1818     body
1819     {
1820         T result = _front;
1821         ptrdiff_t cnt;
1822         while (true)
1823         {
1824             if (cnt++ == index || !result)
1825                 return result;
1826             result = result.nextSibling;
1827         }
1828     }
1829 
1830     /// Support the array syntax.
1831     void opIndexAssign(T item, size_t i)
1832     in
1833     {
1834         assert(_front);
1835         assert(item);
1836     }
1837     body
1838     {
1839         auto old = opIndex(i);
1840         if (!old)
1841             _front.addSibling(item);
1842         else
1843         {
1844             if (_front.findSibling(item) != -1)
1845                 _front.exchangeSibling(item,old);
1846             else
1847             {
1848                 _front.removeSibling(old);
1849                 _front.insertSibling(i,item);
1850             }
1851         }
1852     }
1853 }
1854 
1855 /**
1856  * TreeItemSiblings is an input range that allows to
1857  * iterate over the siblings of a TreeItem.
1858  */
1859 struct TreeItemSiblings(T)
1860 {
1861 
1862 private:
1863 
1864     T _front;
1865 
1866 public:
1867 
1868     /// See $(D initialize()).
1869     this(TT)(auto ref TT t)
1870     if (is(TT == T))
1871     {
1872         initialize(t);
1873     }
1874 
1875     /// Initializes the range from one of the siblings.
1876     void initialize(TT)(auto ref TT t)
1877     if (is(TT == T))
1878     {
1879         TT tt =t;
1880         if (tt.parent)
1881             _front = tt.parent.firstChild;
1882         else
1883         {
1884             while (tt.prevSibling !is null)
1885             {
1886                 tt = tt.prevSibling;
1887             }
1888             _front = tt;
1889         }
1890     }
1891 
1892     ///
1893     T front() @safe @nogc
1894     {
1895         return _front;
1896     }
1897 
1898     ///
1899     void popFront()
1900     {
1901         _front = _front.nextSibling;
1902     }
1903 
1904     ///
1905     bool empty() @safe @nogc
1906     {
1907         return _front is null;
1908     }
1909 
1910     /**
1911      * Support for the array syntax.
1912      * Should be avoided in for loops.
1913      */
1914     T opIndex(ptrdiff_t index)
1915     in
1916     {
1917         assert(_front);
1918     }
1919     body
1920     {
1921         T result = _front;
1922         ptrdiff_t cnt;
1923         while (true)
1924         {
1925             if (cnt++ == index || !result)
1926                 return result;
1927             result = result.nextSibling;
1928         }
1929     }
1930 
1931     /// Support for the array syntax.
1932     void opIndexAssign(T item, size_t i)
1933     in
1934     {
1935         assert(_front);
1936     }
1937     body
1938     {
1939         if (!item)
1940             _front.removeSibling(i);
1941         else
1942         {
1943             auto old = opIndex(i);
1944             if (!old)
1945                 _front.addSibling(item);
1946             else
1947             {
1948                 if (_front.findSibling(item) != -1)
1949                     _front.exchangeSibling(item,old);
1950                 else
1951                 {
1952                     _front.removeSibling(old);
1953                     _front.insertSibling(i,item);
1954                 }
1955             }
1956         }
1957     }
1958 }
1959 
1960 /**
1961  * The TreeItem mixin turns its target into a tree item.
1962  */
1963 mixin template TreeItem()
1964 {
1965 
1966 protected:
1967 
1968     import iz.memory: construct, destruct;
1969 
1970     enum isStruct = is(typeof(this) == struct);
1971     static if (isStruct)
1972         alias TreeItemType = typeof(this)*;
1973     else
1974         alias TreeItemType = typeof(this);
1975 
1976     TreeItemType _prevSibling, _nextSibling, _firstChild, _parent;
1977     TreeItemSiblings!TreeItemType _siblings;
1978     TreeItemChildren!TreeItemType _children;
1979 
1980     import iz.streams: Stream, writeArray;
1981 
1982 public:
1983 
1984     /// Returns $(D this) when mixed in a class or $(D &this) in a struct.
1985     TreeItemType self()
1986     {
1987         static if (isStruct)
1988             return &this;
1989         else
1990             return this;
1991     }
1992 
1993     /**
1994      * Returns the previous TreeItem.
1995      */
1996     TreeItemType prevSibling()
1997     {
1998         return _prevSibling;
1999     }
2000 
2001     /**
2002      * Returns the next TreeItem.
2003      */
2004     TreeItemType nextSibling()
2005     {
2006         return _nextSibling;
2007     }
2008 
2009     /**
2010      * Returns the parent.
2011      */
2012     TreeItemType parent()
2013     {
2014         return _parent;
2015     }
2016 
2017     /**
2018      * Returns the first child.
2019      */
2020     TreeItemType firstChild()
2021     {
2022         return _firstChild;
2023     }
2024 
2025     /**
2026      * Returns an input range that allows to iterate the siblings.
2027      * The array syntax is also supported.
2028      */
2029     TreeItemSiblings!TreeItemType siblings()
2030     {
2031         _siblings.initialize(self);
2032         return _siblings;
2033     }
2034 
2035     /**
2036      * Returns an input range that allows to iterate the children.
2037      * The array syntax is also supported.
2038      */
2039     TreeItemChildren!TreeItemType children()
2040     {
2041         _children.initialize(self);
2042         return _children;
2043     }
2044 
2045 // siblings -------------------------------------------------------------------+
2046 
2047     /**
2048      * Constructs, adds to the back then returns a new sibling.
2049      * This method should be prefered over addChild and insertChild
2050      * if $(D deleteChildren()) is used.
2051      *
2052      * When TreeItem is mixed in a class a template parameter that specifies
2053      * the class type to return must be present, otherwise in both cases the
2054      * function passes the optional run-time parameters to the constructor.
2055      */
2056     static if (is(TreeItemType == class))
2057     {
2058         IT addNewSibling(IT,A...)(A a)
2059         if (is(IT : TreeItemType))
2060         {
2061             auto result = construct!IT(a);
2062             addSibling(result);
2063             return result;
2064         }
2065     }
2066     else
2067     {
2068         TreeItemType addNewSibling(A...)(A a)
2069         {
2070             TreeItemType result = construct!(typeof(this))(a);
2071             addSibling(result);
2072             return result;
2073         }
2074     }
2075 
2076     /**
2077      * Returns the last item.
2078      * The value returned is never null.
2079      */
2080     TreeItemType lastSibling()
2081     {
2082         TreeItemType result;
2083         result = self;
2084         while (result.nextSibling)
2085         {
2086             result = result.nextSibling;
2087         }
2088         return result;
2089     }
2090 
2091     /**
2092      * Returns the first item.
2093      * The value returned is never null.
2094      */
2095     TreeItemType firstSibling()
2096     {
2097         if (_parent)
2098             return _parent._firstChild;
2099         else
2100         {
2101             TreeItemType result;
2102             result = self;
2103             while (result.prevSibling)
2104             {
2105                 result = result.prevSibling;
2106             }
2107             return result;
2108         }
2109     }
2110 
2111     /**
2112      * Returns the index of sibling if it's found otherwise -1.
2113      */
2114     ptrdiff_t findSibling(TreeItemType sibling)
2115     in
2116     {
2117         assert(sibling);
2118     }
2119     body
2120     {
2121         auto current = self;
2122         while (current)
2123         {
2124             if (current is sibling) break;
2125             current = current.prevSibling;
2126         }
2127         if (!current)
2128         {
2129             current = self;
2130             while (current)
2131             {
2132                 if (current is sibling) break;
2133                 current = current.nextSibling;
2134             }
2135         }
2136         if (!current) return -1;
2137         return current.siblingIndex;
2138     }
2139 
2140     /**
2141      * Adds an item at the end of list.
2142      */
2143     void addSibling(TreeItemType sibling)
2144     in
2145     {
2146         assert(sibling);
2147     }
2148     body
2149     {
2150         if (sibling.hasSibling)
2151         {
2152             if (sibling.prevSibling !is null)
2153                 sibling.prevSibling.removeSibling(sibling);
2154             else
2155                 sibling.nextSibling.removeSibling(sibling);
2156         }
2157 
2158         auto oldlast = lastSibling;
2159         assert(oldlast);
2160         oldlast._nextSibling = sibling;
2161         sibling._prevSibling = oldlast;
2162         sibling._nextSibling = null;
2163         sibling._parent = parent;
2164     }
2165 
2166     /**
2167      * Inserts an item at the beginning of the list.
2168      */
2169     void insertSibling(TreeItemType sibling)
2170     in
2171     {
2172         assert(sibling);
2173     }
2174     body
2175     {
2176         if (sibling.hasSibling)
2177         {
2178             if (sibling.prevSibling !is null)
2179                 sibling.prevSibling.removeSibling(sibling);
2180             else
2181                 sibling.nextSibling.removeSibling(sibling);
2182         }
2183 
2184         auto oldfirst = firstSibling;
2185         assert(oldfirst);
2186         oldfirst._prevSibling = sibling;
2187         sibling._nextSibling = oldfirst;
2188         sibling._parent = parent;
2189 
2190         if (parent)
2191         {
2192             parent._firstChild = sibling;
2193         }
2194     }
2195 
2196     /**
2197      * Inserts a sibling.
2198      *
2199      * Params:
2200      *      index = The position where to insert.
2201      *      sibling = the item to insert.
2202      */
2203     void insertSibling(size_t index, TreeItemType sibling)
2204     in
2205     {
2206         assert(sibling);
2207     }
2208     body
2209     {
2210         if (sibling.hasSibling)
2211         {
2212             if (sibling.prevSibling !is null)
2213                 sibling.prevSibling.removeSibling(sibling);
2214             else
2215                 sibling.nextSibling.removeSibling(sibling);
2216         }
2217 
2218         const size_t cnt = siblingCount;
2219         if (index == 0) insertSibling(sibling);
2220         else if (index >= cnt) addSibling(sibling);
2221         else
2222         {
2223             size_t result = 1;
2224             auto old = firstSibling;
2225             while (old)
2226             {
2227                 if (result == index)
2228                 {
2229                     auto item1oldprev = old.prevSibling;
2230                     auto item1oldnext = old.nextSibling;
2231                     sibling._prevSibling = old;
2232                     sibling._nextSibling = item1oldnext;
2233                     old._nextSibling = sibling;
2234                     item1oldnext._prevSibling = sibling;
2235                     sibling._parent = _parent;
2236                     assert(sibling.siblingIndex == index);
2237 
2238                     return;
2239                 }
2240                 old = old.nextSibling;
2241                 result++;
2242             }
2243         }
2244     }
2245 
2246     /**
2247      * Exchanges the position of two siblings.
2248      */
2249     void exchangeSibling(TreeItemType sibling1, TreeItemType sibling2)
2250     in
2251     {
2252         assert(sibling1);
2253         assert(sibling2);
2254         assert(sibling1._parent is sibling2._parent);
2255     }
2256     body
2257     {
2258         auto item1oldprev = sibling1._prevSibling;
2259         auto item1oldnext = sibling1._nextSibling;
2260         auto item2oldprev = sibling2._prevSibling;
2261         auto item2oldnext = sibling2._nextSibling;
2262         const bool contiguous = item2oldprev == sibling1 || item1oldprev == sibling2;
2263 
2264         if (!contiguous)
2265         {
2266             sibling1._prevSibling = item2oldprev;
2267             sibling1._nextSibling = item2oldnext;
2268             sibling2._prevSibling = item1oldprev;
2269             sibling2._nextSibling = item1oldnext;
2270             if (item1oldprev) item1oldprev._nextSibling = sibling2;
2271             if (item1oldnext) item1oldnext._prevSibling = sibling2;
2272             if (item2oldprev) item2oldprev._nextSibling = sibling1;
2273             if (item2oldnext) item2oldnext._prevSibling = sibling1;
2274         }
2275         else
2276         {
2277             if (item1oldnext is sibling2)
2278             {
2279                 sibling1._prevSibling = sibling2;
2280                 sibling1._nextSibling = item2oldnext;
2281                 sibling2._nextSibling = sibling1;
2282                 sibling2._prevSibling = item1oldprev;
2283             }
2284             else
2285             {
2286                 sibling2._prevSibling = sibling1;
2287                 sibling2._nextSibling = item1oldnext;
2288                 sibling1._nextSibling = sibling2;
2289                 sibling1._prevSibling = item2oldprev;
2290             }
2291         }
2292 
2293         if (sibling1._parent && sibling1._parent.firstChild is sibling1)
2294         {
2295             sibling1._parent._firstChild = sibling2;
2296         }
2297         else if (sibling2._parent && sibling2._parent.firstChild is sibling2)
2298         {
2299             sibling2._parent._firstChild = sibling1;
2300         }
2301     }
2302 
2303     /**
2304      * Removes an item.
2305      *
2306      * Params:
2307      *      sibling = The item to remove.
2308      * Returns:
2309      *      true if the item is a sibling otherwise false.
2310      */
2311     bool removeSibling(TreeItemType sibling)
2312     {
2313         if (!sibling || (sibling.parent && sibling.parent != parent))
2314             return false;
2315 
2316         TreeItemType oldprev = sibling._prevSibling;
2317         TreeItemType oldnext = sibling._nextSibling;
2318         if (oldprev) oldprev._nextSibling = oldnext;
2319         if (oldnext) oldnext._prevSibling = oldprev;
2320 
2321         if (parent && parent.firstChild is sibling)
2322         {
2323             parent._firstChild = oldnext;
2324         }
2325 
2326         sibling._prevSibling = null;
2327         sibling._nextSibling = null;
2328         sibling._parent = null;
2329 
2330         return true;
2331     }
2332 
2333     /**
2334      * Removes the nth sibling.
2335      *
2336      * Params:
2337      *      index = the index of the sibling to remove.
2338      *  Returns:
2339      *      The item if the index is valid, otherwise null.
2340      */
2341     TreeItemType removeSibling(size_t index)
2342     {
2343         TreeItemType result = siblings[index];
2344         if (result)
2345         {
2346             TreeItemType oldprev = result._prevSibling;
2347             TreeItemType oldnext = result._nextSibling;
2348             if (oldprev) oldprev._nextSibling = oldnext;
2349             if (oldnext) oldnext._prevSibling = oldprev;
2350 
2351             if (parent && parent.firstChild is result)
2352             {
2353                 parent._firstChild = result._nextSibling;
2354             }
2355 
2356             result._prevSibling = null;
2357             result._nextSibling = null;
2358             result._parent = null;
2359         }
2360         return result;
2361     }
2362 
2363     /**
2364      * Returns the count of sibling in the branch.
2365      * The value returned is always greater than 0.
2366      */
2367     size_t siblingCount()
2368     {
2369         size_t toFront, toBack;
2370         auto current = self;
2371         while (current)
2372         {
2373             current = current._prevSibling;
2374             toFront++;
2375         }
2376         current = self;
2377         while (current)
2378         {
2379             current = current._nextSibling;
2380             toBack++;
2381         }
2382         return toFront + toBack -1;
2383     }
2384 
2385     /**
2386      * Returns the item position in the list.
2387      */
2388     ptrdiff_t siblingIndex()
2389     {
2390         ptrdiff_t result = -1;
2391         TreeItemType current = self;
2392         while (current)
2393         {
2394             current = current._prevSibling;
2395             result++;
2396         }
2397         return result;
2398     }
2399 
2400     /**
2401      * Sets the item position in the list.
2402      * The new position of the previous item is undetermined.
2403      */
2404     void siblingIndex(size_t position)
2405     {
2406         TreeItemType old = siblings[position];
2407         if (old !is self)
2408         {
2409             TreeItemType prt = _parent;
2410             removeSibling(self);
2411             old.insertSibling(position, self);
2412             _parent = prt;
2413         }
2414     }
2415 
2416     /**
2417      * Indicates if the item has neighboors.
2418      */
2419     bool hasSibling()
2420     {
2421         return prevSibling !is null || nextSibling !is null;
2422     }
2423 
2424 // -----------------------------------------------------------------------------
2425 // children -------------------------------------------------------------------+
2426 
2427     /**
2428      * Constructs, adds to the back then returns a new child.
2429      * This method should be prefered over addChild and insertChild
2430      * if $(D deleteChildren()) is used.
2431      *
2432      * When TreeItem is mixed in a class a template parameter that specifies
2433      * the class type to return must be present, otherwise in both cases the
2434      * function passes the optional run-time parameters to the constructor.
2435      */
2436     static if (is(TreeItemType == class))
2437     {
2438         IT addNewChild(IT,A...)(A a)
2439         if (is(IT : TreeItemType))
2440         {
2441             auto result = construct!IT(a);
2442             addChild(result);
2443             return result;
2444         }
2445     }
2446     else
2447     {
2448         TreeItemType addNewChild(A...)(A a)
2449         {
2450             TreeItemType result = construct!(typeof(this))(a);
2451             addChild(result);
2452             return result;
2453         }
2454     }
2455 
2456     /**
2457      * Returns the distance to the root.
2458      */
2459     size_t level()
2460     {
2461         size_t result;
2462         auto current = self;
2463         while (current._parent)
2464         {
2465             current = current._parent;
2466             result++;
2467         }
2468         return result;
2469     }
2470 
2471     /**
2472      * Returns the root.
2473      */
2474     TreeItemType root()
2475     {
2476         auto current = self;
2477         while (current._parent)
2478             current = current._parent;
2479         return current;
2480     }
2481 
2482     /**
2483      * Returns the children count.
2484      */
2485     size_t childrenCount()
2486     {
2487         if ( _firstChild is null)
2488             return 0;
2489         else
2490             return _firstChild.siblingCount;
2491     }
2492 
2493     /**
2494      * Adds child to the back.
2495      */
2496     void addChild(TreeItemType child)
2497     {
2498         if (child.parent)
2499         {
2500             if (child.parent !is self)
2501                 child.parent.removeChild(child);
2502             else
2503                 return;
2504         }
2505         if (!_firstChild)
2506         {
2507             _firstChild = child;
2508             child._parent = self;
2509             return;
2510         }
2511         else _firstChild.addSibling(child);
2512     }
2513 
2514     /**
2515      * Inserts the first child.
2516      */
2517     void insertChild(TreeItemType child)
2518     {
2519         if (!_firstChild)
2520         {
2521             _firstChild = child;
2522             child._parent = self;
2523             return;
2524         }
2525         else _firstChild.insertSibling(child);
2526     }
2527 
2528     /**
2529      * Inserts a child.
2530      *
2531      * Params:
2532      *      index = The position in the children list.
2533      *      child = The child to insert.
2534      */
2535     void insertChild(size_t index, TreeItemType child)
2536     in
2537     {
2538         assert(child);
2539     }
2540     body
2541     {
2542         if (!_firstChild)
2543         {
2544             _firstChild = child;
2545             child._parent = self;
2546             return;
2547         }
2548         else _firstChild.insertSibling(index, child);
2549     }
2550 
2551     /**
2552      * Removes a child from the list.
2553      *
2554      * Params:
2555      *      child = The child to remove.
2556      * Returns:
2557      *      true if child is removed.
2558      */
2559     bool removeChild(TreeItemType child)
2560     in
2561     {
2562         assert(child);
2563     }
2564     body
2565     {
2566         ptrdiff_t i = -1;
2567         if (_firstChild)
2568         {
2569             i = firstChild.findSibling(child);
2570             if (i != -1) removeChild(i);
2571         }
2572         return i != -1;
2573     }
2574 
2575     /**
2576      * Removes the nth child.
2577      *
2578      * Params:
2579      *      index = The child index.
2580      * Returns:
2581      *      The child if index was valid, otherwise null.
2582      */
2583     TreeItemType removeChild(size_t index)
2584     in
2585     {
2586         assert(index >= 0);
2587     }
2588     body
2589     {
2590         TreeItemType result = children[index];
2591         if (result)
2592         {
2593             if (index > 0)
2594                 result.prevSibling.removeSibling(index);
2595             else
2596             {
2597                 if (result.siblingCount == 1)
2598                 {
2599                     result._parent = null;
2600                     _firstChild = null;
2601                 }
2602                 else
2603                     result._nextSibling.removeSibling(index);
2604             }
2605         }
2606         return result;
2607     }
2608 
2609     /**
2610      * Removes the children, without destructing them.
2611      * After the call, the links to the items siblings are also reset to null.
2612      */
2613     void removeChildren()
2614     {
2615         auto current = _firstChild;
2616         while (current)
2617         {
2618             current.removeChildren;
2619 
2620             auto _next = current.nextSibling;
2621             current._parent = null;
2622             current._prevSibling = null;
2623             current._nextSibling = null;
2624             current = _next;
2625         }
2626         _firstChild = null;
2627     }
2628 
2629     /**
2630      * Removes and deletes (destroy) the children.
2631      *
2632      * This method should be used in pair with $(D addNewChild()) and
2633      * $(D addNewSiblings()). If $(D add()) or $(D insert()) have been used to
2634      * build the tree then initial references will be dangling.
2635      */
2636     void deleteChildren()
2637     {
2638         while (_firstChild)
2639         {
2640             auto current = _firstChild;
2641             _firstChild = current.nextSibling;
2642 
2643             current.deleteChildren;
2644             current._parent = null;
2645             current._nextSibling = null;
2646             current._prevSibling = null;
2647             static if (is(TreeItemType == interface) || is(TreeItemType == class))
2648                 destruct(cast(Object) current);
2649             else
2650                 destruct(current);
2651         }
2652     }
2653 // -----------------------------------------------------------------------------
2654 // other ----------------------------------------------------------------------+
2655 
2656     /**
2657      * Converts the node to a string.
2658      * This is used to represent the whole tree in $(D saveToStream()).
2659      */
2660     char[] itemToTextNative()
2661     {
2662         import std.format: format;
2663         char[] result;
2664         foreach (immutable i; 0 .. level) result ~= '\t';
2665         result ~= format( "Index: %.4d - NodeType: %s", siblingIndex, typeof(this).stringof);
2666         return result;
2667     }
2668 
2669     /**
2670      * Saves the textual representation of the tree to a Stream.
2671      *
2672      * Params:
2673      *      stream = The Stream where items are written.
2674      *      itemToText = A custom function to render the items. When not specified,
2675      *      $(D itemToTextNative()) is used.
2676      */
2677     void saveToStream(Stream stream, string function(TreeItemType) itemToText = null)
2678     {
2679         char[] txt;
2680         if (itemToText)
2681             txt = itemToText(self).dup;
2682         else
2683             txt = itemToTextNative ~ "\r\n";
2684         writeArray!false(stream, txt);
2685         foreach (c; children)
2686             c.saveToStream(stream, itemToText);
2687     }
2688 // -----------------------------------------------------------------------------
2689 }
2690 
2691 /**
2692  * Helper class template that implements TreeItem in a C descendant.
2693  */
2694 class TreeItemClass(C): C
2695 if (is(C==class))
2696 {
2697     mixin inheritedDtor;
2698     mixin TreeItem;
2699 }
2700 
2701 /// Alias to the most simple TreeItem class type.
2702 alias ObjectTreeItem = TreeItemClass!Object;
2703 
2704 /**
2705  * Helper struct template that implements TreeItem in a struct.
2706  *
2707  * Params:
2708  *      fieldsAndFuncs = The struct declarations, as a string to mix.
2709  */
2710 struct TreeItemStruct(string fieldsAndFuncs)
2711 {
2712     mixin(fieldsAndFuncs);
2713     mixin TreeItem;
2714 }
2715 
2716 /// Alias to the most simple TreeItem struct type.
2717 alias StructTreeItem = TreeItemStruct!q{public void* data;};
2718 
2719 unittest
2720 {
2721     ObjectTreeItem[20] items;
2722     ObjectTreeItem root;
2723 
2724     items[0] = construct!ObjectTreeItem;
2725     root = items[0];
2726     for (auto i =1; i < items.length; i++)
2727     {
2728         items[i] = construct!ObjectTreeItem;
2729         if (i>0) root.addSibling( items[i] );
2730         assert( items[i].siblingIndex == i );
2731         assert( root.siblings[i].siblingIndex == i );
2732         assert( root.siblings[i] == items[i] );
2733         if (i>0) assert( items[i].prevSibling.siblingIndex == i-1 );
2734         assert(root.lastSibling.siblingIndex == i);
2735     }
2736     assert(root.siblingCount == items.length);
2737 
2738     assert(items[1].nextSibling.siblingIndex == 2);
2739     assert(items[1].prevSibling.siblingIndex == 0);
2740 
2741     root.exchangeSibling(items[10],items[16]);
2742     assert(root.siblingCount == items.length);
2743     assert( items[10].siblingIndex == 16);
2744     assert( items[16].siblingIndex == 10);
2745 
2746     root.exchangeSibling(items[10],items[16]);
2747     assert(root.siblingCount == items.length);
2748     assert( items[10].siblingIndex == 10);
2749     assert( items[16].siblingIndex == 16);
2750 
2751 
2752     items[8].siblingIndex = 4;
2753     assert( items[8].siblingIndex == 4);
2754     //assert( ObjectTreeItems[4].siblingIndex == 5); // when siblingIndex() calls remove/insert
2755     //assert( ObjectTreeItems[4].siblingIndex == 8); // when siblingIndex() calls exchangeSibling.
2756 
2757     assert( root.siblings[16] == items[16]);
2758     assert( root.siblings[10] == items[10]);
2759     root.siblings[16] = items[10]; // exchg
2760     assert(root.siblingCount == items.length);
2761     root.siblings[16] = items[16]; // exchg
2762     assert(root.siblingCount == items.length);
2763     assert( items[16].siblingIndex == 16);
2764     assert( items[10].siblingIndex == 10);
2765 
2766     ObjectTreeItem c = construct!ObjectTreeItem;
2767     root.siblings[10] = c;
2768     root.siblings[16] = items[10];
2769     assert( items[16].siblingIndex == 0);
2770     assert( items[10].siblingIndex == 16);
2771     assert( c.siblingIndex == 10);
2772 
2773     assert(root.findSibling(items[18]) > -1);
2774     assert(root.findSibling(items[0]) > -1);
2775 
2776     foreach (item; root.siblings)
2777     {
2778         assert(root.findSibling(item) == item.siblingIndex);
2779     }
2780 
2781     root.removeSibling(19);
2782     assert(root.siblingCount == items.length -1);
2783     root.removeSibling(18);
2784     assert(root.siblingCount == items.length -2);
2785     root.removeSibling(items[13]);
2786     assert(root.siblingCount == items.length -3);
2787     //root1[0] = null; // exception because root1[0] = root1
2788     assert(root.siblingCount == items.length -3);
2789     root.siblings[1] = null;
2790     assert(root.siblingCount == items.length -4);
2791 
2792     foreach(o; items)
2793         destruct(o);
2794     destruct(c);
2795 }
2796 
2797 unittest
2798 {
2799     ObjectTreeItem root;
2800     ObjectTreeItem[20] items1;
2801     ObjectTreeItem[4][20] items2;
2802 
2803     root = construct!ObjectTreeItem;
2804     assert(root.level == 0);
2805     for (auto i=0; i < items1.length; i++)
2806     {
2807         items1[i] = construct!ObjectTreeItem;
2808         root.addChild(items1[i]);
2809         assert(root.childrenCount == 1 + i);
2810         assert(items1[i].parent is root);
2811         assert(items1[i].siblingCount == 1 + i);
2812         assert(items1[i].level == 1);
2813         assert(items1[i].siblingIndex == i);
2814     }
2815     root.removeChildren;
2816     assert(root.childrenCount == 0);
2817     for (auto i=0; i < items1.length; i++)
2818     {
2819         root.addChild(items1[i]);
2820         assert(items1[i].siblingIndex == i);
2821     }
2822 
2823     for (auto i = 0; i < items2.length; i++)
2824         for (auto j = 0; j < items2[i].length; j++)
2825         {
2826             items2[i][j] = construct!ObjectTreeItem;
2827             items1[i].addChild(items2[i][j]);
2828             assert(items2[i][j].level == 2);
2829             assert(items1[i].childrenCount == 1 + j);
2830             assert(items2[i][j].siblingCount == 1 + j);
2831         }
2832 
2833     root.deleteChildren;
2834 /*
2835     // this is an expected behavior:
2836 
2837     // original refs are dangling
2838     assert( items1[12] is null);
2839     assert( items2[12][0] is null);
2840     assert( items2[18][3] is null);
2841     // A.V: 'cause the items are destroyed
2842     writeln( items1[12].level );
2843 */
2844 
2845     root.addNewChild!ObjectTreeItem();
2846         root.children[0].addNewChild!ObjectTreeItem();
2847         root.children[0].addNewChild!ObjectTreeItem();
2848         root.children[0].addNewChild!ObjectTreeItem();
2849     root.addNewChild!ObjectTreeItem();
2850         root.children[1].addNewChild!ObjectTreeItem();
2851         root.children[1].addNewChild!ObjectTreeItem();
2852         root.children[1].addNewChild!ObjectTreeItem();
2853         root.children[1].addNewChild!ObjectTreeItem();
2854             root.children[1].children[3].addNewChild!ObjectTreeItem();
2855             root.children[1].children[3].addNewChild!ObjectTreeItem();
2856             root.children[1].children[3].addNewChild!ObjectTreeItem();
2857 
2858     assert(root.childrenCount == 2);
2859     assert(root.children[0].childrenCount == 3);
2860     assert(root.children[1].childrenCount == 4);
2861     assert(root.children[1].children[3].childrenCount == 3);
2862     assert(root.children[1].children[3].children[0].level == 3);
2863 
2864     assert(root.children[1].children[3].children[0].root is root);
2865     assert(root.children[1].children[3].root is root);
2866 
2867     auto str = construct!MemoryStream;
2868     root.saveToStream(str);
2869     //str.saveToFile("treenodes.txt");
2870     str.destruct;
2871     root.deleteChildren;
2872     destruct(root);
2873 }
2874 
2875 unittest
2876 {
2877     ObjectTreeItem root = construct!ObjectTreeItem;
2878     ObjectTreeItem c0 = root.addNewChild!ObjectTreeItem;
2879     ObjectTreeItem c1 = root.addNewChild!ObjectTreeItem;
2880     ObjectTreeItem c2 = root.addNewChild!ObjectTreeItem;
2881 
2882     scope(exit) destructEach(root, c0, c1, c2);
2883 
2884     assert(root.childrenCount == 3);
2885     root.removeChild(c0);
2886     assert(root.childrenCount == 2);
2887     root.removeChild(c1);
2888     assert(root.childrenCount == 1);
2889     root.removeChild(c2);
2890     assert(root.childrenCount == 0);
2891     root.removeChild(c2);
2892     assert(root.childrenCount == 0);
2893 }
2894 
2895 unittest
2896 {
2897     alias ItemStruct = TreeItemStruct!"uint a;";
2898 
2899     ItemStruct* root = construct!ItemStruct;
2900 
2901     auto c0 = root.addNewChild;
2902     auto c1 = root.addNewChild;
2903     auto c2 = root.addNewChild;
2904 
2905     scope(exit) destructEach(root, c0, c1, c2);
2906 
2907     assert(root.childrenCount == 3);
2908     root.removeChild(0);
2909     assert(root.childrenCount == 2);
2910     root.removeChild(0);
2911     assert(root.childrenCount == 1);
2912     root.removeChild(0);
2913     assert(root.childrenCount == 0);
2914 
2915     root.addChild(c0);
2916     root.addChild(c1);
2917     root.addChild(c2);
2918     assert(root.childrenCount == 3);
2919     root.removeChild(0);
2920     assert(root.childrenCount == 2);
2921     root.insertChild(c0);
2922     assert(root.childrenCount == 3);
2923     assert(root.children[0] == c0);
2924     root.removeChild(1);
2925     assert(c1.parent == null);
2926     assert(root.childrenCount == 2);
2927     root.insertChild(1, c1);
2928     assert(root.childrenCount == 3);
2929     root.removeChild(1);
2930     assert(root.childrenCount == 2);
2931     assert(c1.parent == null);
2932     root.insertChild(1, c1);
2933     assert(root.childrenCount == 3);
2934     assert(root.children[1] == c1);
2935 
2936     assert(root.children[0] == c0);
2937     assert(root.children[1] == c1);
2938     assert(root.children[2] == c2);
2939 
2940     c2.exchangeSibling(c0,c1);
2941     assert(root.firstChild == c1);
2942     assert(root.children[0] == c1);
2943     assert(root.children[1] == c0);
2944     assert(root.children[2] == c2);
2945     c2.exchangeSibling(c0,c1);
2946     assert(root.firstChild == c0);
2947     root.removeChild(c2);
2948     c0.insertSibling(c2);
2949     assert(root.firstChild == c2);
2950 
2951     root.removeChildren;
2952     root.addChild(c0);
2953     root.addChild(c1);
2954     root.addChild(c2);
2955     auto r = root.children;
2956     assert(r.front == c0);
2957     r.popFront;
2958     assert(r.front == c1);
2959     r.popFront;
2960     assert(r.front == c2);
2961     r.popFront;
2962     assert(r.empty);
2963 }
2964 
2965 unittest
2966 {
2967     ObjectTreeItem root = construct!ObjectTreeItem;
2968     ObjectTreeItem c0 = root.addNewChild!ObjectTreeItem;
2969     ObjectTreeItem c1 = root.addNewChild!ObjectTreeItem;
2970     ObjectTreeItem c2 = root.addNewChild!ObjectTreeItem;
2971     scope(exit) destructEach(root, c0, c1, c2);
2972 
2973     size_t it;
2974     foreach (ObjectTreeItem child; root.children)
2975     {
2976         assert(c0.parent);
2977         assert(c1.parent);
2978         assert(c2.parent);
2979         if (it == 0)
2980         {
2981             c1.siblingIndex = c1.siblingCount-1;
2982             c0.siblingIndex = c0.siblingCount-1;
2983             c0.siblingIndex = 0;
2984         }
2985         else if (it == 1)
2986         {
2987             c1.siblingIndex = c1.siblingCount-1;
2988             c0.siblingIndex = c0.siblingCount-1;
2989             c0.siblingIndex = 0;
2990         }
2991         else if (it == 2)
2992         {
2993             c1.siblingIndex = c1.siblingCount-1;
2994             c0.siblingIndex = c0.siblingCount-1;
2995             c0.siblingIndex = 0;
2996         }
2997         it++;
2998     }
2999 }
3000 
3001 
3002 private struct LinearProbeSlot(K, V = void)
3003 {
3004 
3005     enum isMap = !is(V == void);
3006 
3007 private:
3008 
3009     K _key;
3010     static if (isMap) V _value;
3011 
3012 public:
3013 
3014     @disable this();
3015 
3016     this(this) @nogc
3017     {
3018         static if (is(K == struct) && hasMember!(K, "__postblit") && isCopyable!K)
3019             _key.__postblit;
3020         static if (isMap && is(V == struct) && hasMember!(V, "__postblit") && isCopyable!V)
3021             _value.__postblit;
3022     }
3023 
3024     static if (!isMap)
3025     {
3026         this(K)(auto ref K key)
3027         {
3028             _key = key;
3029         }
3030     }
3031     else
3032     {
3033         this()(auto ref K key, auto ref V value)
3034         {
3035             _key = key;
3036             _value = value;
3037         }
3038     }
3039 
3040     ~this()
3041     {
3042         static if (is(K == struct))
3043         {
3044             destruct(_key);
3045         }
3046         static if (isMap && is(V == struct))
3047         {
3048             destruct(_value);
3049         }
3050     }
3051 
3052     auto opEquals(KK)(auto ref KK key) const
3053     {
3054         static if (!isMap)
3055         {
3056             static if (hasElaborateSelfEquals!K)
3057                 return _key.opEquals(key);
3058             else
3059                 return _key == key;
3060         }
3061         else
3062         {
3063             static if (hasElaborateSelfEquals!K)
3064             {
3065                 if (_key.opEquals(key))
3066                     return cast(const(V)*) &_value;
3067                 else
3068                     return cast(const(V)*) null;
3069             }
3070             else
3071             {
3072                 if (key == _key)
3073                     return cast(const(V)*) &_value;
3074                 else
3075                     return cast(const(V)*) null;
3076             }
3077         }
3078     }
3079 
3080     auto ptr()
3081     {
3082         static if (!isMap)
3083             return &this;
3084         else
3085             return cast(Tuple!(K,V)*) &this;
3086     }
3087 
3088     alias Slot = typeof(this);
3089     struct FindResult
3090     {
3091         @disable this(this);
3092         /// the hash after probing
3093         size_t endHash;
3094         /// the bucket after probing
3095         Slot* slot;
3096     }
3097 }
3098 
3099 unittest
3100 {
3101     LinearProbeSlot!string lpbs = LinearProbeSlot!string("cat");
3102     assert(lpbs == "cat");
3103     assert(lpbs != "dog");
3104 
3105     LinearProbeSlot!(string,int) lpbsi = LinearProbeSlot!(string,int)("cat", 1);
3106     assert(*(lpbsi == "cat") == 1);
3107     assert((lpbsi == "rat") is null);
3108 }
3109 
3110 
3111 /**
3112  * Default hash function used in the HashSet and the HashMap
3113  */
3114 pragma(inline, true)
3115 size_t fnv1(V, bool fnv1a = false)(auto ref V value)
3116 {
3117     static if (isBasicType!V || is(V==struct) || is(V == union))
3118         return fnv1Impl!fnv1a(cast(ubyte*) &value, V.sizeof);
3119     else static if (isArray!V)
3120         return fnv1Impl!fnv1a(cast(ubyte*) value.ptr, value.length * (ElementEncodingType!V).sizeof);
3121     else static if (isPointer!V || is(V == class) || is(V == interface))
3122         return fnv1Impl!fnv1a(cast(ubyte*) value, V.sizeof);
3123     else static assert(0);
3124 }
3125 
3126 private size_t fnv1Impl(bool fnv1a = false)(ubyte* data, size_t length)
3127 {
3128     static if (size_t.sizeof == 8)
3129         size_t h = 0xCBF29CE484222325UL;
3130     else static if (size_t.sizeof == 4)
3131         size_t h = 0x811C9DC5UL;
3132     else static assert(0);
3133 
3134     static if (size_t.sizeof == 8)
3135     foreach (immutable i; 0..length)
3136     {
3137         static if (fnv1a)
3138         {
3139             h ^= *data++;
3140             h *= 0x100000001B3UL;
3141         }
3142         else
3143         {
3144             h *= 0x100000001B3UL;
3145             h ^= *data++;
3146         }
3147     }
3148     else static if (size_t.sizeof == 4)
3149     foreach (immutable i; 0..length)
3150     {
3151         static if (fnv1a)
3152         {
3153             h ^= *data++;
3154             h *= 0x1000193U;
3155         }
3156         else
3157         {
3158             h *= 0x1000193U;
3159             h ^= *data++;
3160         }
3161     }
3162     else static assert(0);
3163     return h;
3164 }
3165 
3166 
3167 /**
3168  * Enumerates the hashset and hashmap insertion mode
3169  */
3170 enum
3171 {
3172     /// Buckets are already reserved.
3173     imReserved = false,
3174     /// Always reserves a bucket.
3175     imExpand = true
3176 }
3177 
3178 
3179 /**
3180  * Enumerates the collision handling modes that
3181  * can be specified to instantiate a HashSet or a Map.
3182  */
3183 enum CollisionHandling
3184 {
3185     /// Hanlde collision using linear probing.
3186     linearProbe,
3187     /// Handle the collision by inserting in a bucket.
3188     bucketArray,
3189     /// Assumes the hash function not to produce collisions.
3190     none,
3191 }
3192 
3193 private alias CH = CollisionHandling;
3194 
3195 /// Aliases an hashset implementation, by default HashSet_AB.
3196 template HashSet(CollisionHandling ch = CH.bucketArray)
3197 {
3198     static if (ch == CH.linearProbe)
3199         alias HashSet = HashSet_LP;
3200     else static if (ch == CH.bucketArray)
3201         alias HashSet = HashSet_AB;
3202     else
3203         static assert(0);
3204 }
3205 
3206 /// Aliases an hashset implementation, by default HashMap_LP.
3207 template HashMap(CollisionHandling ch = CH.linearProbe)
3208 {
3209     static if (ch == CH.linearProbe)
3210         alias HashSet = HashMap_LP;
3211     else
3212         static assert(0);
3213 }
3214 
3215 private enum
3216 {
3217     rngNoMap,
3218     rngMapByKey,
3219     rngMapByValue,
3220     rngMapByKeyValue,
3221 }
3222 
3223 private struct RangeForLpSet(T, alias rngKind = rngNoMap)
3224 {
3225 
3226 private:
3227 
3228     alias PF = ReturnType!(T.slot);
3229     alias F = PointerTarget!PF;
3230 
3231     size_t index;
3232     T* _hashOrMap;
3233 
3234     //pragma(inline, true)
3235     void next()
3236     {
3237         while (index < _hashOrMap.slotCount)
3238         {
3239             if ((*_hashOrMap).slot(index))
3240                 break;
3241             else
3242                 ++index;
3243         }
3244     }
3245 
3246 public:
3247 
3248     this(T* hashOrMap) @nogc
3249     {
3250         assert(hashOrMap);
3251         _hashOrMap = hashOrMap;
3252         next();
3253     }
3254 
3255     void popFront() @nogc
3256     {
3257         ++index;
3258         next();
3259     }
3260 
3261     bool empty() @nogc
3262     {return index >= _hashOrMap.slotCount;}
3263 
3264     ref front() @nogc
3265     {
3266         static if (rngKind == rngNoMap || rngKind == rngMapByKeyValue)
3267             return *(*_hashOrMap).slot(index);
3268         else static if (rngKind == rngMapByKey)
3269             return (*(*_hashOrMap).slot(index))[0];
3270         else static if (rngKind == rngMapByValue)
3271             return (*(*_hashOrMap).slot(index))[1];
3272     }
3273 }
3274 
3275 /**
3276  * A manually managed hashset that uses linear probing to solve the collisions.
3277  *
3278  * Params:
3279  *      K = the key type.
3280  *      hasherFun = The hashing function, a $(D size_t(K value);) function,
3281  *          literal delegate or lambda.
3282  */
3283 struct HashSet_LP(K, alias hasherFun = fnv1)
3284 {
3285     //static assert (is(typeof( (){size_t r = hasherFun(K.init);}  )),
3286       //  "invalid hash function");
3287     static assert (!is(K == void),
3288         "invalid Key type");
3289 
3290 private:
3291 
3292     alias HashSetT = typeof(this);
3293     alias Slot = LinearProbeSlot!K;
3294     @NoGc Array!(Slot*) _slots;
3295     size_t _count;
3296 
3297     pragma(inline, true)
3298     size_t hasher(KK)(auto ref KK key)
3299     {
3300         return hasherFun(key) & (_slots.length - 1);
3301     }
3302 
3303     void reHash()() @nogc
3304     {
3305         _count = 0;
3306         Array!(Slot*) old = _slots;
3307         assert(old == _slots);
3308         _slots[] = null;
3309         foreach (immutable i; 0..old.length)
3310         {
3311             if (auto b = old[i])
3312             {
3313                 insert(b._key);
3314                 destruct(b);
3315             }
3316         }
3317         destruct(old);
3318     }
3319 
3320     pragma(inline, true)
3321     size_t nextHash(size_t value) @nogc @safe
3322     {
3323         return (value + 1) & (_slots.length - 1);
3324     }
3325 
3326     //pragma(inline, true)
3327     Slot.FindResult find(KK)(auto ref KK key)
3328     {
3329         Slot.FindResult fr;
3330         const size_t hb = hasher(key);
3331         fr.endHash = hb;
3332 
3333         if (_slots.length)
3334         {
3335             fr.slot = _slots[hb];
3336             while (true)
3337             {
3338                 if (fr.slot && *fr.slot != key)
3339                 {
3340                     fr.endHash = nextHash(fr.endHash);
3341                     if (fr.endHash == hb)
3342                         break;
3343                     fr.slot = _slots[fr.endHash];
3344                 }
3345                 else break;
3346             }
3347         }
3348         return fr;
3349     }
3350 
3351 public:
3352 
3353     /**
3354      * Constructs using either a list of keys, arrays of keys, or both.
3355      */
3356     this(A...)(A a)
3357     if (A.length)
3358     {
3359         import std.meta: aliasSeqOf;
3360         import std.range: iota;
3361 
3362         foreach (i; aliasSeqOf!(iota(0, A.length)))
3363         {
3364             static if (is(A[i] == K))
3365                 continue;
3366             else static if (isArray!(A[i]))
3367                 continue;
3368             else static if (is(A[i] == Array!K))
3369                 continue;
3370             else static assert(0, A[i].stringof ~ " not supported");
3371         }
3372         foreach (i; aliasSeqOf!(iota(0, A.length)))
3373                 insert(a[i]);
3374     }
3375 
3376     ~this() @nogc
3377     {
3378         foreach (immutable i; 0.._slots.length)
3379             if (Slot* slt = _slots[i])
3380                 destruct(slt);
3381         destruct(_slots);
3382     }
3383 
3384     this(this) @nogc
3385     {
3386         foreach (immutable i; 0.._slots.length)
3387             if (Slot* slt = _slots[i])
3388         {
3389             Slot* n = construct!Slot(slt._key);
3390             n.__postblit();
3391             _slots[i] = n;
3392         }
3393     }
3394 
3395     /**
3396      * Tries to insert key(s) in the set.
3397      *
3398      * Params:
3399      *      mode = If true (imExpand) then reserves a slot else (imReserved)
3400      *          assumes a previous call to $(D reserve()).
3401      *      key = either single keys, array of keys, or both.
3402      * Throws:
3403      *      An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails.
3404      * Returns:
3405      *      If the key is added or if it's already included then returns $(D true),
3406      *      otherwise $(D false).
3407      */
3408     bool insert(alias mode)(ref K key) @nogc
3409     if (isImplicitlyConvertible!(typeof(mode), bool))
3410     {
3411         bool result;
3412         static if (mode)
3413             reserve(1);
3414         Slot.FindResult fr = find(key);
3415         if (fr.slot is null || *fr.slot != key)
3416         {
3417             assert(key !in this);
3418             Slot* n = construct!Slot(key);
3419             if (fr.slot is null)
3420             {
3421                 assert(key !in this);
3422                 _slots[fr.endHash] = n;
3423                 result = true;
3424                 ++_count;
3425             }
3426             else destruct(n);
3427         }
3428         else if (*fr.slot == key)
3429             result = true;
3430         return result;
3431     }
3432 
3433     /// ditto
3434     bool insert(alias mode = true)(K key) @nogc
3435     if (isImplicitlyConvertible!(typeof(mode), bool))
3436     {
3437         return insert!mode(key);
3438     }
3439 
3440     /// ditto
3441     bool insert(KK)(auto ref KK keys)
3442     if ((isArray!KK && is(Unqual!(ElementEncodingType!KK) == K)) || is(KK == Array!K))
3443     {
3444         bool result = true;
3445         reserve(keys.length);
3446         foreach(k; keys)
3447             result &= insert!false(k);
3448         return result;
3449     }
3450 
3451     /// ditto
3452     bool insert(KK...)(auto ref KK keys)
3453     {
3454         bool result = true;
3455         reserve(KK.length);
3456         foreach(k; keys)
3457             result &= insert!false(k);
3458         return result;
3459     }
3460 
3461     /**
3462      * Tries to remove a key from the set.
3463      *
3464      * Returns:
3465      *      $(D true) if the key was included otherwise $(D false).
3466      */
3467     bool remove()(auto ref K key)
3468     {
3469         bool result;
3470         Slot.FindResult fr = find(key);
3471         if (fr.slot)
3472         {
3473             result = true;
3474             destruct(fr.slot);
3475             _slots[fr.endHash] = null;
3476             reHash;
3477         }
3478         return result;
3479     }
3480 
3481     /**
3482      * Clears and empties the set.
3483      */
3484     void clear() @nogc
3485     {
3486         foreach (immutable i; 0.._slots.length)
3487             if (auto b = _slots[i])
3488                 destruct(b);
3489         _slots[] = null;
3490         _slots.length = 0;
3491         _count = 0;
3492     }
3493 
3494     /**
3495      * Support for appending element(s). Forwards $(D insert()).
3496      */
3497     auto opOpAssign(string op : "~" , KK...)(auto ref KK keys)
3498     {
3499         return insert(keys);
3500     }
3501 
3502     /**
3503      * Reserves slots for at least N supplemental keys.
3504      *
3505      * Throws:
3506      *      An $(D OutOfMemoryError) if the reallocation fails.
3507      * Params:
3508      *      value = The count of additional slots to reserve.
3509      */
3510     void reserve()(size_t value) @nogc
3511     {
3512         import std.math: nextPow2;
3513         const size_t nl = nextPow2(_count + value);
3514         const size_t ol = _slots.length;
3515 
3516         if (nl > _slots.length)
3517         {
3518             _slots.length = nl;
3519             _slots[ol..nl] = null;
3520             reHash();
3521         }
3522     }
3523 
3524     /**
3525      * Minimizes the memory usage.
3526      *
3527      * Should be used after removal and only if $(D count() < slotCount()).
3528      *
3529      * Throws:
3530      *      An $(D OutOfMemoryError) if the reallocation fails.
3531      */
3532     void minimize()()
3533     {
3534         import std.math: nextPow2;
3535         const size_t nl = nextPow2(_count-1);
3536 
3537         if (nl < _slots.length)
3538         {
3539             Array!(K) old;
3540             foreach (immutable i; 0.._slots.length)
3541                 if (auto b = _slots[i])
3542                     old ~= b._key;
3543             clear;
3544             foreach (immutable i; 0..old.length)
3545             {
3546                 insert(old[i]);
3547                 static if (is(K==struct))
3548                     destruct(old[i]);
3549             }
3550             destruct(old);
3551         }
3552     }
3553 
3554     /**
3555      * Tests the presence of a key in the set.
3556      *
3557      * Params:
3558      *      key = The key to test.
3559      * Returns:
3560      *      $(D null) if the key is not present otherwise a pointer to the key.
3561      */
3562     K* opBinaryRight(string op : "in", KK)(auto ref KK key)
3563     {
3564         K* result;
3565         Slot.FindResult fr = find(key);
3566         if (fr.slot)
3567             result = &fr.slot._key;
3568         return result;
3569     }
3570 
3571     /**
3572      * Provides an access to the keys.
3573      *
3574      * Params:
3575      *      index = The slot index. Must be in the $(D 0..slotCount()) range.
3576      * Returns:
3577      *      A pointer the nth key.
3578      */
3579     K* slot(const size_t index)
3580     {
3581         return &_slots[index]._key;
3582     }
3583 
3584     /**
3585      * Returns an input range that consists of each non-null key.
3586      */
3587     auto byKey()
3588     {
3589         return RangeForLpSet!HashSetT(&this);
3590     }
3591 
3592     /**
3593      * Returns the keys count.
3594      *
3595      * This matches to $(D byKey.walkLength).
3596      */
3597     size_t count() @nogc {return _count;}
3598 
3599     /**
3600      * Returns the slots count.
3601      */
3602     size_t slotCount() @nogc {return _slots.length;}
3603 }
3604 ///
3605 @nogc unittest
3606 {
3607     HashSet_LP!string commands;
3608     // can insert up to 16 elements without reallocation
3609     commands.reserve(15);
3610     assert(commands.slotCount == 16);
3611     // appends elements
3612     commands.insert("move");
3613     commands.insert("insert");
3614     commands.insert("delete");
3615     // test for inclusion
3616     assert("move" in commands);
3617     // remove something
3618     commands.remove("insert");
3619     assert(commands.count == 2);
3620     assert("insert" !in commands);
3621     // empties and frees memory
3622     commands.clear;
3623     // manually managed implies to destruct by hand
3624     import iz.memory;
3625     destruct(commands);
3626 }
3627 
3628 @nogc unittest
3629 {
3630     HashSet_LP!string hss;
3631 
3632     hss.reserve(7);
3633     assert(hss.slotCount == 8);
3634 
3635     foreach(i; 0 .. hss._slots.length)
3636         assert(hss._slots[i] is null);
3637 
3638     assert(hss.insert("cat"));
3639     assert("dog" !in hss);
3640     assert("cat" in hss);
3641 
3642     assert(hss.insert("rat"));
3643     assert("dog" !in hss);
3644     assert("cat" in hss);
3645     assert("rat" in hss);
3646 
3647     assert(hss.insert("fly"));
3648     assert("dog" !in hss);
3649     assert("cat" in hss);
3650     assert("rat" in hss);
3651     assert("fly" in hss);
3652 
3653     assert(hss.insert("bee"));
3654     assert("dog" !in hss);
3655     assert("cat" in hss);
3656     assert("rat" in hss);
3657     assert("fly" in hss);
3658     assert("bee" in hss);
3659 
3660     assert(hss.insert("ant"));
3661     assert("dog" !in hss);
3662     assert("cat" in hss);
3663     assert("rat" in hss);
3664     assert("fly" in hss);
3665     assert("bee" in hss);
3666     assert("ant" in hss);
3667     assert("fox" !in hss);
3668 
3669     assert(hss.insert("fox"));
3670     assert("dog" !in hss);
3671     assert("cat" in hss);
3672     assert("rat" in hss);
3673     assert("fly" in hss);
3674     assert("bee" in hss);
3675     assert("ant" in hss);
3676     assert("fox" in hss);
3677 
3678     assert(hss.insert("bat"));
3679     assert("dog" !in hss);
3680     assert("cat" in hss);
3681     assert("rat" in hss);
3682     assert("fly" in hss);
3683     assert("bee" in hss);
3684     assert("ant" in hss);
3685     assert("fox" in hss);
3686     assert("bat" in hss);
3687 
3688     assert(hss.insert("cow"));
3689     assert("dog" !in hss);
3690     assert("cat" in hss);
3691     assert("rat" in hss);
3692     assert("fly" in hss);
3693     assert("bee" in hss);
3694     assert("ant" in hss);
3695     assert("fox" in hss);
3696     assert("bat" in hss);
3697     assert("cow" in hss);
3698 
3699     assert(hss.remove("bat"));
3700     assert("bat" !in hss);
3701 
3702     hss.clear;
3703     assert(hss.count == 0);
3704     assert(hss.slotCount == 0);
3705 
3706     hss.reserve(8);
3707     import std.algorithm: among;
3708     assert(hss.insert("cow"));
3709     assert(hss.insert("yak"));
3710     auto r = hss.byKey;
3711     assert(!r.empty);
3712     assert((r.front).among("cow","yak"));
3713     r.popFront;
3714     assert(!r.empty);
3715     assert((r.front).among("cow","yak"));
3716     r.popFront;
3717     assert(r.empty);
3718     assert(hss.slotCount == 16);
3719 
3720     assert(hss.count == 2);
3721     hss.minimize;
3722     assert(hss.slotCount < 16);
3723 
3724     destruct(hss);
3725 }
3726 
3727 @nogc unittest
3728 {
3729     HashSet_LP!string co;
3730     assert(co.count == 0);
3731     co.insert("abcd");
3732     assert(co.count == 1);
3733     co.insert("abcd");
3734     assert(co.count == 1);
3735     co.insert("abcd");
3736     assert(co.count == 1);
3737     co.insert("abcde");
3738     assert(co.count == 2);
3739     co.insert("abcde");
3740     assert(co.count == 2);
3741     co.insert("abcde");
3742     assert(co.count == 2);
3743     co.insert("abcde");
3744     assert(co.count == 2);
3745     destruct(co);
3746 }
3747 
3748 @nogc unittest
3749 {
3750     {
3751         HashSet_LP!string co = HashSet_LP!string("ab", "ab", "cd");
3752         assert(co.count == 2);
3753         destruct(co);
3754     }
3755     {
3756         static a = ["ab", "cd"];
3757         HashSet_LP!string co = HashSet_LP!string("ab", a);
3758         assert(co.count == 2);
3759         destruct(co);
3760     }
3761     {
3762         HashSet_LP!int co = HashSet_LP!int(1);
3763         assert(co.count == 1);
3764         assert(2 !in co);
3765         assert(1 in co);
3766         destruct(co);
3767     }
3768 }
3769 
3770 /**
3771  * A manually managed hashmap that uses linear probing to solve the collisions.
3772  *
3773  * Params:
3774  *      K = The key type.
3775  *      V = The value type
3776  *      hasherFun = The hashing function, a $(D size_t(K value);) function,
3777  *          literal delegate or lambda.
3778  */
3779 struct HashMap_LP(K, V, alias hasherFun = fnv1)
3780 {
3781     static assert (is(typeof( (){size_t r = hasherFun(K.init);}  )),
3782         "invalid hash function");
3783     static assert (!is(K == void),
3784         "invalid Key type");
3785     static assert (!is(V == void),
3786         "invalid Value type");
3787 
3788 private:
3789 
3790     alias MapT = typeof(this);
3791     alias Slot = LinearProbeSlot!(K,V);
3792     @NoGc Array!(Slot*) _slots;
3793     size_t _count;
3794 
3795     pragma(inline, true)
3796     size_t hasher(KK)(auto ref KK key) @nogc
3797     {
3798         return hasherFun(key) & (_slots.length - 1);
3799     }
3800 
3801     void reHash()()
3802     {
3803         _count = 0;
3804         auto old = _slots.dup;
3805         assert(old == _slots);
3806         _slots[] = null;
3807         foreach (immutable i; 0..old.length)
3808         {
3809             if (auto b = old[i])
3810             {
3811                 insert(b._key, b._value);
3812                 destruct(b);
3813             }
3814         }
3815         destruct(old);
3816     }
3817 
3818     pragma(inline, true)
3819     size_t nextHash(size_t value) @nogc @safe
3820     {
3821         return (value + 1) & (_slots.length - 1);
3822     }
3823 
3824     //pragma(inline, true)
3825     Slot.FindResult find(KK)(auto ref KK key)
3826     {
3827         Slot.FindResult fr;
3828         const size_t hb = hasher(key);
3829         fr.endHash = hb;
3830 
3831         if (_slots.length)
3832         {
3833             fr.slot = _slots[hb];
3834             while (true)
3835             {
3836                 if (fr.slot && *fr.slot != key)
3837                 {
3838                     fr.endHash = nextHash(fr.endHash);
3839                     if (fr.endHash == hb)
3840                         break;
3841                     fr.slot = _slots[fr.endHash];
3842                 }
3843                 else break;
3844             }
3845         }
3846         return fr;
3847     }
3848 
3849 public:
3850 
3851     alias MapPair = Tuple!(K, V);
3852 
3853     ~this() @nogc
3854     {
3855         foreach(immutable i; 0.._slots.length)
3856             if (Slot* slt = _slots[i])
3857                 destruct(slt);
3858         destruct(_slots);
3859     }
3860 
3861     this(this) @nogc
3862     {
3863         foreach (immutable i; 0.._slots.length)
3864             if (Slot* slt = _slots[i])
3865         {
3866             Slot* n = construct!Slot(slt._key, slt._value);
3867             n.__postblit();
3868             _slots[i] = n;
3869         }
3870     }
3871 
3872     /**
3873      * Tries to insert a key-value pair in the map.
3874      *
3875      * Params:
3876      *      mode = If set to $(D imExpand) then reserves a slot else if set to
3877      *      $(D imReserved) assumes a previous call to $(D reserve()).
3878      *      key = The key.
3879      *      value = The corresponding value.
3880      * Throws:
3881      *      An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails.
3882      * Returns:
3883      *      If the key is added or if it's already included then returns $(D true),
3884      *      otherwise $(D false).
3885      */
3886     bool insert(alias mode = imExpand)(ref K key, auto ref V value) @nogc
3887     if (isImplicitlyConvertible!(typeof(mode), bool))
3888     {
3889         bool result;
3890         static if (mode)
3891             reserve(1);
3892         Slot.FindResult fr = find(key);
3893         if (fr.slot is null || *fr.slot != key)
3894         {
3895             assert(key !in this);
3896             Slot* n = construct!Slot(key, value);
3897             if (fr.slot is null)
3898             {
3899                 assert(key !in this);
3900                 _slots[fr.endHash] = n;
3901                 result = true;
3902                 ++_count;
3903             }
3904             else destruct(n);
3905         }
3906         else if (*fr.slot == key)
3907         {
3908             result = true;
3909             destruct(fr.slot);
3910             Slot* n = construct!Slot(key, value);
3911             _slots[fr.endHash] = n;
3912         }
3913         return result;
3914     }
3915 
3916     /// ditto
3917     bool insert(alias mode = imExpand)(K key, V value) @nogc
3918     if (isImplicitlyConvertible!(typeof(mode), bool))
3919     {
3920         return insert!mode(key, value);
3921     }
3922 
3923     /**
3924      * Tries to remove a key from the set.
3925      *
3926      * Returns:
3927      *      $(D true) if the key was included otherwise $(D false).
3928      */
3929     bool remove()(auto ref K key)
3930     {
3931         bool result;
3932         Slot.FindResult fr = find(key);
3933         if (fr.slot)
3934         {
3935             result = true;
3936             destruct(fr.slot);
3937             _slots[fr.endHash] = null;
3938             reHash;
3939         }
3940         return result;
3941     }
3942 
3943     /**
3944      * Clears and empties the set.
3945      *
3946      * Throws:
3947      *      An $(D OutOfMemoryError) if the reallocation fails.
3948      */
3949     void clear() @nogc
3950     {
3951         foreach (immutable i; 0.._slots.length)
3952             if (auto b = _slots[i])
3953                 destruct(b);
3954         _slots[] = null;
3955         _slots.length = 0;
3956         _count = 0;
3957     }
3958 
3959     /**
3960      * Support for appending an element.
3961      *
3962      * Forwards $(D insert()) with a default initialized value.
3963      *
3964      * Params:
3965      *      key = The key to insert.
3966      * Returns:
3967      *      If the key is added or if it's already included then returns $(D true),
3968      *      otherwise $(D false).
3969      */
3970     bool opOpAssign(string op : "~")(auto ref K key)
3971     {
3972         return insert(key, V.init);
3973     }
3974 
3975     /**
3976      * Support for inserting using the array syntax. Forwards $(D insert()).
3977      */
3978     void opIndexAssign(KK)(auto ref V value, auto ref KK key)
3979     {
3980         insert(key, value);
3981     }
3982 
3983     /**
3984      * Support for assigning to the value when the value is itself an AA.
3985      *
3986      * Note that this function only exists to port code that uses the runtime AA
3987      * with the syntax $(D aa[k_for_value][k_for_value_of_value] = stuff;).
3988      */
3989     void opIndexAssign(V2, KK1, KK2)(auto ref V2 value, auto ref KK1 key1, auto ref KK2 key2)
3990     {
3991         if (auto v = key1 in this)
3992         {
3993             v.insert(key2, value);
3994         }
3995         else
3996         {
3997             V v;
3998             v.insert(key2, value);
3999             insert(key1, v);
4000         }
4001     }
4002 
4003     /**
4004      * Support for the assignment operators on a value.
4005      */
4006     void opIndexOpAssign(string op, VV, KK)(auto ref VV value, auto ref KK key)
4007     {
4008         if (auto p = key in this)
4009         {
4010             mixin("(*p)" ~ op ~ "= value;");
4011         }
4012         else
4013         {
4014             V v;
4015             mixin("v" ~ op ~ "= value;");
4016             insert(key, v);
4017         }
4018     }
4019 
4020     /**
4021      * Returns an input range consisting of each key.
4022      */
4023     auto byKey() return @nogc
4024     {
4025         return RangeForLpSet!(MapT,rngMapByKey)(&this);
4026     }
4027 
4028     /**
4029      * Returns an input range consisting of each value.
4030      */
4031     auto byValue() return @nogc
4032     {
4033         return RangeForLpSet!(MapT,rngMapByValue)(&this);
4034     }
4035 
4036     /**
4037      * Returns an input range consisting of each non-null key-value pair.
4038      */
4039     auto byKeyValue() return @nogc
4040     {
4041         return RangeForLpSet!MapT(&this);
4042     }
4043 
4044     /**
4045      * Reserves slots for at least N supplemental key-value pairs.
4046      *
4047      * Throws:
4048      *      An $(D OutOfMemoryError) if the reallocation fails.
4049      * Params:
4050      *      value = The count of additional slots to reserve.
4051      */
4052     void reserve()(size_t value) @nogc
4053     {
4054         import std.math: nextPow2;
4055         const size_t nl = nextPow2(_count + value);
4056         const size_t ol = _slots.length;
4057 
4058         if (nl > _slots.length)
4059         {
4060             _slots.length = nl;
4061             _slots[ol..nl] = null;
4062             reHash();
4063         }
4064     }
4065 
4066     /**
4067      * Minimizes the memory usage.
4068      *
4069      * Should be used after removal and only if $(D count() < slotCount()).
4070      */
4071     void minimize()()
4072     {
4073         import std.math: nextPow2;
4074         const size_t nl = nextPow2(_count-1);
4075 
4076         if (nl < _slots.length)
4077         {
4078             Array!(MapPair) old;
4079             foreach (immutable i; 0.._slots.length)
4080                 if (auto b = _slots[i])
4081                     old ~= tuple(b._key, b._value);
4082             clear;
4083             foreach (immutable i; 0..old.length)
4084             {
4085                 insert(old[i][0..2]);
4086                 static if (is(K == struct))
4087                     destruct(old[i]);
4088             }
4089             destruct(old);
4090         }
4091     }
4092 
4093     /**
4094      * Tests the presence of a key in the set.
4095      *
4096      * Params:
4097      *      key = The key to test.
4098      * Returns:
4099      *      $(D null) if the key is not present otherwise a pointer to the
4100      *          value that mapped.
4101      */
4102     V* opBinaryRight(string op : "in", KK)(auto ref KK key)
4103     {
4104         V* result;
4105         Slot.FindResult fr = find(key);
4106         if (fr.slot)
4107             result = &fr.slot._value;
4108         return result;
4109     }
4110 
4111     /**
4112      * Provides an access to the key-value pairs.
4113      *
4114      * Params
4115      *      index = The pair index. Must be in the $(D 0..slotCount()) range.
4116      * Returns:
4117      *      A pointer to a tuple that contains, when not null, the
4118      *      key and the value of the element pointed by $(D_PARAM index).
4119      */
4120     MapPair* slot(const size_t index) @nogc
4121     {
4122         if (auto r = _slots[index])
4123             return r.ptr;
4124         else
4125             return null;
4126     }
4127 
4128     /// ditto
4129     auto ref V opIndex(KK)(auto ref KK key)
4130     if (!is(KK == size_t))
4131     {
4132         return *(key in this);
4133     }
4134 
4135     /**
4136      * Returns the key-value pairs count.
4137      *
4138      * This matches to $(D byKeyValue.walkLength).
4139      */
4140     size_t count() @nogc {return _count;}
4141 
4142     /**
4143      * Returns the slots counts.
4144      */
4145     size_t slotCount() @nogc {return _slots.length;}
4146 }
4147 ///
4148 @nogc unittest
4149 {
4150     HashMap_LP!(string, size_t) stock;
4151     // can insert up to 16 elements without reallocation
4152     stock.reserve(15);
4153     assert(stock.slotCount == 16);
4154     // appends elements, various syntax allowed
4155     stock.insert("pen", 8);
4156     stock["gum"] += 32;
4157     stock["ruler"] += 12;
4158     stock ~= "tape roll";
4159     // test for inclusion, various syntax allowed
4160     assert("gum" in stock);
4161     assert(stock["ruler"] == 12);
4162     assert(stock["tape roll"] == 0);
4163     // remove something
4164     stock.remove("ruler");
4165     assert("ruler" !in stock);
4166     // empties and frees memory
4167     stock.clear;
4168     // manually managed implies to destruct by hand
4169     import iz.memory;
4170     destruct(stock);
4171 }
4172 
4173 @nogc unittest
4174 {
4175     HashMap_LP!(string, int) hmsi;
4176     hmsi.reserve(15);
4177 
4178     hmsi.insert("cat", 0);
4179     hmsi.insert("dog", 1);
4180     hmsi.insert("pig", 2);
4181     assert(hmsi.count == 3);
4182     assert(*("cat" in hmsi) == 0);
4183     assert(*("dog" in hmsi) == 1);
4184     assert(*("pig" in hmsi) == 2);
4185     assert("bat" !in hmsi);
4186     assert("bug" !in hmsi);
4187 
4188     hmsi["bat"] = 3;
4189     hmsi["bug"] = 4;
4190     assert(hmsi.count == 5);
4191     assert(*("cat" in hmsi) == 0);
4192     assert(*("dog" in hmsi) == 1);
4193     assert(*("pig" in hmsi) == 2);
4194     assert(*("bat" in hmsi) == 3);
4195     assert(*("bug" in hmsi) == 4);
4196 
4197     assert(hmsi.remove("cat"));
4198     assert(hmsi.count == 4);
4199     assert("cat" !in hmsi);
4200     assert(*("dog" in hmsi) == 1);
4201     assert(*("pig" in hmsi) == 2);
4202     assert(*("bat" in hmsi) == 3);
4203     assert(*("bug" in hmsi) == 4);
4204 
4205     hmsi["owl"] = 5;
4206     assert(hmsi.count == 5);
4207     assert("cat" !in hmsi);
4208     assert(*("dog" in hmsi) == 1);
4209     assert(*("pig" in hmsi) == 2);
4210     assert(*("bat" in hmsi) == 3);
4211     assert(*("bug" in hmsi) == 4);
4212     assert(*("owl" in hmsi) == 5);
4213 
4214     hmsi.clear;
4215     assert(hmsi.count == 0);
4216     assert("cat" !in hmsi);
4217     assert("dog" !in hmsi);
4218     assert("pig" !in hmsi);
4219     assert("bat" !in hmsi);
4220     assert("bug" !in hmsi);
4221     assert("owl" !in hmsi);
4222 
4223     hmsi["bat"] = 3;
4224     hmsi["bug"] = 4;
4225     assert(hmsi.count == 2);
4226     assert(hmsi["bat"] == 3);
4227     assert(hmsi["bug"] == 4);
4228     hmsi["bat"] = 4;
4229     hmsi["bug"] = 3;
4230     assert(hmsi.count == 2);
4231     assert(hmsi["bat"] == 4);
4232     assert(hmsi["bug"] == 3);
4233 
4234     destruct(hmsi);
4235 }
4236 
4237 @nogc unittest
4238 {
4239     HashMap_LP!(int, int) hmii;
4240     hmii.reserve(32);
4241     hmii[1] = 3;
4242     hmii[2] = 4;
4243     foreach(kv; hmii.byKeyValue)
4244     {
4245         assert(kv[0] == 1 || kv[0] == 2);
4246         assert(kv[1] == 3 || kv[1] == 4);
4247     }
4248     destruct(hmii);
4249 }
4250 
4251 /**
4252  * The bucket used in HashSet_AB and HashMap_AB.
4253  */
4254 struct ArrayBucket(K, V = void)
4255 {
4256 
4257 private:
4258 
4259     static if (!isMap)
4260     {
4261         alias ArrayT = Array!K;
4262     }
4263     else
4264     {
4265         alias Pair = Tuple!(K, V);
4266         alias ArrayT = Array!(Pair);
4267     }
4268 
4269     ArrayT _array;
4270 
4271 public:
4272 
4273     enum isMap = !is(V == void);
4274 
4275     ~this() @nogc
4276     {
4277         static if (isMap)
4278         {
4279             foreach (immutable i; 0.._array.length)
4280             {
4281                 static if (is(K == struct))
4282                     destruct(_array[i][0]);
4283                 static if (is(V == struct))
4284                     destruct(_array[i][1]);
4285             }
4286         }
4287         destruct(_array);
4288     }
4289 
4290     this(this) @nogc
4291     {
4292         _array.__postblit;
4293     }
4294 
4295     ref const(ArrayT) array() const @nogc nothrow
4296     {return _array;}
4297 
4298     static if (isMap)
4299     void insert(ref K key, ref V value) @nogc nothrow
4300     {
4301         _array ~= tuple(key, value);
4302     }
4303     else
4304     void insert(ref K key) @nogc nothrow
4305     {
4306         _array ~= key;
4307     }
4308 
4309     bool remove()(ref K key)
4310     {
4311         bool result;
4312         foreach (immutable i; 0.._array._length)
4313         {
4314             static if (!isMap)
4315             {
4316                 static if (hasElaborateSelfEquals!K)
4317                 {
4318                     if (!_array[i].opEquals(key))
4319                         continue;
4320                 }
4321                 else
4322                 {
4323                     if (_array[i] != key)
4324                         continue;
4325                 }
4326             }
4327             else
4328             {
4329                 static if (hasElaborateSelfEquals!K)
4330                 {
4331                     if (!_array[i][0].opEquals(key))
4332                         continue;
4333                 }
4334                 else
4335                 {
4336                     if (_array[i][0] != key)
4337                         continue;
4338                 }
4339             }
4340             result = true;
4341             if (i == 0)
4342             {
4343                 if (_array.length > 1)
4344                     _array = _array[1..$];
4345                 else
4346                     _array.length = 0;
4347             }
4348             else if (i == _array.length-1)
4349             {
4350                 _array.length = _array.length - 1;
4351             }
4352             else _array = _array[0..i] ~ _array[i+1..$];
4353             break;
4354         }
4355         return result;
4356     }
4357 
4358     pragma(inline, true)
4359     void clear() @nogc nothrow
4360     {
4361         _array.length = 0;
4362     }
4363 
4364     ptrdiff_t indexOfKey()(ref K key)
4365     {
4366         ptrdiff_t result = -1;
4367         foreach (immutable i; 0.._array.length)
4368         {
4369             static if (isMap)
4370             {
4371                 static if (hasElaborateSelfEquals!K)
4372                 {
4373                     if (_array[i][0].opEquals(key))
4374                     {
4375                         result = i;
4376                         break;
4377                     }
4378                 }
4379                 else
4380                 {
4381                     if (_array[i][0] == key)
4382                     {
4383                         result = i;
4384                         break;
4385                     }
4386                 }
4387             }
4388             else
4389             {
4390                 static if (hasElaborateSelfEquals!K)
4391                 {
4392                     if (_array[i].opEquals(key))
4393                     {
4394                         result = i;
4395                         break;
4396                     }
4397                 }
4398                 else
4399                 {
4400                     if (_array[i] == key)
4401                     {
4402                         result = i;
4403                         break;
4404                     }
4405                 }
4406             }
4407         }
4408         return result;
4409     }
4410 
4411     pragma(inline, true)
4412     K* getKey(KK)(ref KK key)
4413     {
4414         K* result;
4415         if (const size_t j =  _array.length)
4416             foreach (immutable i; 0..j)
4417         {
4418             static if (isMap)
4419             {
4420                 static if (hasElaborateSelfEquals!K)
4421                 {
4422                     if (_array[i][0].opEquals(key))
4423                     {
4424                         result = &_array[i][0];
4425                         break;
4426                     }
4427                 }
4428                 else
4429                 {
4430                     if (_array[i][0] == key)
4431                     {
4432                         result = &_array[i][0];
4433                         break;
4434                     }
4435                 }
4436             }
4437             else
4438             {
4439                 static if (hasElaborateSelfEquals!K)
4440                 {
4441                     if (_array[i].opEquals(key))
4442                     {
4443                         result = &_array[i];
4444                         break;
4445                     }
4446                 }
4447                 else
4448                 {
4449                     if (_array[i] == key)
4450                     {
4451                         result = &_array[i];
4452                         break;
4453                     }
4454                 }
4455             }
4456         }
4457         return result;
4458     }
4459 
4460     static if (isMap)
4461     V* getValue(KK)(ref KK key)
4462     {
4463         V* result;
4464         if (const size_t j =  _array.length)
4465             foreach (immutable i; 0..j)
4466         {
4467             static if (hasElaborateSelfEquals!K)
4468             {
4469                 if (_array[i][0].opEquals(key))
4470                 {
4471                     result = &_array[i][1];
4472                         break;
4473                 }
4474             }
4475             else
4476             {
4477                 if (_array[i][0] == key)
4478                 {
4479                     result = &_array[i][1];
4480                         break;
4481                 }
4482             }
4483         }
4484         return result;
4485     }
4486 
4487     static if (isMap)
4488     ptrdiff_t indexOfValue()(ref V value)
4489     {
4490         ptrdiff_t result = -1;
4491         foreach(immutable i; 0.._array.length)
4492         {
4493             if (_array[i][1] == value)
4494             {
4495                 result = i;
4496                 break;
4497             }
4498         }
4499         return result;
4500     }
4501 
4502     size_t length() @nogc const pure nothrow {return _array.length;}
4503 }
4504 
4505 private struct RangeForAbSet(T, alias rngKind = rngNoMap)
4506 {
4507 
4508 private:
4509 
4510     T* _hashSetOrMap;
4511     alias B = ReturnType!(T.bucket);
4512     B _currBucket;
4513     bool _empty;
4514     size_t _bucketIndex;
4515     size_t _keyIndex;
4516 
4517 public:
4518 
4519     this(T* hashSetOrMap) @nogc nothrow
4520     {
4521         assert(hashSetOrMap);
4522         _hashSetOrMap = hashSetOrMap;
4523         popFront;
4524     }
4525 
4526     bool empty() @nogc nothrow
4527     {
4528         return _currBucket is null;
4529     }
4530 
4531     void popFront() @nogc nothrow
4532     {
4533         if (_currBucket)
4534         {
4535             ++_keyIndex;
4536             if (_keyIndex >= _currBucket.length)
4537             {
4538                 _currBucket = null;
4539                 _keyIndex = 0;
4540                 ++_bucketIndex;
4541             }
4542         }
4543         if (!_currBucket)
4544         {
4545             while (_bucketIndex < _hashSetOrMap._buckets.length)
4546             {
4547                 _currBucket = (*_hashSetOrMap).bucket(_bucketIndex);
4548                 if (_currBucket.length)
4549                     break;
4550                 else
4551                     ++_bucketIndex;
4552             }
4553             if (_bucketIndex == _hashSetOrMap._buckets.length)
4554                 _currBucket = null;
4555         }
4556     }
4557 
4558     auto ref front() @nogc
4559     {
4560         static if (rngKind == rngNoMap || rngKind == rngMapByKeyValue)
4561             return _currBucket._array[_keyIndex];
4562         else static if (rngKind == rngMapByKey)
4563             return _currBucket._array[_keyIndex][0];
4564         else static if (rngKind == rngMapByValue)
4565             return _currBucket._array[_keyIndex][1];
4566     }
4567 }
4568 
4569 /**
4570  * A manually managed hashset that uses buckets to solve the collisions.
4571  *
4572  * Params:
4573  *      K = the key type.
4574  *      hasherFun = The hashing function, a $(D size_t(K value);) function,
4575  *          literal delegate or lambda.
4576  */
4577 struct HashSet_AB(K, alias hasherFun = fnv1)
4578 {
4579     static assert (is(typeof( (){size_t r = hasherFun(K.init);}  )),
4580         "invalid hash function");
4581     static assert (!is(K == void),
4582         "invalid Key type");
4583 
4584 private:
4585 
4586     alias HashSetT = typeof(this);
4587     alias BucketT = ArrayBucket!K;
4588     @NoGc Array!BucketT _buckets;
4589     size_t _count;
4590 
4591     pragma(inline, true)
4592     size_t hasher(KK)(auto ref KK key) @nogc
4593     {
4594         return hasherFun(key) & (_buckets.length - 1);
4595     }
4596 
4597     void reHash()()
4598     {
4599         _count = 0;
4600         Array!BucketT old = _buckets;
4601         foreach (immutable i; 0.._buckets.length)
4602             _buckets[i].clear;
4603         foreach (immutable i; 0..old.length)
4604         {
4605             foreach (immutable j; 0..old[i]._array.length)
4606                 insert!false(old[i]._array[j]);
4607         }
4608         destruct(old);
4609     }
4610 
4611 public:
4612 
4613     /**
4614      * Constructs using either a list of keys, arrays of keys, or both.
4615      */
4616     this(A...)(A a)
4617     {
4618         import std.meta: aliasSeqOf;
4619         import std.range: iota;
4620 
4621         foreach (i; aliasSeqOf!(iota(0, A.length)))
4622         {
4623             static if (is(A[i] == K))
4624                 continue;
4625             else static if (isArray!(A[i]))
4626                 continue;
4627             else static if (is(A[i] == Array!K))
4628                 continue;
4629             else static assert(0, A[i].stringof ~ " not supported");
4630         }
4631         foreach (i; aliasSeqOf!(iota(0, A.length)))
4632                 insert(a[i]);
4633     }
4634 
4635     ~this() @nogc
4636     {
4637         destruct(_buckets);
4638     }
4639 
4640     /**
4641      * Tries to insert key(s) in the set.
4642      *
4643      * Params:
4644      *      mode = If true (imExpand) then reserves a slot else (imReserved)
4645      *          assumes a previous call to $(D reserve()).
4646      *      key = either single keys, array of keys, or both.
4647      * Throws:
4648      *      An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails.
4649      * Returns:
4650      *      If the key is added or if it's already included then returns $(D true),
4651      *      otherwise $(D false).
4652      */
4653     bool insert(alias mode = true)(ref K key) @nogc
4654     if (isImplicitlyConvertible!(typeof(mode), bool))
4655     {
4656         bool result;
4657         if (!_buckets.length || key !in this)
4658         {
4659             result = true;
4660             static if (mode)
4661                 reserve(1);
4662             const size_t h = hasher(key);
4663             assert(h < _buckets.length);
4664             _buckets[h].insert(key);
4665             ++_count;
4666         }
4667         return result;
4668     }
4669 
4670     /// ditto
4671     bool insert(alias mode = true)(K key) @nogc
4672     if (isImplicitlyConvertible!(typeof(mode), bool))
4673     {
4674         return insert!mode(key);
4675     }
4676 
4677     /// ditto
4678     bool insert(KK)(auto ref KK keys)
4679     if ((isArray!KK && is(Unqual!(ElementEncodingType!KK) == K)) || is(KK == Array!K))
4680     {
4681         bool result = true;
4682         reserve(keys.length);
4683         foreach(k; keys)
4684             result &= insert!false(k);
4685         return result;
4686     }
4687 
4688     /// ditto
4689     bool insert(KK...)(auto ref KK keys)
4690     {
4691         bool result = true;
4692         reserve(KK.length);
4693         foreach(k; keys)
4694             result &= insert!false(k);
4695         return result;
4696     }
4697 
4698     /**
4699      * Tries to remove a key from the set.
4700      *
4701      * Returns:
4702      *      $(D true) if the key was included otherwise $(D false).
4703      */
4704     bool remove()(auto ref K key)
4705     {
4706         const size_t h = hasher(key);
4707         const bool result = _buckets[h].remove(key);
4708         if (result)
4709             --_count;
4710         return result;
4711     }
4712 
4713     /**
4714      * Reserves buckets for at least N supplemental keys.
4715      *
4716      * Throws:
4717      *      An $(D OutOfMemoryError) if the reallocation fails.
4718      * Params:
4719      *      value = The count of additional slots to reserve.
4720      */
4721     void reserve()(size_t value)
4722     {
4723         import std.math: nextPow2;
4724         const size_t nl = nextPow2(_count + value);
4725         if (nl > _buckets.length)
4726         {
4727             _buckets.length = nl;
4728             reHash();
4729         }
4730     }
4731 
4732     /**
4733      * Minimizes the memory used by the set.
4734      *
4735      * Throws:
4736      *      An $(D OutOfMemoryError) if the reallocation fails.
4737      */
4738     void minimize()()
4739     {
4740         import std.math: nextPow2;
4741         const size_t nl = nextPow2(_count-1);
4742 
4743         if (nl < _buckets.length)
4744         {
4745             Array!BucketT old = _buckets;
4746             clear;
4747              _buckets.length = nl;
4748             foreach (immutable i; 0..old.length)
4749                 foreach (immutable j; 0..old[i]._array.length)
4750             {
4751                 insert!false(old[i]._array[j]);
4752             }
4753             destruct(old);
4754         }
4755     }
4756 
4757     /**
4758      * Empties the set.
4759      */
4760     void clear() @nogc
4761     {
4762         _buckets.length = 0;
4763         _buckets.length = 2;
4764         _count = 0;
4765     }
4766 
4767     /**
4768      * Tests the presence of a key in the set.
4769      *
4770      * Params:
4771      *      key = The key to test.
4772      * Returns:
4773      *      $(D null) if the key is not present otherwise a pointer to the key.
4774      */
4775     pragma(inline, true)
4776     K* opBinaryRight(string op : "in", KK)(auto ref KK key)
4777     {
4778         return _buckets[hasher(key)].getKey(key);
4779     }
4780 
4781     /**
4782      * Provides an access to the buckets.
4783      *
4784      * Params:
4785      *      index = The bucket index. Must be in the $(D 0..bucketCount()) range.
4786      * Returns:
4787      *      A never null, pointer to a bucket.
4788      */
4789     BucketT* bucket(const size_t index) pure nothrow @nogc
4790     {
4791         return &_buckets[index];
4792     }
4793 
4794     /**
4795      * Returns: an input range that allows to iterate the keys.
4796      */
4797     auto byKey()
4798     {
4799         return RangeForAbSet!HashSetT(&this);
4800     }
4801 
4802     /**
4803      * Returns: the elements count.
4804      */
4805     size_t count() pure nothrow @nogc {return _count;}
4806 
4807     /**
4808      * Returns: the buckets count.
4809      */
4810     size_t bucketCount() pure nothrow @nogc {return _buckets.length;}
4811 
4812     /**
4813      * Returns: the collisions count.
4814      */
4815     size_t collisions() pure nothrow @nogc
4816     {
4817         size_t result;
4818         foreach(immutable i; 0.._buckets.length)
4819             result += _buckets[i]._array.length > 1 ?
4820                 _buckets[i]._array.length - 1 : 0;
4821         return result;
4822     }
4823 }
4824 ///
4825 @nogc unittest
4826 {
4827     HashSet_AB!string commands;
4828     // can insert up to 16 elements without reallocation
4829     commands.reserve(15);
4830     assert(commands.bucketCount == 16);
4831     // appends elements
4832     commands.insert("move");
4833     commands.insert("insert");
4834     commands.insert("delete");
4835     // test for inclusion
4836     assert("move" in commands);
4837     // remove something
4838     commands.remove("insert");
4839     assert(commands.count == 2);
4840     assert("insert" !in commands);
4841     // empties and frees memory
4842     commands.clear;
4843     // manually managed implies to destruct by hand
4844     import iz.memory;
4845     destruct(commands);
4846 }
4847 
4848 @nogc unittest
4849 {
4850     HashSet_AB!string hss;
4851 
4852     assert(hss.insert("cat"));
4853     assert(hss.bucketCount == 2);
4854     assert("dog" !in hss);
4855     assert("cat" in hss);
4856 
4857     assert(hss.insert("rat"));
4858     assert("dog" !in hss);
4859     assert("cat" in hss);
4860     assert("rat" in hss);
4861 
4862     assert(hss.insert("fly"));
4863     assert("dog" !in hss);
4864     assert("cat" in hss);
4865     assert("rat" in hss);
4866     assert("fly" in hss);
4867 
4868     assert(hss.insert("bee"));
4869     assert("dog" !in hss);
4870     assert("cat" in hss);
4871     assert("rat" in hss);
4872     assert("fly" in hss);
4873     assert("bee" in hss);
4874 
4875     assert(hss.insert("ant"));
4876     assert("dog" !in hss);
4877     assert("cat" in hss);
4878     assert("rat" in hss);
4879     assert("fly" in hss);
4880     assert("bee" in hss);
4881     assert("ant" in hss);
4882     assert("fox" !in hss);
4883 
4884     assert(hss.insert("fox"));
4885     assert("dog" !in hss);
4886     assert("cat" in hss);
4887     assert("rat" in hss);
4888     assert("fly" in hss);
4889     assert("bee" in hss);
4890     assert("ant" in hss);
4891     assert("fox" in hss);
4892 
4893     assert(hss.insert("bat"));
4894     assert("dog" !in hss);
4895     assert("cat" in hss);
4896     assert("rat" in hss);
4897     assert("fly" in hss);
4898     assert("bee" in hss);
4899     assert("ant" in hss);
4900     assert("fox" in hss);
4901     assert("bat" in hss);
4902 
4903     assert(hss.insert("cow"));
4904     assert("dog" !in hss);
4905     assert("cat" in hss);
4906     assert("rat" in hss);
4907     assert("fly" in hss);
4908     assert("bee" in hss);
4909     assert("ant" in hss);
4910     assert("fox" in hss);
4911     assert("bat" in hss);
4912     assert("cow" in hss);
4913 
4914     assert(hss.remove("bat"));
4915     assert("bat" !in hss);
4916 
4917     hss.clear;
4918     assert(hss.count == 0);
4919 
4920     import std.algorithm: among;
4921     hss.reserve(20);
4922     assert(hss.insert("cow"));
4923     assert(hss.insert("yak"));
4924     auto r = hss.byKey;
4925     assert(!r.empty);
4926     assert((r.front).among("cow","yak"));
4927     r.popFront;
4928     assert(!r.empty);
4929     assert((r.front).among("cow","yak"));
4930     r.popFront;
4931     assert(r.empty);
4932 
4933     assert(hss.bucketCount == 32);
4934     hss.minimize;
4935     assert(hss.bucketCount == 2);
4936 
4937     destruct(hss);
4938 }
4939 
4940 @nogc unittest
4941 {
4942     HashSet_AB!int hsi;
4943     assert(hsi.byKey.empty);
4944     destruct(hsi);
4945 }
4946 
4947 /**
4948  * A manually managed hashmap that uses buckets to solve the collisions.
4949  *
4950  * Params:
4951  *      K = the key type.
4952  *      V = the value type.
4953  *      hasherFun = The hashing function, a $(D size_t(K value);) function,
4954  *          literal delegate or lambda.
4955  */
4956 struct HashMap_AB(K, V, alias hasherFun = fnv1)
4957 {
4958     static assert (is(typeof( (){size_t r = hasherFun(K.init);}  )),
4959         "invalid hash function");
4960     static assert (!is(K == void),
4961         "invalid Key type");
4962     static assert (!is(V == void),
4963         "invalid Value type");
4964 
4965 private:
4966 
4967     alias HashMapT = typeof(this);
4968     alias BucketT = ArrayBucket!(K,V);
4969     @NoGc Array!BucketT _buckets;
4970     size_t _count;
4971 
4972     pragma(inline, true)
4973     size_t hasher(KK)(auto ref KK key) @nogc
4974     {
4975         return hasherFun(key) & (_buckets.length - 1);
4976     }
4977 
4978     void reHash()()
4979     {
4980         //_count = 0;
4981         Array!BucketT old = _buckets;
4982         foreach (immutable i; 0.._buckets.length)
4983             _buckets[i].clear;
4984         foreach (immutable i; 0..old.length)
4985         {
4986             foreach (immutable j; 0..old[i]._array.length)
4987             {
4988                 const h = hasher(old[i]._array[j][0]);
4989                 _buckets[h].insert(old[i]._array[j][0], old[i]._array[j][1]);
4990             }
4991         }
4992         destruct(old);
4993     }
4994 
4995 public:
4996 
4997     ~this() @nogc
4998     {
4999         destruct(_buckets);
5000     }
5001 
5002     /**
5003      * Tries to insert a key-value pair in the set.
5004      *
5005      * Params:
5006      *      mode = If set to $(D imExpand) then reserves a slot else
5007      *          if set to $(D imReserved) assumes a previous call to $(D reserve()).
5008      *      key = The key.
5009      *      value = The value.
5010      * Throws:
5011      *      An $(D OutOfMemoryError) if an internal call to $(D reserve()) fails.
5012      * Returns:
5013      *      If the key is added or if it's already included then returns $(D true),
5014      *      otherwise $(D false).
5015      */
5016     bool insert(alias mode = imExpand)(ref K key, auto ref V value) @nogc
5017     if (isImplicitlyConvertible!(typeof(mode), bool))
5018     {
5019         bool result;
5020         if (!_buckets.length)
5021             reserve(1);
5022         if (key !in this)
5023         {
5024             result = true;
5025             static if (mode)
5026                 reserve(1);
5027             const size_t h = hasher(key);
5028             assert(h < _buckets.length);
5029             _buckets[h].insert(key, value);
5030             ++_count;
5031         }
5032         else
5033         {
5034             result = true;
5035             const size_t h = hasher(key);
5036             assert(h < _buckets.length);
5037             _buckets[h].remove(key);
5038             _buckets[h].insert(key, value);
5039         }
5040         return result;
5041     }
5042 
5043     /// ditto
5044     bool insert(alias mode = imExpand)(K key, V value) @nogc
5045     if (isImplicitlyConvertible!(typeof(mode), bool))
5046     {
5047         return insert!mode(key, value);
5048     }
5049 
5050     /**
5051      * Tries to remove a key from the set.
5052      *
5053      * Returns:
5054      *      $(D true) if the key was included otherwise $(D false).
5055      */
5056     bool remove()(auto ref K key) @nogc
5057     {
5058         const size_t h = hasher(key);
5059         const bool result = _buckets[h].remove(key);
5060         if (result)
5061             --_count;
5062         return result;
5063     }
5064 
5065     /**
5066      * Reserves buckets for at least N supplemental key-value pairs.
5067      *
5068      * Throws:
5069      *      An $(D OutOfMemoryError) if the reallocation fails.
5070      * Params:
5071      *      value = The count of additional slots to reserve.
5072      */
5073     void reserve()(size_t value) @nogc
5074     {
5075         import std.math: nextPow2;
5076         const size_t nl = nextPow2(_count + value);
5077         if (nl > _buckets.length)
5078         {
5079             _buckets.length = nl;
5080             reHash();
5081         }
5082     }
5083 
5084     /**
5085      * Minimizes the memory used by the map.
5086      *
5087      * Throws:
5088      *      An $(D OutOfMemoryError) if the reallocation fails.
5089      */
5090     void minimize()()
5091     {
5092         import std.math: nextPow2;
5093         const size_t nl = nextPow2(_count-1);
5094 
5095         if (nl < _buckets.length)
5096         {
5097             Array!BucketT old = _buckets;
5098             clear;
5099              _buckets.length = nl;
5100             foreach (immutable i; 0..old.length)
5101                 foreach (immutable j; 0..old[i]._array.length)
5102             {
5103                 insert!false(old[i]._array[j][0], old[i]._array[j][1]);
5104             }
5105             destruct(old);
5106         }
5107     }
5108 
5109     /**
5110      * Empties the map.
5111      */
5112     void clear() @nogc
5113     {
5114         _buckets.length = 0;
5115         _buckets.length = 2;
5116         _count = 0;
5117     }
5118 
5119     /**
5120      * Retrieves the value associated to a key.
5121      *
5122      * Params:
5123      *      key = The key.
5124      * Returns:
5125      *      $(D null) if the key is not present otherwise a pointer to associated value.
5126      */
5127     V* opBinaryRight(string op : "in", KK)(auto ref KK key)
5128     {
5129         V* result;
5130         if (_buckets.length)
5131             result = _buckets[hasher(key)].getValue(key);
5132         return result;
5133     }
5134 
5135     /**
5136      * Support for appending an element.
5137      *
5138      * Forwards $(D insert()) with a default initialized value.
5139      *
5140      * Params:
5141      *      key = The key to insert.
5142      * Returns:
5143      *      If the key is added or if it's already included then returns $(D true),
5144      *      otherwise $(D false).
5145      */
5146     bool opOpAssign(string op : "~")(auto ref K key)
5147     {
5148         return insert(key, V.init);
5149     }
5150 
5151     /**
5152      * Provides an access to the buckets.
5153      *
5154      * Params:
5155      *      index = The bucket index. Must be in the $(D 0..bucketCount()) range.
5156      * Returns:
5157      *      A never null pointer to a bucket.
5158      */
5159     BucketT* bucket(const size_t index) pure nothrow @nogc
5160     {
5161         return &_buckets[index];
5162     }
5163 
5164     /**
5165      * Support for retrieving a value using the array syntax.
5166      */
5167     auto ref V opIndex(KK)(auto ref KK key)
5168     {
5169         import std.stdio;
5170         return *(key in this);
5171     }
5172 
5173     /**
5174      * Support for assigning using the array syntax.
5175      */
5176     void opIndexAssign(KK)(auto ref V value, auto ref KK key)
5177     {
5178         insert(key, value);
5179     }
5180 
5181     /**
5182      * Support for assigning to the value when the value is itself an AA.
5183      *
5184      * Note that this function only exists to port code that uses the runtime AA
5185      * with the syntax $(D aa[k_for_value][k_for_value_of_value] = stuff;).
5186      */
5187     void opIndexAssign(V2, KK1, KK2)(auto ref V2 value, auto ref KK1 key1, auto ref KK2 key2)
5188     {
5189         if (auto v = key1 in this)
5190         {
5191             v.insert(key2, value);
5192         }
5193         else
5194         {
5195             V v; v.reserve(1);
5196             v.insert(key2, value);
5197             insert!imReserved(key1, v);
5198         }
5199     }
5200 
5201     /**
5202      * Support for the assignment operators on a value.
5203      */
5204     void opIndexOpAssign(string op, VV, KK)(auto ref VV value, auto ref KK key)
5205     {
5206         if (auto p = key in this)
5207         {
5208             mixin("(*p) " ~ op ~ "= value;");
5209         }
5210         else
5211         {
5212             V v;
5213             mixin("v" ~ op ~ "= value;");
5214             insert(key, v);
5215         }
5216     }
5217 
5218     /**
5219      * Returns: an input range that allows to iterate the key-value pairs.
5220      */
5221     auto byKeyValue()
5222     {
5223         return RangeForAbSet!HashMapT(&this);
5224     }
5225 
5226     /**
5227      * Returns: an input range that allows to iterate the keys.
5228      */
5229     auto byKey()
5230     {
5231         return RangeForAbSet!(HashMapT,rngMapByKey)(&this);
5232     }
5233 
5234     /**
5235      * Returns: an input range that allows to iterate the values.
5236      */
5237     auto byValue()
5238     {
5239         return RangeForAbSet!(HashMapT,rngMapByValue)(&this);
5240     }
5241 
5242     /**
5243      * Returns: the elements count.
5244      */
5245     size_t count() pure nothrow @nogc {return _count;}
5246 
5247     /**
5248      * Returns the buckets count.
5249      */
5250     size_t bucketCount() pure nothrow @nogc {return _buckets.length;}
5251 
5252     /**
5253      * Returns: the collisions count.
5254      */
5255     size_t collisions() pure nothrow @nogc
5256     {
5257         size_t result;
5258         foreach(immutable i; 0.._buckets.length)
5259             result += _buckets[i]._array.length > 1 ?
5260                 _buckets[i]._array.length - 1 : 0;
5261         return result;
5262     }
5263 }
5264 ///
5265 @nogc unittest
5266 {
5267     HashMap_AB!(string, size_t) stock;
5268     // can insert up to 16 elements without reallocation
5269     stock.reserve(15);
5270     assert(stock.bucketCount == 16);
5271     // appends elements, various syntax allowed
5272     stock.insert("pen", 8);
5273     stock["gum"] += 32;
5274     stock["ruler"] += 12;
5275     stock ~= "tape roll";
5276     // test for inclusion, various syntax allowed
5277     assert("gum" in stock);
5278     assert(stock["ruler"] == 12);
5279     assert(stock["tape roll"] == 0);
5280     // remove something
5281     stock.remove("ruler");
5282     assert("ruler" !in stock);
5283     // empties and frees memory
5284     stock.clear;
5285     // manually managed implies to destruct by hand
5286     import iz.memory;
5287     destruct(stock);
5288 }
5289 
5290 @nogc unittest
5291 {
5292     HashMap_AB!(string, int) hmsi;
5293 
5294     hmsi.insert("cat", 0);
5295     hmsi.insert("dog", 1);
5296     hmsi.insert("pig", 2);
5297     assert(hmsi.count == 3);
5298     assert(*("cat" in hmsi) == 0);
5299     assert(*("dog" in hmsi) == 1);
5300     assert(*("pig" in hmsi) == 2);
5301     assert("bat" !in hmsi);
5302     assert("bug" !in hmsi);
5303 
5304     hmsi["bat"] = 3;
5305     hmsi["bug"] = 4;
5306     assert(hmsi.count == 5);
5307     assert(*("cat" in hmsi) == 0);
5308     assert(*("dog" in hmsi) == 1);
5309     assert(*("pig" in hmsi) == 2);
5310     assert(*("bat" in hmsi) == 3);
5311     assert(*("bug" in hmsi) == 4);
5312 
5313     assert(hmsi.remove("cat"));
5314     assert(hmsi.count == 4);
5315     assert("cat" !in hmsi);
5316     assert(*("dog" in hmsi) == 1);
5317     assert(*("pig" in hmsi) == 2);
5318     assert(*("bat" in hmsi) == 3);
5319     assert(*("bug" in hmsi) == 4);
5320 
5321     hmsi["owl"] = 5;
5322     assert(hmsi.count == 5);
5323     assert("cat" !in hmsi);
5324     assert(*("dog" in hmsi) == 1);
5325     assert(*("pig" in hmsi) == 2);
5326     assert(*("bat" in hmsi) == 3);
5327     assert(*("bug" in hmsi) == 4);
5328     assert(*("owl" in hmsi) == 5);
5329 
5330     hmsi.clear;
5331     assert(hmsi.count == 0);
5332     assert("cat" !in hmsi);
5333     assert("dog" !in hmsi);
5334     assert("pig" !in hmsi);
5335     assert("bat" !in hmsi);
5336     assert("bug" !in hmsi);
5337     assert("owl" !in hmsi);
5338 
5339     hmsi["bat"] = 3;
5340     hmsi["bug"] = 4;
5341     assert(hmsi.count == 2);
5342     assert(hmsi["bat"] == 3);
5343     assert(hmsi["bug"] == 4);
5344     hmsi["bat"] = 4;
5345     hmsi["bug"] = 3;
5346     assert(hmsi.count == 2);
5347     assert(hmsi["bat"] == 4);
5348     assert(hmsi["bug"] == 3);
5349 
5350     destruct(hmsi);
5351 }
5352 
5353 @nogc unittest
5354 {
5355     HashMap_AB!(int, int) aa;
5356     assert(1 !in aa);
5357 }
5358 
5359 @nogc unittest
5360 {
5361     HashMap_AB!(int, int) aa;
5362     aa[0] = 0;
5363 }
5364 
5365 @nogc unittest
5366 {
5367     HashMap_AB!(string, void*) aa0;
5368     aa0[""] = null;
5369     HashMap_AB!(void*, string) aa1;
5370     //aa1[null] = "";
5371 }
5372 
5373 unittest
5374 {
5375     HashSet_AB!(const(char)[]) aa0;
5376     string s = "s";
5377     aa0.insert(s);
5378 }
5379 
5380 @nogc unittest
5381 {
5382     struct Foo {}
5383     HashMap_AB!(Foo,Foo) a1;
5384     class Bar
5385     {
5386         override bool opEquals(Object o) const pure @nogc nothrow {return o is this;}
5387     }
5388     {HashMap_AB!(Bar,Bar) a2;}
5389     {HashMap_LP!(Bar,Bar) a2;}
5390     {
5391         HashSet_AB!(Bar) a2;
5392         Bar b = construct!Bar;
5393         a2.insert(b);
5394         a2.remove(b);
5395         destruct!true(b);
5396     }
5397     {
5398         HashSet_LP!(Bar) a2;
5399         Bar b = construct!Bar;
5400         a2.insert(b);
5401         a2.remove(b);
5402         destruct!true(b);
5403     }
5404 }
5405 
5406 //TODO-cHashMaps: proper support for post++/--
5407 version (none) unittest
5408 {
5409     {
5410         HashMap_LP!(string, size_t) aa;
5411         aa["0"] += 1;
5412         assert(aa["0"] == 1);
5413         aa["0"]++ ;
5414         assert(aa["0"] == 2);
5415     }
5416     {
5417         //HashMap_AB!(string, size_t) aa;
5418         //aa["0"]++;
5419         //assert(aa["0"] == 1);
5420         //aa["0"]++ ;
5421         //assert(aa["0"] == 2);
5422         //aa["1"]++;
5423         //assert(aa["1"] == 1);
5424         //aa["1"]-- ;
5425         //assert(aa["1"] == 0);
5426     }
5427     {
5428         //HashMap_LP!(string, size_t) aa;
5429         //aa["0"]++;
5430         //assert(aa["0"] == 1);
5431         //aa["0"]++;
5432         //assert(aa["0"] == 2);
5433         //aa["1"]++;
5434         //assert(aa["1"] == 1);
5435         //aa["1"]-- ;
5436         //assert(aa["1"] == 0);
5437     }
5438 }
5439 
5440 unittest
5441 {
5442     HashMap_AB!(string, int) aa;
5443     aa.insert("0",2);
5444     aa["0"] += 0;
5445     aa.insert("1",2);
5446     assert("1" in aa);
5447     aa["1"] += 0;
5448     assert(aa.count == 2);
5449     auto rng = aa.byValue;
5450     assert(!rng.empty);
5451     assert(rng.front == 2);
5452     rng.popFront;
5453     assert(!rng.empty);
5454     assert(rng.front == 2);
5455     rng.popFront;
5456     assert(rng.empty);
5457     destruct(aa);
5458 }
5459 
5460 unittest
5461 {
5462     {
5463         alias AA1 = HashMap_AB!(string, int);
5464         HashMap_AB!(string, AA1) aa;
5465         // note: runtime AA syntax is `aa["0"]["0"] = 42;`
5466         aa["0", "0"] = 42;
5467         auto aaOf_0 = aa["0"];
5468         assert(aaOf_0["0"] == 42);
5469         destruct(aa);
5470     }
5471     {
5472         alias AA1 = HashMap_LP!(string, int);
5473         HashMap_LP!(string, AA1) aa;
5474         aa["0", "0"] = 42;
5475         auto aaOf_0 = aa["0"];
5476         assert(aaOf_0["0"] == 42);
5477         destruct(aa);
5478     }
5479 }
5480