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);
}