module doodle.containers.list;

///
/// Doubly-linked list.
/// Consists of a sequence of cells with references to the previous and next member.
/// List keeps track of its length.
/// 
/// The list has two ends:
///     "head" and "tail".
/// There are two directions:
///     "forwards" -> towards the "head" and
///     "backwards" -> towards the "tail"
/// opApply works from the head to the tail.
/// opApplyReverse works from the tail to the head.
///
/// When used as a queue, typically use addTail and removeHead.
///
/// Design goals of list is to be completely symmetric and clear in its
/// forwards and backwards operations, and to be able to contain immutable types.
///
class List(T) {

    //
    // Standard operations:
    //

    /// Construct an empty list
    this() { }

    /// Return a copy of the list
    List!(T) dup() const {
        auto l = new List!(T);
        for (auto c = &mHead; c; c = &c.mBackward) {
            l.addTail(c.mElement);
        }
        return l;
    }

    /// Return true if the list is empty
    bool isEmpty() const {
        return mLength == 0;
    }

    /// Return the length of the list
    uint length() const {
        return mLength;
    }

    /// Return the head of the list, asserting if the list is empty
    T head() {
        assert(!isEmpty());
        return mHead.mElement;
    }

    /// Return the tail of the list, asserting if the list is empty
    T tail() {
        assert(!isEmpty());
        return mTail.mElement;
    }

    /// Add to the head of the list
    void addHead(T t) {
        add(mHead, null, t);
    }

    /// Add to the tail of the list
    void addTail(T t) {
        add(null, mTail, t);
    }

    /// Remove the head of the list, asserting if the list is empty
    T removeHead() {
        return remove(mHead).mElement;
    }

    /// Remove the tail of the list, asserting of the list is empty 
    T removeTail() {
        return remove(mTail).mElement;
    }

    // Clear the list (garbage collector does the rest)
    void clear() {
        mHead = mTail = null;
        mLength = 0;
    }

    /// Iterate over the list from head to tail - used by foreach
    int opApply(int delegate(ref T) dg) {
        int result;

        auto c = mHead;

        while (c !is null) {
            auto t = c.mElement;
            result = dg(t);
            if (result != 0) {
                break;
            }
            c = c.mBackward;
        }

        return result;
    }

    /// Iterate over the list from tail to head - used by foreach_reverse
    int opApplyReverse(int delegate(ref T) dg) {
        int result;

        auto c = mTail;

        while (c !is null) {
            auto t = c.mElement;
            result = dg(t);
            if (result != 0) {
                break;
            }
            c = c.mForward;
        }

        return result;
    }


    //
    // Iterator operations:
    //

    /// Return the first matching element going backward from head, or null
    Iterator findHead(T t) {
        for (auto c = mHead; c !is null; c = c.mBackward) {
            if (c.mElement == t) {
                return new Iterator(c);
            }
        }

        return null;
    }

    /// Return the first matching element going forward from tail, or null
    Iterator findTail(T t) {
        for (auto c = mTail; c !is null; c = c.mForward) {
            if (c.mElement == t) {
                return new Iterator(c);
            }
        }

        return null;
    }

    /// insert a new entry into list, forward of entry specified by iterator
    void insertForward(Iterator i, T t) {
        assert(i !is null);
        add(i.mCell, i.mCell.mForward, t);
    }

    /// insert a new entry into list, backward of entry specified by iterator
    void insertBackward(Iterator i, T t) {
        assert(i !is null);
        add(i.mCell.mBackward, i.mCell, t);
    }

    /// Remove specified entry from list, returning iterator to entry forward of removed one
    Iterator eraseForward(Iterator i) {
        assert(i !is null);
        Cell cell = remove(i.mCell);
        return cell.mForward ? new Iterator(cell.mForward) : null;
    }

    /// Remove specified entry from list, returning iterator to entry backward of removed one
    Iterator eraseBackward(Iterator i) {
        assert(i !is null);
        Cell cell = remove(i.mCell);
        return cell.mBackward ? new Iterator(cell.mBackward) : null;
    }

    ///
    /// Iterator for a List
    ///
    class Iterator {

        private Cell mCell;

        private this(Cell cell) {
            assert(cell !is null);
            mCell = cell;
        }

        T element() {
            return mCell.mElement;
        }

        void goForward() {
            assert(mCell.mForward !is null);
            mCell = mCell.mForward;
        }

        void goBackward() {
            assert(mCell.mBackward !is null);
            mCell = mCell.mBackward;
        }

        bool forwardValid() const {
            return mCell.mForward !is null;
        }

        bool backwardValid() const {
            return mCell.mBackward !is null;
        }

        override bool opEquals(Object other) const {
            Iterator o = cast(Iterator) other;
            if (!o) return 0;
            return mCell is o.mCell;
        }
    }

    //
    // Implementation:
    //

    private {
        Cell mHead;
        Cell mTail;
        uint mLength;

        /// An entry in the list
        class Cell {
            Cell mForward, mBackward;
            T mElement;

            this(T element, Cell backward, Cell forward) {
                mElement = element;
                mBackward = backward;
                mForward = forward;
            }
        }

        /// Add new cell between backward and forward
        void add(Cell backward, Cell forward, T t) {
            Cell cell = new Cell(t, backward, forward);

            if (backward) {
                backward.mForward = cell;
            }
            else {
                mTail = cell;
            }

            if (forward) {
                forward.mBackward = cell;
            }
            else {
                mHead = cell;
            }

            ++mLength;
        }

        /// Remove a cell from the list, returning the removed cell
        Cell remove(Cell cell) {
            if (cell.mBackward) {
                cell.mBackward.mForward = cell.mForward;
            }
            else {
                mTail = cell.mForward;
            }

            if (cell.mForward) {
                cell.mForward.mBackward = cell.mBackward;
            }
            else {
                mHead = cell.mBackward;
            }

            --mLength;

            return cell;
        }
    }
}