The OpenD Programming Language

1 /**
2  * This module provides an `Array` type with deterministic memory usage not
3  * reliant on the GC, as an alternative to the built-in arrays.
4  *
5  * This module is a submodule of $(MREF std, container).
6  *
7  * Source: $(PHOBOSSRC std/container/array.d)
8  *
9  * Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
10  *
11  * License: Distributed under the Boost Software License, Version 1.0.
12  * (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
13  * boost.org/LICENSE_1_0.txt)).
14  *
15  * Authors: $(HTTP erdani.com, Andrei Alexandrescu)
16  *
17  * $(SCRIPT inhibitQuickIndex = 1;)
18  */
19 module std.container.array;
20 
21 import core.exception : RangeError;
22 import std.range.primitives;
23 import std.traits;
24 
25 public import std.container.util;
26 
27 pure @system unittest
28 {
29     // We test multiple array lengths in order to ensure that the "a1.capacity == a0.length" test is meaningful
30     // for the version in which the constructor uses insertBack
31     // (because for some lengths, the test passes even without reserve).
32     for (size_t n = 0; n < 100; ++n)
33     {
34         float[] a0;
35         {
36             import std.range : iota;
37             import std.array : array;
38             import std.algorithm.iteration : map;
39             a0 = iota (0, n).map!(i => i * 1.1f).array;
40         }
41 
42         auto a1 = Array!float(a0);
43 
44         // We check that a1 has the same length and contents as a0:
45         {
46             assert(a1.length == a0.length);
47 
48             // I wish that I could write "assert(a1[] == a0[]);",
49             // but the compiler complains: "Error: incompatible types for `(a1.opSlice()) == (a0[])`: `RangeT!(Array!float)` and `float[]`".
50             import std.algorithm.comparison : equal;
51             assert(equal(a1[], a0[]));
52         }
53 
54         // We check that a1's constructor has called reserve (to maintain good performance):
55         assert(a1.capacity == a0.length);
56     }
57 }
58 
59 pure @system unittest
60 {
61     // To avoid bad performance, we check that an Array constructed from an empty range
62     // does not initialize its RefCountedStore object, even after a call to "reserve(0)".
63 
64     {
65         Array!float a1;
66         assert(! a1._data.refCountedStore.isInitialized);
67         a1.reserve(0);
68         assert(! a1._data.refCountedStore.isInitialized);
69     }
70 
71     {
72         float[] a0 = [];
73         Array!float a1 = a0;
74         // [2021-09-26] TODO: Investigate RefCounted.
75         //assert(! a1._data.refCountedStore.isInitialized);
76         a1.reserve(0);
77         // [2021-09-26] TODO: Investigate RefCounted.
78         //assert(! a1._data.refCountedStore.isInitialized);
79     }
80 }
81 
82 ///
83 pure @system unittest
84 {
85     auto arr = Array!int(0, 2, 3);
86     assert(arr[0] == 0);
87     assert(arr.front == 0);
88     assert(arr.back == 3);
89 
90     // reserve space
91     arr.reserve(1000);
92     assert(arr.length == 3);
93     assert(arr.capacity >= 1000);
94 
95     // insertion
96     arr.insertBefore(arr[1..$], 1);
97     assert(arr.front == 0);
98     assert(arr.length == 4);
99 
100     arr.insertBack(4);
101     assert(arr.back == 4);
102     assert(arr.length == 5);
103 
104     // set elements
105     arr[1] *= 42;
106     assert(arr[1] == 42);
107 }
108 
109 ///
110 pure @system unittest
111 {
112     import std.algorithm.comparison : equal;
113     auto arr = Array!int(1, 2, 3);
114 
115     // concat
116     auto b = Array!int(11, 12, 13);
117     arr ~= b;
118     assert(arr.length == 6);
119 
120     // slicing
121     assert(arr[1 .. 3].equal([2, 3]));
122 
123     // remove
124     arr.linearRemove(arr[1 .. 3]);
125     assert(arr[0 .. 2].equal([1, 11]));
126 }
127 
128 /// `Array!bool` packs together values efficiently by allocating one bit per element
129 pure @system unittest
130 {
131     auto arr = Array!bool([true, true, false, true, false]);
132     assert(arr.length == 5);
133 }
134 
135 private struct RangeT(A)
136 {
137     /* Workaround for https://issues.dlang.org/show_bug.cgi?id=13629
138        See also: http://forum.dlang.org/post/vbmwhzvawhnkoxrhbnyb@forum.dlang.org
139     */
140     private A[1] _outer_;
141     private @property ref inout(A) _outer() inout { return _outer_[0]; }
142 
143     private size_t _a, _b;
144 
145     /* E is different from T when A is more restrictively qualified than T:
146        immutable(Array!int) => T == int, E = immutable(int) */
147     alias E = typeof(_outer_[0]._data._payload[0]);
148 
149     private this(ref A data, size_t a, size_t b)
150     {
151         _outer_ = data;
152         _a = a;
153         _b = b;
154     }
155 
156     @property RangeT save()
157     {
158         return this;
159     }
160 
161     @property bool empty() @safe pure nothrow const
162     {
163         return _a >= _b;
164     }
165 
166     @property size_t length() @safe pure nothrow const
167     {
168         return _b - _a;
169     }
170     alias opDollar = length;
171 
172     @property ref inout(E) front() inout
173     {
174         assert(!empty, "Attempting to access the front of an empty Array");
175         return _outer[_a];
176     }
177     @property ref inout(E) back() inout
178     {
179         assert(!empty, "Attempting to access the back of an empty Array");
180         return _outer[_b - 1];
181     }
182 
183     void popFront() @safe @nogc pure nothrow
184     {
185         assert(!empty, "Attempting to popFront an empty Array");
186         ++_a;
187     }
188 
189     void popBack() @safe @nogc pure nothrow
190     {
191         assert(!empty, "Attempting to popBack an empty Array");
192         --_b;
193     }
194 
195     static if (isMutable!A)
196     {
197         import std.algorithm.mutation : move;
198 
199         E moveFront()
200         {
201             assert(!empty, "Attempting to moveFront an empty Array");
202             assert(_a < _outer.length,
203                 "Attempting to moveFront using an out of bounds low index on an Array");
204             return move(_outer._data._payload[_a]);
205         }
206 
207         E moveBack()
208         {
209             assert(!empty, "Attempting to moveBack an empty Array");
210             assert(_b - 1 < _outer.length,
211                 "Attempting to moveBack using an out of bounds high index on an Array");
212             return move(_outer._data._payload[_b - 1]);
213         }
214 
215         E moveAt(size_t i)
216         {
217             assert(_a + i < _b,
218                 "Attempting to moveAt using an out of bounds index on an Array");
219             assert(_a + i < _outer.length,
220                 "Cannot move past the end of the array");
221             return move(_outer._data._payload[_a + i]);
222         }
223     }
224 
225     ref inout(E) opIndex(size_t i) inout
226     {
227         assert(_a + i < _b,
228             "Attempting to fetch using an out of bounds index on an Array");
229         return _outer[_a + i];
230     }
231 
232     RangeT opSlice()
233     {
234         return typeof(return)(_outer, _a, _b);
235     }
236 
237     RangeT opSlice(size_t i, size_t j)
238     {
239         assert(i <= j && _a + j <= _b,
240             "Attempting to slice using an out of bounds indices on an Array");
241         return typeof(return)(_outer, _a + i, _a + j);
242     }
243 
244     RangeT!(const(A)) opSlice() const
245     {
246         return typeof(return)(_outer, _a, _b);
247     }
248 
249     RangeT!(const(A)) opSlice(size_t i, size_t j) const
250     {
251         assert(i <= j && _a + j <= _b,
252             "Attempting to slice using an out of bounds indices on an Array");
253         return typeof(return)(_outer, _a + i, _a + j);
254     }
255 
256     static if (isMutable!A)
257     {
258         void opSliceAssign(E value)
259         {
260             assert(_b <= _outer.length,
261                 "Attempting to assign using an out of bounds indices on an Array");
262             _outer[_a .. _b] = value;
263         }
264 
265         void opSliceAssign(E value, size_t i, size_t j)
266         {
267             assert(_a + j <= _b,
268                 "Attempting to slice assign using an out of bounds indices on an Array");
269             _outer[_a + i .. _a + j] = value;
270         }
271 
272         void opSliceUnary(string op)()
273         if (op == "++" || op == "--")
274         {
275             assert(_b <= _outer.length,
276                 "Attempting to slice using an out of bounds indices on an Array");
277             mixin(op~"_outer[_a .. _b];");
278         }
279 
280         void opSliceUnary(string op)(size_t i, size_t j)
281         if (op == "++" || op == "--")
282         {
283             assert(_a + j <= _b,
284                 "Attempting to slice using an out of bounds indices on an Array");
285             mixin(op~"_outer[_a + i .. _a + j];");
286         }
287 
288         void opSliceOpAssign(string op)(E value)
289         {
290             assert(_b <= _outer.length,
291                 "Attempting to slice using an out of bounds indices on an Array");
292             mixin("_outer[_a .. _b] "~op~"= value;");
293         }
294 
295         void opSliceOpAssign(string op)(E value, size_t i, size_t j)
296         {
297             assert(_a + j <= _b,
298                 "Attempting to slice using an out of bounds indices on an Array");
299             mixin("_outer[_a + i .. _a + j] "~op~"= value;");
300         }
301     }
302 }
303 
304 @system unittest
305 {
306     enum : bool { display = false }
307     static if (display)
308     {
309         import std.stdio;
310         enum { nDigitsForPointer = 2 * size_t.sizeof, nDigitsForNObjects = 4 }
311     }
312 
313     static struct S
314     {
315         static size_t s_nConstructed;
316         static size_t s_nDestroyed;
317         static void throwIfTooMany()
318         {
319             if (s_nConstructed >= 7) throw new Exception ("Ka-boom !");
320         }
321 
322         uint _i;
323 
324         ~this()
325         {
326             static if (display) writefln("@%*Xh: Destroying.", nDigitsForPointer, &this);
327             ++s_nDestroyed;
328         }
329 
330         this(uint i)
331         {
332             static if (display) writefln("@%*Xh: Constructing.", nDigitsForPointer, &this);
333             _i = i;
334             ++s_nConstructed;
335             throwIfTooMany();
336         }
337 
338         this(this)
339         {
340             static if (display) writefln("@%*Xh: Copying.", nDigitsForPointer, &this);
341             ++s_nConstructed;
342             throwIfTooMany();
343         }
344     }
345 
346     try
347     {
348         auto a = Array!S (S(0), S(1), S(2), S(3));
349         static if (display) writefln("@%*Xh: This is where the array elements are.", nDigitsForPointer, &a [0]);
350     }
351     catch (Exception e)
352     {
353         static if (display) writefln("Exception caught !");
354     }
355 
356     static if (display)
357     {
358         writefln("s_nConstructed %*Xh.", nDigitsForNObjects, S.s_nConstructed);
359         writefln("s_nDestroyed   %*Xh.", nDigitsForNObjects, S.s_nDestroyed);
360         writefln("s_nConstructed should be equal to s_nDestroyed.");
361         writefln("");
362     }
363 
364     assert(S.s_nDestroyed == S.s_nConstructed);
365 }
366 
367 
368 /**
369  * _Array type with deterministic control of memory. The memory allocated
370  * for the array is reclaimed as soon as possible; there is no reliance
371  * on the garbage collector. `Array` uses `malloc`, `realloc` and `free`
372  * for managing its own memory.
373  *
374  * This means that pointers to elements of an `Array` will become
375  * dangling as soon as the element is removed from the `Array`. On the other hand
376  * the memory allocated by an `Array` will be scanned by the GC and
377  * GC managed objects referenced from an `Array` will be kept alive.
378  *
379  * Note:
380  *
381  * When using `Array` with range-based functions like those in `std.algorithm`,
382  * `Array` must be sliced to get a range (for example, use `array[].map!`
383  * instead of `array.map!`). The container itself is not a range.
384  */
385 struct Array(T)
386 if (!is(immutable T == immutable bool))
387 {
388     import core.memory : free = pureFree;
389     import std.internal.memory : enforceMalloc, enforceRealloc;
390     import core.stdc.string : memcpy, memmove, memset;
391 
392     import core.memory : GC;
393 
394     import std.exception : enforce;
395     import std.typecons : RefCounted, RefCountedAutoInitialize;
396 
397     // This structure is not copyable.
398     private struct Payload
399     {
400         size_t _capacity;
401         T[] _payload;
402 
403         this(T[] p) { _capacity = p.length; _payload = p; }
404 
405         // Destructor releases array memory
406         ~this()
407         {
408             // Warning: destroy would destroy also class instances.
409             // The hasElaborateDestructor protects us here.
410             static if (hasElaborateDestructor!T)
411                 foreach (ref e; _payload)
412                     .destroy(e);
413 
414             static if (hasIndirections!T)
415                 GC.removeRange(cast(void*) _payload.ptr);
416 
417             free(cast(void*) _payload.ptr);
418         }
419 
420         this(this) @disable;
421 
422         void opAssign(Payload rhs) @disable;
423 
424         @property size_t length() const
425         {
426             return _payload.length;
427         }
428 
429         @property void length(size_t newLength)
430         {
431             if (length >= newLength)
432             {
433                 // shorten
434                 static if (hasElaborateDestructor!T)
435                     foreach (ref e; _payload.ptr[newLength .. _payload.length])
436                         .destroy(e);
437 
438                 _payload = _payload.ptr[0 .. newLength];
439                 return;
440             }
441 
442             static if (__traits(compiles, { static T _; }))
443             {
444                 import std.algorithm.mutation : initializeAll;
445 
446                 immutable startEmplace = length;
447                 reserve(newLength);
448                 initializeAll(_payload.ptr[startEmplace .. newLength]);
449                 _payload = _payload.ptr[0 .. newLength];
450             }
451             else
452             {
453                 assert(0, "Cannot add elements to array because `" ~
454                     fullyQualifiedName!T ~ ".this()` is annotated with " ~
455                     "`@disable`.");
456             }
457         }
458 
459         @property size_t capacity() const
460         {
461             return _capacity;
462         }
463 
464         void reserve(size_t elements)
465         {
466             if (elements <= capacity) return;
467             static if (T.sizeof == 1)
468             {
469                 const sz = elements;
470             }
471             else
472             {
473                 import core.checkedint : mulu;
474                 bool overflow;
475                 const sz = mulu(elements, T.sizeof, overflow);
476                 if (overflow)
477                     assert(false, "Overflow");
478             }
479             static if (hasIndirections!T)
480             {
481                 /* Because of the transactional nature of this
482                  * relative to the garbage collector, ensure no
483                  * threading bugs by using malloc/copy/free rather
484                  * than realloc.
485                  */
486                 immutable oldLength = length;
487 
488                 auto newPayloadPtr = cast(T*) enforceMalloc(sz);
489                 auto newPayload = newPayloadPtr[0 .. oldLength];
490 
491                 // copy old data over to new array
492                 memcpy(cast(void*) newPayload.ptr, cast(void*) _payload.ptr, T.sizeof * oldLength);
493                 // Zero out unused capacity to prevent gc from seeing false pointers
494                 memset( cast(void*) (newPayload.ptr + oldLength),
495                         0,
496                         (elements - oldLength) * T.sizeof);
497                 GC.addRange(cast(void*) newPayload.ptr, sz);
498                 GC.removeRange(cast(void*) _payload.ptr);
499                 free(cast(void*) _payload.ptr);
500                 _payload = newPayload;
501             }
502             else
503             {
504                 // These can't have pointers, so no need to zero unused region
505                 auto newPayloadPtr = cast(T*) enforceRealloc(_payload.ptr, sz);
506                 auto newPayload = newPayloadPtr[0 .. length];
507                 _payload = newPayload;
508             }
509             _capacity = elements;
510         }
511 
512         // Insert one item
513         size_t insertBack(Elem)(Elem elem)
514         if (isImplicitlyConvertible!(Elem, T))
515         {
516             import core.lifetime : emplace;
517             assert(_capacity >= length);
518             if (_capacity == length)
519             {
520                 import core.checkedint : addu;
521 
522                 bool overflow;
523                 immutable size_t newCapacity = addu(capacity, capacity / 2 + 1, overflow);
524                 if (overflow)
525                     assert(false, "Overflow");
526 
527                 reserve(newCapacity);
528             }
529             assert(capacity > length && _payload.ptr,
530                 "Failed to reserve memory");
531             emplace(_payload.ptr + _payload.length, elem);
532             _payload = _payload.ptr[0 .. _payload.length + 1];
533             return 1;
534         }
535 
536         // Insert a range of items
537         size_t insertBack(Range)(Range r)
538         if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T))
539         {
540             immutable size_t oldLength = length;
541 
542             static if (hasLength!Range)
543             {
544                 immutable size_t rLength = r.length;
545                 reserve(oldLength + rLength);
546             }
547 
548             size_t result;
549             foreach (item; r)
550             {
551                 insertBack(item);
552                 ++result;
553             }
554 
555             static if (hasLength!Range)
556                 assert(result == rLength, "insertBack: range might have changed length");
557 
558             assert(length == oldLength + result,
559                 "Failed to insertBack range");
560 
561             return result;
562         }
563     }
564     private alias Data = RefCounted!(Payload, RefCountedAutoInitialize.no);
565     private Data _data;
566 
567     /**
568      * Constructor taking a number of items.
569      */
570     this(U)(U[] values...)
571     if (isImplicitlyConvertible!(U, T))
572     {
573         // [2021-07-17] Checking to see whether *always* calling ensureInitialized works-around-and/or-is-related-to https://issues.dlang.org/show_bug.cgihttps://issues.dlang.org/show_bug.cgi...
574         //if (values.length)
575         {
576             _data.refCountedStore.ensureInitialized();
577             _data.reserve(values.length);
578             foreach (ref value; values)
579             {
580                 // We do not simply write "_data.insertBack(value);"
581                 // because that might perform, on each iteration, a now-redundant check of length vs capacity.
582                 // Thanks to @dkorpel (https://github.com/dlang/phobos/pull/8162#discussion_r667479090).
583 
584                 import core.lifetime : emplace;
585                 emplace(_data._payload.ptr + _data._payload.length, value);
586 
587                 // We increment the length after each iteration (as opposed to adjusting it just once, after the loop)
588                 // in order to improve error-safety (in case one of the calls to emplace throws).
589                 _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1];
590             }
591         }
592 
593         assert(length == values.length);   // We check that all values have been inserted.
594         assert(capacity == values.length); // We check that reserve has been called before the loop.
595     }
596 
597     /// ditto
598     // needed when T is an array and only one argument is passed
599     this(T single) { __ctor!T(single); }
600 
601     /**
602      * Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
603      */
604     this(Range)(Range r)
605     if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[]))
606     {
607         insertBack(r);
608     }
609 
610     /**
611      * Comparison for equality.
612      */
613     bool opEquals(const Array rhs) const
614     {
615         return opEquals(rhs);
616     }
617 
618     // fix https://issues.dlang.org/show_bug.cgi?23140
619     private alias Unshared(T) = T;
620     private alias Unshared(T: shared U, U) = U;
621 
622     /// ditto
623     bool opEquals(ref const Array rhs) const
624     {
625         if (empty) return rhs.empty;
626         if (rhs.empty) return false;
627 
628         return cast(Unshared!(T)[]) _data._payload ==  cast(Unshared!(T)[]) rhs._data._payload;
629     }
630 
631     /**
632      *  Defines the array's primary range, which is a random-access range.
633      *
634      *  `ConstRange` is a variant with `const` elements.
635      *  `ImmutableRange` is a variant with `immutable` elements.
636      */
637     alias Range = RangeT!Array;
638 
639     /// ditto
640     alias ConstRange = RangeT!(const Array);
641 
642     /// ditto
643     alias ImmutableRange = RangeT!(immutable Array);
644 
645     /**
646      * Duplicates the array. The elements themselves are not transitively
647      * duplicated.
648      *
649      * Complexity: $(BIGOH length).
650      */
651     @property Array dup()
652     {
653         if (!_data.refCountedStore.isInitialized) return this;
654         return Array(_data._payload);
655     }
656 
657     /**
658      * Returns: `true` if and only if the array has no elements.
659      *
660      * Complexity: $(BIGOH 1)
661      */
662     @property bool empty() const
663     {
664         return !_data.refCountedStore.isInitialized || _data._payload.empty;
665     }
666 
667     /**
668      * Returns: The number of elements in the array.
669      *
670      * Complexity: $(BIGOH 1).
671      */
672     @property size_t length() const
673     {
674         return _data.refCountedStore.isInitialized ? _data._payload.length : 0;
675     }
676 
677     /// ditto
678     size_t opDollar() const
679     {
680         return length;
681     }
682 
683     /**
684      * Returns: The maximum number of elements the array can store without
685      * reallocating memory and invalidating iterators upon insertion.
686      *
687      * Complexity: $(BIGOH 1)
688      */
689     @property size_t capacity()
690     {
691         return _data.refCountedStore.isInitialized ? _data._capacity : 0;
692     }
693 
694     /**
695      * Returns: the internal representation of the array.
696      *
697      * Complexity: $(BIGOH 1).
698      */
699 
700     inout(T)[] data() inout @system
701     {
702         return _data.refCountedStore.isInitialized ? _data._payload : [];
703     }
704 
705     /**
706      * Ensures sufficient capacity to accommodate `e` _elements.
707      * If `e < capacity`, this method does nothing.
708      *
709      * Postcondition: `capacity >= e`
710      *
711      * Note: If the capacity is increased, one should assume that all
712      * iterators to the elements are invalidated.
713      *
714      * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1).
715      */
716     void reserve(size_t elements)
717     {
718         if (elements > capacity)
719         {
720             _data.refCountedStore.ensureInitialized();
721             _data.reserve(elements);
722             assert(capacity == elements); // Might need changing to ">=" if implementation of Payload.reserve is changed.
723         }
724     }
725 
726     /**
727      * Returns: A range that iterates over elements of the array in
728      * forward order.
729      *
730      * Complexity: $(BIGOH 1)
731      */
732     Range opSlice()
733     {
734         return typeof(return)(this, 0, length);
735     }
736 
737     ConstRange opSlice() const
738     {
739         return typeof(return)(this, 0, length);
740     }
741 
742     ImmutableRange opSlice() immutable
743     {
744         return typeof(return)(this, 0, length);
745     }
746 
747     /**
748      * Returns: A range that iterates over elements of the array from
749      * index `i` up to (excluding) index `j`.
750      *
751      * Precondition: `i <= j && j <= length`
752      *
753      * Complexity: $(BIGOH 1)
754      */
755     Range opSlice(size_t i, size_t j)
756     {
757         assert(i <= j && j <= length, "Invalid slice bounds");
758         return typeof(return)(this, i, j);
759     }
760 
761     ConstRange opSlice(size_t i, size_t j) const
762     {
763         assert(i <= j && j <= length, "Invalid slice bounds");
764         return typeof(return)(this, i, j);
765     }
766 
767     ImmutableRange opSlice(size_t i, size_t j) immutable
768     {
769         assert(i <= j && j <= length, "Invalid slice bounds");
770         return typeof(return)(this, i, j);
771     }
772 
773     /**
774      * Returns: The first element of the array.
775      *
776      * Precondition: `empty == false`
777      *
778      * Complexity: $(BIGOH 1)
779      */
780     @property ref inout(T) front() inout
781     {
782         assert(_data.refCountedStore.isInitialized,
783             "Cannot get front of empty range");
784         return _data._payload[0];
785     }
786 
787     /**
788      * Returns: The last element of the array.
789      *
790      * Precondition: `empty == false`
791      *
792      * Complexity: $(BIGOH 1)
793      */
794     @property ref inout(T) back() inout
795     {
796         assert(_data.refCountedStore.isInitialized,
797             "Cannot get back of empty range");
798         return _data._payload[$ - 1];
799     }
800 
801     /**
802      * Returns: The element or a reference to the element at the specified index.
803      *
804      * Precondition: `i < length`
805      *
806      * Complexity: $(BIGOH 1)
807      */
808     ref inout(T) opIndex(size_t i) inout
809     {
810         assert(_data.refCountedStore.isInitialized,
811             "Cannot index empty range");
812         return _data._payload[i];
813     }
814 
815     /**
816      * Slicing operators executing the specified operation on the entire slice.
817      *
818      * Precondition: `i < j && j < length`
819      *
820      * Complexity: $(BIGOH slice.length)
821      */
822     void opSliceAssign(T value)
823     {
824         if (!_data.refCountedStore.isInitialized) return;
825         _data._payload[] = value;
826     }
827 
828     /// ditto
829     void opSliceAssign(T value, size_t i, size_t j)
830     {
831         auto slice = _data.refCountedStore.isInitialized ?
832             _data._payload :
833             T[].init;
834         slice[i .. j] = value;
835     }
836 
837     /// ditto
838     void opSliceUnary(string op)()
839     if (op == "++" || op == "--")
840     {
841         if (!_data.refCountedStore.isInitialized) return;
842         mixin(op~"_data._payload[];");
843     }
844 
845     /// ditto
846     void opSliceUnary(string op)(size_t i, size_t j)
847     if (op == "++" || op == "--")
848     {
849         auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init;
850         mixin(op~"slice[i .. j];");
851     }
852 
853     /// ditto
854     void opSliceOpAssign(string op)(T value)
855     {
856         if (!_data.refCountedStore.isInitialized) return;
857         mixin("_data._payload[] "~op~"= value;");
858     }
859 
860     /// ditto
861     void opSliceOpAssign(string op)(T value, size_t i, size_t j)
862     {
863         auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init;
864         mixin("slice[i .. j] "~op~"= value;");
865     }
866 
867     private enum hasSliceWithLength(T) = is(typeof({ T t = T.init; t[].length; }));
868 
869     /**
870      * Returns: A new array which is a concatenation of `this` and its argument.
871      *
872      * Complexity:
873      * $(BIGOH length + m), where `m` is the number of elements in `stuff`.
874      */
875     Array opBinary(string op, Stuff)(Stuff stuff)
876     if (op == "~")
877     {
878         Array result;
879 
880         static if (hasLength!Stuff || isNarrowString!Stuff)
881             result.reserve(length + stuff.length);
882         else static if (hasSliceWithLength!Stuff)
883             result.reserve(length + stuff[].length);
884         else static if (isImplicitlyConvertible!(Stuff, T))
885             result.reserve(length + 1);
886 
887         result.insertBack(this[]);
888         result ~= stuff;
889         return result;
890     }
891 
892     /**
893      * Forwards to `insertBack`.
894      */
895     void opOpAssign(string op, Stuff)(auto ref Stuff stuff)
896     if (op == "~")
897     {
898         static if (is(typeof(stuff[])) && isImplicitlyConvertible!(typeof(stuff[0]), T))
899         {
900             insertBack(stuff[]);
901         }
902         else
903         {
904             insertBack(stuff);
905         }
906     }
907 
908     /**
909      * Removes all the elements from the array and releases allocated memory.
910      *
911      * Postcondition: `empty == true && capacity == 0`
912      *
913      * Complexity: $(BIGOH length)
914      */
915     void clear()
916     {
917         _data = Data.init;
918     }
919 
920     /**
921      * Sets the number of elements in the array to `newLength`. If `newLength`
922      * is greater than `length`, the new elements are added to the end of the
923      * array and initialized with `T.init`. If `T` is a `struct` whose default
924      * constructor is annotated with `@disable`, `newLength` must be lower than
925      * or equal to `length`.
926      *
927      * Complexity:
928      * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`.
929      * If `capacity < newLength` the worst case is $(BIGOH newLength).
930      *
931      * Precondition: `__traits(compiles, { static T _; }) || newLength <= length`
932      *
933      * Postcondition: `length == newLength`
934      */
935     @property void length(size_t newLength)
936     {
937         _data.refCountedStore.ensureInitialized();
938         _data.length = newLength;
939     }
940 
941     /**
942      * Removes the last element from the array and returns it.
943      * Both stable and non-stable versions behave the same and guarantee
944      * that ranges iterating over the array are never invalidated.
945      *
946      * Precondition: `empty == false`
947      *
948      * Returns: The element removed.
949      *
950      * Complexity: $(BIGOH 1).
951      *
952      * Throws: `Exception` if the array is empty.
953      */
954     T removeAny()
955     {
956         auto result = back;
957         removeBack();
958         return result;
959     }
960 
961     /// ditto
962     alias stableRemoveAny = removeAny;
963 
964     /**
965      * Inserts the specified elements at the back of the array. `stuff` can be
966      * a value convertible to `T` or a range of objects convertible to `T`.
967      *
968      * Returns: The number of elements inserted.
969      *
970      * Complexity:
971      * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m),
972      * where `m` is the number of elements in `stuff`.
973      */
974     size_t insertBack(Stuff)(Stuff stuff)
975     if (isImplicitlyConvertible!(Stuff, T) ||
976             isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
977     {
978         _data.refCountedStore.ensureInitialized();
979         return _data.insertBack(stuff);
980     }
981 
982     /// ditto
983     alias insert = insertBack;
984 
985     /**
986      * Removes the value from the back of the array. Both stable and non-stable
987      * versions behave the same and guarantee that ranges iterating over the
988      * array are never invalidated.
989      *
990      * Precondition: `empty == false`
991      *
992      * Complexity: $(BIGOH 1).
993      *
994      * Throws: `Exception` if the array is empty.
995      */
996     void removeBack()
997     {
998         assert(!empty);
999         static if (hasElaborateDestructor!T)
1000             .destroy(_data._payload[$ - 1]);
1001 
1002         _data._payload = _data._payload[0 .. $ - 1];
1003     }
1004 
1005     /// ditto
1006     alias stableRemoveBack = removeBack;
1007 
1008     /**
1009      * Removes `howMany` values from the back of the array.
1010      * Unlike the unparameterized versions above, these functions
1011      * do not throw if they could not remove `howMany` elements. Instead,
1012      * if `howMany > n`, all elements are removed. The returned value is
1013      * the effective number of elements removed. Both stable and non-stable
1014      * versions behave the same and guarantee that ranges iterating over
1015      * the array are never invalidated.
1016      *
1017      * Returns: The number of elements removed.
1018      *
1019      * Complexity: $(BIGOH howMany).
1020      */
1021     size_t removeBack(size_t howMany)
1022     {
1023         if (howMany > length) howMany = length;
1024         static if (hasElaborateDestructor!T)
1025             foreach (ref e; _data._payload[$ - howMany .. $])
1026                 .destroy(e);
1027 
1028         _data._payload = _data._payload[0 .. $ - howMany];
1029         return howMany;
1030     }
1031 
1032     /// ditto
1033     alias stableRemoveBack = removeBack;
1034 
1035     /**
1036      * Inserts `stuff` before, after, or instead range `r`, which must
1037      * be a valid range previously extracted from this array. `stuff`
1038      * can be a value convertible to `T` or a range of objects convertible
1039      * to `T`. Both stable and non-stable version behave the same and
1040      * guarantee that ranges iterating over the array are never invalidated.
1041      *
1042      * Returns: The number of values inserted.
1043      *
1044      * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`.
1045      *
1046      * Throws: `Exception` if `r` is not a range extracted from this array.
1047      */
1048     size_t insertBefore(Stuff)(Range r, Stuff stuff)
1049     if (isImplicitlyConvertible!(Stuff, T))
1050     {
1051         import core.lifetime : emplace;
1052         enforce(r._outer._data is _data && r._a <= length);
1053         reserve(length + 1);
1054         assert(_data.refCountedStore.isInitialized,
1055             "Failed to allocate capacity to insertBefore");
1056         // Move elements over by one slot
1057         memmove(_data._payload.ptr + r._a + 1,
1058                 _data._payload.ptr + r._a,
1059                 T.sizeof * (length - r._a));
1060         emplace(_data._payload.ptr + r._a, stuff);
1061         _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1];
1062         return 1;
1063     }
1064 
1065     /// ditto
1066     size_t insertBefore(Stuff)(Range r, Stuff stuff)
1067     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
1068     {
1069         import core.lifetime : emplace;
1070         enforce(r._outer._data is _data && r._a <= length);
1071         static if (isForwardRange!Stuff)
1072         {
1073             // Can find the length in advance
1074             auto extra = walkLength(stuff);
1075             if (!extra) return 0;
1076             reserve(length + extra);
1077             assert(_data.refCountedStore.isInitialized,
1078                 "Failed to allocate capacity to insertBefore");
1079             // Move elements over by extra slots
1080             memmove(_data._payload.ptr + r._a + extra,
1081                     _data._payload.ptr + r._a,
1082                     T.sizeof * (length - r._a));
1083             foreach (p; _data._payload.ptr + r._a ..
1084                     _data._payload.ptr + r._a + extra)
1085             {
1086                 emplace(p, stuff.front);
1087                 stuff.popFront();
1088             }
1089             _data._payload =
1090                 _data._payload.ptr[0 .. _data._payload.length + extra];
1091             return extra;
1092         }
1093         else
1094         {
1095             import std.algorithm.mutation : bringToFront;
1096             enforce(_data);
1097             immutable offset = r._a;
1098             enforce(offset <= length);
1099             auto result = insertBack(stuff);
1100             bringToFront(this[offset .. length - result],
1101                     this[length - result .. length]);
1102             return result;
1103         }
1104     }
1105 
1106     /// ditto
1107     alias stableInsertBefore = insertBefore;
1108 
1109     /// ditto
1110     size_t insertAfter(Stuff)(Range r, Stuff stuff)
1111     if (isImplicitlyConvertible!(Stuff, T) ||
1112             isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
1113     {
1114         import std.algorithm.mutation : bringToFront;
1115         enforce(r._outer._data is _data);
1116         // TODO: optimize
1117         immutable offset = r._b;
1118         enforce(offset <= length);
1119         auto result = insertBack(stuff);
1120         bringToFront(this[offset .. length - result],
1121                 this[length - result .. length]);
1122         return result;
1123     }
1124 
1125     /// ditto
1126     size_t replace(Stuff)(Range r, Stuff stuff)
1127     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
1128     {
1129         enforce(r._outer._data is _data);
1130         size_t result;
1131         for (; !stuff.empty; stuff.popFront())
1132         {
1133             if (r.empty)
1134             {
1135                 // insert the rest
1136                 return result + insertBefore(r, stuff);
1137             }
1138             r.front = stuff.front;
1139             r.popFront();
1140             ++result;
1141         }
1142         // Remove remaining stuff in r
1143         linearRemove(r);
1144         return result;
1145     }
1146 
1147     /// ditto
1148     size_t replace(Stuff)(Range r, Stuff stuff)
1149     if (isImplicitlyConvertible!(Stuff, T))
1150     {
1151         enforce(r._outer._data is _data);
1152         if (r.empty)
1153         {
1154             insertBefore(r, stuff);
1155         }
1156         else
1157         {
1158             r.front = stuff;
1159             r.popFront();
1160             linearRemove(r);
1161         }
1162         return 1;
1163     }
1164 
1165     /**
1166      * Removes all elements belonging to `r`, which must be a range
1167      * obtained originally from this array.
1168      *
1169      * Returns: A range spanning the remaining elements in the array that
1170      * initially were right after `r`.
1171      *
1172      * Complexity: $(BIGOH length)
1173      *
1174      * Throws: `Exception` if `r` is not a valid range extracted from this array.
1175      */
1176     Range linearRemove(Range r)
1177     {
1178         import std.algorithm.mutation : copy;
1179 
1180         enforce(r._outer._data is _data);
1181         enforce(_data.refCountedStore.isInitialized);
1182         enforce(r._a <= r._b && r._b <= length);
1183         immutable offset1 = r._a;
1184         immutable offset2 = r._b;
1185         immutable tailLength = length - offset2;
1186         // Use copy here, not a[] = b[] because the ranges may overlap
1187         copy(this[offset2 .. length], this[offset1 .. offset1 + tailLength]);
1188         length = offset1 + tailLength;
1189         return this[length - tailLength .. length];
1190     }
1191 }
1192 
1193 @system unittest
1194 {
1195     Array!int a;
1196     assert(a.empty);
1197 }
1198 
1199 @system unittest
1200 {
1201     Array!int a;
1202     a.length = 10;
1203     assert(a.length == 10);
1204     assert(a.capacity >= a.length);
1205 }
1206 
1207 @system unittest
1208 {
1209     struct Dumb { int x = 5; }
1210     Array!Dumb a;
1211     a.length = 10;
1212     assert(a.length == 10);
1213     assert(a.capacity >= a.length);
1214     immutable cap = a.capacity;
1215     foreach (ref e; a)
1216         e.x = 10;
1217     a.length = 5;
1218     assert(a.length == 5);
1219     // do not realloc if length decreases
1220     assert(a.capacity == cap);
1221     foreach (ref e; a)
1222         assert(e.x == 10);
1223 
1224     a.length = 8;
1225     assert(a.length == 8);
1226     // do not realloc if capacity sufficient
1227     assert(a.capacity == cap);
1228     assert(Dumb.init.x == 5);
1229     foreach (i; 0 .. 5)
1230         assert(a[i].x == 10);
1231     foreach (i; 5 .. a.length)
1232         assert(a[i].x == Dumb.init.x);
1233 
1234     // realloc required, check if values properly copied
1235     a[] = Dumb(1);
1236     a.length = 20;
1237     assert(a.capacity >= 20);
1238     foreach (i; 0 .. 8)
1239         assert(a[i].x == 1);
1240     foreach (i; 8 .. a.length)
1241         assert(a[i].x == Dumb.init.x);
1242 
1243     // check if overlapping elements properly initialized
1244     a.length = 1;
1245     a.length = 20;
1246     assert(a[0].x == 1);
1247     foreach (e; a[1 .. $])
1248         assert(e.x == Dumb.init.x);
1249 }
1250 
1251 @system unittest
1252 {
1253     Array!int a = Array!int(1, 2, 3);
1254     //a._data._refCountedDebug = true;
1255     auto b = a.dup;
1256     assert(b == Array!int(1, 2, 3));
1257     b.front = 42;
1258     assert(b == Array!int(42, 2, 3));
1259     assert(a == Array!int(1, 2, 3));
1260 }
1261 
1262 @system unittest
1263 {
1264     auto a = Array!int(1, 2, 3);
1265     assert(a.length == 3);
1266 }
1267 
1268 @system unittest
1269 {
1270     const Array!int a = [1, 2];
1271 
1272     assert(a[0] == 1);
1273     assert(a.front == 1);
1274     assert(a.back == 2);
1275 
1276     static assert(!__traits(compiles, { a[0] = 1; }));
1277     static assert(!__traits(compiles, { a.front = 1; }));
1278     static assert(!__traits(compiles, { a.back = 1; }));
1279 
1280     auto r = a[];
1281     size_t i;
1282     foreach (e; r)
1283     {
1284         assert(e == i + 1);
1285         i++;
1286     }
1287 }
1288 
1289 @system unittest
1290 {
1291     import std.algorithm.comparison : equal;
1292     auto a = Array!string("test");
1293     assert(a[].equal(["test"]));
1294 }
1295 
1296 @safe unittest
1297 {
1298     // https://issues.dlang.org/show_bug.cgi?id=13621
1299     import std.container : Array, BinaryHeap;
1300     alias Heap = BinaryHeap!(Array!int);
1301 }
1302 
1303 @system unittest
1304 {
1305     // https://issues.dlang.org/show_bug.cgi?id=18800
1306     static struct S { void* p; }
1307     Array!S a;
1308     a.length = 10;
1309 }
1310 
1311 @system unittest
1312 {
1313     Array!int a;
1314     a.reserve(1000);
1315     assert(a.length == 0);
1316     assert(a.empty);
1317     assert(a.capacity >= 1000);
1318     auto p = a._data._payload.ptr;
1319     foreach (i; 0 .. 1000)
1320     {
1321         a.insertBack(i);
1322     }
1323     assert(p == a._data._payload.ptr);
1324 }
1325 
1326 @system unittest
1327 {
1328     auto a = Array!int(1, 2, 3);
1329     a[1] *= 42;
1330     assert(a[1] == 84);
1331 }
1332 
1333 @system unittest
1334 {
1335     auto a = Array!int(1, 2, 3);
1336     auto b = Array!int(11, 12, 13);
1337     auto c = a ~ b;
1338     assert(c == Array!int(1, 2, 3, 11, 12, 13));
1339     assert(a ~ b[] == Array!int(1, 2, 3, 11, 12, 13));
1340     assert(a ~ [4,5] == Array!int(1,2,3,4,5));
1341 }
1342 
1343 @system unittest
1344 {
1345     auto a = Array!int(1, 2, 3);
1346     auto b = Array!int(11, 12, 13);
1347     a ~= b;
1348     assert(a == Array!int(1, 2, 3, 11, 12, 13));
1349 }
1350 
1351 @system unittest
1352 {
1353     auto a = Array!int(1, 2, 3, 4);
1354     assert(a.removeAny() == 4);
1355     assert(a == Array!int(1, 2, 3));
1356 }
1357 
1358 @system unittest
1359 {
1360     auto a = Array!int(1, 2, 3, 4, 5);
1361     auto r = a[2 .. a.length];
1362     assert(a.insertBefore(r, 42) == 1);
1363     assert(a == Array!int(1, 2, 42, 3, 4, 5));
1364     r = a[2 .. 2];
1365     assert(a.insertBefore(r, [8, 9]) == 2);
1366     assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5));
1367 }
1368 
1369 @system unittest
1370 {
1371     auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8);
1372     a.linearRemove(a[4 .. 6]);
1373     assert(a == Array!int(0, 1, 2, 3, 6, 7, 8));
1374 }
1375 
1376 // Give the Range object some testing.
1377 @system unittest
1378 {
1379     import std.algorithm.comparison : equal;
1380     import std.range : retro;
1381     auto a = Array!int(0, 1, 2, 3, 4, 5, 6)[];
1382     auto b = Array!int(6, 5, 4, 3, 2, 1, 0)[];
1383     alias A = typeof(a);
1384 
1385     static assert(isRandomAccessRange!A);
1386     static assert(hasSlicing!A);
1387     static assert(hasAssignableElements!A);
1388     static assert(hasMobileElements!A);
1389 
1390     assert(equal(retro(b), a));
1391     assert(a.length == 7);
1392     assert(equal(a[1 .. 4], [1, 2, 3]));
1393 }
1394 
1395 // https://issues.dlang.org/show_bug.cgi?id=5920
1396 @system unittest
1397 {
1398     struct structBug5920
1399     {
1400         int order;
1401         uint* pDestructionMask;
1402         ~this()
1403         {
1404             if (pDestructionMask)
1405                 *pDestructionMask += 1 << order;
1406         }
1407     }
1408 
1409     alias S = structBug5920;
1410     uint dMask;
1411 
1412     auto arr = Array!S(cast(S[])[]);
1413     foreach (i; 0 .. 8)
1414         arr.insertBack(S(i, &dMask));
1415     // don't check dMask now as S may be copied multiple times (it's ok?)
1416     {
1417         assert(arr.length == 8);
1418         dMask = 0;
1419         arr.length = 6;
1420         assert(arr.length == 6);    // make sure shrinking calls the d'tor
1421         assert(dMask == 0b1100_0000);
1422         arr.removeBack();
1423         assert(arr.length == 5);    // make sure removeBack() calls the d'tor
1424         assert(dMask == 0b1110_0000);
1425         arr.removeBack(3);
1426         assert(arr.length == 2);    // ditto
1427         assert(dMask == 0b1111_1100);
1428         arr.clear();
1429         assert(arr.length == 0);    // make sure clear() calls the d'tor
1430         assert(dMask == 0b1111_1111);
1431     }
1432     assert(dMask == 0b1111_1111);   // make sure the d'tor is called once only.
1433 }
1434 
1435 // Test for https://issues.dlang.org/show_bug.cgi?id=5792
1436 // (mainly just to check if this piece of code is compilable)
1437 @system unittest
1438 {
1439     auto a = Array!(int[])([[1,2],[3,4]]);
1440     a.reserve(4);
1441     assert(a.capacity >= 4);
1442     assert(a.length == 2);
1443     assert(a[0] == [1,2]);
1444     assert(a[1] == [3,4]);
1445     a.reserve(16);
1446     assert(a.capacity >= 16);
1447     assert(a.length == 2);
1448     assert(a[0] == [1,2]);
1449     assert(a[1] == [3,4]);
1450 }
1451 
1452 // test replace!Stuff with range Stuff
1453 @system unittest
1454 {
1455     import std.algorithm.comparison : equal;
1456     auto a = Array!int([1, 42, 5]);
1457     a.replace(a[1 .. 2], [2, 3, 4]);
1458     assert(equal(a[], [1, 2, 3, 4, 5]));
1459 }
1460 
1461 // test insertBefore and replace with empty Arrays
1462 @system unittest
1463 {
1464     import std.algorithm.comparison : equal;
1465     auto a = Array!int();
1466     a.insertBefore(a[], 1);
1467     assert(equal(a[], [1]));
1468 }
1469 @system unittest
1470 {
1471     import std.algorithm.comparison : equal;
1472     auto a = Array!int();
1473     a.insertBefore(a[], [1, 2]);
1474     assert(equal(a[], [1, 2]));
1475 }
1476 @system unittest
1477 {
1478     import std.algorithm.comparison : equal;
1479     auto a = Array!int();
1480     a.replace(a[], [1, 2]);
1481     assert(equal(a[], [1, 2]));
1482 }
1483 @system unittest
1484 {
1485     import std.algorithm.comparison : equal;
1486     auto a = Array!int();
1487     a.replace(a[], 1);
1488     assert(equal(a[], [1]));
1489 }
1490 // make sure that Array instances refuse ranges that don't belong to them
1491 @system unittest
1492 {
1493     import std.exception : assertThrown;
1494 
1495     Array!int a = [1, 2, 3];
1496     auto r = a.dup[];
1497     assertThrown(a.insertBefore(r, 42));
1498     assertThrown(a.insertBefore(r, [42]));
1499     assertThrown(a.insertAfter(r, 42));
1500     assertThrown(a.replace(r, 42));
1501     assertThrown(a.replace(r, [42]));
1502     assertThrown(a.linearRemove(r));
1503 }
1504 @system unittest
1505 {
1506     auto a = Array!int([1, 1]);
1507     a[1]  = 0; //Check Array.opIndexAssign
1508     assert(a[1] == 0);
1509     a[1] += 1; //Check Array.opIndexOpAssign
1510     assert(a[1] == 1);
1511 
1512     //Check Array.opIndexUnary
1513     ++a[0];
1514     //a[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
1515     assert(a[0] == 2);
1516     assert(+a[0] == +2);
1517     assert(-a[0] == -2);
1518     assert(~a[0] == ~2);
1519 
1520     auto r = a[];
1521     r[1]  = 0; //Check Array.Range.opIndexAssign
1522     assert(r[1] == 0);
1523     r[1] += 1; //Check Array.Range.opIndexOpAssign
1524     assert(r[1] == 1);
1525 
1526     //Check Array.Range.opIndexUnary
1527     ++r[0];
1528     //r[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
1529     assert(r[0] == 3);
1530     assert(+r[0] == +3);
1531     assert(-r[0] == -3);
1532     assert(~r[0] == ~3);
1533 }
1534 
1535 @system unittest
1536 {
1537     import std.algorithm.comparison : equal;
1538 
1539     //Test "array-wide" operations
1540     auto a = Array!int([0, 1, 2]); //Array
1541     a[] += 5;
1542     assert(a[].equal([5, 6, 7]));
1543     ++a[];
1544     assert(a[].equal([6, 7, 8]));
1545     a[1 .. 3] *= 5;
1546     assert(a[].equal([6, 35, 40]));
1547     a[0 .. 2] = 0;
1548     assert(a[].equal([0, 0, 40]));
1549 
1550     //Test empty array
1551     auto a2 = Array!int.init;
1552     ++a2[];
1553     ++a2[0 .. 0];
1554     a2[] = 0;
1555     a2[0 .. 0] = 0;
1556     a2[] += 0;
1557     a2[0 .. 0] += 0;
1558 
1559     //Test "range-wide" operations
1560     auto r = Array!int([0, 1, 2])[]; //Array.Range
1561     r[] += 5;
1562     assert(r.equal([5, 6, 7]));
1563     ++r[];
1564     assert(r.equal([6, 7, 8]));
1565     r[1 .. 3] *= 5;
1566     assert(r.equal([6, 35, 40]));
1567     r[0 .. 2] = 0;
1568     assert(r.equal([0, 0, 40]));
1569 
1570     //Test empty Range
1571     auto r2 = Array!int.init[];
1572     ++r2[];
1573     ++r2[0 .. 0];
1574     r2[] = 0;
1575     r2[0 .. 0] = 0;
1576     r2[] += 0;
1577     r2[0 .. 0] += 0;
1578 }
1579 
1580 // Test https://issues.dlang.org/show_bug.cgi?id=11194
1581 @system unittest
1582 {
1583     static struct S {
1584         int i = 1337;
1585         void* p;
1586         this(this) { assert(i == 1337); }
1587         ~this() { assert(i == 1337); }
1588     }
1589     Array!S arr;
1590     S s;
1591     arr ~= s;
1592     arr ~= s;
1593 }
1594 
1595 // https://issues.dlang.org/show_bug.cgi?id=11459
1596 @safe unittest
1597 {
1598     static struct S
1599     {
1600         bool b;
1601         alias b this;
1602     }
1603     alias A = Array!S;
1604     alias B = Array!(shared bool);
1605 }
1606 
1607 // https://issues.dlang.org/show_bug.cgi?id=11884
1608 @system unittest
1609 {
1610     import std.algorithm.iteration : filter;
1611     auto a = Array!int([1, 2, 2].filter!"true"());
1612 }
1613 
1614 // https://issues.dlang.org/show_bug.cgi?id=8282
1615 @safe unittest
1616 {
1617     auto arr = new Array!int;
1618 }
1619 
1620 // https://issues.dlang.org/show_bug.cgi?id=6998
1621 @system unittest
1622 {
1623     static int i = 0;
1624     class C
1625     {
1626         int dummy = 1;
1627         this(){++i;}
1628         ~this(){--i;}
1629     }
1630 
1631     assert(i == 0);
1632     auto c = new C();
1633     assert(i == 1);
1634 
1635     //scope
1636     {
1637         auto arr = Array!C(c);
1638         assert(i == 1);
1639     }
1640     //Array should not have destroyed the class instance
1641     assert(i == 1);
1642 
1643     //Just to make sure the GC doesn't collect before the above test.
1644     assert(c.dummy == 1);
1645 }
1646 
1647 //https://issues.dlang.org/show_bug.cgi?id=6998 (2)
1648 @system unittest
1649 {
1650     static class C {int i;}
1651     auto c = new C;
1652     c.i = 42;
1653     Array!C a;
1654     a ~= c;
1655     a.clear;
1656     assert(c.i == 42); //fails
1657 }
1658 
1659 @safe unittest
1660 {
1661     static assert(is(Array!int.Range));
1662     static assert(is(Array!int.ConstRange));
1663 }
1664 
1665 @system unittest // const/immutable Array and Ranges
1666 {
1667     static void test(A, R, E, S)()
1668     {
1669         A a;
1670         R r = a[];
1671         assert(r.empty);
1672         assert(r.length == 0);
1673         static assert(is(typeof(r.front) == E));
1674         static assert(is(typeof(r.back) == E));
1675         static assert(is(typeof(r[0]) == E));
1676         static assert(is(typeof(r[]) == S));
1677         static assert(is(typeof(r[0 .. 0]) == S));
1678     }
1679 
1680     alias A = Array!int;
1681 
1682     test!(A, A.Range, int, A.Range);
1683     test!(A, const A.Range, const int, A.ConstRange);
1684 
1685     test!(const A, A.ConstRange, const int, A.ConstRange);
1686     test!(const A, const A.ConstRange, const int, A.ConstRange);
1687 
1688     test!(immutable A, A.ImmutableRange, immutable int, A.ImmutableRange);
1689     test!(immutable A, const A.ImmutableRange, immutable int, A.ImmutableRange);
1690     test!(immutable A, immutable A.ImmutableRange, immutable int,
1691         A.ImmutableRange);
1692 }
1693 
1694 // ensure @nogc
1695 @nogc @system unittest
1696 {
1697     Array!int ai;
1698     ai ~= 1;
1699     assert(ai.front == 1);
1700 
1701     ai.reserve(10);
1702     assert(ai.capacity == 10);
1703 
1704     static immutable arr = [1, 2, 3];
1705     ai.insertBack(arr);
1706 }
1707 
1708 /*
1709  * typeof may give wrong result in case of classes defining `opCall` operator
1710  * https://issues.dlang.org/show_bug.cgi?id=20589
1711  *
1712  * destructor std.container.array.Array!(MyClass).Array.~this is @system
1713  * so the unittest is @system too
1714  */
1715 @system unittest
1716 {
1717     class MyClass
1718     {
1719         T opCall(T)(T p)
1720         {
1721             return p;
1722         }
1723     }
1724 
1725     Array!MyClass arr;
1726 }
1727 
1728 @system unittest
1729 {
1730     import std.algorithm.comparison : equal;
1731     auto a = Array!int([1,2,3,4,5]);
1732     assert(a.length == 5);
1733 
1734     assert(a.insertAfter(a[0 .. 5], [7, 8]) == 2);
1735     assert(equal(a[], [1,2,3,4,5,7,8]));
1736 
1737     assert(a.insertAfter(a[0 .. 5], 6) == 1);
1738     assert(equal(a[], [1,2,3,4,5,6,7,8]));
1739 }
1740 
1741 // https://issues.dlang.org/show_bug.cgi?id=22105
1742 @system unittest
1743 {
1744     import core.exception : AssertError;
1745     import std.exception : assertThrown, assertNotThrown;
1746 
1747     struct NoDefaultCtor
1748     {
1749         int i;
1750         @disable this();
1751         this(int j) { i = j; }
1752     }
1753 
1754     auto array = Array!NoDefaultCtor([NoDefaultCtor(1), NoDefaultCtor(2)]);
1755     assertNotThrown!AssertError(array.length = 1);
1756     assertThrown!AssertError(array.length = 5);
1757 }
1758 
1759 // https://issues.dlang.org/show_bug.cgi?id=23140
1760 @system unittest
1761 {
1762     shared class C
1763     {
1764     }
1765 
1766     Array!C ac;
1767     ac = Array!C([new C]);
1768 }
1769 ////////////////////////////////////////////////////////////////////////////////
1770 // Array!bool
1771 ////////////////////////////////////////////////////////////////////////////////
1772 
1773 /**
1774  * _Array specialized for `bool`. Packs together values efficiently by
1775  * allocating one bit per element.
1776  */
1777 struct Array(T)
1778 if (is(immutable T == immutable bool))
1779 {
1780     import std.exception : enforce;
1781     import std.typecons : RefCounted, RefCountedAutoInitialize;
1782 
1783     static immutable uint bitsPerWord = size_t.sizeof * 8;
1784     private static struct Data
1785     {
1786         Array!size_t.Payload _backend;
1787         size_t _length;
1788     }
1789     private RefCounted!(Data, RefCountedAutoInitialize.no) _store;
1790 
1791     private @property ref size_t[] data()
1792     {
1793         assert(_store.refCountedStore.isInitialized,
1794             "Cannot get data of uninitialized Array");
1795         return _store._backend._payload;
1796     }
1797 
1798     /**
1799      * Defines the array's primary range.
1800      */
1801     struct Range
1802     {
1803         private Array _outer;
1804         private size_t _a, _b;
1805         /// Range primitives
1806         @property Range save()
1807         {
1808             version (bug4437)
1809             {
1810                 return this;
1811             }
1812             else
1813             {
1814                 auto copy = this;
1815                 return copy;
1816             }
1817         }
1818         /// Ditto
1819         @property bool empty()
1820         {
1821             return _a >= _b || _outer.length < _b;
1822         }
1823         /// Ditto
1824         @property T front()
1825         {
1826             assert(!empty, "Attempting to access the front of an empty Array");
1827             return _outer[_a];
1828         }
1829         /// Ditto
1830         @property void front(bool value)
1831         {
1832             assert(!empty, "Attempting to set the front of an empty Array");
1833             _outer[_a] = value;
1834         }
1835         /// Ditto
1836         T moveFront()
1837         {
1838             assert(!empty, "Attempting to move the front of an empty Array");
1839             return _outer.moveAt(_a);
1840         }
1841         /// Ditto
1842         void popFront()
1843         {
1844             assert(!empty, "Attempting to popFront an empty Array");
1845             ++_a;
1846         }
1847         /// Ditto
1848         @property T back()
1849         {
1850             assert(!empty, "Attempting to access the back of an empty Array");
1851             return _outer[_b - 1];
1852         }
1853         /// Ditto
1854         @property void back(bool value)
1855         {
1856             assert(!empty, "Attempting to set the back of an empty Array");
1857             _outer[_b - 1] = value;
1858         }
1859         /// Ditto
1860         T moveBack()
1861         {
1862             assert(!empty, "Attempting to move the back of an empty Array");
1863             return _outer.moveAt(_b - 1);
1864         }
1865         /// Ditto
1866         void popBack()
1867         {
1868             assert(!empty, "Attempting to popBack an empty Array");
1869             --_b;
1870         }
1871         /// Ditto
1872         T opIndex(size_t i)
1873         {
1874             return _outer[_a + i];
1875         }
1876         /// Ditto
1877         void opIndexAssign(T value, size_t i)
1878         {
1879             _outer[_a + i] = value;
1880         }
1881         /// Ditto
1882         T moveAt(size_t i)
1883         {
1884             return _outer.moveAt(_a + i);
1885         }
1886         /// Ditto
1887         @property size_t length() const
1888         {
1889             assert(_a <= _b, "Invalid bounds");
1890             return _b - _a;
1891         }
1892         alias opDollar = length;
1893         /// ditto
1894         Range opSlice(size_t low, size_t high)
1895         {
1896             // Note: indexes start at 0, which is equivalent to _a
1897             assert(
1898                 low <= high && high <= (_b - _a),
1899                 "Using out of bounds indexes on an Array"
1900             );
1901             return Range(_outer, _a + low, _a + high);
1902         }
1903     }
1904 
1905     /**
1906      * Constructor taking a number of items.
1907      */
1908     this(U)(U[] values...)
1909     if (isImplicitlyConvertible!(U, T))
1910     {
1911         reserve(values.length);
1912         foreach (i, v; values)
1913         {
1914             auto rem = i % bitsPerWord;
1915             if (rem)
1916             {
1917                 // Fits within the current array
1918                 if (v)
1919                 {
1920                     data[$ - 1] |= (cast(size_t) 1 << rem);
1921                 }
1922                 else
1923                 {
1924                     data[$ - 1] &= ~(cast(size_t) 1 << rem);
1925                 }
1926             }
1927             else
1928             {
1929                 // Need to add more data
1930                 _store._backend.insertBack(v);
1931             }
1932         }
1933         _store._length = values.length;
1934     }
1935 
1936     /**
1937      * Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1938      */
1939     this(Range)(Range r)
1940     if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[]))
1941     {
1942         insertBack(r);
1943     }
1944 
1945     /**
1946      * Property returning `true` if and only if the array has
1947      * no elements.
1948      *
1949      * Complexity: $(BIGOH 1)
1950      */
1951     @property bool empty()
1952     {
1953         return !length;
1954     }
1955 
1956     /**
1957      * Returns: A duplicate of the array.
1958      *
1959      * Complexity: $(BIGOH length).
1960      */
1961     @property Array dup()
1962     {
1963         Array result;
1964         result.insertBack(this[]);
1965         return result;
1966     }
1967 
1968     /**
1969      * Returns the number of elements in the array.
1970      *
1971      * Complexity: $(BIGOH 1).
1972      */
1973     @property size_t length() const
1974     {
1975         return _store.refCountedStore.isInitialized ? _store._length : 0;
1976     }
1977     alias opDollar = length;
1978 
1979     /**
1980      * Returns: The maximum number of elements the array can store without
1981      * reallocating memory and invalidating iterators upon insertion.
1982      *
1983      * Complexity: $(BIGOH 1).
1984      */
1985     @property size_t capacity()
1986     {
1987         return _store.refCountedStore.isInitialized
1988             ? cast(size_t) bitsPerWord * _store._backend.capacity
1989             : 0;
1990     }
1991 
1992     /**
1993      * Ensures sufficient capacity to accommodate `e` _elements.
1994      * If `e < capacity`, this method does nothing.
1995      *
1996      * Postcondition: `capacity >= e`
1997      *
1998      * Note: If the capacity is increased, one should assume that all
1999      * iterators to the elements are invalidated.
2000      *
2001      * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1).
2002      */
2003     void reserve(size_t e)
2004     {
2005         import std.conv : to;
2006         _store.refCountedStore.ensureInitialized();
2007         _store._backend.reserve(to!size_t((e + bitsPerWord - 1) / bitsPerWord));
2008     }
2009 
2010     /**
2011      * Returns: A range that iterates over all elements of the array in forward order.
2012      *
2013      * Complexity: $(BIGOH 1)
2014      */
2015     Range opSlice()
2016     {
2017         return Range(this, 0, length);
2018     }
2019 
2020 
2021     /**
2022      * Returns: A range that iterates the array between two specified positions.
2023      *
2024      * Complexity: $(BIGOH 1)
2025      */
2026     Range opSlice(size_t a, size_t b)
2027     {
2028         enforce(a <= b && b <= length);
2029         return Range(this, a, b);
2030     }
2031 
2032     /**
2033      * Returns: The first element of the array.
2034      *
2035      * Precondition: `empty == false`
2036      *
2037      * Complexity: $(BIGOH 1)
2038      *
2039      * Throws: `Exception` if the array is empty.
2040      */
2041     @property bool front()
2042     {
2043         assert(!empty);
2044         return data.ptr[0] & 1;
2045     }
2046 
2047     /// Ditto
2048     @property void front(bool value)
2049     {
2050         assert(!empty);
2051         if (value) data.ptr[0] |= 1;
2052         else data.ptr[0] &= ~cast(size_t) 1;
2053     }
2054 
2055     /**
2056      * Returns: The last element of the array.
2057      *
2058      * Precondition: `empty == false`
2059      *
2060      * Complexity: $(BIGOH 1)
2061      *
2062      * Throws: `Exception` if the array is empty.
2063      */
2064     @property bool back()
2065     {
2066         assert(!empty);
2067         return cast(bool)(data.back & (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord)));
2068     }
2069 
2070     /// Ditto
2071     @property void back(bool value)
2072     {
2073         assert(!empty);
2074         if (value)
2075         {
2076             data.back |= (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord));
2077         }
2078         else
2079         {
2080             data.back &=
2081                 ~(cast(size_t) 1 << ((_store._length - 1) % bitsPerWord));
2082         }
2083     }
2084 
2085     /**
2086      * Indexing operators yielding or modifyng the value at the specified index.
2087      *
2088      * Precondition: `i < length`
2089      *
2090      * Complexity: $(BIGOH 1)
2091      */
2092     bool opIndex(size_t i)
2093     {
2094         auto div = cast(size_t) (i / bitsPerWord);
2095         auto rem = i % bitsPerWord;
2096         enforce(div < data.length);
2097         return cast(bool)(data.ptr[div] & (cast(size_t) 1 << rem));
2098     }
2099 
2100     /// ditto
2101     void opIndexAssign(bool value, size_t i)
2102     {
2103         auto div = cast(size_t) (i / bitsPerWord);
2104         auto rem = i % bitsPerWord;
2105         enforce(div < data.length);
2106         if (value) data.ptr[div] |= (cast(size_t) 1 << rem);
2107         else data.ptr[div] &= ~(cast(size_t) 1 << rem);
2108     }
2109 
2110     /// ditto
2111     void opIndexOpAssign(string op)(bool value, size_t i)
2112     {
2113         auto div = cast(size_t) (i / bitsPerWord);
2114         auto rem = i % bitsPerWord;
2115         enforce(div < data.length);
2116         auto oldValue = cast(bool) (data.ptr[div] & (cast(size_t) 1 << rem));
2117         // Do the deed
2118         auto newValue = mixin("oldValue "~op~" value");
2119         // Write back the value
2120         if (newValue != oldValue)
2121         {
2122             if (newValue) data.ptr[div] |= (cast(size_t) 1 << rem);
2123             else data.ptr[div] &= ~(cast(size_t) 1 << rem);
2124         }
2125     }
2126 
2127     /// Ditto
2128     T moveAt(size_t i)
2129     {
2130         return this[i];
2131     }
2132 
2133     /**
2134      * Returns: A new array which is a concatenation of `this` and its argument.
2135      *
2136      * Complexity:
2137      * $(BIGOH length + m), where `m` is the number of elements in `stuff`.
2138      */
2139     Array!bool opBinary(string op, Stuff)(Stuff rhs)
2140     if (op == "~")
2141     {
2142         Array!bool result;
2143 
2144         static if (hasLength!Stuff)
2145             result.reserve(length + rhs.length);
2146         else static if (is(typeof(rhs[])) && hasLength!(typeof(rhs[])))
2147             result.reserve(length + rhs[].length);
2148         else static if (isImplicitlyConvertible!(Stuff, bool))
2149             result.reserve(length + 1);
2150 
2151         result.insertBack(this[]);
2152         result ~= rhs;
2153         return result;
2154     }
2155 
2156     /**
2157      * Forwards to `insertBack`.
2158      */
2159     Array!bool opOpAssign(string op, Stuff)(Stuff stuff)
2160     if (op == "~")
2161     {
2162         static if (is(typeof(stuff[]))) insertBack(stuff[]);
2163         else insertBack(stuff);
2164         return this;
2165     }
2166 
2167     /**
2168      * Removes all the elements from the array and releases allocated memory.
2169      *
2170      * Postcondition: `empty == true && capacity == 0`
2171      *
2172      * Complexity: $(BIGOH length)
2173      */
2174     void clear()
2175     {
2176         this = Array();
2177     }
2178 
2179     /**
2180      * Sets the number of elements in the array to `newLength`. If `newLength`
2181      * is greater than `length`, the new elements are added to the end of the
2182      * array and initialized with `false`.
2183      *
2184      * Complexity:
2185      * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`.
2186      * If `capacity < newLength` the worst case is $(BIGOH newLength).
2187      *
2188      * Postcondition: `length == newLength`
2189      */
2190     @property void length(size_t newLength)
2191     {
2192         import std.conv : to;
2193         _store.refCountedStore.ensureInitialized();
2194         auto newDataLength =
2195             to!size_t((newLength + bitsPerWord - 1) / bitsPerWord);
2196         _store._backend.length = newDataLength;
2197         _store._length = newLength;
2198     }
2199 
2200     /**
2201      * Removes the last element from the array and returns it.
2202      * Both stable and non-stable versions behave the same and guarantee
2203      * that ranges iterating over the array are never invalidated.
2204      *
2205      * Precondition: `empty == false`
2206      *
2207      * Returns: The element removed.
2208      *
2209      * Complexity: $(BIGOH 1).
2210      *
2211      * Throws: `Exception` if the array is empty.
2212      */
2213     T removeAny()
2214     {
2215         auto result = back;
2216         removeBack();
2217         return result;
2218     }
2219 
2220     /// ditto
2221     alias stableRemoveAny = removeAny;
2222 
2223     /**
2224      * Inserts the specified elements at the back of the array. `stuff` can be
2225      * a value convertible to `bool` or a range of objects convertible to `bool`.
2226      *
2227      * Returns: The number of elements inserted.
2228      *
2229      * Complexity:
2230      * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m),
2231      * where `m` is the number of elements in `stuff`.
2232      */
2233     size_t insertBack(Stuff)(Stuff stuff)
2234     if (is(Stuff : bool))
2235     {
2236         _store.refCountedStore.ensureInitialized();
2237         auto rem = _store._length % bitsPerWord;
2238         if (rem)
2239         {
2240             // Fits within the current array
2241             if (stuff)
2242             {
2243                 data[$ - 1] |= (cast(size_t) 1 << rem);
2244             }
2245             else
2246             {
2247                 data[$ - 1] &= ~(cast(size_t) 1 << rem);
2248             }
2249         }
2250         else
2251         {
2252             // Need to add more data
2253             _store._backend.insertBack(stuff);
2254         }
2255         ++_store._length;
2256         return 1;
2257     }
2258 
2259     /// ditto
2260     size_t insertBack(Stuff)(Stuff stuff)
2261     if (isInputRange!Stuff && is(ElementType!Stuff : bool))
2262     {
2263         size_t result;
2264         static if (hasLength!Stuff)
2265             result = stuff.length;
2266 
2267         for (; !stuff.empty; stuff.popFront())
2268         {
2269             insertBack(stuff.front);
2270             static if (!hasLength!Stuff) ++result;
2271         }
2272 
2273         return result;
2274     }
2275 
2276     /// ditto
2277     alias stableInsertBack = insertBack;
2278 
2279     /// ditto
2280     alias insert = insertBack;
2281 
2282     /// ditto
2283     alias stableInsert = insertBack;
2284 
2285     /// ditto
2286     alias linearInsert = insertBack;
2287 
2288     /// ditto
2289     alias stableLinearInsert = insertBack;
2290 
2291     /**
2292      * Removes the value from the back of the array. Both stable and non-stable
2293      * versions behave the same and guarantee that ranges iterating over the
2294      * array are never invalidated.
2295      *
2296      * Precondition: `empty == false`
2297      *
2298      * Complexity: $(BIGOH 1).
2299      *
2300      * Throws: `Exception` if the array is empty.
2301      */
2302     void removeBack()
2303     {
2304         enforce(_store._length);
2305         if (_store._length % bitsPerWord)
2306         {
2307             // Cool, just decrease the length
2308             --_store._length;
2309         }
2310         else
2311         {
2312             // Reduce the allocated space
2313             --_store._length;
2314             _store._backend.length = _store._backend.length - 1;
2315         }
2316     }
2317 
2318     /// ditto
2319     alias stableRemoveBack = removeBack;
2320 
2321     /**
2322      * Removes `howMany` values from the back of the array. Unlike the
2323      * unparameterized versions above, these functions do not throw if
2324      * they could not remove `howMany` elements. Instead, if `howMany > n`,
2325      * all elements are removed. The returned value is the effective number
2326      * of elements removed. Both stable and non-stable versions behave the same
2327      * and guarantee that ranges iterating over the array are never invalidated.
2328      *
2329      * Returns: The number of elements removed.
2330      *
2331      * Complexity: $(BIGOH howMany).
2332      */
2333     size_t removeBack(size_t howMany)
2334     {
2335         if (howMany >= length)
2336         {
2337             howMany = length;
2338             clear();
2339         }
2340         else
2341         {
2342             length = length - howMany;
2343         }
2344         return howMany;
2345     }
2346 
2347     /// ditto
2348     alias stableRemoveBack = removeBack;
2349 
2350     /**
2351      * Inserts `stuff` before, after, or instead range `r`, which must
2352      * be a valid range previously extracted from this array. `stuff`
2353      * can be a value convertible to `bool` or a range of objects convertible
2354      * to `bool`. Both stable and non-stable version behave the same and
2355      * guarantee that ranges iterating over the array are never invalidated.
2356      *
2357      * Returns: The number of values inserted.
2358      *
2359      * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`.
2360      */
2361     size_t insertBefore(Stuff)(Range r, Stuff stuff)
2362     {
2363         import std.algorithm.mutation : bringToFront;
2364         // TODO: make this faster, it moves one bit at a time
2365         immutable inserted = stableInsertBack(stuff);
2366         immutable tailLength = length - inserted;
2367         bringToFront(
2368             this[r._a .. tailLength],
2369             this[tailLength .. length]);
2370         return inserted;
2371     }
2372 
2373     /// ditto
2374     alias stableInsertBefore = insertBefore;
2375 
2376     /// ditto
2377     size_t insertAfter(Stuff)(Range r, Stuff stuff)
2378     if (isImplicitlyConvertible!(Stuff, T) ||
2379             isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
2380     {
2381         import std.algorithm.mutation : bringToFront;
2382         // TODO: make this faster, it moves one bit at a time
2383         immutable inserted = stableInsertBack(stuff);
2384         immutable tailLength = length - inserted;
2385         bringToFront(
2386             this[r._b .. tailLength],
2387             this[tailLength .. length]);
2388         return inserted;
2389     }
2390 
2391     /// ditto
2392     alias stableInsertAfter = insertAfter;
2393 
2394     /// ditto
2395     size_t replace(Stuff)(Range r, Stuff stuff)
2396     if (is(Stuff : bool))
2397     {
2398         if (!r.empty)
2399         {
2400             // There is room
2401             r.front = stuff;
2402             r.popFront();
2403             linearRemove(r);
2404         }
2405         else
2406         {
2407             // No room, must insert
2408             insertBefore(r, stuff);
2409         }
2410         return 1;
2411     }
2412 
2413     /// ditto
2414     alias stableReplace = replace;
2415 
2416     /**
2417      * Removes all elements belonging to `r`, which must be a range
2418      * obtained originally from this array.
2419      *
2420      * Returns: A range spanning the remaining elements in the array that
2421      * initially were right after `r`.
2422      *
2423      * Complexity: $(BIGOH length)
2424      */
2425     Range linearRemove(Range r)
2426     {
2427         import std.algorithm.mutation : copy;
2428         copy(this[r._b .. length], this[r._a .. length]);
2429         length = length - r.length;
2430         return this[r._a .. length];
2431     }
2432 }
2433 
2434 @system unittest
2435 {
2436     import std.algorithm.comparison : equal;
2437 
2438     auto a = Array!bool([true, true, false, false, true, false]);
2439     assert(equal(a[], [true, true, false, false, true, false]));
2440 }
2441 
2442 // using Ranges
2443 @system unittest
2444 {
2445     import std.algorithm.comparison : equal;
2446     import std.range : retro;
2447     bool[] arr = [true, true, false, false, true, false];
2448 
2449     auto a = Array!bool(retro(arr));
2450     assert(equal(a[], retro(arr)));
2451 }
2452 
2453 @system unittest
2454 {
2455     Array!bool a;
2456     assert(a.empty);
2457 }
2458 
2459 @system unittest
2460 {
2461     auto arr = Array!bool([false, false, false, false]);
2462     assert(arr.front == false);
2463     assert(arr.back == false);
2464     assert(arr[1] == false);
2465     auto slice = arr[];
2466     slice = arr[0 .. $];
2467     slice = slice[1 .. $];
2468     slice.front = true;
2469     slice.back = true;
2470     slice[1] = true;
2471     slice = slice[0 .. $]; // https://issues.dlang.org/show_bug.cgi?id=19171
2472     assert(slice.front == true);
2473     assert(slice.back == true);
2474     assert(slice[1] == true);
2475     assert(slice.moveFront == true);
2476     assert(slice.moveBack == true);
2477     assert(slice.moveAt(1) == true);
2478 }
2479 
2480 // uncomparable values are valid values for an array
2481 // https://issues.dlang.org/show_bug.cgi?id=16331
2482 @system unittest
2483 {
2484     double[] values = [double.nan, double.nan];
2485     auto arr = Array!double(values);
2486 }
2487 
2488 @nogc @system unittest
2489 {
2490     auto a = Array!int(0, 1, 2);
2491     int[3] b = [3, 4, 5];
2492     short[3] ci = [0, 1, 0];
2493     auto c = Array!short(ci);
2494     assert(Array!int(0, 1, 2, 0, 1, 2) == a ~ a);
2495     assert(Array!int(0, 1, 2, 3, 4, 5) == a ~ b);
2496     assert(Array!int(0, 1, 2, 3) == a ~ 3);
2497     assert(Array!int(0, 1, 2, 0, 1, 0) == a ~ c);
2498 }
2499 
2500 @nogc @system unittest
2501 {
2502     auto a = Array!char('a', 'b');
2503     assert(Array!char("abc") == a ~ 'c');
2504     import std.utf : byCodeUnit;
2505     assert(Array!char("abcd") == a ~ "cd".byCodeUnit);
2506 }
2507 
2508 @nogc @system unittest
2509 {
2510     auto a = Array!dchar("ąćę"d);
2511     assert(Array!dchar("ąćęϢϖ"d) == a ~ "Ϣϖ"d);
2512     wchar x = 'Ϣ';
2513     assert(Array!dchar("ąćęϢz"d) == a ~ x ~ 'z');
2514 }
2515 
2516 @system unittest
2517 {
2518     Array!bool a;
2519     assert(a.empty);
2520     a.insertBack(false);
2521     assert(!a.empty);
2522 }
2523 
2524 @system unittest
2525 {
2526     Array!bool a;
2527     assert(a.empty);
2528     auto b = a.dup;
2529     assert(b.empty);
2530     a.insertBack(true);
2531     assert(b.empty);
2532 }
2533 
2534 @system unittest
2535 {
2536     import std.conv : to;
2537     Array!bool a;
2538     assert(a.length == 0);
2539     a.insert(true);
2540     assert(a.length == 1, to!string(a.length));
2541 }
2542 
2543 @system unittest
2544 {
2545     import std.conv : to;
2546     Array!bool a;
2547     assert(a.capacity == 0);
2548     foreach (i; 0 .. 100)
2549     {
2550         a.insert(true);
2551         assert(a.capacity >= a.length, to!string(a.capacity));
2552     }
2553 }
2554 
2555 @system unittest
2556 {
2557     Array!bool a;
2558     assert(a.capacity == 0);
2559     a.reserve(15657);
2560     assert(a.capacity >= 15657);
2561     a.reserve(100);
2562     assert(a.capacity >= 15657);
2563 }
2564 
2565 @system unittest
2566 {
2567     auto a = Array!bool([true, false, true, true]);
2568     assert(a[0 .. 2].length == 2);
2569 }
2570 
2571 @system unittest
2572 {
2573     auto a = Array!bool([true, false, true, true]);
2574     assert(a[].length == 4);
2575 }
2576 
2577 @system unittest
2578 {
2579     auto a = Array!bool([true, false, true, true]);
2580     assert(a.front);
2581     a.front = false;
2582     assert(!a.front);
2583 }
2584 
2585 @system unittest
2586 {
2587     auto a = Array!bool([true, false, true, true]);
2588     assert(a[].length == 4);
2589 }
2590 
2591 @system unittest
2592 {
2593     auto a = Array!bool([true, false, true, true]);
2594     assert(a.back);
2595     a.back = false;
2596     assert(!a.back);
2597 }
2598 
2599 @system unittest
2600 {
2601     auto a = Array!bool([true, false, true, true]);
2602     assert(a[0] && !a[1]);
2603     a[0] &= a[1];
2604     assert(!a[0]);
2605 }
2606 
2607 @system unittest
2608 {
2609     import std.algorithm.comparison : equal;
2610     auto a = Array!bool([true, false, true, true]);
2611     auto b = Array!bool([true, true, false, true]);
2612     assert(equal((a ~ b)[],
2613                     [true, false, true, true, true, true, false, true]));
2614     assert((a ~ [true, false])[].equal([true, false, true, true, true, false]));
2615     Array!bool c;
2616     c.insertBack(true);
2617     assert((c ~ false)[].equal([true, false]));
2618 }
2619 @system unittest
2620 {
2621     import std.algorithm.comparison : equal;
2622     auto a = Array!bool([true, false, true, true]);
2623     auto b = Array!bool([false, true, false, true, true]);
2624     a ~= b;
2625     assert(equal(
2626                 a[],
2627                 [true, false, true, true, false, true, false, true, true]));
2628 }
2629 
2630 @system unittest
2631 {
2632     auto a = Array!bool([true, false, true, true]);
2633     a.clear();
2634     assert(a.capacity == 0);
2635 }
2636 
2637 @system unittest
2638 {
2639     Array!bool a;
2640     a.length = 1057;
2641     assert(a.length == 1057);
2642     assert(a.capacity >= a.length);
2643     foreach (e; a)
2644     {
2645         assert(!e);
2646     }
2647     immutable cap = a.capacity;
2648     a.length = 100;
2649     assert(a.length == 100);
2650     // do not realloc if length decreases
2651     assert(a.capacity == cap);
2652 }
2653 
2654 @system unittest
2655 {
2656     Array!bool a;
2657     a.length = 1057;
2658     assert(!a.removeAny());
2659     assert(a.length == 1056);
2660     foreach (e; a)
2661     {
2662         assert(!e);
2663     }
2664 }
2665 
2666 @system unittest
2667 {
2668     Array!bool a;
2669     for (int i = 0; i < 100; ++i)
2670         a.insertBack(true);
2671     foreach (e; a)
2672         assert(e);
2673 }
2674 
2675 @system unittest
2676 {
2677     Array!bool a;
2678     a.length = 1057;
2679     assert(a.removeBack(1000) == 1000);
2680     assert(a.length == 57);
2681     foreach (e; a)
2682     {
2683         assert(!e);
2684     }
2685 }
2686 
2687 @system unittest
2688 {
2689     import std.conv : to;
2690     Array!bool a;
2691     version (bugxxxx)
2692     {
2693         a._store.refCountedDebug = true;
2694     }
2695     a.insertBefore(a[], true);
2696     assert(a.length == 1, to!string(a.length));
2697     a.insertBefore(a[], false);
2698     assert(a.length == 2, to!string(a.length));
2699     a.insertBefore(a[1 .. $], true);
2700     import std.algorithm.comparison : equal;
2701     assert(a[].equal([false, true, true]));
2702 }
2703 
2704 // https://issues.dlang.org/show_bug.cgi?id=21555
2705 @system unittest
2706 {
2707     import std.algorithm.comparison : equal;
2708     Array!bool arr;
2709     size_t len = arr.insertBack([false, true]);
2710     assert(len == 2);
2711 }
2712 
2713 // https://issues.dlang.org/show_bug.cgi?id=21556
2714 @system unittest
2715 {
2716     import std.algorithm.comparison : equal;
2717     Array!bool a;
2718     a.insertBack([true, true, false, false, true]);
2719     assert(a.length == 5);
2720 
2721     assert(a.insertAfter(a[0 .. 5], [false, false]) == 2);
2722     assert(equal(a[], [true, true, false, false, true, false, false]));
2723 
2724     assert(a.insertAfter(a[0 .. 5], true) == 1);
2725     assert(equal(a[], [true, true, false, false, true, true, false, false]));
2726 }
2727 
2728 @system unittest
2729 {
2730     import std.conv : to;
2731     Array!bool a;
2732     a.length = 10;
2733     a.insertAfter(a[0 .. 5], true);
2734     assert(a.length == 11, to!string(a.length));
2735     assert(a[5]);
2736 }
2737 @system unittest
2738 {
2739     alias V3 = int[3];
2740     V3 v = [1, 2, 3];
2741     Array!V3 arr;
2742     arr ~= v;
2743     assert(arr[0] == [1, 2, 3]);
2744 }
2745 @system unittest
2746 {
2747     alias V3 = int[3];
2748     V3[2] v = [[1, 2, 3], [4, 5, 6]];
2749     Array!V3 arr;
2750     arr ~= v;
2751     assert(arr[0] == [1, 2, 3]);
2752     assert(arr[1] == [4, 5, 6]);
2753 }
2754 
2755 // Change of length reallocates without calling GC.
2756 // https://issues.dlang.org/show_bug.cgi?id=13642
2757 @system unittest
2758 {
2759     import core.memory;
2760     class ABC { void func() { int x = 5; } }
2761 
2762     Array!ABC arr;
2763     // Length only allocates if capacity is too low.
2764     arr.reserve(4);
2765     assert(arr.capacity == 4);
2766 
2767     void func() @nogc
2768     {
2769         arr.length = 5;
2770     }
2771     func();
2772 
2773     foreach (ref b; arr) b = new ABC;
2774     GC.collect();
2775     arr[1].func();
2776 }
2777 
2778 @system unittest
2779 {
2780 
2781     Array!int arr = [1, 2, 4, 5];
2782     int[] data = arr.data();
2783 
2784     const Array!int arr2 = [8, 9];
2785     assert(arr2.data() == [8, 9]);
2786 
2787     data[0] = 0;
2788     assert(arr[0] == 0);
2789 
2790     arr.length = 0;
2791     assert(arr.data == []);
2792 
2793     Array!int empty;
2794     assert(empty.data == []);
2795 }