# HG changeset patch
# User daveb
# Date 1271046714 -34200
# Node ID 1f97022e5c6d0af73b93a29cfc870b0b9564a447
# Parent  b6c34f1fc7f3b7708b39933154d87c02737fb999
Checkpoint. Development continues...

diff -r b6c34f1fc7f3 -r 1f97022e5c6d README
--- a/README	Fri Apr 09 15:19:14 2010 +0930
+++ b/README	Mon Apr 12 14:01:54 2010 +0930
@@ -4,7 +4,7 @@
 
 1. Add any comiler directives you need to the options file.
     eg:
-        -I<path-to-gtkd-includes>
+        -O -I<path-to-gtkd-includes>
 
 2. Configure the project:
         rdmd configure.d <full-path-to-build-dir>
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/cairo/routines.d
--- a/doodle/cairo/routines.d	Fri Apr 09 15:19:14 2010 +0930
+++ b/doodle/cairo/routines.d	Mon Apr 12 14:01:54 2010 +0930
@@ -16,12 +16,14 @@
 }
 
 // Horizontal line
+// void hline(scope Context cr, in double x, double y, double dx)
 void hline(scope Context cr, in double y, double x0, double x1) {
     cr.moveTo(x0, y);
     cr.lineTo(x1, y);
 }
 
 // Vertical line
