--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doodle/containers/list.d	Mon Apr 12 14:01:54 2010 +0930
@@ -0,0 +1,280 @@
+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;
+        }
+    }
+}