diff options
Diffstat (limited to 'libphobos/src/std/container/array.d')
| -rw-r--r-- | libphobos/src/std/container/array.d | 2419 |
1 files changed, 2419 insertions, 0 deletions
diff --git a/libphobos/src/std/container/array.d b/libphobos/src/std/container/array.d new file mode 100644 index 0000000..eee8901 --- /dev/null +++ b/libphobos/src/std/container/array.d @@ -0,0 +1,2419 @@ +/** + * This module provides an `Array` type with deterministic memory usage not + * reliant on the GC, as an alternative to the built-in arrays. + * + * This module is a submodule of $(MREF std, container). + * + * Source: $(PHOBOSSRC std/container/_array.d) + * + * Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. + * + * License: Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at $(HTTP + * boost.org/LICENSE_1_0.txt)). + * + * Authors: $(HTTP erdani.com, Andrei Alexandrescu) + * + * $(SCRIPT inhibitQuickIndex = 1;) + */ +module std.container.array; + +import core.exception : RangeError; +import std.range.primitives; +import std.traits; + +public import std.container.util; + +/// +@system unittest +{ + auto arr = Array!int(0, 2, 3); + assert(arr[0] == 0); + assert(arr.front == 0); + assert(arr.back == 3); + + // reserve space + arr.reserve(1000); + assert(arr.length == 3); + assert(arr.capacity >= 1000); + + // insertion + arr.insertBefore(arr[1..$], 1); + assert(arr.front == 0); + assert(arr.length == 4); + + arr.insertBack(4); + assert(arr.back == 4); + assert(arr.length == 5); + + // set elements + arr[1] *= 42; + assert(arr[1] == 42); +} + +/// +@system unittest +{ + import std.algorithm.comparison : equal; + auto arr = Array!int(1, 2, 3); + + // concat + auto b = Array!int(11, 12, 13); + arr ~= b; + assert(arr.length == 6); + + // slicing + assert(arr[1 .. 3].equal([2, 3])); + + // remove + arr.linearRemove(arr[1 .. 3]); + assert(arr[0 .. 2].equal([1, 11])); +} + +/// `Array!bool` packs together values efficiently by allocating one bit per element +@system unittest +{ + Array!bool arr; + arr.insert([true, true, false, true, false]); + assert(arr.length == 5); +} + +private struct RangeT(A) +{ + /* Workaround for Issue 13629 at https://issues.dlang.org/show_bug.cgi?id=13629 + See also: http://forum.dlang.org/post/vbmwhzvawhnkoxrhbnyb@forum.dlang.org + */ + private A[1] _outer_; + private @property ref inout(A) _outer() inout { return _outer_[0]; } + + private size_t _a, _b; + + /* E is different from T when A is more restrictively qualified than T: + immutable(Array!int) => T == int, E = immutable(int) */ + alias E = typeof(_outer_[0]._data._payload[0]); + + private this(ref A data, size_t a, size_t b) + { + _outer_ = data; + _a = a; + _b = b; + } + + @property RangeT save() + { + return this; + } + + @property bool empty() @safe pure nothrow const + { + return _a >= _b; + } + + @property size_t length() @safe pure nothrow const + { + return _b - _a; + } + alias opDollar = length; + + @property ref inout(E) front() inout + { + assert(!empty, "Attempting to access the front of an empty Array"); + return _outer[_a]; + } + @property ref inout(E) back() inout + { + assert(!empty, "Attempting to access the back of an empty Array"); + return _outer[_b - 1]; + } + + void popFront() @safe @nogc pure nothrow + { + assert(!empty, "Attempting to popFront an empty Array"); + ++_a; + } + + void popBack() @safe @nogc pure nothrow + { + assert(!empty, "Attempting to popBack an empty Array"); + --_b; + } + + static if (isMutable!A) + { + import std.algorithm.mutation : move; + + E moveFront() + { + assert(!empty && _a < _outer.length); + return move(_outer._data._payload[_a]); + } + + E moveBack() + { + assert(!empty && _b <= _outer.length); + return move(_outer._data._payload[_b - 1]); + } + + E moveAt(size_t i) + { + assert(_a + i < _b && _a + i < _outer.length); + return move(_outer._data._payload[_a + i]); + } + } + + ref inout(E) opIndex(size_t i) inout + { + assert(_a + i < _b); + return _outer[_a + i]; + } + + RangeT opSlice() + { + return typeof(return)(_outer, _a, _b); + } + + RangeT opSlice(size_t i, size_t j) + { + assert(i <= j && _a + j <= _b); + return typeof(return)(_outer, _a + i, _a + j); + } + + RangeT!(const(A)) opSlice() const + { + return typeof(return)(_outer, _a, _b); + } + + RangeT!(const(A)) opSlice(size_t i, size_t j) const + { + assert(i <= j && _a + j <= _b); + return typeof(return)(_outer, _a + i, _a + j); + } + + static if (isMutable!A) + { + void opSliceAssign(E value) + { + assert(_b <= _outer.length); + _outer[_a .. _b] = value; + } + + void opSliceAssign(E value, size_t i, size_t j) + { + assert(_a + j <= _b); + _outer[_a + i .. _a + j] = value; + } + + void opSliceUnary(string op)() + if (op == "++" || op == "--") + { + assert(_b <= _outer.length); + mixin(op~"_outer[_a .. _b];"); + } + + void opSliceUnary(string op)(size_t i, size_t j) + if (op == "++" || op == "--") + { + assert(_a + j <= _b); + mixin(op~"_outer[_a + i .. _a + j];"); + } + + void opSliceOpAssign(string op)(E value) + { + assert(_b <= _outer.length); + mixin("_outer[_a .. _b] "~op~"= value;"); + } + + void opSliceOpAssign(string op)(E value, size_t i, size_t j) + { + assert(_a + j <= _b); + mixin("_outer[_a + i .. _a + j] "~op~"= value;"); + } + } +} + +/** + * _Array type with deterministic control of memory. The memory allocated + * for the array is reclaimed as soon as possible; there is no reliance + * on the garbage collector. `Array` uses `malloc`, `realloc` and `free` + * for managing its own memory. + * + * This means that pointers to elements of an `Array` will become + * dangling as soon as the element is removed from the `Array`. On the other hand + * the memory allocated by an `Array` will be scanned by the GC and + * GC managed objects referenced from an `Array` will be kept alive. + * + * Note: + * + * When using `Array` with range-based functions like those in `std.algorithm`, + * `Array` must be sliced to get a range (for example, use `array[].map!` + * instead of `array.map!`). The container itself is not a range. + */ +struct Array(T) +if (!is(Unqual!T == bool)) +{ + import core.stdc.stdlib : malloc, realloc, free; + import core.stdc.string : memcpy, memmove, memset; + + import core.memory : GC; + + import std.exception : enforce; + import std.typecons : RefCounted, RefCountedAutoInitialize; + + // This structure is not copyable. + private struct Payload + { + size_t _capacity; + T[] _payload; + + this(T[] p) { _capacity = p.length; _payload = p; } + + // Destructor releases array memory + ~this() + { + // Warning: destroy would destroy also class instances. + // The hasElaborateDestructor protects us here. + static if (hasElaborateDestructor!T) + foreach (ref e; _payload) + .destroy(e); + + static if (hasIndirections!T) + GC.removeRange(_payload.ptr); + + free(_payload.ptr); + } + + this(this) @disable; + + void opAssign(Payload rhs) @disable; + + @property size_t length() const + { + return _payload.length; + } + + @property void length(size_t newLength) + { + import std.algorithm.mutation : initializeAll; + + if (length >= newLength) + { + // shorten + static if (hasElaborateDestructor!T) + foreach (ref e; _payload.ptr[newLength .. _payload.length]) + .destroy(e); + + _payload = _payload.ptr[0 .. newLength]; + return; + } + immutable startEmplace = length; + if (_capacity < newLength) + { + // enlarge + import core.checkedint : mulu; + + bool overflow; + const nbytes = mulu(newLength, T.sizeof, overflow); + if (overflow) + assert(0); + _payload = (cast(T*) realloc(_payload.ptr, nbytes))[0 .. newLength]; + _capacity = newLength; + } + else + { + _payload = _payload.ptr[0 .. newLength]; + } + initializeAll(_payload.ptr[startEmplace .. newLength]); + } + + @property size_t capacity() const + { + return _capacity; + } + + void reserve(size_t elements) + { + if (elements <= capacity) return; + import core.checkedint : mulu; + bool overflow; + const sz = mulu(elements, T.sizeof, overflow); + if (overflow) + assert(0); + static if (hasIndirections!T) + { + /* Because of the transactional nature of this + * relative to the garbage collector, ensure no + * threading bugs by using malloc/copy/free rather + * than realloc. + */ + immutable oldLength = length; + + auto newPayloadPtr = cast(T*) malloc(sz); + newPayloadPtr || assert(false, "std.container.Array.reserve failed to allocate memory"); + auto newPayload = newPayloadPtr[0 .. oldLength]; + + // copy old data over to new array + memcpy(newPayload.ptr, _payload.ptr, T.sizeof * oldLength); + // Zero out unused capacity to prevent gc from seeing false pointers + memset(newPayload.ptr + oldLength, + 0, + (elements - oldLength) * T.sizeof); + GC.addRange(newPayload.ptr, sz); + GC.removeRange(_payload.ptr); + free(_payload.ptr); + _payload = newPayload; + } + else + { + // These can't have pointers, so no need to zero unused region + auto newPayloadPtr = cast(T*) realloc(_payload.ptr, sz); + newPayloadPtr || assert(false, "std.container.Array.reserve failed to allocate memory"); + auto newPayload = newPayloadPtr[0 .. length]; + _payload = newPayload; + } + _capacity = elements; + } + + // Insert one item + size_t insertBack(Elem)(Elem elem) + if (isImplicitlyConvertible!(Elem, T)) + { + import std.conv : emplace; + if (_capacity == length) + { + reserve(1 + capacity * 3 / 2); + } + assert(capacity > length && _payload.ptr); + emplace(_payload.ptr + _payload.length, elem); + _payload = _payload.ptr[0 .. _payload.length + 1]; + return 1; + } + + // Insert a range of items + size_t insertBack(Range)(Range r) + if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T)) + { + static if (hasLength!Range) + { + immutable oldLength = length; + reserve(oldLength + r.length); + } + size_t result; + foreach (item; r) + { + insertBack(item); + ++result; + } + static if (hasLength!Range) + { + assert(length == oldLength + r.length); + } + return result; + } + } + private alias Data = RefCounted!(Payload, RefCountedAutoInitialize.no); + private Data _data; + + /** + * Constructor taking a number of items. + */ + this(U)(U[] values...) + if (isImplicitlyConvertible!(U, T)) + { + import core.checkedint : mulu; + import std.conv : emplace; + bool overflow; + const nbytes = mulu(values.length, T.sizeof, overflow); + if (overflow) assert(0); + auto p = cast(T*) malloc(nbytes); + static if (hasIndirections!T) + { + if (p) + GC.addRange(p, T.sizeof * values.length); + } + + foreach (i, e; values) + { + emplace(p + i, e); + } + _data = Data(p[0 .. values.length]); + } + + /** + * Constructor taking an input range + */ + this(Range)(Range r) + if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[])) + { + insertBack(r); + } + + /** + * Comparison for equality. + */ + bool opEquals(const Array rhs) const + { + return opEquals(rhs); + } + + /// ditto + bool opEquals(ref const Array rhs) const + { + if (empty) return rhs.empty; + if (rhs.empty) return false; + return _data._payload == rhs._data._payload; + } + + /** + * Defines the array's primary range, which is a random-access range. + * + * `ConstRange` is a variant with `const` elements. + * `ImmutableRange` is a variant with `immutable` elements. + */ + alias Range = RangeT!Array; + + /// ditto + alias ConstRange = RangeT!(const Array); + + /// ditto + alias ImmutableRange = RangeT!(immutable Array); + + /** + * Duplicates the array. The elements themselves are not transitively + * duplicated. + * + * Complexity: $(BIGOH length). + */ + @property Array dup() + { + if (!_data.refCountedStore.isInitialized) return this; + return Array(_data._payload); + } + + /** + * Returns: `true` if and only if the array has no elements. + * + * Complexity: $(BIGOH 1) + */ + @property bool empty() const + { + return !_data.refCountedStore.isInitialized || _data._payload.empty; + } + + /** + * Returns: The number of elements in the array. + * + * Complexity: $(BIGOH 1). + */ + @property size_t length() const + { + return _data.refCountedStore.isInitialized ? _data._payload.length : 0; + } + + /// ditto + size_t opDollar() const + { + return length; + } + + /** + * Returns: The maximum number of elements the array can store without + * reallocating memory and invalidating iterators upon insertion. + * + * Complexity: $(BIGOH 1) + */ + @property size_t capacity() + { + return _data.refCountedStore.isInitialized ? _data._capacity : 0; + } + + /** + * Ensures sufficient capacity to accommodate `e` _elements. + * If `e < capacity`, this method does nothing. + * + * Postcondition: `capacity >= e` + * + * Note: If the capacity is increased, one should assume that all + * iterators to the elements are invalidated. + * + * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1). + */ + void reserve(size_t elements) + { + if (!_data.refCountedStore.isInitialized) + { + if (!elements) return; + import core.checkedint : mulu; + bool overflow; + const sz = mulu(elements, T.sizeof, overflow); + if (overflow) assert(0); + auto p = malloc(sz); + p || assert(false, "std.container.Array.reserve failed to allocate memory"); + static if (hasIndirections!T) + { + GC.addRange(p, sz); + } + _data = Data(cast(T[]) p[0 .. 0]); + _data._capacity = elements; + } + else + { + _data.reserve(elements); + } + } + + /** + * Returns: A range that iterates over elements of the array in + * forward order. + * + * Complexity: $(BIGOH 1) + */ + Range opSlice() + { + return typeof(return)(this, 0, length); + } + + ConstRange opSlice() const + { + return typeof(return)(this, 0, length); + } + + ImmutableRange opSlice() immutable + { + return typeof(return)(this, 0, length); + } + + /** + * Returns: A range that iterates over elements of the array from + * index `i` up to (excluding) index `j`. + * + * Precondition: `i <= j && j <= length` + * + * Complexity: $(BIGOH 1) + */ + Range opSlice(size_t i, size_t j) + { + assert(i <= j && j <= length); + return typeof(return)(this, i, j); + } + + ConstRange opSlice(size_t i, size_t j) const + { + assert(i <= j && j <= length); + return typeof(return)(this, i, j); + } + + ImmutableRange opSlice(size_t i, size_t j) immutable + { + assert(i <= j && j <= length); + return typeof(return)(this, i, j); + } + + /** + * Returns: The first element of the array. + * + * Precondition: `empty == false` + * + * Complexity: $(BIGOH 1) + */ + @property ref inout(T) front() inout + { + assert(_data.refCountedStore.isInitialized); + return _data._payload[0]; + } + + /** + * Returns: The last element of the array. + * + * Precondition: `empty == false` + * + * Complexity: $(BIGOH 1) + */ + @property ref inout(T) back() inout + { + assert(_data.refCountedStore.isInitialized); + return _data._payload[$ - 1]; + } + + /** + * Returns: The element or a reference to the element at the specified index. + * + * Precondition: `i < length` + * + * Complexity: $(BIGOH 1) + */ + ref inout(T) opIndex(size_t i) inout + { + assert(_data.refCountedStore.isInitialized); + return _data._payload[i]; + } + + /** + * Slicing operators executing the specified operation on the entire slice. + * + * Precondition: `i < j && j < length` + * + * Complexity: $(BIGOH slice.length) + */ + void opSliceAssign(T value) + { + if (!_data.refCountedStore.isInitialized) return; + _data._payload[] = value; + } + + /// ditto + void opSliceAssign(T value, size_t i, size_t j) + { + auto slice = _data.refCountedStore.isInitialized ? + _data._payload : + T[].init; + slice[i .. j] = value; + } + + /// ditto + void opSliceUnary(string op)() + if (op == "++" || op == "--") + { + if (!_data.refCountedStore.isInitialized) return; + mixin(op~"_data._payload[];"); + } + + /// ditto + void opSliceUnary(string op)(size_t i, size_t j) + if (op == "++" || op == "--") + { + auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init; + mixin(op~"slice[i .. j];"); + } + + /// ditto + void opSliceOpAssign(string op)(T value) + { + if (!_data.refCountedStore.isInitialized) return; + mixin("_data._payload[] "~op~"= value;"); + } + + /// ditto + void opSliceOpAssign(string op)(T value, size_t i, size_t j) + { + auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init; + mixin("slice[i .. j] "~op~"= value;"); + } + + private enum hasSliceWithLength(T) = is(typeof({ T t = T.init; t[].length; })); + + /** + * Returns: A new array which is a concatenation of `this` and its argument. + * + * Complexity: + * $(BIGOH length + m), where `m` is the number of elements in `stuff`. + */ + Array opBinary(string op, Stuff)(Stuff stuff) + if (op == "~") + { + Array result; + + static if (hasLength!Stuff || isNarrowString!Stuff) + result.reserve(length + stuff.length); + else static if (hasSliceWithLength!Stuff) + result.reserve(length + stuff[].length); + else static if (isImplicitlyConvertible!(Stuff, T)) + result.reserve(length + 1); + + result.insertBack(this[]); + result ~= stuff; + return result; + } + + /** + * Forwards to `insertBack`. + */ + void opOpAssign(string op, Stuff)(auto ref Stuff stuff) + if (op == "~") + { + static if (is(typeof(stuff[])) && isImplicitlyConvertible!(typeof(stuff[0]), T)) + { + insertBack(stuff[]); + } + else + { + insertBack(stuff); + } + } + + /** + * Removes all the elements from the array and releases allocated memory. + * + * Postcondition: `empty == true && capacity == 0` + * + * Complexity: $(BIGOH length) + */ + void clear() + { + _data = Data.init; + } + + /** + * Sets the number of elements in the array to `newLength`. If `newLength` + * is greater than `length`, the new elements are added to the end of the + * array and initialized with `T.init`. + * + * Complexity: + * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`. + * If `capacity < newLength` the worst case is $(BIGOH newLength). + * + * Postcondition: `length == newLength` + */ + @property void length(size_t newLength) + { + _data.refCountedStore.ensureInitialized(); + _data.length = newLength; + } + + /** + * Removes the last element from the array and returns it. + * Both stable and non-stable versions behave the same and guarantee + * that ranges iterating over the array are never invalidated. + * + * Precondition: `empty == false` + * + * Returns: The element removed. + * + * Complexity: $(BIGOH 1). + * + * Throws: `Exception` if the array is empty. + */ + T removeAny() + { + auto result = back; + removeBack(); + return result; + } + + /// ditto + alias stableRemoveAny = removeAny; + + /** + * Inserts the specified elements at the back of the array. `stuff` can be + * a value convertible to `T` or a range of objects convertible to `T`. + * + * Returns: The number of elements inserted. + * + * Complexity: + * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m), + * where `m` is the number of elements in `stuff`. + */ + size_t insertBack(Stuff)(Stuff stuff) + if (isImplicitlyConvertible!(Stuff, T) || + isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) + { + _data.refCountedStore.ensureInitialized(); + return _data.insertBack(stuff); + } + + /// ditto + alias insert = insertBack; + + /** + * Removes the value from the back of the array. Both stable and non-stable + * versions behave the same and guarantee that ranges iterating over the + * array are never invalidated. + * + * Precondition: `empty == false` + * + * Complexity: $(BIGOH 1). + * + * Throws: `Exception` if the array is empty. + */ + void removeBack() + { + enforce(!empty); + static if (hasElaborateDestructor!T) + .destroy(_data._payload[$ - 1]); + + _data._payload = _data._payload[0 .. $ - 1]; + } + + /// ditto + alias stableRemoveBack = removeBack; + + /** + * Removes `howMany` values from the back of the array. + * Unlike the unparameterized versions above, these functions + * do not throw if they could not remove `howMany` elements. Instead, + * if `howMany > n`, all elements are removed. The returned value is + * the effective number of elements removed. Both stable and non-stable + * versions behave the same and guarantee that ranges iterating over + * the array are never invalidated. + * + * Returns: The number of elements removed. + * + * Complexity: $(BIGOH howMany). + */ + size_t removeBack(size_t howMany) + { + if (howMany > length) howMany = length; + static if (hasElaborateDestructor!T) + foreach (ref e; _data._payload[$ - howMany .. $]) + .destroy(e); + + _data._payload = _data._payload[0 .. $ - howMany]; + return howMany; + } + + /// ditto + alias stableRemoveBack = removeBack; + + /** + * Inserts `stuff` before, after, or instead range `r`, which must + * be a valid range previously extracted from this array. `stuff` + * can be a value convertible to `T` or a range of objects convertible + * to `T`. Both stable and non-stable version behave the same and + * guarantee that ranges iterating over the array are never invalidated. + * + * Returns: The number of values inserted. + * + * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`. + * + * Throws: `Exception` if `r` is not a range extracted from this array. + */ + size_t insertBefore(Stuff)(Range r, Stuff stuff) + if (isImplicitlyConvertible!(Stuff, T)) + { + import std.conv : emplace; + enforce(r._outer._data is _data && r._a <= length); + reserve(length + 1); + assert(_data.refCountedStore.isInitialized); + // Move elements over by one slot + memmove(_data._payload.ptr + r._a + 1, + _data._payload.ptr + r._a, + T.sizeof * (length - r._a)); + emplace(_data._payload.ptr + r._a, stuff); + _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1]; + return 1; + } + + /// ditto + size_t insertBefore(Stuff)(Range r, Stuff stuff) + if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) + { + import std.conv : emplace; + enforce(r._outer._data is _data && r._a <= length); + static if (isForwardRange!Stuff) + { + // Can find the length in advance + auto extra = walkLength(stuff); + if (!extra) return 0; + reserve(length + extra); + assert(_data.refCountedStore.isInitialized); + // Move elements over by extra slots + memmove(_data._payload.ptr + r._a + extra, + _data._payload.ptr + r._a, + T.sizeof * (length - r._a)); + foreach (p; _data._payload.ptr + r._a .. + _data._payload.ptr + r._a + extra) + { + emplace(p, stuff.front); + stuff.popFront(); + } + _data._payload = + _data._payload.ptr[0 .. _data._payload.length + extra]; + return extra; + } + else + { + import std.algorithm.mutation : bringToFront; + enforce(_data); + immutable offset = r._a; + enforce(offset <= length); + auto result = insertBack(stuff); + bringToFront(this[offset .. length - result], + this[length - result .. length]); + return result; + } + } + + /// ditto + alias stableInsertBefore = insertBefore; + + /// ditto + size_t insertAfter(Stuff)(Range r, Stuff stuff) + { + import std.algorithm.mutation : bringToFront; + enforce(r._outer._data is _data); + // TODO: optimize + immutable offset = r._b; + enforce(offset <= length); + auto result = insertBack(stuff); + bringToFront(this[offset .. length - result], + this[length - result .. length]); + return result; + } + + /// ditto + size_t replace(Stuff)(Range r, Stuff stuff) + if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) + { + enforce(r._outer._data is _data); + size_t result; + for (; !stuff.empty; stuff.popFront()) + { + if (r.empty) + { + // insert the rest + return result + insertBefore(r, stuff); + } + r.front = stuff.front; + r.popFront(); + ++result; + } + // Remove remaining stuff in r + linearRemove(r); + return result; + } + + /// ditto + size_t replace(Stuff)(Range r, Stuff stuff) + if (isImplicitlyConvertible!(Stuff, T)) + { + enforce(r._outer._data is _data); + if (r.empty) + { + insertBefore(r, stuff); + } + else + { + r.front = stuff; + r.popFront(); + linearRemove(r); + } + return 1; + } + + /** + * Removes all elements belonging to `r`, which must be a range + * obtained originally from this array. + * + * Returns: A range spanning the remaining elements in the array that + * initially were right after `r`. + * + * Complexity: $(BIGOH length) + * + * Throws: `Exception` if `r` is not a valid range extracted from this array. + */ + Range linearRemove(Range r) + { + import std.algorithm.mutation : copy; + + enforce(r._outer._data is _data); + enforce(_data.refCountedStore.isInitialized); + enforce(r._a <= r._b && r._b <= length); + immutable offset1 = r._a; + immutable offset2 = r._b; + immutable tailLength = length - offset2; + // Use copy here, not a[] = b[] because the ranges may overlap + copy(this[offset2 .. length], this[offset1 .. offset1 + tailLength]); + length = offset1 + tailLength; + return this[length - tailLength .. length]; + } +} + +@system unittest +{ + Array!int a; + assert(a.empty); +} + +@system unittest +{ + Array!int a; + a.length = 10; + assert(a.length == 10); + assert(a.capacity >= a.length); +} + +@system unittest +{ + struct Dumb { int x = 5; } + Array!Dumb a; + a.length = 10; + assert(a.length == 10); + assert(a.capacity >= a.length); + immutable cap = a.capacity; + foreach (ref e; a) + e.x = 10; + a.length = 5; + assert(a.length == 5); + // do not realloc if length decreases + assert(a.capacity == cap); + foreach (ref e; a) + assert(e.x == 10); + + a.length = 8; + assert(a.length == 8); + // do not realloc if capacity sufficient + assert(a.capacity == cap); + assert(Dumb.init.x == 5); + foreach (i; 0 .. 5) + assert(a[i].x == 10); + foreach (i; 5 .. a.length) + assert(a[i].x == Dumb.init.x); + + // realloc required, check if values properly copied + a[] = Dumb(1); + a.length = 20; + assert(a.capacity >= 20); + foreach (i; 0 .. 8) + assert(a[i].x == 1); + foreach (i; 8 .. a.length) + assert(a[i].x == Dumb.init.x); + + // check if overlapping elements properly initialized + a.length = 1; + a.length = 20; + assert(a[0].x == 1); + foreach (e; a[1 .. $]) + assert(e.x == Dumb.init.x); +} + +@system unittest +{ + Array!int a = Array!int(1, 2, 3); + //a._data._refCountedDebug = true; + auto b = a.dup; + assert(b == Array!int(1, 2, 3)); + b.front = 42; + assert(b == Array!int(42, 2, 3)); + assert(a == Array!int(1, 2, 3)); +} + +@system unittest +{ + auto a = Array!int(1, 2, 3); + assert(a.length == 3); +} + +@system unittest +{ + const Array!int a = [1, 2]; + + assert(a[0] == 1); + assert(a.front == 1); + assert(a.back == 2); + + static assert(!__traits(compiles, { a[0] = 1; })); + static assert(!__traits(compiles, { a.front = 1; })); + static assert(!__traits(compiles, { a.back = 1; })); + + auto r = a[]; + size_t i; + foreach (e; r) + { + assert(e == i + 1); + i++; + } +} + +@safe unittest +{ + // REG https://issues.dlang.org/show_bug.cgi?id=13621 + import std.container : Array, BinaryHeap; + alias Heap = BinaryHeap!(Array!int); +} + +@system unittest +{ + Array!int a; + a.reserve(1000); + assert(a.length == 0); + assert(a.empty); + assert(a.capacity >= 1000); + auto p = a._data._payload.ptr; + foreach (i; 0 .. 1000) + { + a.insertBack(i); + } + assert(p == a._data._payload.ptr); +} + +@system unittest +{ + auto a = Array!int(1, 2, 3); + a[1] *= 42; + assert(a[1] == 84); +} + +@system unittest +{ + auto a = Array!int(1, 2, 3); + auto b = Array!int(11, 12, 13); + auto c = a ~ b; + assert(c == Array!int(1, 2, 3, 11, 12, 13)); + assert(a ~ b[] == Array!int(1, 2, 3, 11, 12, 13)); + assert(a ~ [4,5] == Array!int(1,2,3,4,5)); +} + +@system unittest +{ + auto a = Array!int(1, 2, 3); + auto b = Array!int(11, 12, 13); + a ~= b; + assert(a == Array!int(1, 2, 3, 11, 12, 13)); +} + +@system unittest +{ + auto a = Array!int(1, 2, 3, 4); + assert(a.removeAny() == 4); + assert(a == Array!int(1, 2, 3)); +} + +@system unittest +{ + auto a = Array!int(1, 2, 3, 4, 5); + auto r = a[2 .. a.length]; + assert(a.insertBefore(r, 42) == 1); + assert(a == Array!int(1, 2, 42, 3, 4, 5)); + r = a[2 .. 2]; + assert(a.insertBefore(r, [8, 9]) == 2); + assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5)); +} + +@system unittest +{ + auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8); + a.linearRemove(a[4 .. 6]); + assert(a == Array!int(0, 1, 2, 3, 6, 7, 8)); +} + +// Give the Range object some testing. +@system unittest +{ + import std.algorithm.comparison : equal; + import std.range : retro; + auto a = Array!int(0, 1, 2, 3, 4, 5, 6)[]; + auto b = Array!int(6, 5, 4, 3, 2, 1, 0)[]; + alias A = typeof(a); + + static assert(isRandomAccessRange!A); + static assert(hasSlicing!A); + static assert(hasAssignableElements!A); + static assert(hasMobileElements!A); + + assert(equal(retro(b), a)); + assert(a.length == 7); + assert(equal(a[1 .. 4], [1, 2, 3])); +} +// Test issue 5920 +@system unittest +{ + struct structBug5920 + { + int order; + uint* pDestructionMask; + ~this() + { + if (pDestructionMask) + *pDestructionMask += 1 << order; + } + } + + alias S = structBug5920; + uint dMask; + + auto arr = Array!S(cast(S[])[]); + foreach (i; 0 .. 8) + arr.insertBack(S(i, &dMask)); + // don't check dMask now as S may be copied multiple times (it's ok?) + { + assert(arr.length == 8); + dMask = 0; + arr.length = 6; + assert(arr.length == 6); // make sure shrinking calls the d'tor + assert(dMask == 0b1100_0000); + arr.removeBack(); + assert(arr.length == 5); // make sure removeBack() calls the d'tor + assert(dMask == 0b1110_0000); + arr.removeBack(3); + assert(arr.length == 2); // ditto + assert(dMask == 0b1111_1100); + arr.clear(); + assert(arr.length == 0); // make sure clear() calls the d'tor + assert(dMask == 0b1111_1111); + } + assert(dMask == 0b1111_1111); // make sure the d'tor is called once only. +} +// Test issue 5792 (mainly just to check if this piece of code is compilable) +@system unittest +{ + auto a = Array!(int[])([[1,2],[3,4]]); + a.reserve(4); + assert(a.capacity >= 4); + assert(a.length == 2); + assert(a[0] == [1,2]); + assert(a[1] == [3,4]); + a.reserve(16); + assert(a.capacity >= 16); + assert(a.length == 2); + assert(a[0] == [1,2]); + assert(a[1] == [3,4]); +} + +// test replace!Stuff with range Stuff +@system unittest +{ + import std.algorithm.comparison : equal; + auto a = Array!int([1, 42, 5]); + a.replace(a[1 .. 2], [2, 3, 4]); + assert(equal(a[], [1, 2, 3, 4, 5])); +} + +// test insertBefore and replace with empty Arrays +@system unittest +{ + import std.algorithm.comparison : equal; + auto a = Array!int(); + a.insertBefore(a[], 1); + assert(equal(a[], [1])); +} +@system unittest +{ + import std.algorithm.comparison : equal; + auto a = Array!int(); + a.insertBefore(a[], [1, 2]); + assert(equal(a[], [1, 2])); +} +@system unittest +{ + import std.algorithm.comparison : equal; + auto a = Array!int(); + a.replace(a[], [1, 2]); + assert(equal(a[], [1, 2])); +} +@system unittest +{ + import std.algorithm.comparison : equal; + auto a = Array!int(); + a.replace(a[], 1); + assert(equal(a[], [1])); +} +// make sure that Array instances refuse ranges that don't belong to them +@system unittest +{ + import std.exception : assertThrown; + + Array!int a = [1, 2, 3]; + auto r = a.dup[]; + assertThrown(a.insertBefore(r, 42)); + assertThrown(a.insertBefore(r, [42])); + assertThrown(a.insertAfter(r, 42)); + assertThrown(a.replace(r, 42)); + assertThrown(a.replace(r, [42])); + assertThrown(a.linearRemove(r)); +} +@system unittest +{ + auto a = Array!int([1, 1]); + a[1] = 0; //Check Array.opIndexAssign + assert(a[1] == 0); + a[1] += 1; //Check Array.opIndexOpAssign + assert(a[1] == 1); + + //Check Array.opIndexUnary + ++a[0]; + //a[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed + assert(a[0] == 2); + assert(+a[0] == +2); + assert(-a[0] == -2); + assert(~a[0] == ~2); + + auto r = a[]; + r[1] = 0; //Check Array.Range.opIndexAssign + assert(r[1] == 0); + r[1] += 1; //Check Array.Range.opIndexOpAssign + assert(r[1] == 1); + + //Check Array.Range.opIndexUnary + ++r[0]; + //r[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed + assert(r[0] == 3); + assert(+r[0] == +3); + assert(-r[0] == -3); + assert(~r[0] == ~3); +} + +@system unittest +{ + import std.algorithm.comparison : equal; + + //Test "array-wide" operations + auto a = Array!int([0, 1, 2]); //Array + a[] += 5; + assert(a[].equal([5, 6, 7])); + ++a[]; + assert(a[].equal([6, 7, 8])); + a[1 .. 3] *= 5; + assert(a[].equal([6, 35, 40])); + a[0 .. 2] = 0; + assert(a[].equal([0, 0, 40])); + + //Test empty array + auto a2 = Array!int.init; + ++a2[]; + ++a2[0 .. 0]; + a2[] = 0; + a2[0 .. 0] = 0; + a2[] += 0; + a2[0 .. 0] += 0; + + //Test "range-wide" operations + auto r = Array!int([0, 1, 2])[]; //Array.Range + r[] += 5; + assert(r.equal([5, 6, 7])); + ++r[]; + assert(r.equal([6, 7, 8])); + r[1 .. 3] *= 5; + assert(r.equal([6, 35, 40])); + r[0 .. 2] = 0; + assert(r.equal([0, 0, 40])); + + //Test empty Range + auto r2 = Array!int.init[]; + ++r2[]; + ++r2[0 .. 0]; + r2[] = 0; + r2[0 .. 0] = 0; + r2[] += 0; + r2[0 .. 0] += 0; +} + +// Test issue 11194 +@system unittest +{ + static struct S { + int i = 1337; + void* p; + this(this) { assert(i == 1337); } + ~this() { assert(i == 1337); } + } + Array!S arr; + S s; + arr ~= s; + arr ~= s; +} + +@safe unittest //11459 +{ + static struct S + { + bool b; + alias b this; + } + alias A = Array!S; + alias B = Array!(shared bool); +} + +@system unittest //11884 +{ + import std.algorithm.iteration : filter; + auto a = Array!int([1, 2, 2].filter!"true"()); +} + +@safe unittest //8282 +{ + auto arr = new Array!int; +} + +@system unittest //6998 +{ + static int i = 0; + class C + { + int dummy = 1; + this(){++i;} + ~this(){--i;} + } + + assert(i == 0); + auto c = new C(); + assert(i == 1); + + //scope + { + auto arr = Array!C(c); + assert(i == 1); + } + //Array should not have destroyed the class instance + assert(i == 1); + + //Just to make sure the GC doesn't collect before the above test. + assert(c.dummy == 1); +} +@system unittest //6998-2 +{ + static class C {int i;} + auto c = new C; + c.i = 42; + Array!C a; + a ~= c; + a.clear; + assert(c.i == 42); //fails +} + +@safe unittest +{ + static assert(is(Array!int.Range)); + static assert(is(Array!int.ConstRange)); +} + +@system unittest // const/immutable Array and Ranges +{ + static void test(A, R, E, S)() + { + A a; + R r = a[]; + assert(r.empty); + assert(r.length == 0); + static assert(is(typeof(r.front) == E)); + static assert(is(typeof(r.back) == E)); + static assert(is(typeof(r[0]) == E)); + static assert(is(typeof(r[]) == S)); + static assert(is(typeof(r[0 .. 0]) == S)); + } + + alias A = Array!int; + + test!(A, A.Range, int, A.Range); + test!(A, const A.Range, const int, A.ConstRange); + + test!(const A, A.ConstRange, const int, A.ConstRange); + test!(const A, const A.ConstRange, const int, A.ConstRange); + + test!(immutable A, A.ImmutableRange, immutable int, A.ImmutableRange); + test!(immutable A, const A.ImmutableRange, immutable int, A.ImmutableRange); + test!(immutable A, immutable A.ImmutableRange, immutable int, + A.ImmutableRange); +} + +// ensure @nogc +@nogc @system unittest +{ + Array!int ai; + ai ~= 1; + assert(ai.front == 1); + + ai.reserve(10); + assert(ai.capacity == 10); + + static immutable arr = [1, 2, 3]; + ai.insertBack(arr); +} + + +//////////////////////////////////////////////////////////////////////////////// +// Array!bool +//////////////////////////////////////////////////////////////////////////////// + +/** + * _Array specialized for `bool`. Packs together values efficiently by + * allocating one bit per element. + */ +struct Array(T) +if (is(Unqual!T == bool)) +{ + import std.exception : enforce; + import std.typecons : RefCounted, RefCountedAutoInitialize; + + static immutable uint bitsPerWord = size_t.sizeof * 8; + private static struct Data + { + Array!size_t.Payload _backend; + size_t _length; + } + private RefCounted!(Data, RefCountedAutoInitialize.no) _store; + + private @property ref size_t[] data() + { + assert(_store.refCountedStore.isInitialized); + return _store._backend._payload; + } + + /** + * Defines the array's primary range. + */ + struct Range + { + private Array _outer; + private size_t _a, _b; + /// Range primitives + @property Range save() + { + version (bug4437) + { + return this; + } + else + { + auto copy = this; + return copy; + } + } + /// Ditto + @property bool empty() + { + return _a >= _b || _outer.length < _b; + } + /// Ditto + @property T front() + { + enforce(!empty, "Attempting to access the front of an empty Array"); + return _outer[_a]; + } + /// Ditto + @property void front(bool value) + { + enforce(!empty, "Attempting to set the front of an empty Array"); + _outer[_a] = value; + } + /// Ditto + T moveFront() + { + enforce(!empty, "Attempting to move the front of an empty Array"); + return _outer.moveAt(_a); + } + /// Ditto + void popFront() + { + enforce(!empty, "Attempting to popFront an empty Array"); + ++_a; + } + /// Ditto + @property T back() + { + enforce(!empty, "Attempting to access the back of an empty Array"); + return _outer[_b - 1]; + } + /// Ditto + @property void back(bool value) + { + enforce(!empty, "Attempting to set the back of an empty Array"); + _outer[_b - 1] = value; + } + /// Ditto + T moveBack() + { + enforce(!empty, "Attempting to move the back of an empty Array"); + return _outer.moveAt(_b - 1); + } + /// Ditto + void popBack() + { + enforce(!empty, "Attempting to popBack an empty Array"); + --_b; + } + /// Ditto + T opIndex(size_t i) + { + return _outer[_a + i]; + } + /// Ditto + void opIndexAssign(T value, size_t i) + { + _outer[_a + i] = value; + } + /// Ditto + T moveAt(size_t i) + { + return _outer.moveAt(_a + i); + } + /// Ditto + @property size_t length() const + { + assert(_a <= _b); + return _b - _a; + } + alias opDollar = length; + /// ditto + Range opSlice(size_t low, size_t high) + { + assert( + _a <= low && low <= high && high <= _b, + "Using out of bounds indexes on an Array" + ); + return Range(_outer, _a + low, _a + high); + } + } + + /** + * Property returning `true` if and only if the array has + * no elements. + * + * Complexity: $(BIGOH 1) + */ + @property bool empty() + { + return !length; + } + + /** + * Returns: A duplicate of the array. + * + * Complexity: $(BIGOH length). + */ + @property Array dup() + { + Array result; + result.insertBack(this[]); + return result; + } + + /** + * Returns the number of elements in the array. + * + * Complexity: $(BIGOH 1). + */ + @property size_t length() const + { + return _store.refCountedStore.isInitialized ? _store._length : 0; + } + size_t opDollar() const + { + return length; + } + + /** + * Returns: The maximum number of elements the array can store without + * reallocating memory and invalidating iterators upon insertion. + * + * Complexity: $(BIGOH 1). + */ + @property size_t capacity() + { + return _store.refCountedStore.isInitialized + ? cast(size_t) bitsPerWord * _store._backend.capacity + : 0; + } + + /** + * Ensures sufficient capacity to accommodate `e` _elements. + * If `e < capacity`, this method does nothing. + * + * Postcondition: `capacity >= e` + * + * Note: If the capacity is increased, one should assume that all + * iterators to the elements are invalidated. + * + * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1). + */ + void reserve(size_t e) + { + import std.conv : to; + _store.refCountedStore.ensureInitialized(); + _store._backend.reserve(to!size_t((e + bitsPerWord - 1) / bitsPerWord)); + } + + /** + * Returns: A range that iterates over all elements of the array in forward order. + * + * Complexity: $(BIGOH 1) + */ + Range opSlice() + { + return Range(this, 0, length); + } + + + /** + * Returns: A range that iterates the array between two specified positions. + * + * Complexity: $(BIGOH 1) + */ + Range opSlice(size_t a, size_t b) + { + enforce(a <= b && b <= length); + return Range(this, a, b); + } + + /** + * Returns: The first element of the array. + * + * Precondition: `empty == false` + * + * Complexity: $(BIGOH 1) + * + * Throws: `Exception` if the array is empty. + */ + @property bool front() + { + enforce(!empty); + return data.ptr[0] & 1; + } + + /// Ditto + @property void front(bool value) + { + enforce(!empty); + if (value) data.ptr[0] |= 1; + else data.ptr[0] &= ~cast(size_t) 1; + } + + /** + * Returns: The last element of the array. + * + * Precondition: `empty == false` + * + * Complexity: $(BIGOH 1) + * + * Throws: `Exception` if the array is empty. + */ + @property bool back() + { + enforce(!empty); + return cast(bool)(data.back & (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord))); + } + + /// Ditto + @property void back(bool value) + { + enforce(!empty); + if (value) + { + data.back |= (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord)); + } + else + { + data.back &= + ~(cast(size_t) 1 << ((_store._length - 1) % bitsPerWord)); + } + } + + /** + * Indexing operators yielding or modifyng the value at the specified index. + * + * Precondition: `i < length` + * + * Complexity: $(BIGOH 1) + */ + bool opIndex(size_t i) + { + auto div = cast(size_t) (i / bitsPerWord); + auto rem = i % bitsPerWord; + enforce(div < data.length); + return cast(bool)(data.ptr[div] & (cast(size_t) 1 << rem)); + } + + /// ditto + void opIndexAssign(bool value, size_t i) + { + auto div = cast(size_t) (i / bitsPerWord); + auto rem = i % bitsPerWord; + enforce(div < data.length); + if (value) data.ptr[div] |= (cast(size_t) 1 << rem); + else data.ptr[div] &= ~(cast(size_t) 1 << rem); + } + + /// ditto + void opIndexOpAssign(string op)(bool value, size_t i) + { + auto div = cast(size_t) (i / bitsPerWord); + auto rem = i % bitsPerWord; + enforce(div < data.length); + auto oldValue = cast(bool) (data.ptr[div] & (cast(size_t) 1 << rem)); + // Do the deed + auto newValue = mixin("oldValue "~op~" value"); + // Write back the value + if (newValue != oldValue) + { + if (newValue) data.ptr[div] |= (cast(size_t) 1 << rem); + else data.ptr[div] &= ~(cast(size_t) 1 << rem); + } + } + + /// Ditto + T moveAt(size_t i) + { + return this[i]; + } + + /** + * Returns: A new array which is a concatenation of `this` and its argument. + * + * Complexity: + * $(BIGOH length + m), where `m` is the number of elements in `stuff`. + */ + Array!bool opBinary(string op, Stuff)(Stuff rhs) + if (op == "~") + { + Array!bool result; + + static if (hasLength!Stuff) + result.reserve(length + rhs.length); + else static if (is(typeof(rhs[])) && hasLength!(typeof(rhs[]))) + result.reserve(length + rhs[].length); + else static if (isImplicitlyConvertible!(Stuff, bool)) + result.reserve(length + 1); + + result.insertBack(this[]); + result ~= rhs; + return result; + } + + /** + * Forwards to `insertBack`. + */ + Array!bool opOpAssign(string op, Stuff)(Stuff stuff) + if (op == "~") + { + static if (is(typeof(stuff[]))) insertBack(stuff[]); + else insertBack(stuff); + return this; + } + + /** + * Removes all the elements from the array and releases allocated memory. + * + * Postcondition: `empty == true && capacity == 0` + * + * Complexity: $(BIGOH length) + */ + void clear() + { + this = Array(); + } + + /** + * Sets the number of elements in the array to `newLength`. If `newLength` + * is greater than `length`, the new elements are added to the end of the + * array and initialized with `false`. + * + * Complexity: + * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`. + * If `capacity < newLength` the worst case is $(BIGOH newLength). + * + * Postcondition: `length == newLength` + */ + @property void length(size_t newLength) + { + import std.conv : to; + _store.refCountedStore.ensureInitialized(); + auto newDataLength = + to!size_t((newLength + bitsPerWord - 1) / bitsPerWord); + _store._backend.length = newDataLength; + _store._length = newLength; + } + + /** + * Removes the last element from the array and returns it. + * Both stable and non-stable versions behave the same and guarantee + * that ranges iterating over the array are never invalidated. + * + * Precondition: `empty == false` + * + * Returns: The element removed. + * + * Complexity: $(BIGOH 1). + * + * Throws: `Exception` if the array is empty. + */ + T removeAny() + { + auto result = back; + removeBack(); + return result; + } + + /// ditto + alias stableRemoveAny = removeAny; + + /** + * Inserts the specified elements at the back of the array. `stuff` can be + * a value convertible to `bool` or a range of objects convertible to `bool`. + * + * Returns: The number of elements inserted. + * + * Complexity: + * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m), + * where `m` is the number of elements in `stuff`. + */ + size_t insertBack(Stuff)(Stuff stuff) + if (is(Stuff : bool)) + { + _store.refCountedStore.ensureInitialized(); + auto rem = _store._length % bitsPerWord; + if (rem) + { + // Fits within the current array + if (stuff) + { + data[$ - 1] |= (cast(size_t) 1 << rem); + } + else + { + data[$ - 1] &= ~(cast(size_t) 1 << rem); + } + } + else + { + // Need to add more data + _store._backend.insertBack(stuff); + } + ++_store._length; + return 1; + } + + /// ditto + size_t insertBack(Stuff)(Stuff stuff) + if (isInputRange!Stuff && is(ElementType!Stuff : bool)) + { + static if (!hasLength!Stuff) size_t result; + for (; !stuff.empty; stuff.popFront()) + { + insertBack(stuff.front); + static if (!hasLength!Stuff) ++result; + } + static if (!hasLength!Stuff) return result; + else return stuff.length; + } + + /// ditto + alias stableInsertBack = insertBack; + + /// ditto + alias insert = insertBack; + + /// ditto + alias stableInsert = insertBack; + + /// ditto + alias linearInsert = insertBack; + + /// ditto + alias stableLinearInsert = insertBack; + + /** + * Removes the value from the back of the array. Both stable and non-stable + * versions behave the same and guarantee that ranges iterating over the + * array are never invalidated. + * + * Precondition: `empty == false` + * + * Complexity: $(BIGOH 1). + * + * Throws: `Exception` if the array is empty. + */ + void removeBack() + { + enforce(_store._length); + if (_store._length % bitsPerWord) + { + // Cool, just decrease the length + --_store._length; + } + else + { + // Reduce the allocated space + --_store._length; + _store._backend.length = _store._backend.length - 1; + } + } + + /// ditto + alias stableRemoveBack = removeBack; + + /** + * Removes `howMany` values from the back of the array. Unlike the + * unparameterized versions above, these functions do not throw if + * they could not remove `howMany` elements. Instead, if `howMany > n`, + * all elements are removed. The returned value is the effective number + * of elements removed. Both stable and non-stable versions behave the same + * and guarantee that ranges iterating over the array are never invalidated. + * + * Returns: The number of elements removed. + * + * Complexity: $(BIGOH howMany). + */ + size_t removeBack(size_t howMany) + { + if (howMany >= length) + { + howMany = length; + clear(); + } + else + { + length = length - howMany; + } + return howMany; + } + + /// ditto + alias stableRemoveBack = removeBack; + + /** + * Inserts `stuff` before, after, or instead range `r`, which must + * be a valid range previously extracted from this array. `stuff` + * can be a value convertible to `bool` or a range of objects convertible + * to `bool`. Both stable and non-stable version behave the same and + * guarantee that ranges iterating over the array are never invalidated. + * + * Returns: The number of values inserted. + * + * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`. + */ + size_t insertBefore(Stuff)(Range r, Stuff stuff) + { + import std.algorithm.mutation : bringToFront; + // TODO: make this faster, it moves one bit at a time + immutable inserted = stableInsertBack(stuff); + immutable tailLength = length - inserted; + bringToFront( + this[r._a .. tailLength], + this[tailLength .. length]); + return inserted; + } + + /// ditto + alias stableInsertBefore = insertBefore; + + /// ditto + size_t insertAfter(Stuff)(Range r, Stuff stuff) + { + import std.algorithm.mutation : bringToFront; + // TODO: make this faster, it moves one bit at a time + immutable inserted = stableInsertBack(stuff); + immutable tailLength = length - inserted; + bringToFront( + this[r._b .. tailLength], + this[tailLength .. length]); + return inserted; + } + + /// ditto + alias stableInsertAfter = insertAfter; + + /// ditto + size_t replace(Stuff)(Range r, Stuff stuff) + if (is(Stuff : bool)) + { + if (!r.empty) + { + // There is room + r.front = stuff; + r.popFront(); + linearRemove(r); + } + else + { + // No room, must insert + insertBefore(r, stuff); + } + return 1; + } + + /// ditto + alias stableReplace = replace; + + /** + * Removes all elements belonging to `r`, which must be a range + * obtained originally from this array. + * + * Returns: A range spanning the remaining elements in the array that + * initially were right after `r`. + * + * Complexity: $(BIGOH length) + */ + Range linearRemove(Range r) + { + import std.algorithm.mutation : copy; + copy(this[r._b .. length], this[r._a .. length]); + length = length - r.length; + return this[r._a .. length]; + } +} + +@system unittest +{ + Array!bool a; + assert(a.empty); +} + +@system unittest +{ + Array!bool arr; + arr.insert([false, false, false, false]); + assert(arr.front == false); + assert(arr.back == false); + assert(arr[1] == false); + auto slice = arr[]; + slice = arr[0 .. $]; + slice = slice[1 .. $]; + slice.front = true; + slice.back = true; + slice[1] = true; + assert(slice.front == true); + assert(slice.back == true); + assert(slice[1] == true); + assert(slice.moveFront == true); + assert(slice.moveBack == true); + assert(slice.moveAt(1) == true); +} + +// issue 16331 - uncomparable values are valid values for an array +@system unittest +{ + double[] values = [double.nan, double.nan]; + auto arr = Array!double(values); +} + +@nogc @system unittest +{ + auto a = Array!int(0, 1, 2); + int[3] b = [3, 4, 5]; + short[3] ci = [0, 1, 0]; + auto c = Array!short(ci); + assert(Array!int(0, 1, 2, 0, 1, 2) == a ~ a); + assert(Array!int(0, 1, 2, 3, 4, 5) == a ~ b); + assert(Array!int(0, 1, 2, 3) == a ~ 3); + assert(Array!int(0, 1, 2, 0, 1, 0) == a ~ c); +} + +@nogc @system unittest +{ + auto a = Array!char('a', 'b'); + assert(Array!char("abc") == a ~ 'c'); + import std.utf : byCodeUnit; + assert(Array!char("abcd") == a ~ "cd".byCodeUnit); +} + +@nogc @system unittest +{ + auto a = Array!dchar("ąćę"d); + assert(Array!dchar("ąćęϢϖ"d) == a ~ "Ϣϖ"d); + wchar x = 'Ϣ'; + assert(Array!dchar("ąćęϢz"d) == a ~ x ~ 'z'); +} + +@system unittest +{ + Array!bool a; + assert(a.empty); + a.insertBack(false); + assert(!a.empty); +} + +@system unittest +{ + Array!bool a; + assert(a.empty); + auto b = a.dup; + assert(b.empty); + a.insertBack(true); + assert(b.empty); +} + +@system unittest +{ + import std.conv : to; + Array!bool a; + assert(a.length == 0); + a.insert(true); + assert(a.length == 1, to!string(a.length)); +} + +@system unittest +{ + import std.conv : to; + Array!bool a; + assert(a.capacity == 0); + foreach (i; 0 .. 100) + { + a.insert(true); + assert(a.capacity >= a.length, to!string(a.capacity)); + } +} + +@system unittest +{ + Array!bool a; + assert(a.capacity == 0); + a.reserve(15657); + assert(a.capacity >= 15657); + a.reserve(100); + assert(a.capacity >= 15657); +} + +@system unittest +{ + Array!bool a; + a.insertBack([true, false, true, true]); + assert(a[0 .. 2].length == 2); +} + +@system unittest +{ + Array!bool a; + a.insertBack([true, false, true, true]); + assert(a[].length == 4); +} + +@system unittest +{ + Array!bool a; + a.insertBack([true, false, true, true]); + assert(a.front); + a.front = false; + assert(!a.front); +} + +@system unittest +{ + Array!bool a; + a.insertBack([true, false, true, true]); + assert(a[].length == 4); +} + +@system unittest +{ + Array!bool a; + a.insertBack([true, false, true, true]); + assert(a.back); + a.back = false; + assert(!a.back); +} + +@system unittest +{ + Array!bool a; + a.insertBack([true, false, true, true]); + assert(a[0] && !a[1]); + a[0] &= a[1]; + assert(!a[0]); +} + +@system unittest +{ + import std.algorithm.comparison : equal; + Array!bool a; + a.insertBack([true, false, true, true]); + Array!bool b; + b.insertBack([true, true, false, true]); + assert(equal((a ~ b)[], + [true, false, true, true, true, true, false, true])); + assert((a ~ [true, false])[].equal([true, false, true, true, true, false])); + Array!bool c; + c.insertBack(true); + assert((c ~ false)[].equal([true, false])); +} +@system unittest +{ + import std.algorithm.comparison : equal; + Array!bool a; + a.insertBack([true, false, true, true]); + Array!bool b; + a.insertBack([false, true, false, true, true]); + a ~= b; + assert(equal( + a[], + [true, false, true, true, false, true, false, true, true])); +} + +@system unittest +{ + Array!bool a; + a.insertBack([true, false, true, true]); + a.clear(); + assert(a.capacity == 0); +} + +@system unittest +{ + Array!bool a; + a.length = 1057; + assert(a.length == 1057); + assert(a.capacity >= a.length); + foreach (e; a) + { + assert(!e); + } + immutable cap = a.capacity; + a.length = 100; + assert(a.length == 100); + // do not realloc if length decreases + assert(a.capacity == cap); +} + +@system unittest +{ + Array!bool a; + a.length = 1057; + assert(!a.removeAny()); + assert(a.length == 1056); + foreach (e; a) + { + assert(!e); + } +} + +@system unittest +{ + Array!bool a; + for (int i = 0; i < 100; ++i) + a.insertBack(true); + foreach (e; a) + assert(e); +} + +@system unittest +{ + Array!bool a; + a.length = 1057; + assert(a.removeBack(1000) == 1000); + assert(a.length == 57); + foreach (e; a) + { + assert(!e); + } +} + +@system unittest +{ + import std.conv : to; + Array!bool a; + version (bugxxxx) + { + a._store.refCountedDebug = true; + } + a.insertBefore(a[], true); + assert(a.length == 1, to!string(a.length)); + a.insertBefore(a[], false); + assert(a.length == 2, to!string(a.length)); + a.insertBefore(a[1 .. $], true); + import std.algorithm.comparison : equal; + assert(a[].equal([false, true, true])); +} + +@system unittest +{ + import std.conv : to; + Array!bool a; + a.length = 10; + a.insertAfter(a[0 .. 5], true); + assert(a.length == 11, to!string(a.length)); + assert(a[5]); +} +@system unittest +{ + alias V3 = int[3]; + V3 v = [1, 2, 3]; + Array!V3 arr; + arr ~= v; + assert(arr[0] == [1, 2, 3]); +} +@system unittest +{ + alias V3 = int[3]; + V3[2] v = [[1, 2, 3], [4, 5, 6]]; + Array!V3 arr; + arr ~= v; + assert(arr[0] == [1, 2, 3]); + assert(arr[1] == [4, 5, 6]); +} |