1 module nxt.cyclic;
2 
3 import core.internal.traits : hasElaborateDestructor;
4 import std.algorithm : max;
5 import std.container.array : Array;
6 import std.range;
7 import std.traits : isMutable;
8 import nxt.container_traits : mustAddGCRange;
9 
10 private mixin template CyclicRangePrimitives(T, string makeCopy = "typeof(cast() this) copy;")
11 {
12     size_t capacity() const @property @nogc @safe
13     {
14         return array.length;
15     }
16 
17     size_t length() const @property @nogc @safe
18     {
19         return size;
20     }
21 
22     void put()(auto ref T val)
23     {
24         if (size >= array.length)
25             throw staticError!CyclicRangeError("array capacity overflow", __FILE__, __LINE__);
26         array[(start + size) % array.length] = val;
27         size++;
28     }
29 
30     void put()(const auto ref T val)
31     {
32         if (size >= array.length)
33             throw staticError!CyclicRangeError("array capacity overflow", __FILE__, __LINE__);
34         array[(start + size) % array.length] = val;
35         size++;
36     }
37 
38     void insertBack(T rhs)
39     {
40         put(rhs);
41     }
42 
43     void insertBack(size_t n)(T[n] rhs)
44     {
45         foreach (c; rhs)
46         {
47             put(c);
48         }
49     }
50 
51     void insertBack(Range)(Range rhs)
52         if (__traits(compiles, ElementType!Range) &&
53             is(ElementType!Range : T))
54     {
55         foreach (c; rhs)
56         {
57             put(c);
58         }
59     }
60 
61     alias stableInsertBack = insertBack;
62     alias insert = insertBack;
63     alias stableInsert = insertBack;
64     alias linearInsert = insertBack;
65     alias stableLinearInsert = insertBack;
66 
67     void insertFront()(auto ref T val)
68     {
69         if (size >= array.length)
70             throw staticError!CyclicRangeError("array capacity overflow", __FILE__, __LINE__);
71         start = (start + array.length - 1) % array.length;
72         array[start] = val;
73         size++;
74     }
75 
76     void popFront()
77     {
78         if (size == 0)
79             throw staticError!CyclicRangeError("trying to pop an empty array", __FILE__, __LINE__);
80         static if (hasElaborateDestructor!T)
81             destroy(array[start]);
82         else static if (mustAddGCRange!T)
83             array[start] = T.init; // avoid GC mark-phase dereference
84         start = (start + 1) % array.length;
85         size--;
86     }
87 
88     auto save()
89     {
90         return this;
91     }
92 
93     bool empty() @nogc @safe @property const
94     {
95         return size == 0;
96     }
97 
98     ref auto front() @nogc @safe @property inout
99     {
100         if (size == 0)
101             throw staticError!CyclicRangeError("trying to call front on empty array",
102                                                __FILE__, __LINE__);
103         return array[start];
104     }
105 
106     void popBack()
107     {
108         if (size == 0)
109             throw staticError!CyclicRangeError("trying to pop an empty array", __FILE__, __LINE__);
110         size--;
111         static if (hasElaborateDestructor!T)
112             destroy(array[(start + size) % array.length]);
113         else static if (mustAddGCRange!T)
114             array[(start + size) % array.length] = T.init; // avoid GC mark-phase dereference
115     }
116 
117     ref auto back() @property
118     {
119         if (size == 0)
120             throw staticError!CyclicRangeError("trying to call back on empty array",
121                                                __FILE__, __LINE__);
122         return array[(start + size - 1) % array.length];
123     }
124 
125     auto back() @property const
126     {
127         if (size == 0)
128             throw staticError!CyclicRangeError("trying to call back on empty array",
129                                                __FILE__, __LINE__);
130         return array[(start + size - 1) % array.length];
131     }
132 
133     size_t opDollar() @nogc @safe const
134     {
135         return length;
136     }
137 
138     ref inout(T) opIndex(size_t v) inout
139     {
140         if (v >= size)
141             throw staticError!CyclicRangeError("out of range", __FILE__, __LINE__);
142         else
143             return array[(v + start) % array.length];
144     }
145 
146     auto opIndex() const
147     {
148         return this.dup();
149     }
150 
151     private void validateRange(size_t[2] range)
152     {
153         immutable size_t from = range[0];
154         immutable size_t to = range[1];
155         if (to > size)
156             throw staticError!CyclicRangeError("trying to slice over array size",
157                                                __FILE__, __LINE__);
158         if (from > to)
159             throw staticError!CyclicRangeError("trying to negative slice", __FILE__, __LINE__);
160         if (from != to && from >= size || to - from > size)
161             throw staticError!CyclicRangeError("trying to slice over array bounds",
162                                                __FILE__, __LINE__);
163     }
164 
165     auto opIndex(size_t[2] range)
166     {
167         immutable size_t from = range[0];
168         immutable size_t to = range[1];
169         validateRange(range);
170 
171         mixin(makeCopy);
172         copy.start = 0;
173         copy.size = to - from;
174 
175         foreach (const i; 0 .. copy.size)
176         {
177             copy.array[i] = array[(i + start + from) % array.length];
178         }
179         return copy;
180     }
181 
182     static if (isMutable!T)
183     {
184         void opIndexUnary(string op)()
185         {
186             foreach (const i; 0 .. size)
187             {
188                 mixin(op ~ "array[(i + start) % array.length];");
189             }
190         }
191 
192         auto opIndexUnary(string op)(size_t i)
193         {
194             return mixin(op ~ "array[(i + start) % array.length]");
195         }
196 
197         void opIndexUnary(string op)(size_t[2] range)
198         {
199             immutable size_t from = range[0];
200             immutable size_t to = range[1];
201             validateRange(range);
202 
203             foreach (const i; 0 .. to - from)
204             {
205                 mixin(op ~ "array[(i + start + from) % array.length];");
206             }
207         }
208 
209         void opIndexAssign(U)(U val)
210         {
211             foreach (const i; 0 .. size)
212             {
213                 array[(i + start) % array.length] = val;
214             }
215         }
216 
217         void opIndexAssign(U)(U val, size_t i)
218         {
219             opIndex(i) = val;
220         }
221 
222         void opIndexAssign(U)(U val, size_t[2] range)
223         {
224             immutable size_t from = range[0];
225             immutable size_t to = range[1];
226             validateRange(range);
227 
228             foreach (const i; 0 .. to - from)
229             {
230                 array[(i + start + from) % array.length] = val;
231             }
232         }
233 
234         void opIndexOpAssign(string op, U)(U val)
235         {
236             foreach (const i; 0 .. size)
237             {
238                 mixin("array[(i + start) % array.length] " ~ op ~ "= val;");
239             }
240         }
241 
242         void opIndexOpAssign(string op, U)(U val, size_t i)
243         {
244             mixin("array[(i + start) % array.length] " ~ op ~ "= val;");
245         }
246 
247         void opIndexOpAssign(string op, U)(U val, size_t[2] range)
248         {
249             immutable size_t from = range[0];
250             immutable size_t to = range[1];
251             validateRange(range);
252 
253             foreach (const i; 0 .. to - from)
254             {
255                 mixin("array[(i + start + from) % array.length] " ~ op ~ "= val;");
256             }
257         }
258     }
259 
260     static if (isMutable!T)
261     {
262         import std.algorithm.mutation : move;
263 
264         T moveFront()
265         {
266             if (size == 0)
267                 throw staticError!CyclicRangeError("trying to move in empty array",
268                                                    __FILE__, __LINE__);
269             return move(array[0]);
270         }
271 
272         T moveBack()
273         {
274             if (size == 0)
275                 throw staticError!CyclicRangeError("trying to move in empty array",
276                                                    __FILE__, __LINE__);
277             return move(array[(start + size - 1) % array.length]);
278         }
279 
280         T moveAt(size_t i)
281         {
282             if (i >= size)
283                 throw staticError!CyclicRangeError("trying to move outside range",
284                                                    __FILE__, __LINE__);
285             return move(array[(start + i) % array.length]);
286         }
287     }
288 
289     size_t[2] opSlice(size_t i : 0)() const
290     {
291         return [0, size];
292     }
293 
294     size_t[2] opSlice(size_t i : 0)(size_t from, size_t to) const
295     {
296         return [from, to];
297     }
298 
299     /**
300      * Removes the last element from the array and returns it.
301      * Both stable and non-stable versions behave the same and guarantee
302      * that ranges iterating over the array are never invalidated.
303      *
304      * Precondition: `empty == false`
305      *
306      * Returns: The element removed.
307      *
308      * Complexity: $(BIGOH 1).
309      *
310      * Throws: `Exception` if the array is empty.
311      */
312     T removeAny()
313     {
314         auto result = back;
315         removeBack();
316         return result;
317     }
318 
319     alias stableRemoveAny = removeAny;
320 
321     /**
322      * Removes the value from the back of the array. Both stable and non-stable
323      * versions behave the same and guarantee that ranges iterating over the
324      * array are never invalidated.
325      *
326      * Precondition: `empty == false`
327      *
328      * Complexity: $(BIGOH 1).
329      *
330      * Throws: `Exception` if the array is empty.
331      */
332     void removeBack()
333     {
334         popBack();
335     }
336 
337     /// ditto
338     alias stableRemoveBack = removeBack;
339 
340     void removeBack(int howMany)
341     {
342         foreach (const i; 0 .. howMany)
343         {
344             popBack();
345         }
346     }
347 }
348 
349 struct CyclicRange(T)
350 {
351     T[] array;
352     size_t start, size;
353 
354     mixin CyclicRangePrimitives!T;
355 
356     CyclicRange!T dup() const
357     {
358         return cast(CyclicRange!T) this;
359     }
360 }
361 
362 /// @nogc array without memory management using a cyclic array internally
363 /// Should be treated like a static array when no len is set (copies on assignment)
364 /// The maximum capacity is static and by default so many elements that it fills at most 4KiB, but at least 8 elements (even if that is more than 4KiB).
365 /// Set length to 0 to make it a std.container.Array based array
366 /// Bugs: foreach with ref value requires @nogc body to make this @nogc compatible
367 struct CyclicArray(T, size_t len = max(8, 4096 / T.sizeof))
368 {
369     static if (len == 0)
370     {
371         private void reserve(size_t length) @nogc @system nothrow
372         {
373             assert(length > 0);
374             array.length = length;
375         }
376     }
377 
378 private:
379     static if (len == 0)
380         Array!T array;
381     else
382         T[len] array;
383     size_t start;
384     size_t size;
385 
386 public:
387     static if (len == 0)
388     {
389         invariant
390         {
391             assert(array.length > 0);
392         }
393 
394         // @disable this(); // TODO this triggers bug in dmd: https://issues.dlang.org/show_bug.cgi?id=20934
395 
396         this(Array!T array) @nogc
397         {
398             assert(array.length > 0);
399             this.array = array;
400         }
401 
402         this(size_t length) @nogc
403         {
404             assert(length > 0);
405             array = Array!T();
406             reserve(length);
407         }
408 
409         this(size_t n)(T[n] val)
410         {
411             array = Array!T();
412             reserve(max(8, 4096 / T.sizeof));
413             static if (len != 0)
414                 static assert(n <= len);
415             foreach (ref v; val)
416             {
417                 put(v);
418             }
419         }
420 
421         this(Range)(Range val)
422         if (__traits(compiles, ElementType!Range) && is(ElementType!Range : T))
423         {
424             array = Array!T();
425             reserve(max(8, 4096 / T.sizeof));
426             foreach (ref v; val)
427             {
428                 put(v);
429             }
430         }
431 
432         this(Args...)(Args val)
433         {
434             array = Array!T();
435             reserve(max(8, 4096 / T.sizeof));
436             foreach (ref v; val)
437             {
438                 put(v);
439             }
440         }
441     }
442     else
443     {
444         this(size_t n)(T[n] val)
445         {
446             static if (len != 0)
447             {
448                 static assert(n <= len);
449             }
450             foreach (ref v; val)
451             {
452                 put(v);
453             }
454         }
455 
456         this(Range)(Range val)
457             if (__traits(compiles, ElementType!Range) && is(ElementType!Range : T))
458         {
459             foreach (ref v; val)
460             {
461                 put(v);
462             }
463         }
464 
465         this(Args...)(Args val)
466         {
467             foreach (ref v; val)
468             {
469                 put(v);
470             }
471         }
472     }
473 
474     mixin CyclicRangePrimitives!(T, q{
475             static if (len == 0)
476                 auto copy = typeof(cast() this)(array.length);
477             else
478                 typeof(cast() this) copy;
479 	});
480 
481     static if (len != 0)
482         CyclicRange!T byRef() @property @nogc @safe
483         {
484             return CyclicRange!T(array[], start, size);
485         }
486 
487     size_t length() const @property @nogc @safe
488     {
489         return size;
490     }
491 
492     size_t length(size_t val) @property
493     {
494         if (size > array.length)
495             assert(false);
496         if (val == 0)
497         {
498             clear();
499             return size;
500         }
501         if (val > size)
502         {
503             foreach (const i; size .. val)
504                 array[(start + i) % array.length] = T.init;
505         }
506         else if (val < size)
507         {
508             static if (hasElaborateDestructor!T)
509                 foreach (const i; val .. size)
510                     destroy(array[(start + i) % array.length]);
511             else static if (mustAddGCRange!T)
512                 foreach (const i; val .. size)
513                     array[(start + i) % array.length] = T.init; // avoid GC mark-phase dereference
514         }
515         return size = val;
516     }
517 
518     void clear()
519     {
520         static if (hasElaborateDestructor!T)
521             foreach (const i; 0 .. size)
522                 destroy(array[(start + i) % array.length]);
523         start = 0; // optimize clears
524         size = 0;
525     }
526 
527     auto opBinary(string op : "~")(T rhs) const
528     {
529         auto copy = this.dup;
530         copy.put(rhs);
531         return copy;
532     }
533 
534     auto opBinary(string op : "~", size_t n)(T[n] rhs) const
535     {
536         auto copy = this.dup;
537         copy ~= rhs;
538         return copy;
539     }
540 
541     auto opBinary(string op : "~", Range)(Range rhs) const
542         if (isInputRange!Range && is(ElementType!Range : T))
543         {
544             auto copy = this.dup;
545             copy ~= rhs;
546             return copy;
547         }
548 
549     void opOpAssign(string op : "~")(T rhs)
550     {
551         put(rhs);
552     }
553 
554     void opOpAssign(string op : "~", size_t n)(T[n] rhs)
555     {
556         foreach (c; rhs)
557         {
558             put(c);
559         }
560     }
561 
562     void opOpAssign(string op : "~", size_t n)(CyclicArray!(T, n) rhs)
563     {
564         for (int i = 0; i < rhs.size; i++)
565             put(rhs.array[(rhs.start + i) % rhs.array.length]);
566     }
567 
568     void opOpAssign(string op : "~", Range)(Range rhs)
569         if (__traits(compiles, ElementType!Range) && is(ElementType!Range : T))
570     {
571         foreach (c; rhs)
572             put(c);
573     }
574 
575     static if (len == 0)
576     {
577         CyclicArray!(T, len) dup() const
578         {
579             auto ret = CyclicArray!(T, len)(array);
580             ret.start = start;
581             ret.size = size;
582             return ret;
583         }
584     }
585     else
586     {
587         CyclicArray!(T, len) dup() const
588         {
589             CyclicArray!(T, len) ret;
590             ret.array = cast(typeof(ret.array)) array;
591             ret.start = start;
592             ret.size = size;
593             return ret;
594         }
595     }
596 
597     static if (len != 0)
598     {
599         int opApply(int delegate(ref T) @nogc dg) @nogc
600         {
601             int result = 0;
602 
603             for (size_t i = 0; i < size; i++)
604             {
605                 result = dg(array[(i + start) % array.length]);
606                 if (result)
607                     break;
608             }
609 
610             return result;
611         }
612 
613         int opApply(int delegate(size_t, ref T) @nogc dg) @nogc
614         {
615             int result = 0;
616 
617             for (size_t i = 0; i < size; i++)
618             {
619                 result = dg(i, array[(i + start) % array.length]);
620                 if (result)
621                     break;
622             }
623 
624             return result;
625         }
626     }
627 
628     bool opEquals(in CyclicArray!(T, len) b)
629     {
630         if (size != b.size)
631             return false;
632         for (int i = 0; i < size; i++)
633             if (array[(i + start) % array.length] !=
634                 b.array[(i + b.start) % b.array.length])
635                 return false;
636         return true;
637     }
638 
639     bool opEquals(size_t n)(T[n] b)
640     {
641         if (size != n)
642             return false;
643         for (int i = 0; i < size; i++)
644             if (array[(i + start) % array.length] != b[i])
645                 return false;
646         return true;
647     }
648 
649     bool opEquals(Range)(Range b) if (hasLength!Range && is(ElementType!Range : T))
650     {
651         if (size != b.length)
652             return false;
653         auto r = b.save;
654         for (int i = 0; i < size; i++)
655         {
656             if (array[(i + start) % array.length] != r.front)
657                 return false;
658             r.popFront;
659         }
660         return true;
661     }
662 }
663 
664 ///
665 @nogc @safe unittest
666 {
667     CyclicArray!int array;
668     assert(array.length == 0);
669     array ~= 5;
670     assert(!array.empty);
671     assert(array.front == 5);
672     assert(array[0] == 5);
673     array ~= [4, 3];
674 
675     assert(array == [5, 4, 3]);
676 
677     // same efficiency as insertBack/put/concat
678     array.insertFront(5);
679 }
680 
681 @nogc @system unittest
682 {
683     // heap array using std.container.Array with 16 elements
684     auto heapArray = CyclicArray!(int, 0)(16);
685 
686     // custom memory using Array
687     auto myArray = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
688     auto customArray = CyclicArray!(int, 0)(myArray[0 .. 6]);
689 }
690 
691 class CyclicRangeError : Error
692 {
693     @nogc @safe pure nothrow this(string msg, string file = __FILE__,
694                                   size_t line = __LINE__, Throwable next = null)
695     {
696         super(msg, file, line, next);
697     }
698 }
699 
700 // TLS storage shared for all errors, chaining might create circular reference
701 private void[128] _store;
702 
703 // only Errors for now as those are rarely chained
704 private T staticError(T, Args...)(auto ref Args args) @trusted if (is(T : Error))
705 {
706     // pure hack, what we actually need is @noreturn and allow to call that in pure functions
707     static T get()
708     {
709         static assert(__traits(classInstanceSize, T) <= _store.length,
710                       T.stringof ~ " is too large for staticError()");
711 
712         _store[0 .. __traits(classInstanceSize, T)] = typeid(T).initializer[];
713         return cast(T) _store.ptr;
714     }
715 
716     auto res = (cast(T function() @trusted pure nothrow @nogc)&get)();
717     res.__ctor(args);
718     return res;
719 }
720 
721 // lots of unittests taken from std.container.array
722 
723 // Give the Range object some testing.
724 @system unittest
725 {
726     import std.algorithm.comparison : equal;
727     import std.range : retro;
728 
729     auto a = CyclicArray!int(0, 1, 2, 3, 4, 5, 6)[];
730     assert(equal(a, [0, 1, 2, 3, 4, 5, 6]));
731     assert(equal(a[], [0, 1, 2, 3, 4, 5, 6]));
732     assert(equal(a[0 .. $], [0, 1, 2, 3, 4, 5, 6]));
733     auto b = CyclicArray!int(6, 5, 4, 3, 2, 1, 0)[];
734     alias A = typeof(a);
735     alias ARef = typeof(a.byRef);
736 
737     static assert(isRandomAccessRange!A);
738     static assert(hasSlicing!A);
739     static assert(hasAssignableElements!A);
740     static assert(hasMobileElements!A);
741 
742     static assert(isRandomAccessRange!ARef);
743     static assert(hasSlicing!ARef);
744     static assert(hasAssignableElements!ARef);
745     static assert(hasMobileElements!ARef);
746 
747     assert(equal(retro(b), a));
748     assert(a.length == 7);
749     assert(equal(a[1 .. 4], [1, 2, 3]));
750 }
751 
752 @system unittest
753 {
754     alias S = structBug5920;
755     uint dMask;
756 
757     auto arr = CyclicArray!S(cast(S[])[]);
758     foreach (const i; 0 .. 8)
759     {
760         arr.insertBack(S(i, &dMask));
761     }
762     // don't check dMask now as S may be copied multiple times (it's ok?)
763     {
764         assert(arr.length == 8);
765         dMask = 0;
766         arr.length = 6;
767         assert(arr.length == 6); // make sure shrinking calls the d'tor
768         assert(dMask == 0b1100_0000);
769         arr.removeBack();
770         assert(arr.length == 5); // make sure removeBack() calls the d'tor
771         assert(dMask == 0b1110_0000);
772         arr.removeBack(3);
773         assert(arr.length == 2); // ditto
774         assert(dMask == 0b1111_1100);
775         arr.clear();
776         assert(arr.length == 0); // make sure clear() calls the d'tor
777         assert(dMask == 0b1111_1111);
778     }
779     assert(dMask == 0b1111_1111); // make sure the d'tor is called once only.
780 }
781 
782 @system unittest
783 {
784     auto a = CyclicArray!(int[])([[1, 2], [3, 4]]);
785     assert(a.length == 2);
786     assert(a[0] == [1, 2]);
787     assert(a[1] == [3, 4]);
788 }
789 
790 @system unittest
791 {
792     import std.algorithm.comparison : equal;
793 
794     //Test "array-wide" operations
795     auto a = CyclicArray!int([0, 1, 2]); //CyclicArray
796     a[] += 5;
797     assert(a[].equal([5, 6, 7]));
798     ++a[];
799     assert(a[].equal([6, 7, 8]));
800     import std.stdio;
801 
802     a[1 .. 3] *= 5;
803     assert(a[].equal([6, 35, 40]));
804     a[0 .. 2] = 0;
805     assert(a[].equal([0, 0, 40]));
806 
807     //Test empty array
808     auto a2 = CyclicArray!int.init;
809     ++a2[];
810     ++a2[0 .. 0];
811     a2[] = 0;
812     a2[0 .. 0] = 0;
813     a2[] += 0;
814     a2[0 .. 0] += 0;
815 
816     //Test "range-wide" operations
817     auto r = CyclicArray!int([0, 1, 2])[]; //CyclicArray.Range
818     r[] += 5;
819     assert(r.equal([5, 6, 7]));
820     ++r[];
821     assert(r.equal([6, 7, 8]));
822     r[1 .. 3] *= 5;
823     assert(r.equal([6, 35, 40]));
824     r[0 .. 2] = 0;
825     assert(r.equal([0, 0, 40]));
826 
827     //Test empty Range
828     auto r2 = CyclicArray!int.init[];
829     ++r2[];
830     ++r2[0 .. 0];
831     r2[] = 0;
832     r2[0 .. 0] = 0;
833     r2[] += 0;
834     r2[0 .. 0] += 0;
835 }
836 
837 // Test issue
838 @system unittest
839 {
840     static struct S
841     {
842         int i = 1337;
843         void* p;
844         this(this)
845         {
846             assert(i == 1337);
847         }
848 
849         ~this() @nogc
850         {
851             assert(i == 1337);
852         }
853     }
854 
855     CyclicArray!S arr;
856     S s;
857     arr ~= s;
858     arr ~= s;
859 }
860 
861 @system unittest
862 {
863     import std.algorithm.iteration : filter;
864 
865     auto a = CyclicArray!int([1, 2, 2].filter!"true"());
866 }
867 
868 @safe unittest
869 {
870     auto arr = new CyclicArray!int;
871 }
872 
873 @system unittest  //6998
874 {
875     static int i = 0;
876     class C
877     {
878         int dummy = 1;
879         this()
880         {
881             ++i;
882         }
883 
884         ~this() @nogc
885         {
886             --i;
887         }
888     }
889 
890     assert(i == 0);
891     auto c = new C();
892     assert(i == 1);
893 
894     //scope
895     {
896         auto arr = CyclicArray!C(c);
897         assert(i == 1);
898     }
899     //CyclicArray should not have destroyed the class instance
900     assert(i == 1);
901 
902     //Just to make sure the GC doesn't collect before the above test.
903     assert(c.dummy == 1);
904 }
905 
906 @system unittest  //6998-2
907 {
908     static class C
909     {
910         int i;
911     }
912 
913     auto c = new C;
914     c.i = 42;
915     CyclicArray!C a;
916     a ~= c;
917     a.clear;
918     assert(c.i == 42); //fails
919 }
920 
921 @nogc:
922 unittest
923 {
924     alias IntArray = CyclicArray!int;
925     alias IntRange = CyclicRange!int;
926 
927     static assert(isInputRange!IntArray);
928     static assert(isOutputRange!(IntArray, int));
929     static assert(isForwardRange!IntArray);
930     static assert(isBidirectionalRange!IntArray);
931     static assert(isRandomAccessRange!IntArray);
932     static assert(hasMobileElements!IntArray);
933     static assert(is(ElementType!IntArray == int));
934     static assert(hasSwappableElements!IntArray);
935     static assert(hasAssignableElements!IntArray);
936     static assert(hasLvalueElements!IntArray);
937     static assert(hasLength!IntArray);
938     static assert(hasSlicing!IntArray);
939 
940     static assert(isInputRange!IntRange);
941     static assert(isOutputRange!(IntRange, int));
942     static assert(isForwardRange!IntRange);
943     static assert(isBidirectionalRange!IntRange);
944     static assert(isRandomAccessRange!IntRange);
945     static assert(hasMobileElements!IntRange);
946     static assert(is(ElementType!IntRange == int));
947     static assert(hasSwappableElements!IntRange);
948     static assert(hasAssignableElements!IntRange);
949     static assert(hasLvalueElements!IntRange);
950     static assert(hasLength!IntRange);
951     static assert(hasSlicing!IntRange);
952 
953     IntArray array;
954     assert(array.length == 0);
955     assert(array.empty);
956     array ~= 5;
957     assert(!array.empty);
958     assert(array.length == 1);
959     assert(array.front == 5);
960     assert(array[0] == 5);
961     assert(array[0 .. 1].front == 5);
962     assert(array[0 .. 0].empty);
963     array ~= cast(int[2])[4, 3];
964     assert(array.length == 3);
965     assert(array[1] == 4);
966     assert(array[2] == 3);
967 
968     for (int i = 0; i < 50000; i++)
969     {
970         array ~= i;
971         array.popFront();
972     }
973 
974     assert(array.length == 3);
975 
976     array ~= array;
977     assert(array.length == 6);
978     assert((array ~ array).length == 12);
979     assert(array.length == 6);
980 
981     array[5] = 1;
982     assert(array[5] == 1);
983     auto copy = array;
984     copy[5] = 2;
985     assert(array[5] == 1);
986     array[][5] = 1;
987     assert(array[5] == 1);
988 
989     foreach (ref v; array.byRef)
990     {
991         v = 42;
992     }
993 
994     assert(array[5] == 42);
995 }
996 
997 unittest
998 {
999     alias IntArray = CyclicArray!(int, 0);
1000 
1001     static assert(isInputRange!IntArray);
1002     static assert(isOutputRange!(IntArray, int));
1003     static assert(isForwardRange!IntArray);
1004     static assert(isBidirectionalRange!IntArray);
1005     static assert(isRandomAccessRange!IntArray);
1006     static assert(hasMobileElements!IntArray);
1007     static assert(is(ElementType!IntArray == int));
1008     static assert(hasSwappableElements!IntArray);
1009     static assert(hasAssignableElements!IntArray);
1010     static assert(hasLvalueElements!IntArray);
1011     static assert(hasLength!IntArray);
1012     static assert(hasSlicing!IntArray);
1013 
1014     auto array = IntArray(1024);
1015     assert(array.length == 0);
1016     assert(array.empty);
1017     array ~= 5;
1018     assert(!array.empty);
1019     assert(array.length == 1);
1020     assert(array.front == 5);
1021     assert(array[0] == 5);
1022     assert(array[0 .. 1].front == 5);
1023     assert(array[0 .. 0].empty);
1024     array ~= cast(int[2])[4, 3];
1025     assert(array.length == 3);
1026     assert(array[1] == 4);
1027     assert(array[2] == 3);
1028 
1029     for (int i = 0; i < 50000; i++)
1030     {
1031         array ~= i;
1032         array.popFront();
1033     }
1034 
1035     assert(array.length == 3);
1036 
1037     array ~= array;
1038     assert(array.length == 6);
1039     assert((array ~ array).length == 12);
1040     assert(array.length == 6);
1041 
1042     array[5] = 1;
1043     assert(array[5] == 1);
1044     auto copy = array[];
1045     copy[5] = 2;
1046     assert(array[5] == 1);
1047     array[][5] = 1;
1048     assert(array[5] == 1);
1049 }
1050 
1051 @system unittest
1052 {
1053     CyclicArray!int a;
1054     assert(a.empty);
1055 }
1056 
1057 @system unittest
1058 {
1059     CyclicArray!int a;
1060     a.length = 10;
1061     assert(a.length == 10);
1062     assert(a.capacity >= a.length);
1063 }
1064 
1065 @system unittest
1066 {
1067     struct Dumb
1068     {
1069         int x = 5;
1070     }
1071 
1072     CyclicArray!Dumb a;
1073     a.length = 10;
1074     assert(a.length == 10);
1075     assert(a.capacity >= a.length);
1076     immutable cap = a.capacity;
1077     foreach (ref e; a)
1078     {
1079         e.x = 10;
1080     }
1081     a.length = 5;
1082     assert(a.length == 5);
1083     foreach (ref e; a)
1084     {
1085         assert(e.x == 10);
1086     }
1087 
1088     a.length = 8;
1089     assert(a.length == 8);
1090     assert(Dumb.init.x == 5);
1091     foreach (const i; 0 .. 5)
1092     {
1093         assert(a[i].x == 10);
1094     }
1095     foreach (const i; 5 .. a.length)
1096     {
1097         assert(a[i].x == Dumb.init.x);
1098     }
1099 
1100     a[] = Dumb(1);
1101     a.length = 20;
1102     foreach (const i; 0 .. 8)
1103     {
1104         assert(a[i].x == 1);
1105     }
1106     foreach (const i; 8 .. a.length)
1107     {
1108         assert(a[i].x == Dumb.init.x);
1109     }
1110 
1111     // check if overlapping elements properly initialized
1112     a.length = 1;
1113     a.length = 20;
1114     assert(a[0].x == 1);
1115     foreach (e; a[1 .. $])
1116     {
1117         assert(e.x == Dumb.init.x);
1118     }
1119 }
1120 
1121 @system unittest
1122 {
1123     CyclicArray!int a = CyclicArray!int(1, 2, 3);
1124     //a._data._refCountedDebug = true;
1125     auto b = a.dup;
1126     assert(b == CyclicArray!int(1, 2, 3));
1127     b.front = 42;
1128     assert(b == CyclicArray!int(42, 2, 3));
1129     assert(a == CyclicArray!int(1, 2, 3));
1130 }
1131 
1132 @system unittest
1133 {
1134     auto a = CyclicArray!int(1, 2, 3);
1135     assert(a.length == 3);
1136 }
1137 
1138 @system unittest
1139 {
1140     const CyclicArray!int a = [1, 2];
1141 
1142     assert(a[0] == 1);
1143     assert(a.front == 1);
1144     assert(a.back == 2);
1145 
1146     static assert(!__traits(compiles, { a[0] = 1; }));
1147     static assert(!__traits(compiles, { a.front = 1; }));
1148     static assert(!__traits(compiles, { a.back = 1; }));
1149 
1150     auto r = a[];
1151     size_t i;
1152     foreach (e; r)
1153     {
1154         assert(e == i + 1);
1155         i++;
1156     }
1157 }
1158 
1159 @system unittest
1160 {
1161     auto a = CyclicArray!int(1, 2, 3);
1162     a[1] *= 42;
1163     assert(a[1] == 84);
1164 }
1165 
1166 @system unittest
1167 {
1168     auto a = CyclicArray!int(1, 2, 3);
1169     auto b = CyclicArray!int(11, 12, 13);
1170     auto c = a ~ b;
1171     assert(c == CyclicArray!int(1, 2, 3, 11, 12, 13));
1172     assert(a ~ b[] == CyclicArray!int(1, 2, 3, 11, 12, 13));
1173     assert(a ~ [4, 5] == CyclicArray!int(1, 2, 3, 4, 5));
1174 }
1175 
1176 @system unittest
1177 {
1178     auto a = CyclicArray!int(1, 2, 3);
1179     auto b = CyclicArray!int(11, 12, 13);
1180     a ~= b;
1181     assert(a == CyclicArray!int(1, 2, 3, 11, 12, 13));
1182 }
1183 
1184 @system unittest
1185 {
1186     auto a = CyclicArray!int(1, 2, 3, 4);
1187     assert(a.removeAny() == 4);
1188     assert(a == CyclicArray!int(1, 2, 3));
1189 }
1190 
1191 private struct structBug5920
1192 {
1193     int order;
1194     uint* pDestructionMask;
1195     ~this() @nogc
1196     {
1197         if (pDestructionMask)
1198             *pDestructionMask += 1 << order;
1199     }
1200 }
1201 
1202 @system unittest
1203 {
1204     auto a = CyclicArray!int([1, 1]);
1205     a[1] = 0; //Check CyclicArray.opIndexAssign
1206     assert(a[1] == 0);
1207     a[1] += 1; //Check CyclicArray.opIndexOpAssign
1208     assert(a[1] == 1);
1209 
1210     //Check CyclicArray.opIndexUnary
1211     ++a[0];
1212     //a[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
1213     assert(a[0] == 2);
1214     assert(+a[0] == +2);
1215     assert(-a[0] == -2);
1216     assert(~a[0] == ~2);
1217 
1218     auto r = a[];
1219     r[1] = 0; //Check CyclicArray.Range.opIndexAssign
1220     assert(r[1] == 0);
1221     r[1] += 1; //Check CyclicArray.Range.opIndexOpAssign
1222     assert(r[1] == 1);
1223 
1224     //Check CyclicArray.Range.opIndexUnary
1225     ++r[0];
1226     //r[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
1227     assert(r[0] == 3);
1228     assert(+r[0] == +3);
1229     assert(-r[0] == -3);
1230     assert(~r[0] == ~3);
1231 }
1232 
1233 @safe unittest
1234 {
1235     static struct S
1236     {
1237         bool b;
1238         alias b this;
1239     }
1240 
1241     alias A = CyclicArray!S;
1242     alias B = CyclicArray!(shared bool);
1243 }
1244 
1245 @system unittest
1246 {
1247     CyclicArray!int ai;
1248     ai ~= 1;
1249     assert(ai.front == 1);
1250 
1251     static const arr = [1, 2, 3];
1252     ai.insertBack(arr);
1253 }