/** Cyclic array-like container.
 *
 * See_Also: https://en.wikipedia.org/wiki/Sorted_array
 *
 * Test: dmd -preview=in -debug -g -unittest -checkaction=context -allinst -main -unittest -I../.. -i -run cyclic.d
 */
module nxt.container.cyclic;

import std.algorithm.comparison : max;

private enum PAGESIZE = 4096;	// Linux $(shell getconf PAGESIZE)

/** Cyclic array-like container.
 *
 * Set `capacity_` to `size_t.max` for array with dynamic length.
 *
 * TODO: replace PAGESIZE / T.sizeof with standard logic and Allocator
 * TODO: replace throw staticError!CyclicRangeError with onRangeError
 *
 * See_Also: `nxt.container.sorted.Sorted`.
 */
struct CyclicArray(T, size_t capacity_ = max(8, PAGESIZE / T.sizeof))
{
	import core.internal.traits : hasElaborateDestructor;
	import std.traits : isMutable;
	import std.range.primitives;
	// TODO: Make the child container type a template parameter and remove this import:
	import std.container.array : Array;
	import nxt.container.traits : mustAddGCRange;

    alias capacity = capacity_; // for public use
	enum isDynamic = capacity == capacity.max;

private:
    static if (capacity >= capacity.max)
	{
        private size_t reserve(size_t length) nothrow @nogc
        {
            assert(length > 0);
            array.length = length;
			return length;
        }
        Array!T array;
	}
    else
        T[capacity] array;
    size_t start;
    size_t size;

public:
    static if (isDynamic)
    {
        invariant { assert(array.length > 0); }

        // @disable this(); // TODO: this triggers bug in dmd: https://issues.dlang.org/show_bug.cgi?id=20934

        this(Array!T array) @nogc
        {
            assert(array.length > 0);
            this.array = array;
        }

        this(size_t length) @nogc
        {
            assert(length > 0);
            array = Array!T();
            reserve(length);
        }

        this(size_t n)(T[n] val)
        {
            array = Array!T();
            reserve(max(8, PAGESIZE / T.sizeof));
            static if (capacity != 0)
                static assert(n <= capacity);
            foreach (const ref v; val)
            {
                put(v);
            }
        }

        this(Range)(Range val)
        if (__traits(compiles, ElementType!Range) && is(ElementType!Range : T))
        {
            array = Array!T();
            reserve(max(8, PAGESIZE / T.sizeof));
            foreach (const ref v; val)
                put(v);
        }

        this(Args...)(Args val)
        {
            array = Array!T();
            reserve(max(8, PAGESIZE / T.sizeof));
            foreach (const ref v; val)
                put(v);
        }
    }
    else
    {
        this(size_t n)(T[n] val)
        {
            static if (!isDynamic)
                static assert(n <= capacity_);
            foreach (ref v; val)
                put(v);
        }

        this(Range)(Range val)
            if (__traits(compiles, ElementType!Range) && is(ElementType!Range : T))
        {
            foreach (const ref v; val)
                put(v);
        }

        this(Args...)(Args val)
        {
            foreach (ref v; val)
                put(v);
        }
    }

    mixin CyclicRangePrimitives!(T, q{
            static if (capacity_ == size_t.max)
                auto copy = typeof(cast() this)(array.length);
            else
                typeof(cast() this) copy;
	});

    static if (!isDynamic)
        CyclicRange!T byRef() @property @nogc @safe => typeof(return)(array[], start, size);

    size_t length() const @property @nogc @safe => size;

    size_t length(size_t val) @property
    {
        if (size > array.length)
            assert(false);
        if (val == 0)
        {
            clear();
            return size;
        }
        if (val > size)
            foreach (const i; size .. val)
                array[(start + i) % array.length] = T.init;
        else if (val < size)
        {
            static if (hasElaborateDestructor!T)
                foreach (const i; val .. size)
                    destroy(array[(start + i) % array.length]);
            else static if (mustAddGCRange!T)
                foreach (const i; val .. size)
                    array[(start + i) % array.length] = T.init; // avoid GC mark-phase dereference
        }
        return size = val;
    }

