/*
Boost Software License - Version 1.0 - August 17th, 2003

Copyright (c) 2019 Clipsey

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/
module containers.list;

/**
    An array-based list implementation
*/
struct List(T) {
private:
    T[] data;

    /// front element id
    size_t frontElm;

public:
    /// Constructs a list of specified length
    this(size_t length) {
        data = new T[](length);
    }

    /// Constructs a list with specified data
    this(T[] data) {
        this.data = data;
    }

    /// Constructs a list with specified data
    this(List!T data) {
        this.data = data.toArray;
    }

    /// Assignment overload for list
    void opAssign(T rhs) {
        this.data = [rhs];
    }

    /// Assignment overload for list
    void opAssign(T[] rhs) {
        this.data = rhs;
    }

    /// Assignment overload for list at index
    T opIndexAssign(T value, size_t index) {
        data[index] = value;
        return value;
    }

    /// Assignment overload for list append
    T opOpAssign(string op = "~")(T value) {
        add(value);
        return value;
    }

    /// Assignment overload for list append
    T opOpAssign(string op = "~")(T[] value) {
        addRange(value);
        return value;
    }

    /// Assignment overload for list append
    T opOpAssign(string op = "~")(List!T value) {
        addRange(value);
        return value;
    }

    /// Index overload for list
    T opIndex(size_t index) {
        return data[index];
    }

    int opApply(int delegate(ref T) operations) {
        int result = 0;

        for (size_t i = 0; i < data.length; ++i) {
            result = operations(data[i]);

            if (result) break;
        }

        return result;
    }

    int opApply(int delegate(ref size_t, ref T) operations) {
        int result = 0;

        for (size_t i = 0; i < data.length; ++i) {
            result = operations(i, data[i]);

            if (result) break;
        }

        return result;
    }

    int opApplyReverse(int delegate(ref T) operations) {
        int result = 0;

        for (ptrdiff_t i = data.length-1; i >= 0; i--) {
            result = operations(data[i]);

            if (result) break;
        }

        return result;
    }

    int opApplyReverse(int delegate(ref ptrdiff_t, ref T) operations) {
        int result = 0;

        for (ptrdiff_t i = data.length-1; i >= 0; i--) {
            result = operations(i, data[i]);

            if (result) break;
        }

        return result;
    }

    /// Returns the count of items in the list
    @property size_t count() {
        return data.length;
    }

    /// Returns wether the list is empty (has no items)
    bool empty() {
        return data.length != 0;
    }

    /// Add item to list
    void add(T item) {
        data ~= item;
    }

    /// Add range of items to list
    void addRange(List!T items) {
        data ~= items.toArray();
    }

    /// Add range of items to list
    void addRange(T[] items) {
        data ~= items;
    }

    /// Clears the list
    void clear() {
        data = [];
    }

    /// Returns true if the list contains the item
    bool contains(T item) {
        foreach(srch; data) {
            if (srch == item) return true;
        }
        return false;
    }

    /// copy elements (starting from start) to array.
    void copyTo(T[] arr, size_t start) {
        arr[start..start+count()] = data;
    }

    /++
        Returns the index of the first occurence of value.
        Returns -1 if nothing was found
    +/
    ptrdiff_t indexOf(T item) {
        foreach(i, srch; data) {
            if (srch == item) return i;
        }
        return -1;
    }

    /++
        Returns the index of the last occurence of value.
        Returns -1 if nothing was found
    +/
    ptrdiff_t lastIndexOf(T item) {
        foreach_reverse(i, srch; data) {
            if (srch == item) return i;
        }
        return -1;
    }

    /// Inserts item in to list at index
    void insert(size_t index, T item) {
        data.length++;
        // First, move stuff 1 step ahead
        data[index+1..$] = data[index+1..$-1];

        // Then insert the item
        data[index] = item;
    }

    /// Inserts item range in to list at index
    void insertRange(size_t index, List!T items) {
        insertRange(index, items.toArray);
    }

    /// Inserts item range in to list at index
    void insertRange(size_t index, T[] items) {
        data.length += items.length;

        // First, move stuff x steps ahead
        data[index+items.length..$] = data[index+items.length..$-1];

        // Then insert the item range
        data[index..index+items.length] = items[0..items.length];
    }

    /// Remove item from list
    void remove(T item) {
        // Get the index
        size_t index = indexOf(item);
        removeAt(index);
    }

    /// Removes the element at index from the list
    void removeAt(size_t index) {
        // Slice it outta there.
        data = data[0..index] ~ data[index+1..$];
    }

    /// Removes a range of items from the list
    void removeRange(size_t index, size_t count) {
        size_t end = index+count;

        // Slice it outta there.
        data = data[0..index] ~ data[end..$];
    }
    
    /// Reverses the contents of the list
    void reverse() {
        /// Store the old state temporarily.
        T[] tmp = toArray();
        foreach_reverse(i, srch; tmp) {
            data[(data.length-1)-i] = srch;
        }
    }

    /// Returns a copy of the internal data of the list as an array
    T[] toArray() {
        T[] output = new T[](data.length);
        /// Make a copy, by making the LEFT HAND side a slice.
        output[] = data;
        return output;
    }

    /// Gets string representation of list
    string toString() {
        import std.conv : text;
        return data.text;
    }
}