+//void vline(scope Context cr, in double x, double y, double dy)
 void vline(scope Context cr, in double x, double y0, double y1) {
     cr.moveTo(x, y0);
     cr.lineTo(x, y1);
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/containers/hash_map.d
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/containers/hash_set.d
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/containers/list.d
--- /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;
+        }
+    }
+}
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/containers/stack.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doodle/containers/stack.d	Mon Apr 12 14:01:54 2010 +0930
@@ -0,0 +1,97 @@
+module doodle.containers.stack;
+
+class Stack(T) {
+    this() {
+        _data.length = 1;
+    }
+
+    bool isEmpty() {
+        return _depth == 0;
+    }
+
+    void push(T t) {
+        if (_depth == _data.length) {
+            // Need it to grow
+            _data.length = 2 * _data.length;
+        }
+
+        _data[_depth] = t;
+        ++_depth;
+    }
+
+    T pop() {
+        assert(!isEmpty());
+        --_depth;
+        auto t = _data[_depth];
+        _data[_depth] = T.init;
+        return t;
+    }
+
+    T top() {
+        assert(!isEmpty());
+        return _data[_depth - 1];
+    }
+
+    void top(T t) {
+        assert(!isEmpty());
+        _data[_depth - 1] = t;
+    }
+
+    void clear() {
+        while (_depth > 0) {
+            --_depth;
+            _data[_depth] = T.init;
+        }
+    }
+
+    void shrink() {
+        size_t new_l = _data.length;
+        do new_l /= 2; while (new_l > _depth * 2);
+        _data.length = new_l;
+    }
+
+    void capacity(size_t l) {
+        if (l > _data.length) {
+            size_t new_l = _data.length;
+            do new_l *= 2; while (new_l < l);
+            _data.length = new_l;
+        }
+    }
+
+    private {
+        size_t capacity() {
+            return _data.length;
+        }
+
+        size_t depth() {
+            return _depth;
+        }
+
+        T[] _data;          //  capacity
+        size_t _depth;
+    }
+}
+unittest {
+    auto s = new Stack!(int);
+
+    assert(s.capacity() == 1);
+
+    assert(s.depth() == 0);
+    s.push(15);
+    assert(s.depth() == 1);
+    assert(s.top() == 15);
+    assert(s.pop() == 15);
+    assert(s.depth() == 0);
+    assert(s.isEmpty());
+
+    assert(s.capacity() == 1);
+    s.push(12);
+    assert(s.capacity() == 1);
+    s.push(13);
+    assert(s.capacity() == 2);
+    s.push(14);
+    assert(s.depth() == 3);
+    assert(s.capacity() == 4);
+    s.push(s.pop());
+    assert(s.capacity() == 4);
+}
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/containers/tree_map.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doodle/containers/tree_map.d	Mon Apr 12 14:01:54 2010 +0930
@@ -0,0 +1,58 @@
+module delve.util.map;
+
+class Map(K, V) {
+    this() {
+    }
+
+    bool isEmpty() {
+    }
+
+    size_t size() {
+    }
+
+    // Error if already present
+    void add(K k, V v) {
+    }
+
+    // Error if not present
+    void set(K k, V v) {
+    }
+
+    // Error if not present
+    void remove(K k) {
+    }
+
+    bool contains(K k) {
+    }
+
+    void clear() {
+    }
+
+    int opApply(int delegate (inout T) dg) {
+    }
+
+    class Iterator {
+    }
+
+    Iterator find(K k) {
+    }
+
+    void erase(Iterator iter) {
+    }
+
+    class Iterator {
+        K key() {
+            return _cell.key();
+        }
+
+        V value() {
+            return _cell.value();
+        }
+
+        void value(V v) {
+            _cell.value(v);
+        }
+    }
+}
+unittest {
+}
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/containers/tree_set.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doodle/containers/tree_set.d	Mon Apr 12 14:01:54 2010 +0930
@@ -0,0 +1,772 @@
+module delve.util.set;
+
+class Set(T) {
+    this() {
+    }
+
+    bool isEmpty() {
+        return _root is null;
+    }
+
+    size_t size() {
+        return 0;       // FIXME
+    }
+
+    // Error if already present
+    void add(T t) {
+    }
+
+    // Error if not present
+    void remove(T t) {
+    }
+
+    bool contains(T t) {
+        return false;       // FIXME
+    }
+
+    void clear() {
+    }
+
+    int opApply(int delegate (inout T) dg) {
+        return 0;           // FIXME
+    }
+
+    /*
+    void erase(Iterator iter) {
+    }
+
+    class Iterator {
+        T element();
+
+        void goNext() {
+        }
+
+        void goPrevious() {
+        }
+
+        bool nextValid() {
+        }
+
+        bool previousValid() {
+        }
+
+        Cell _cell;
+    }
+    */
+
+    private {
+        void _add(T t) {
+            if (_root is null) {
+                _root = new Cell(t);
+            }
+            else {
+            }
+
+            ++_size;
+        }
+
+        class Cell {
+            static bool RED = false;
+            static bool BLACK = true;
+
+            /**
+             * The node color (RED, BLACK)
+             **/
+
+            bool color_;
+
+            /**
+             * Pointer to left child
+             **/
+
+            Cell left_;
+
+            /**
+             * Pointer to right child
+             **/
+
+            Cell right_;
+
+            T _element;
+
+            /**
+             * Pointer to parent (null if root)
+             **/
+
+            private Cell parent_;
+
+            /**
+             * Make a new Cell with given element, null links, and BLACK color.
+             * Normally only called to establish a new root.
+             **/
+
+            public this (T element) {
+                _element = element;
+                left_ = null;
+                right_ = null;
+                parent_ = null;
+                color_ = BLACK;
+            }
+
+            /**
+             * Return a new Cell with same element and color as self,
+             * but with null links. (Since it is never OK to have
+             * multiple identical links in a RB tree.)
+             **/ 
+
+            protected Cell duplicate() {
+                Cell t = new Cell(_element);
+                t.color_ = color_;
+                return t;
+            }
+
+
+            /**
+             * Return left child (or null)
+             **/
+
+            public final Cell left() {
+                return left_;
+            }
+
+            /**
+             * Return right child (or null)
+             **/
+
+            public final Cell right() {
+                return right_;
+            }
+
+            /**
+             * Return parent (or null)
+             **/
+            public final Cell parent() {
+                return parent_;
+            }
+
+
+            /**
+             * See_Also: tango.util.collection.model.View.View.checkImplementation.
+             **/
+            public void checkImplementation() {
+
+                // It's too hard to check the property that every simple
+                // path from node to leaf has same number of black nodes.
+                // So restrict to the following
+
+                assert(parent_ is null || this is parent_.left_ || this is parent_.right_);
+                assert(left_ is null || this is left_.parent_);
+                assert(right_ is null || this is right_.parent_);
+                assert(color_ is BLACK || (colorOf(left_) is BLACK) && (colorOf(right_) is BLACK));
+
+                if (left_ !is null)
+                    left_.checkImplementation();
+                if (right_ !is null)
+                    right_.checkImplementation();
+            }
+
+            /**
+             * Return the minimum element of the current (sub)tree
+             **/
+
+            public final Cell leftmost() {
+                auto p = this;
+                for ( ; p.left_ !is null; p = p.left_) {
+                }
+                return p;
+            }
+
+            /**
+             * Return the maximum element of the current (sub)tree
+             **/
+            public final Cell rightmost() {
+                auto p = this;
+                for ( ; p.right_ !is null; p = p.right_) {
+                }
+                return p;
+            }
+
+            /**
+             * Return the root (parentless node) of the tree
+             **/
+            public final Cell root() {
+                auto p = this;
+                for ( ; p.parent_ !is null; p = p.parent_) {
+                }
+                return p;
+            }
+
+            /**
+             * Return true if node is a root (i.e., has a null parent)
+             **/
+
+            public final bool isRoot() {
+                return parent_ is null;
+            }
+
+
+            /**
+             * Return the inorder successor, or null if no such
+             **/
+
+            public final Cell successor() {
+                if (right_ !is null)
+                    return right_.leftmost();
+                else {
+                    auto p = parent_;
+                    auto ch = this;
+                    while (p !is null && ch is p.right_) {
+                        ch = p;
+                        p = p.parent_;
+                    }
+                    return p;
+                }
+            }
+
+            /**
+             * Return the inorder predecessor, or null if no such
+             **/
+
+            public final Cell predecessor() {
+                if (left_ !is null)
+                    return left_.rightmost();
+                else
+                {
+                    auto p = parent_;
+                    auto ch = this;
+                    while (p !is null && ch is p.left_)
+                    {
+                        ch = p;
+                        p = p.parent_;
+                    }
+                    return p;
+                }
+            }
+
+            /**
+             * Return the number of nodes in the subtree
+             **/
+            public final int size() {
+                int c = 1;
+                if (left_ !is null)
+                    c += left_.size();
+                if (right_ !is null)
+                    c += right_.size();
+                return c;
+            }
+
+
+            /**
+             * Return node of current subtree containing element as element(), 
+             * if it exists, else null. 
+             * Uses Comparator cmp to find and to check equality.
+             **/
+
+            /+
+            public Cell find(T element, Comparator!(T) cmp) {
+                auto t = this;
+                for (;;) {
+                    int diff = cmp.compare(element, t.element());
+                    if (diff is 0)
+                        return t;
+                    else
+                        if (diff < 0)
+                            t = t.left_;
+                        else
+                            t = t.right_;
+                    if (t is null)
+                        break;
+                }
+                return null;
+            }
+
+
+            /**
+             * Return number of nodes of current subtree containing element.
+             * Uses Comparator cmp to find and to check equality.
+             **/
+            public int count(T element, Comparator!(T) cmp) {
+                int c = 0;
+                auto t = this;
+                while (t !is null) {
+                    int diff = cmp.compare(element, t.element());
+                    if (diff is 0) {
+                        ++c;
+                        if (t.left_ is null)
+                            t = t.right_;
+                        else
+                            if (t.right_ is null)
+                                t = t.left_;
+                            else {
+                                c += t.right_.count(element, cmp);
+                                t = t.left_;
+                            }
+                    }
+                    else
+                        if (diff < 0)
+                            t = t.left_;
+                        else
+                            t = t.right_;
+                }
+                return c;
+            }
+            +/
+
+
+
+
+            /**
+             * Return a new subtree containing each element of current subtree
+             **/
+
+            public final Cell copyTree() {
+                auto t = cast(Cell)(duplicate());
+
+                if (left_ !is null) {
+                    t.left_ = left_.copyTree();
+                    t.left_.parent_ = t;
+                }
+                if (right_ !is null) {
+                    t.right_ = right_.copyTree();
+                    t.right_.parent_ = t;
+                }
+                return t;
+            }
+
+
+            /**
+             * There's no generic element insertion. Instead find the
+             * place you want to add a node and then invoke insertLeft
+             * or insertRight.
+             * <P>
+             * Insert Cell as the left child of current node, and then
+             * rebalance the tree it is in.
+             * @param Cell the Cell to add
+             * @param root, the root of the current tree
+             * Returns: the new root of the current tree. (Rebalancing
+             * can change the root!)
+             **/
+
+
+            public final Cell insertLeft(Cell Cell, Cell root) {
+                left_ = Cell;
+                Cell.parent_ = this;
+                return Cell.fixAfterInsertion(root);
+            }
+
+            /**
+             * Insert Cell as the right child of current node, and then
+             * rebalance the tree it is in.
+             * @param Cell the Cell to add
+             * @param root, the root of the current tree
+             * Returns: the new root of the current tree. (Rebalancing
+             * can change the root!)
+             **/
+
+            public final Cell insertRight(Cell Cell, Cell root) {
+                right_ = Cell;
+                Cell.parent_ = this;
+                return Cell.fixAfterInsertion(root);
+            }
+
+
+            /**
+             * Delete the current node, and then rebalance the tree it is in
+             * @param root the root of the current tree
+             * Returns: the new root of the current tree. (Rebalancing
+             * can change the root!)
+             **/
+
+
+            public final Cell remove (Cell root) {
+
+                // handle case where we are only node
+                if (left_ is null && right_ is null && parent_ is null)
+                    return null;
+
+                // if strictly internal, swap places with a successor
+                if (left_ !is null && right_ !is null) {
+                    auto s = successor();
+                    // To work nicely with arbitrary subclasses of Cell, we don't want to
+                    // just copy successor's fields. since we don't know what
+                    // they are.  Instead we swap positions _in the tree.
+                    root = swapPosition(this, s, root);
+                }
+
+                // Start fixup at replacement node (normally a child).
+                // But if no children, fake it by using self
+
+                if (left_ is null && right_ is null) {
+
+                    if (color_ is BLACK)
+                        root = this.fixAfterDeletion(root);
+
+                    // Unlink  (Couldn't before since fixAfterDeletion needs parent ptr)
+
+                    if (parent_ !is null) {
+                        if (this is parent_.left_)
+                            parent_.left_ = null;
+                        else
+                            if (this is parent_.right_)
+                                parent_.right_ = null;
+                        parent_ = null;
+                    }
+
+                }
+                else {
+                    auto replacement = left_;
+                    if (replacement is null)
+                        replacement = right_;
+
+                    // link replacement to parent
+                    replacement.parent_ = parent_;
+
+                    if (parent_ is null)
+                        root = replacement;
+                    else
+                        if (this is parent_.left_)
+                            parent_.left_ = replacement;
+                        else
+                            parent_.right_ = replacement;
+
+                    left_ = null;
+                    right_ = null;
+                    parent_ = null;
+
+                    // fix replacement
+                    if (color_ is BLACK)
+                        root = replacement.fixAfterDeletion(root);
+
+                }
+
+                return root;
+            }
+
+            /**
+             * Swap the linkages of two nodes in a tree.
+             * Return new root, in case it changed.
+             **/
+
+            static final Cell swapPosition(Cell x, Cell y, Cell root) {
+
+                /* Too messy. TODO: find sequence of assigments that are always OK */
+
+                auto px = x.parent_;
+                bool xpl = px !is null && x is px.left_;
+                auto lx = x.left_;
+                auto rx = x.right_;
+
+                auto py = y.parent_;
+                bool ypl = py !is null && y is py.left_;
+                auto ly = y.left_;
+                auto ry = y.right_;
+
+                if (x is py) {
+                    y.parent_ = px;
+                    if (px !is null)
+                        if (xpl)
+                            px.left_ = y;
+                        else
+                            px.right_ = y;
+                    x.parent_ = y;
+                    if (ypl) {
+                        y.left_ = x;
+                        y.right_ = rx;
+                        if (rx !is null)
+                            rx.parent_ = y;
+                    }
+                    else {
+                        y.right_ = x;
+                        y.left_ = lx;
+                        if (lx !is null)
+                            lx.parent_ = y;
+                    }
+                    x.left_ = ly;
+                    if (ly !is null)
+                        ly.parent_ = x;
+                    x.right_ = ry;
+                    if (ry !is null)
+                        ry.parent_ = x;
+                }
+                else
+                    if (y is px) {
+                        x.parent_ = py;
+                        if (py !is null)
+                            if (ypl)
+                                py.left_ = x;
+                            else
+                                py.right_ = x;
+                        y.parent_ = x;
+                        if (xpl) {
+                            x.left_ = y;
+                            x.right_ = ry;
+                            if (ry !is null)
+                                ry.parent_ = x;
+                        }
+                        else {
+                            x.right_ = y;
+                            x.left_ = ly;
+                            if (ly !is null)
+                                ly.parent_ = x;
+                        }
+                        y.left_ = lx;
+                        if (lx !is null)
+                            lx.parent_ = y;
+                        y.right_ = rx;
+                        if (rx !is null)
+                            rx.parent_ = y;
+                    }
+                    else {
+                        x.parent_ = py;
+                        if (py !is null)
+                            if (ypl)
+                                py.left_ = x;
+                            else
+                                py.right_ = x;
+                        x.left_ = ly;
+                        if (ly !is null)
+                            ly.parent_ = x;
+                        x.right_ = ry;
+                        if (ry !is null)
+                            ry.parent_ = x;
+
+                        y.parent_ = px;
+                        if (px !is null)
+                            if (xpl)
+                                px.left_ = y;
+                            else
+                                px.right_ = y;
+                        y.left_ = lx;
+                        if (lx !is null)
+                            lx.parent_ = y;
+                        y.right_ = rx;
+                        if (rx !is null)
+                            rx.parent_ = y;
+                    }
+
+                bool c = x.color_;
+                x.color_ = y.color_;
+                y.color_ = c;
+
+                if (root is x) {
+                    root = y;
+                }
+                else {
+                    if (root is y)
+                        root = x;
+                }
+                return root;
+            }
+
+
+
+            /**
+             * Return color of node p, or BLACK if p is null
+             * (In the CLR version, they use
+             * a special dummy `nil' node for such purposes, but that doesn't
+             * work well here, since it could lead to creating one such special
+             * node per real node.)
+             *
+             **/
+
+            static final bool colorOf(Cell p) {
+                return (p is null) ? BLACK : p.color_;
+            }
+
+            /**
+             * return parent of node p, or null if p is null
+             **/
+            static final Cell parentOf(Cell p) {
+                return (p is null) ? null : p.parent_;
+            }
+
+            /**
+             * Set the color of node p, or do nothing if p is null
+             **/
+
+            static final void setColor(Cell p, bool c) {
+                if (p !is null)
+                    p.color_ = c;
+            }
+
+            /**
+             * return left child of node p, or null if p is null
+             **/
+
+            static final Cell leftOf(Cell p) {
+                return (p is null) ? null : p.left_;
+            }
+
+            /**
+             * return right child of node p, or null if p is null
+             **/
+
+            static final Cell rightOf(Cell p) {
+                return (p is null) ? null : p.right_;
+            }
+
+
+            /** From CLR **/
+            protected final Cell rotateLeft(Cell root) {
+                auto r = right_;
+                right_ = r.left_;
+                if (r.left_ !is null)
+                    r.left_.parent_ = this;
+                r.parent_ = parent_;
+                if (parent_ is null)
+                    root = r;
+                else {
+                    if (parent_.left_ is this)
+                        parent_.left_ = r;
+                    else
+                        parent_.right_ = r;
+                }
+                r.left_ = this;
+                parent_ = r;
+                return root;
+            }
+
+            /** From CLR **/
+            protected final Cell rotateRight(Cell root) {
+                auto l = left_;
+                left_ = l.right_;
+                if (l.right_ !is null)
+                    l.right_.parent_ = this;
+                l.parent_ = parent_;
+                if (parent_ is null) {
+                    root = l;
+                }
+                else {
+                    if (parent_.right_ is this)
+                        parent_.right_ = l;
+                    else
+                        parent_.left_ = l;
+                }
+                l.right_ = this;
+                parent_ = l;
+                return root;
+            }
+
+
+            /** From CLR **/
+            protected final Cell fixAfterInsertion(Cell root) {
+                color_ = RED;
+                auto x = this;
+
+                while (x !is null && x !is root && x.parent_.color_ is RED) {
+                    if (parentOf(x) is leftOf(parentOf(parentOf(x)))) {
+                        auto y = rightOf(parentOf(parentOf(x)));
+                        if (colorOf(y) is RED) {
+                            setColor(parentOf(x), BLACK);
+                            setColor(y, BLACK);
+                            setColor(parentOf(parentOf(x)), RED);
+                            x = parentOf(parentOf(x));
+                        }
+                        else {
+                            if (x is rightOf(parentOf(x))) {
+                                x = parentOf(x);
+                                root = x.rotateLeft(root);
+                            }
+                            setColor(parentOf(x), BLACK);
+                            setColor(parentOf(parentOf(x)), RED);
+                            if (parentOf(parentOf(x)) !is null) {
+                                root = parentOf(parentOf(x)).rotateRight(root);
+                            }
+                        }
+                    }
+                    else {
+                        auto y = leftOf(parentOf(parentOf(x)));
+                        if (colorOf(y) is RED) {
+                            setColor(parentOf(x), BLACK);
+                            setColor(y, BLACK);
+                            setColor(parentOf(parentOf(x)), RED);
+                            x = parentOf(parentOf(x));
+                        }
+                        else {
+                            if (x is leftOf(parentOf(x))) {
+                                x = parentOf(x);
+                                root = x.rotateRight(root);
+                            }
+                            setColor(parentOf(x), BLACK);
+                            setColor(parentOf(parentOf(x)), RED);
+                            if (parentOf(parentOf(x)) !is null)
+                                root = parentOf(parentOf(x)).rotateLeft(root);
+                        }
+                    }
+                }
+                root.color_ = BLACK;
+                return root;
+            }
+
+
+
+            /** From CLR **/
+            protected final Cell fixAfterDeletion(Cell root) {
+                auto x = this;
+                while (x !is root && colorOf(x) is BLACK) {
+                    if (x is leftOf(parentOf(x))) {
+                        auto sib = rightOf(parentOf(x));
+                        if (colorOf(sib) is RED) {
+                            setColor(sib, BLACK);
+                            setColor(parentOf(x), RED);
+                            root = parentOf(x).rotateLeft(root);
+                            sib = rightOf(parentOf(x));
+                        }
+
+                        if (colorOf(leftOf(sib)) is BLACK && colorOf(rightOf(sib)) is BLACK) {
+                            setColor(sib, RED);
+                            x = parentOf(x);
+                        }
+                        else {
+                            if (colorOf(rightOf(sib)) is BLACK) {
+                                setColor(leftOf(sib), BLACK);
+                                setColor(sib, RED);
+                                root = sib.rotateRight(root);
+                                sib = rightOf(parentOf(x));
+                            }
+                            setColor(sib, colorOf(parentOf(x)));
+                            setColor(parentOf(x), BLACK);
+                            setColor(rightOf(sib), BLACK);
+                            root = parentOf(x).rotateLeft(root);
+                            x = root;
+                        }
+                    }
+                    else {
+                        auto sib = leftOf(parentOf(x));
+                        if (colorOf(sib) is RED) {
+                            setColor(sib, BLACK);
+                            setColor(parentOf(x), RED);
+                            root = parentOf(x).rotateRight(root);
+                            sib = leftOf(parentOf(x));
+                        }
+                        if (colorOf(rightOf(sib)) is BLACK && colorOf(leftOf(sib)) is BLACK) {
+                            setColor(sib, RED);
+                            x = parentOf(x);
+                        }
+                        else {
+                            if (colorOf(leftOf(sib)) is BLACK) {
+                                setColor(rightOf(sib), BLACK);
+                                setColor(sib, RED);
+                                root = sib.rotateLeft(root);
+                                sib = leftOf(parentOf(x));
+                            }
+                            setColor(sib, colorOf(parentOf(x)));
+                            setColor(parentOf(x), BLACK);
+                            setColor(leftOf(sib), BLACK);
+                            root = parentOf(x).rotateRight(root);
+                            x = root;
+                        }
+                    }
+                }
+                setColor(x, BLACK);
+                return root;
+            }
+        }
+
+        Cell _root;
+        size_t _size;
+    }
+}
+unittest {
+    auto s = new Set!(int);
+}
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/containers/vector.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doodle/containers/vector.d	Mon Apr 12 14:01:54 2010 +0930
@@ -0,0 +1,191 @@
+module delve.util.vector;
+
+class Vector(T) {
+    this() {
+        _data.length = 1;
+    }
+
+    bool isEmpty() {
+        return _length == 0;
+    }
+
+    size_t length() {
+        return _length;
+    }
+
+    void length(size_t l) {
+        if (l > _data.length) {
+            size_t new_l = _data.length;
+            do new_l *= 2; while (new_l < l);
+            _data.length = new_l;
+        }
+
+        if (l < _length) {
+            foreach(t; _data[l.._length]) {
+                t = T.init;
+            }
+        }
+
+        _length = l;
+    }
+
+    T first() {
+        assert(!isEmpty());
+        return _data[0];
+    }
+
+    void first(T t) {
+        assert(!isEmpty());
+        _data[0] = t;
+    }
+
+    T last() {
+        assert(!isEmpty);
+        return _data[_length - 1];
+    }
+
+    void last(T t) {
+        assert(!isEmpty);
+        _data[_length - 1] = t;
+    }
+
+    void push(T t) {
+        if (_length == _data.length) {
+            // Need it to grow
+            _data.length = 2 * _data.length;
+        }
+
+        _data[_length] = t;
+        ++_length;
+    }
+
+    T pop() {
+        assert(_length > 0);
+        --_length;
+        auto t = _data[_length];
+        _data[_length] = T.init;
+        return t;
+    }
+
+    void shrink() {
+        size_t new_l = _data.length;
+        do new_l /= 2; while (new_l > _length * 2);
+        _data.length = new_l;
+    }
+
+    void capacity(size_t l) {
+        if (l > _data.length) {
+            size_t new_l = _data.length;
+            do new_l *= 2; while (new_l < l);
+            _data.length = new_l;
+        }
+    }
+
+    size_t capacity() {
+        return _data.length;
+    }
+
+    void clear() {
+        while (_length > 0) {
+            --_length;
+            _data[_length] = T.init;
+        }
+    }
+
+    int opApply(int delegate (inout T) dg) {
+        int result;
+
+        for (size_t i = 0; i < _length; ++i) {
+            auto t = _data[i];
+            result = dg(t);
+            if (result != 0) {
+                break;
+            }
+        }
+
+        return result;
+    }
+
+    T opIndex(int i) {
+        assert(i < _length && i >= 0);
+        return _data[i];
+    }
+
+    void opIndex(T t, int i) {
+        assert(i < _length && i >= 0);
+        _data[i] = t;
+    }
+
+    class Iterator {
+        T element() {
+            return *_element;
+        }
+
+        void element(T t) {
+            *_element = t;
+        }
+
+        void forward() {
+            --_element;
+        }
+
+        void backward() {
+            ++_element;
+        }
+
+        void opEquals(Iterator other) {
+            return cast(int)(_element == other._element);
+        }
+
+        private {
+            this(ref T t) {
+                _element = &t;
+            }
+
+            T * _element;
+        }
+    }
+
+    /*
+    Iterator find(T t) {
+    }
+    */
+
+    private {
+        T[] _data;          // capacity
+        size_t _length;
+    }
+}
+unittest {
+    auto v = new Vector!(int);
+
+    assert(v.length() == 0);
+    assert(v.isEmpty());
+    assert(v.capacity() == 1);
+
+    v.push(1);
+    assert(v[0] == 1);
+    assert(v.length() == 1);
+    assert(v.first() == 1);
+    assert(v.last() == 1);
+    assert(v.capacity() == 1);
+
+    v.push(2);
+    assert(v[1] == 2);
+    assert(v.length() == 2);
+    assert(v.first() == 1);
+    assert(v.last() == 2);
+    assert(v.capacity() == 2);
+
+    v.pop();
+    assert(v.length() == 1);
+    assert(v.first() == 1);
+    assert(v.last() == 1);
+    assert(v.capacity() == 2);
+
+    v.shrink();
+    assert(v.capacity() == 1);
+
+    v.first(100);
+    assert(v.first == 100);
+}
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/core/logging.d
--- a/doodle/core/logging.d	Fri Apr 09 15:19:14 2010 +0930
+++ b/doodle/core/logging.d	Mon Apr 12 14:01:54 2010 +0930
@@ -45,6 +45,8 @@
             return modifier_string(Modifier.BRIGHT) ~ fg_color_string(Color.RED);
         case Severity.FATAL:
             return modifier_string(Modifier.BRIGHT) ~ bg_color_string(Color.RED) ~ fg_color_string(Color.WHITE);