    void clear()
    {
        static if (hasElaborateDestructor!T)
            foreach (const i; 0 .. size)
                destroy(array[(start + i) % array.length]);
        start = 0; // optimize clears
        size = 0;
    }

    auto opBinary(string op : "~")(T rhs) const
    {
        auto copy = this.dup;
        copy.put(rhs);
        return copy;
    }

    auto opBinary(string op : "~", size_t n)(T[n] rhs) const
    {
        auto copy = this.dup;
        copy ~= rhs;
        return copy;
    }

    auto opBinary(string op : "~", Range)(Range rhs) const
        if (isInputRange!Range && is(ElementType!Range : T))
        {
            auto copy = this.dup;
            copy ~= rhs;
            return copy;
        }

    void opOpAssign(string op : "~")(T rhs)
    {
        put(rhs);
    }

    void opOpAssign(string op : "~", size_t n)(T[n] rhs)
    {
        foreach (const ref c; rhs)
            put(c);
    }

    void opOpAssign(string op : "~", size_t n)(CyclicArray!(T, n) rhs)
    {
        foreach (const i; 0 .. rhs.size)
            put(rhs.array[(rhs.start + i) % rhs.array.length]);
    }

    void opOpAssign(string op : "~", Range)(Range rhs)
        if (__traits(compiles, ElementType!Range) && is(ElementType!Range : T))
    {
        foreach (const ref c; rhs)
            put(c);
    }

    static if (capacity_ == size_t.max)
    {
        CyclicArray!(T, capacity_) dup() const
        {
            auto ret = CyclicArray!(T, capacity_)(array);
            ret.start = start;
            ret.size = size;
            return ret;
        }
    }
    else
    {
        CyclicArray!(T, capacity_) dup() const
        {
            CyclicArray!(T, capacity_) ret;
            ret.array = cast(typeof(ret.array)) array;
            ret.start = start;
            ret.size = size;
            return ret;
        }
    }

    static if (!isDynamic)
    {
        int opApply(int delegate(ref T) @nogc dg) @nogc
        {
            int result = 0;
            foreach (const i; 0 .. size)
            {
                result = dg(array[(i + start) % array.length]);
                if (result)
                    break;
            }
            return result;
        }

        int opApply(int delegate(size_t, ref T) @nogc dg) @nogc
        {
            int result = 0;
            foreach (const i; 0 .. size)
            {
                result = dg(i, array[(i + start) % array.length]);
                if (result)
                    break;
            }
            return result;
        }
    }

    bool opEquals(in CyclicArray!(T, capacity_) b)
    {
        if (size != b.size)
            return false;
        foreach (const i; 0 .. size)
            if (array[(i + start) % array.length] !=
                b.array[(i + b.start) % b.array.length])
                return false;
        return true;
    }

    bool opEquals(size_t n)(T[n] b)
    {
        if (size != n)
            return false;
        foreach (const i; 0 .. size)
            if (array[(i + start) % array.length] != b[i])
                return false;
        return true;
    }

    bool opEquals(Range)(Range b) if (hasLength!Range && is(ElementType!Range : T))
    {
        if (size != b.length)
            return false;
        auto r = b.save;
        foreach (const i; 0 .. size)
        {
            if (array[(i + start) % array.length] != r.front)
                return false;
            r.popFront();
        }
        return true;
    }
}

struct CyclicRange(T)
{
    T[] array;
    size_t start, size;
    mixin CyclicRangePrimitives!T;
    CyclicRange!T dup() const => cast(CyclicRange!T) this;
}

