"Fossies" - the Fresh Open Source Software Archive

Member "dmd2/src/phobos/std/container/array.d" (20 Nov 2020, 66676 Bytes) of package /linux/misc/dmd.2.094.2.linux.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) D source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

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