+        default:
+            assert(0);
         }
         assert(0);
     }
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/dia/standard_tools.d
--- a/doodle/dia/standard_tools.d	Fri Apr 09 15:19:14 2010 +0930
+++ b/doodle/dia/standard_tools.d	Mon Apr 12 14:01:54 2010 +0930
@@ -39,10 +39,10 @@
 
             switch (event.scroll_direction) {
             case ScrollDirection.UP:
-                delta = event.mask.is_set(Modifier.SHIFT) ? Vector(AMOUNT, 0.0) : Vector(0.0, AMOUNT);
+                delta = event.mask.is_set(Modifier.SHIFT) ? Vector(-AMOUNT, 0.0) : Vector(0.0, AMOUNT);
                 break;
             case ScrollDirection.DOWN:
-                delta = event.mask.is_set(Modifier.SHIFT) ? Vector(-AMOUNT, 0.0) : Vector(0.0, -AMOUNT);
+                delta = event.mask.is_set(Modifier.SHIFT) ? Vector(AMOUNT, 0.0) : Vector(0.0, -AMOUNT);
                 break;
             case ScrollDirection.LEFT:
                 delta = Vector(-AMOUNT, 0.0);
@@ -50,6 +50,8 @@
             case ScrollDirection.RIGHT:
                 delta = Vector(AMOUNT, 0.0);
                 break;
+            default:
+                assert(0);
             }
 
             viewport.pan_relative(delta);
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/gtk/canvas.d
--- a/doodle/gtk/canvas.d	Fri Apr 09 15:19:14 2010 +0930
+++ b/doodle/gtk/canvas.d	Mon Apr 12 14:01:54 2010 +0930
@@ -6,6 +6,7 @@
 }
 
 private {
+    import doodle.core.logging;
     import doodle.gtk.conversions;
     import doodle.tk.misc;
     import doodle.cairo.routines;
@@ -52,6 +53,7 @@
 
         // Create our child widgets and register callbacks
 
+        info("B1");
         mHRuler = new HRuler;
         attach(mHRuler,
                1, 2,
@@ -60,13 +62,16 @@
                0, 0);
         mHRuler.setMetric(MetricType.PIXELS);
 
+        info("B2");
         mVRuler = new VRuler;
         attach(mVRuler,
                0, 1,
                1, 2,
                AttachOptions.SHRINK, AttachOptions.FILL | AttachOptions.EXPAND,
                0, 0);
+        info("B3");
         mVRuler.setMetric(MetricType.PIXELS);
+        info("J");
 
         mDrawingArea = new DrawingArea;
         mDrawingArea.addOnRealize(&on_realize);
@@ -92,6 +97,7 @@
                                EventMask.LEAVE_NOTIFY_MASK |
                                EventMask.FOCUS_CHANGE_MASK |
                                EventMask.SCROLL_MASK);