private mixin template CyclicRangePrimitives(T, string makeCopy = "typeof(cast() this) copy;")
{
	import core.internal.traits : hasElaborateDestructor;
	import std.traits : isMutable;
	import nxt.container.traits : mustAddGCRange;

    size_t capacity() const @property @nogc @safe => array.length;
    size_t length() const @property @nogc @safe => size;

    void put()(auto ref T val)
    {
        if (size >= array.length)
            throw staticError!CyclicRangeError("array capacity overflow", __FILE__, __LINE__);
        array[(start + size) % array.length] = val;
        size++;
    }
	/// ditto
    void put()(const auto ref T val)
    {
        if (size >= array.length)
            throw staticError!CyclicRangeError("array capacity overflow", __FILE__, __LINE__);
        array[(start + size) % array.length] = val;
        size++;
    }
	/// ditto
    void put(size_t n)(T[n] rhs)
    {
        foreach (const ref c; rhs)
            put(c);
    }
	/// ditto
    void put(Range)(Range rhs)
        if (__traits(compiles, ElementType!Range) &&
            is(ElementType!Range : T))
    {
        foreach (const ref c; rhs)
            put(c);
    }
	/// ditto
	alias opOpAssign(string op : "~") = put;
    alias insertBack = put;
    alias stableInsertBack = insertBack;

    void insertFront()(auto ref T val)
    {
        if (size >= array.length)
            throw staticError!CyclicRangeError("array capacity overflow", __FILE__, __LINE__);
        start = (start + array.length - 1) % array.length;
        array[start] = val;
        size++;
    }

    void popFront()
    {
        if (size == 0)
            throw staticError!CyclicRangeError("trying to pop an empty array", __FILE__, __LINE__);
        static if (hasElaborateDestructor!T)
            destroy(array[start]);
        else static if (mustAddGCRange!T)
            array[start] = T.init; // avoid GC mark-phase dereference
        start = (start + 1) % array.length;
        size--;
    }

    auto save() => this;

    bool empty() @nogc @safe @property const => size == 0;

    ref auto front() @nogc @safe @property inout
    {
        if (size == 0)
            throw staticError!CyclicRangeError("trying to call front on empty array",
                                               __FILE__, __LINE__);
        return array[start];
    }

    void popBack()
    {
        if (size == 0)
            throw staticError!CyclicRangeError("trying to pop an empty array", __FILE__, __LINE__);
        size--;
        static if (hasElaborateDestructor!T)
            destroy(array[(start + size) % array.length]);
        else static if (mustAddGCRange!T)
            array[(start + size) % array.length] = T.init; // avoid GC mark-phase dereference
    }

    ref auto back() @property
    {
        if (size == 0)
            throw staticError!CyclicRangeError("trying to call back on empty array",
                                               __FILE__, __LINE__);
        return array[(start + size - 1) % array.length];
    }

    auto back() @property const
    {
        if (size == 0)
            throw staticError!CyclicRangeError("trying to call back on empty array",
                                               __FILE__, __LINE__);
        return array[(start + size - 1) % array.length];
    }

    size_t opDollar() @nogc @safe const => length;

    ref inout(T) opIndex(size_t v) inout
    {
        if (v >= size)
            throw staticError!CyclicRangeError("out of range", __FILE__, __LINE__);
        else
            return array[(v + start) % array.length];
    }

    auto opIndex() const => this.dup();

    private void validateRange(size_t[2] range)
    {
        immutable size_t from = range[0];
        immutable size_t to = range[1];
        if (to > size)
            throw staticError!CyclicRangeError("trying to slice over array size",
                                               __FILE__, __LINE__);
        if (from > to)
            throw staticError!CyclicRangeError("trying to negative slice", __FILE__, __LINE__);
        if (from != to && from >= size || to - from > size)
            throw staticError!CyclicRangeError("trying to slice over array bounds",
                                               __FILE__, __LINE__);
    }

    auto opIndex(size_t[2] range)
    {
        immutable size_t from = range[0];
        immutable size_t to = range[1];
        validateRange(range);

        mixin(makeCopy);
        copy.start = 0;
        copy.size = to - from;

        foreach (const i; 0 .. copy.size)
            copy.array[i] = array[(i + start + from) % array.length];
        return copy;
    }

    static if (isMutable!T)
    {
        void opIndexUnary(string op)()
        {
            foreach (const i; 0 .. size)
                mixin(op ~ "array[(i + start) % array.length];");
        }

        auto opIndexUnary(string op)(size_t i)
        {
            return mixin(op ~ "array[(i + start) % array.length]");
        }

        void opIndexUnary(string op)(size_t[2] range)
        {
            immutable size_t from = range[0];
            immutable size_t to = range[1];
            validateRange(range);

            foreach (const i; 0 .. to - from)
                mixin(op ~ "array[(i + start + from) % array.length];");
        }

        void opIndexAssign(U)(U val)
        {
            foreach (const i; 0 .. size)
                array[(i + start) % array.length] = val;
        }

        void opIndexAssign(U)(U val, size_t i)
        {
            opIndex(i) = val;
        }

        void opIndexAssign(U)(U val, size_t[2] range)
        {
            immutable size_t from = range[0];
            immutable size_t to = range[1];
            validateRange(range);

            foreach (const i; 0 .. to - from)
                array[(i + start + from) % array.length] = val;
        }

        void opIndexOpAssign(string op, U)(U val)
        {
            foreach (const i; 0 .. size)
                mixin("array[(i + start) % array.length] " ~ op ~ "= val;");
        }

        void opIndexOpAssign(string op, U)(U val, size_t i)
        {
            mixin("array[(i + start) % array.length] " ~ op ~ "= val;");
        }

        void opIndexOpAssign(string op, U)(U val, size_t[2] range)
        {
            immutable size_t from = range[0];
            immutable size_t to = range[1];
            validateRange(range);

            foreach (const i; 0 .. to - from)
                mixin("array[(i + start + from) % array.length] " ~ op ~ "= val;");
        }
    }

    static if (isMutable!T)
    {
        import std.algorithm.mutation : move;

        T moveFront()
        {
            if (size == 0)
                throw staticError!CyclicRangeError("trying to move in empty array",
                                                   __FILE__, __LINE__);
            return move(array[0]);
        }

        T moveBack()
        {
            if (size == 0)
                throw staticError!CyclicRangeError("trying to move in empty array",
                                                   __FILE__, __LINE__);
            return move(array[(start + size - 1) % array.length]);
        }

        T moveAt(size_t i)
        {
            if (i >= size)
                throw staticError!CyclicRangeError("trying to move outside range",
                                                   __FILE__, __LINE__);
            return move(array[(start + i) % array.length]);
        }
    }

    size_t[2] opSlice(size_t i : 0)() const => [0, size];
    size_t[2] opSlice(size_t i : 0)(size_t from, size_t to) const => [from, to];

    /**
     * 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;
    }

    alias stableRemoveAny = removeAny;

    /**
     * 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() => popBack();

    /// ditto
    alias stableRemoveBack = removeBack;

    void removeBack(int howMany)
    {
        foreach (const i; 0 .. howMany)
            popBack();
    }
}

/// @nogc array without memory management using a cyclic array internally
/// Should be treated like a static array when no capacity_ is set (copies on assignment)
/// The maximum capacity is static and by default so many elements that it fills at most 4KiB, but at least 8 elements (even if that is more than 4KiB).
/// Set length to 0 to make it a std.container.Array based array
/// Bugs: foreach with ref value requires @nogc body to make this @nogc compatible
///
@nogc @safe unittest
{
    CyclicArray!int array;
    assert(array.length == 0);
    array ~= 5;
    assert(!array.empty);
    assert(array.front == 5);
    assert(array[0] == 5);
    array ~= [4, 3];

    assert(array == [5, 4, 3]);

    // same efficiency as insertBack/put/concat
    array.insertFront(5);
}

@nogc @system unittest
{
    // heap array using std.container.Array with 16 elements
    auto heapArray = CyclicArray!(int, size_t.max)(16);

    // custom memory using Array
    auto myArray = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
    auto customArray = CyclicArray!(int, size_t.max)(myArray[0 .. 6]);
}

class CyclicRangeError : Error
{
    @nogc @safe pure nothrow this(string msg, string file = __FILE__,
                                  size_t line = __LINE__, Throwable next = null)
    {
        super(msg, file, line, next);
    }
}

// TLS storage shared for all errors, chaining might create circular reference
private void[128] _store;

// only Errors for now as those are rarely chained
private T staticError(T, Args...)(auto ref Args args) @trusted if (is(T : Error))
{
    // pure hack, what we actually need is @noreturn and allow to call that in pure functions
    static T get()
    {
        static assert(__traits(classInstanceSize, T) <= _store.length,
                      T.stringof ~ " is too large for staticError()");

        _store[0 .. __traits(classInstanceSize, T)] = typeid(T).initializer[];
        return cast(T) _store.ptr;
    }

    auto res = (cast(T function() @trusted pure nothrow @nogc)&get)();
    res.__ctor(args);
    return res;
}

// lots of unittests taken from std.container.array

// Give the Range object some testing.
@system unittest
{
    import std.algorithm.comparison : equal;
    import std.range : retro;

    auto a = CyclicArray!int(0, 1, 2, 3, 4, 5, 6)[];
    assert(equal(a, [0, 1, 2, 3, 4, 5, 6]));
    assert(equal(a[], [0, 1, 2, 3, 4, 5, 6]));
    assert(equal(a[0 .. $], [0, 1, 2, 3, 4, 5, 6]));
    auto b = CyclicArray!int(6, 5, 4, 3, 2, 1, 0)[];
    alias A = typeof(a);
    alias ARef = typeof(a.byRef);

    static assert(isRandomAccessRange!A);
    static assert(hasSlicing!A);
    static assert(hasAssignableElements!A);
    static assert(hasMobileElements!A);

    static assert(isRandomAccessRange!ARef);
    static assert(hasSlicing!ARef);
    static assert(hasAssignableElements!ARef);
    static assert(hasMobileElements!ARef);

    assert(equal(retro(b), a));
    assert(a.length == 7);
    assert(equal(a[1 .. 4], [1, 2, 3]));
}

@system unittest
{
    alias S = structBug5920;
    uint dMask;

    auto arr = CyclicArray!S(cast(S[])[]);
    foreach (const 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.
}

@system unittest
{
    auto a = CyclicArray!(int[])([[1, 2], [3, 4]]);
    assert(a.length == 2);
    assert(a[0] == [1, 2]);
    assert(a[1] == [3, 4]);
}

@system unittest
{
    import std.algorithm.comparison : equal;

    //Test "array-wide" operations
    auto a = CyclicArray!int([0, 1, 2]); //CyclicArray
    a[] += 5;
    assert(a[].equal([5, 6, 7]));
    ++a[];
    assert(a[].equal([6, 7, 8]));
    import std.stdio;

    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 = CyclicArray!int.init;
    ++a2[];
    ++a2[0 .. 0];
    a2[] = 0;
    a2[0 .. 0] = 0;
    a2[] += 0;
    a2[0 .. 0] += 0;

    //Test "range-wide" operations
    auto r = CyclicArray!int([0, 1, 2])[]; //CyclicArray.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 = CyclicArray!int.init[];
    ++r2[];
    ++r2[0 .. 0];
    r2[] = 0;
    r2[0 .. 0] = 0;
    r2[] += 0;
    r2[0 .. 0] += 0;
}

// Test issue
@system unittest
{
    static struct S
    {
        int i = 1337;
        void* p;
        this(this)
        {
            assert(i == 1337);
        }

        ~this() nothrow @nogc
        {
            assert(i == 1337);
        }
    }

    CyclicArray!S arr;
    S s;
    arr ~= s;
    arr ~= s;
}

@system unittest
{
    import std.algorithm.iteration : filter;

    auto a = CyclicArray!int([1, 2, 2].filter!"true"());
}

@safe unittest
{
    auto arr = new CyclicArray!int;
}

@system unittest  //6998
{
    static int i = 0;
    class C
    {
        int dummy = 1;
        this()
        {
            ++i;
        }

        ~this() nothrow @nogc
        {
            --i;
        }
    }

    assert(i == 0);
    auto c = new C();
    assert(i == 1);

    //scope
    {
        auto arr = CyclicArray!C(c);
        assert(i == 1);
    }
    //CyclicArray 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;
    CyclicArray!C a;
    a ~= c;
    a.clear;
    assert(c.i == 42); //fails
}

@nogc:
unittest
{
    alias IntArray = CyclicArray!int;
    alias IntRange = CyclicRange!int;

    static assert(isInputRange!IntArray);
    static assert(isOutputRange!(IntArray, int));
    static assert(isForwardRange!IntArray);
    static assert(isBidirectionalRange!IntArray);
    static assert(isRandomAccessRange!IntArray);
    static assert(hasMobileElements!IntArray);
    static assert(is(ElementType!IntArray == int));
    static assert(hasSwappableElements!IntArray);
    static assert(hasAssignableElements!IntArray);
    static assert(hasLvalueElements!IntArray);
    static assert(hasLength!IntArray);
    static assert(hasSlicing!IntArray);

    static assert(isInputRange!IntRange);
    static assert(isOutputRange!(IntRange, int));
    static assert(isForwardRange!IntRange);
    static assert(isBidirectionalRange!IntRange);
    static assert(isRandomAccessRange!IntRange);
    static assert(hasMobileElements!IntRange);
    static assert(is(ElementType!IntRange == int));
    static assert(hasSwappableElements!IntRange);
    static assert(hasAssignableElements!IntRange);
    static assert(hasLvalueElements!IntRange);
    static assert(hasLength!IntRange);
    static assert(hasSlicing!IntRange);

    IntArray array;
    assert(array.length == 0);
    assert(array.empty);
    array ~= 5;
    assert(!array.empty);
    assert(array.length == 1);
    assert(array.front == 5);
    assert(array[0] == 5);
    assert(array[0 .. 1].front == 5);
    assert(array[0 .. 0].empty);
    array ~= cast(int[2])[4, 3];
    assert(array.length == 3);
    assert(array[1] == 4);
    assert(array[2] == 3);

    foreach (const i; 0 .. 50000)
    {
        array ~= i;
        array.popFront();
    }

    assert(array.length == 3);

    array ~= array;
    assert(array.length == 6);
    assert((array ~ array).length == 12);
    assert(array.length == 6);

    array[5] = 1;
    assert(array[5] == 1);
    auto copy = array;
    copy[5] = 2;
    assert(array[5] == 1);
    array[][5] = 1;
    assert(array[5] == 1);

    foreach (ref v; array.byRef)
        v = 42;

    assert(array[5] == 42);
}

unittest
{
    alias IntArray = CyclicArray!(int, size_t.max);

    static assert(isInputRange!IntArray);
    static assert(isOutputRange!(IntArray, int));
    static assert(isForwardRange!IntArray);
    static assert(isBidirectionalRange!IntArray);
    static assert(isRandomAccessRange!IntArray);
    static assert(hasMobileElements!IntArray);
    static assert(is(ElementType!IntArray == int));
    static assert(hasSwappableElements!IntArray);
    static assert(hasAssignableElements!IntArray);
    static assert(hasLvalueElements!IntArray);
    static assert(hasLength!IntArray);
    static assert(hasSlicing!IntArray);

    auto array = IntArray(1024);
    assert(array.length == 0);
    assert(array.empty);
    array ~= 5;
    assert(!array.empty);
    assert(array.length == 1);
    assert(array.front == 5);
    assert(array[0] == 5);
    assert(array[0 .. 1].front == 5);
    assert(array[0 .. 0].empty);
    array ~= cast(int[2])[4, 3];
    assert(array.length == 3);
    assert(array[1] == 4);
    assert(array[2] == 3);

    foreach (const i; 0 .. 50000)
    {
        array ~= i;
        array.popFront();
    }

    assert(array.length == 3);

    array ~= array;
    assert(array.length == 6);
    assert((array ~ array).length == 12);
    assert(array.length == 6);

    array[5] = 1;
    assert(array[5] == 1);
    auto copy = array[];
    copy[5] = 2;
    assert(array[5] == 1);
    array[][5] = 1;
    assert(array[5] == 1);
}

@system unittest
{
    CyclicArray!int a;
    assert(a.empty);
}

@system unittest
{
    CyclicArray!int a;
    a.length = 10;
    assert(a.length == 10);
    assert(a.capacity >= a.length);
}

@system unittest
{
    struct Dumb
    {
        int x = 5;
    }

    CyclicArray!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);
    foreach (ref e; a)
        assert(e.x == 10);

    a.length = 8;
    assert(a.length == 8);
    assert(Dumb.init.x == 5);
    foreach (const i; 0 .. 5)
        assert(a[i].x == 10);
    foreach (const i; 5 .. a.length)
        assert(a[i].x == Dumb.init.x);

    a[] = Dumb(1);
    a.length = 20;
    foreach (const i; 0 .. 8)
        assert(a[i].x == 1);
    foreach (const 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
{
    CyclicArray!int a = CyclicArray!int(1, 2, 3);
    //a._data._refCountedDebug = true;
    auto b = a.dup;
    assert(b == CyclicArray!int(1, 2, 3));
    b.front = 42;
    assert(b == CyclicArray!int(42, 2, 3));
    assert(a == CyclicArray!int(1, 2, 3));
}

@system unittest
{
    auto a = CyclicArray!int(1, 2, 3);
    assert(a.length == 3);
}

@system unittest
{
    const CyclicArray!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++;
    }
}

@system unittest
{
    auto a = CyclicArray!int(1, 2, 3);
    a[1] *= 42;
    assert(a[1] == 84);
}

@system unittest
{
    auto a = CyclicArray!int(1, 2, 3);
    auto b = CyclicArray!int(11, 12, 13);
    auto c = a ~ b;
    assert(c == CyclicArray!int(1, 2, 3, 11, 12, 13));
    assert(a ~ b[] == CyclicArray!int(1, 2, 3, 11, 12, 13));
    assert(a ~ [4, 5] == CyclicArray!int(1, 2, 3, 4, 5));
}

@system unittest
{
    auto a = CyclicArray!int(1, 2, 3);
    auto b = CyclicArray!int(11, 12, 13);
    a ~= b;
    assert(a == CyclicArray!int(1, 2, 3, 11, 12, 13));
}

@system unittest
{
    auto a = CyclicArray!int(1, 2, 3, 4);
    assert(a.removeAny() == 4);
    assert(a == CyclicArray!int(1, 2, 3));
}

private struct structBug5920
{
    int order;
    uint* pDestructionMask;
    ~this() nothrow @nogc
    {
        if (pDestructionMask)
            *pDestructionMask += 1 << order;
    }
}

@system unittest
{
    auto a = CyclicArray!int([1, 1]);
    a[1] = 0; //Check CyclicArray.opIndexAssign
    assert(a[1] == 0);
    a[1] += 1; //Check CyclicArray.opIndexOpAssign
    assert(a[1] == 1);

    //Check CyclicArray.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 CyclicArray.Range.opIndexAssign
    assert(r[1] == 0);
    r[1] += 1; //Check CyclicArray.Range.opIndexOpAssign
    assert(r[1] == 1);

    //Check CyclicArray.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);
}

@safe unittest
{
    static struct S
    {
        bool b;
        alias b this;
    }

    alias A = CyclicArray!S;
    alias B = CyclicArray!(shared bool);
}

@system unittest
{
    CyclicArray!int ai;
    ai ~= 1;
    assert(ai.front == 1);

    static const arr = [1, 2, 3];
    ai.insertBack(arr);
}

version(unittest)
{
	import std.range.primitives;
	import std.container.array : Array;
}