+        info("M");
 
         attach(mDrawingArea,
                1, 2,
@@ -110,6 +116,7 @@
                2, 3,
                AttachOptions.FILL | AttachOptions.EXPAND, AttachOptions.SHRINK,
                0, 0);
+        info("Q");
 
         mVAdjustment = new Adjustment(0.0, 0.0, 1.0, 0.2, 0.5, 0.5);
         mVAdjustment.addOnValueChanged(&onValueChanged);
@@ -160,6 +167,8 @@
         case Cursor.CROSSHAIR:
             cursor_type = CursorType.CROSSHAIR;
             break;
+        default:
+            assert(0);
         }
 
         mDrawingArea.setCursor(new gdk.Cursor.Cursor(cursor_type));
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/main/prog/doodler.d
--- a/doodle/main/prog/doodler.d	Fri Apr 09 15:19:14 2010 +0930
+++ b/doodle/main/prog/doodler.d	Mon Apr 12 14:01:54 2010 +0930
@@ -17,6 +17,7 @@
 }
 
 void main(string[] args) {
+    trace("Test trace");
     /+
     trace("Test trace");
     info("Test trace");
@@ -26,25 +27,37 @@
     fatal("Test trace");
     +/
 
+    trace("Test trace1");
     Main.init(args);
+    trace("Test trace2");
     auto window = new MainWindow("Doodle");
+    trace("Test trace3");
     auto vbox = new VBox(false, 0);
+    trace("Test trace4");
     auto tool_bar = new ToolBar;
+    trace("Test trace5");
     vbox.packStart(tool_bar, false, false, 0);
     Tool[] tools;
     tools ~= new PanTool;
     tools ~= new ZoomTool;
     tools ~= new LassoTool;
+    trace("Test trace4");
     auto tool_layer = new ToolLayer(tools, "Tools");
     auto grid_layer = new GridLayer("Grid");
     Layer[] layers;
+    trace("Test trace5");
     layers ~= new PageLayer("Page");
     layers ~= grid_layer;
     layers ~= tool_layer;
+    trace("Test trace6");
     auto canvas = new Canvas(layers, tool_layer, grid_layer, 120.0);
+    trace("Test trace7");
     vbox.packStart(canvas, true, true, 0);
+    trace("Test trace8");
     window.add(vbox);
+    trace("Test trace9");
     window.setDefaultSize(380, 380);
     window.showAll();
+    trace("Test trace8");
     Main.run();
 }
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/tk/geometry.d
--- a/doodle/tk/geometry.d	Fri Apr 09 15:19:14 2010 +0930
+++ b/doodle/tk/geometry.d	Mon Apr 12 14:01:54 2010 +0930
@@ -271,7 +271,7 @@
     // This is a commmon building block for intersection of lines and segments
     // Two lines "a" and "b" are defined by two points each .
     // "ua" and "ub" define the intersection as a fraction along
-    // the two respetive line segments (FIXME this comment sucks)
+    // the two respective line segments (FIXME this comment sucks)
     // Influenced by http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
     bool compute_intersection(in Point pa1, in Point pa2, out double ua,
                               in Point pb1, in Point pb2, out double ub) {
diff -r b6c34f1fc7f3 -r 1f97022e5c6d doodle/undo/undo.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doodle/undo/undo.d	Mon Apr 12 14:01:54 2010 +0930
@@ -0,0 +1,66 @@
+module doodle.undo.undo;
+
+// http://doc.trolltech.com/4.2/qundo.html
+// http://www.codeproject.com/KB/cs/undo_support.aspx
+
+// rename Action to Edit?
+
+// Related design patterns: Command, Memento
+
+// Action represents and encapsulates the information needed 
+// Consider command merging and time-stamping of commands
+
+abstract class Action {
+    void undo();
+    void redo();
+    //string description() const;
+    // bool merge(Action other);
+    // time-stamp
+}
+
+final class CompoundAction {
+    this(in Action[] sub_actions) {
+        mSubActions = sub_actions.dup;
+    }
+
+    void undo() {
+        foreach_reverse(a; mSubActions) { a.undo(); }
+    }
+
+    void redo() {
+        foreach(a; mSubActions) { a.redo(); }
+    }
+
+    private {
+        Action[] mSubActions;
+    }
+}
+
+interface IUndoManagerObserver {
+    void canUndo(in bool value, in string description);
+    void canRedo(in bool value, in string description);
+}
+
+interface IUndoManager {
+    void addAction(Action action);
+    void undo();
+    void redo();
+    // bool can_undo() const;
+    // bool can_redo() const;
+}
+
+class UndoManager : IUndoManager {
+    this(int max_undo_level = -1) {
+    }
+
+    void addAction(Action action);
+    void undo();
+    void redo();
+
+    // IUndoManager overrides:
+
+    private {
+        Action[] mUndoActions;
+        Action[] mRedoActions;
+    }
+}
diff -r b6c34f1fc7f3 -r 1f97022e5c6d options
--- a/options	Fri Apr 09 15:19:14 2010 +0930
+++ b/options	Mon Apr 12 14:01:54 2010 +0930
@@ -1,4 +1,5 @@
--I~/Development/d/local/include/d
--O
+-I~/source/d/local/include/d
 -L-lgtkd
 -L-ldl
+-w
+-wi