//module RedBlackTree;

import  tango.util.collection.model.Comparator,
        tango.util.collection.model.GuardIterator,
        tango.util.collection.model.Iterator;

// TODO should these be in Basic Node?

// The two children of a node
enum {Left = 0, Right}

// Tags the links of a node
enum Tag {Thread = 0, Child}





/*******************************************************************************
    The basic structure of a node needed for the RedBlackTree.
    
    Remarks:
    This class is meant to be overriden using the Curriosly Reoccuring Template
    Pattern (CRTP). Each subclass must expose a default constructor.
    
    Examples:
    ---
    class Node(V) : BasicNode!(V, Node!(V)) {
        alias V KeyType;
        this() {}
        
    }
    ---
*******************************************************************************/
abstract class BasicNode(KeyType, NodeType) {
    alias KeyType KeyTypeT;
protected:
    // the data used in comparison
    protected KeyType key;
    
    /****************************************************************
        Construct a new node.
    
        Params:
        value = the value to store in the node
     ****************************************************************/
    this(KeyType value) {
        this();
        key = value;
    }


    /****************************************************************
        Construct a new node without any data.
     ****************************************************************/
    this() {
        red = true;
        link[Left] = null;
        link[Right] = null;
        tag[Left] = Tag.Thread;
        tag[Right] = Tag.Thread;
    }


protected:
    // is the node red (as opposed to black)
    bool red;
    
    // the two children/thread nodes
    NodeType[2] link;
    
    // tag the links as children or threads
    Tag[2] tag;
    

    /****************************************************************
        Get either the first or last descendant of the sub-tree.
        
        Params:
        dir = which direction to go, use Left or Right.
        
        Remarks:
        Traverse down the tree, returning the the node containing
        either the smallest or the largest value, depending on dir
        and the comparotor in use.        
        
        Returns:
        The right- or left-most node of the sub-tree
     ****************************************************************/
    NodeType end(int dir) {
        NodeType n = cast(NodeType)this;
        while (n.tag[dir])
            n = n.link[dir];
        return n;
    }
    

    /****************************************************************
        Produce a deep copy of the node

        Returns the copied node.

     ****************************************************************/
    protected NodeType copyOf() {
        NodeType newNode = new NodeType();
        newNode.key = key;
        newNode.link[0] = link[0].copyOf();
        newNode.link[1] = link[1].copyOf();
        newNode.tag[] = tag;
        return newNode;
    }
}





template RBIterMixins(KeyType, Node, ParentIterator) {

    // the current node 
    protected Node mNode;

    // how many items left to enumerate
    uint countLeft;

    public Node node() {
        return mNode;
    }

    // the direction we are iterating
    private const int mDir;

    static if (is(ParentIterator : GuardIterator!(KeyType))) {
        // the latest tree version
        private const uint* mLatestVersion;
        // the tree version we are used to
        private const uint mVersion;

        /***************************************************************
            Construct a new iterator.
            
            Params:
            ver = the tree version number
            node = the start node of the iteration
            dir = the direction the iteration is going (default: Right)
         ***************************************************************/
        this(uint* ver, Node node, int dir = Right) {
            mNode = node;
            mDir = dir;
            mVersion = *ver;
            mLatestVersion = ver;
        }

        bool corrupted() {
            return mVersion != *mLatestVersion;
        }
        
        uint remaining() {
            return countLeft;
        }
    } else {
        this (Node node, int dir = Right) {
            mNode = node;
            mDir = dir;
        }
    }

    /****************************************************************
        Ask whether the enumeration can continue.
        
        Remarks:
        This iterator has more elements if the base tree has more
        elements and hasn't changed since the iterator's construction.
        
        Returns:
        True if the enumeration can continue, false otherwise
     ****************************************************************/
    bool more() {
        static if (is(ParentIterator : GuardIterator!(KeyType))) {
            if (corrupted())
                return false;
        }
        return mNode !is null;
    }

    /****************************************************************
        Get the next element from the iteration.
        
        Remarks:
        Returns the next element of the collection and advances the
        iterator. O(log n).
        
        Results are undefined if !more().
        
        Returns:
        The next element of the collection.
     ****************************************************************/
    KeyType get() {
        assert(more());
        KeyType data = mNode.value();
        advanceNode();
        return data;
    }
    
    protected void advanceNode() {        
        // if the next element is a thread, follow it
        if (!mNode.tag[mDir]) {
            mNode = mNode.link[mDir];
        
        // get the next descendant
        } else {
            mNode = mNode.link[mDir].end(!mDir);
        }
        countLeft--;
    }
}





/******************************************************************************
    A genericized RedBlackTree

    Params:
    TODO

    Remarks:
    TODO
 ******************************************************************************/
abstract class RedBlackTree(alias Traits) : Traits.ParentCollectionT {
    alias Traits.NodeT Node;
    alias Traits.KeyTypeT KeyType;
    alias Traits.ValueTypeT ValueType;
    alias Traits.IteratorT IteratorT;
    alias Traits.GuardIteratorT GuardIteratorT;
    
    alias Traits.SINGLETON SINGLETON;
    alias Traits.DUAL_ITERATION DUAL_ITERATION;
    
    alias Comparator!(KeyType) ComparatorT;


    // the root of the tree
    protected Node mRoot;
    
    // the comparing function
    protected ComparatorT mComparator;

    
    /***************************************************************
         Construct an empty RedBlackTree.
         
         Remarks:
         The objects natural ordering will be used.
     ***************************************************************/
    this() {
        this(null, null, 0);
    }
    

    /***************************************************************
         Construct a RedBlackTree using this comparator
         
         Params:
         c = 
     ***************************************************************/
    this(ComparatorT c, Node root, uint size) {
        //mRoot = root;
        vershion = 0;
        count = size;
        mComparator = c is null ? &compare : c;
    }
    
    /*
     */
    override void clear() {
        vershion = 0;
        mRoot = null;
        count = 0;
    }
    

    /*
     */
    protected Node first() {
        if (mRoot is null)
            return null;
        return mRoot.end(Left);
    }


    /*
     */
    protected Node last() {
        if (mRoot is null)
            return null;
        return mRoot.end(Right);
    }
    

    /*
     */
    GuardIteratorT elements() {
        return new GuardIteratorT(&vershion, first());
    }


    /*
     */
    GuardIteratorT reverseElements() {
        return new GuardIteratorT(&vershion, last(), Left);
    }
    

    /*
     */
    IteratorT iterator() {
        return new IteratorT(first());
    }


    /*
     */
    IteratorT reverseIterator() {
        return new IteratorT(last(), Left);
    }
    

    /*
     */
    protected bool contains_(KeyType obj) {
        return getFirstElement(obj) !is null;
    }
    

    /*
     */
    protected Node insert_(KeyType obj, lazy Node newNode, bool singletons=true) {
        if (mRoot is null) {
            mRoot = newNode;
            mRoot.red = false;
            setCount(1);
            return mRoot;
        }
        
        bool isInserted = false;
        
        auto fakeHead = new Node();
        int dir = Left, last = Left;
        
        Node great = fakeHead;
        Node grand = null;
        Node parent = null;
        Node current = fakeHead.link[Right] = mRoot;
        
        Tag grandTag = Tag.Thread;
        Tag parentTag = Tag.Child;
        
        for (;;) {
            if (!parentTag) {
                current = newNode;
                current.link[dir] = parent.link[dir];
                current.link[!dir] = parent;
                
                parent.link[dir] = current;
                parent.tag[dir] = parentTag = Tag.Child;
                
                isInserted = true;
                incCount();
            }
            
            // color flip
            else if (isRed(current, Left) && isRed(current, Right)) {
                current.red = true;
                current.link[Left].red = false;
                current.link[Right].red = false;
            }
            
            // fix red violation
            if (isRed(current, parentTag) && isRed(parent, grandTag)) {
                int dir2 = great.link[Right] is grand;
                
                if (current is parent.link[last])
                    great.link[dir2] = singleRotate(grand, !last);
                else
                    great.link[dir2] = doubleRotate(grand, !last);
            }
            
            // Stop if found
            int cmp = mComparator(current.key, obj);
            static if (SINGLETON) {
                if (!cmp)
                    break;
            } else {
                if (!cmp && (singletons || isInserted)) {
                    break;
                }
            }
            
            last = dir;
            dir = cmp < 0;
            
            // update helpers
            if (grand !is null) {
                great = grand;
            }
            
            grand = parent;
            parent = current;
            current = current.link[dir];
            
            grandTag = parentTag;
            parentTag = parent.tag[dir];
        }
        
        // update the root and make it black
        mRoot = fakeHead.link[Right];
        mRoot.red = false;
        
        return current;
    }
    

    /*
     */
    void remove(KeyType obj) {
        if (mRoot is null)
            return;// false;
        
        Node fakeHead = new Node();
        fakeHead.link[Right] = mRoot;
        fakeHead.tag[Right] = Tag.Child;
        
        Node current = fakeHead;
        Node parent = null;
        Node grand = null;
        Node found = null;
        
        int dir = Right;
        
        // search and push down red node
        while (current.tag[dir]) {
            int last = dir;
            
            // update helpers
            grand = parent;
            parent = current;
            current = current.link[dir];
            
            int cmp = mComparator(current.key, obj);
            dir = cmp < 0;
            
            // save the found node
            if (!cmp) {
                found = current;
            }
            
            // push the red node down
            if (!isRed(current, parent.tag[last]) && !isRed(current, dir)) {
                if (isRed(current, !dir)) {
                    parent = parent.link[last] = singleRotate(current, dir);
                } else {
                    Node save = parent.link[!last];
                    
                    if (parent.tag[!last]) {
                        if (!isRed(save, Left) && !isRed(save, Right)) {
                            // Color flip
                            parent.red = false;
                            save.red = true;
                            current.red = true;
                        } else {
                            int dir2 = grand.link[Right] is parent;
                            
                            if (isRed(save, last))
                                grand.link[dir2] = doubleRotate(parent, last);
                            else
                                grand.link[dir2] = singleRotate(parent, last);
                            
                            // ensure correct coloring
                            Node uncle = grand.link[dir2];
                            current.red = uncle.red = true;
                            uncle.link[Left].red = false;
                            uncle.link[Right].red = false;
                        }
                    }
                }
            }
        } // end while
        
        // replace and remove if found
        if (found !is null) {
            found.key = current.key;
            decCount();
            
            int replacementDir = parent.link[Right] is current;
            int otherDir = !replacementDir;
            
            //assert(!current.tag[otherDir]);
            //assert(current.link[otherDir] is parent || parent is fakeHead);
            
            parent.link[replacementDir] = current.link[replacementDir];
            parent.tag[replacementDir] = Tag.Thread;
        }
        
        // update the root and make it black
        mRoot = fakeHead.link[Right];
        if (mRoot !is null) {
            mRoot.red = false;
        }
        
        // return found !is null;
    }
    

    /*
     */
    void comparator(ComparatorT c) {
        if (c == null)
            mComparator = &compare;
        if (mComparator is c || !count)
            return;
        scope auto iter = iterator();

        auto node = iter.node;
        iter.get();
        while (iter.more()) {
            node.link[0] = node.link[1] = null;
            node.tag[0] = node.tag[1] = Tag.Thread;
            insert_(node.key, node);
            iter.get();
            node = iter.node;
        }
        node.link[0] = node.link[1] = null;
        node.tag[0] = node.tag[1] = Tag.Thread;
        insert_(node.key, node);

    }
    

    /*
     */
    int opApply(int delegate(inout ValueType) dg) {
        auto scope iter = elements();
        return iter.opApply(dg);
    }
    

    /*
     */
    int opApplyReverse(int delegate(inout ValueType) dg) {
        auto scope iter = reverseElements();
        return iter.opApply(dg);
    }
    

    /*
     */
    static if (DUAL_ITERATION) {
        int opApply(int delegate(inout KeyType, inout ValueType) dg) {
            scope auto iter = elements();
            return iter.opApply(dg);
        }
        int opApplyReverse(int delegate(inout KeyType, inout ValueType) dg) {
            scope auto iter = reverseElements();
            return iter.opApply(dg);
        }
    }


    // default comparison function
    private int compare(KeyType a, KeyType b) {
        static if (is(KeyType : Object)) {
            if (a is b)
                return 0;
            return a.opCmp(b);
        } else {
            KeyType cmp = a - b;
            return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
        }
    }
    

    /*
     */
    protected Node getFirstElement(KeyType obj) {
        if (mRoot is null) return null;
        
        Node cur = mRoot;
        auto parentTag = Tag.Child; 
        while (parentTag) {
            int cmp = mComparator(cur.key, obj);
            if (!cmp)
                return cur;
            
            int dir = cmp < 0;
            parentTag = cur.tag[dir];
            cur = cur.link[dir];
        }
        return null;
    }
    
    static if (false) {
    invariant {
        int checkImpl(Node n) {
            int lh, rh;
            
            if (n is null)
                return 1;
            
            auto ln = n.link[0];
            auto rn = n.link[1];
            
            /* Consecutive red */
            if (isRed(n, Tag.Child)) {
                if (isRed(ln, n.tag[0]) || isRed(rn, n.tag[1])) {
                    //Stdout("Red violation");
                    assert(false);
                }
            }
            
            lh = n.tag[0] ? checkImpl(ln) : 0;
            rh = n.tag[1] ? checkImpl(rn) : 0;
            
            /* invalid bst */
            if ((n.tag[0] && mComparator(ln.key, n.key) > 0) ||
                    n.tag[1] && mComparator(rn.key, n.key) < 0) {
                //Stdout("BST Violation");
                assert(false);
            }
            
            // black height mismatch
            if (lh != 0 && rh != 0 && lh != rh) {
                //Stdout("Black Violation");
                assert(false);
            }
            
            if (lh != 0 && rh != 0) {
                return isRed(n, Tag.Child) ? lh : lh + 1;
            }
            return 0;
        }
        
        checkImpl(mRoot);
    }
    }
    

    
    
private static:

    // helper methods
    
    Node singleRotate(Node node, int dir) {
        int otherDir = !dir;
        Node save = node.link[otherDir];
        // If save's thread points back to node, then just fix the tags
        if (!save.tag[dir]) {
            save.tag[dir] = Tag.Child;
            node.tag[otherDir] = Tag.Thread;
        
        // otherwise swap children
        } else {
            node.link[otherDir] = save.link[dir];
            save.link[dir] = node;
        }
        
        node.red = true;
        save.red = false;
        return save;
    }

    Node doubleRotate(Node node, int dir) {
        int otherDir = !dir;
        node.link[otherDir] = singleRotate(node.link[otherDir], otherDir);
        return singleRotate(node, dir);
    }

    bool isRed(Node node, Tag tag) {
        return tag && node.red;
    }

    bool isRed(Node node, int dir) {
        return isRed(node.link[dir], node.tag[dir]);
    }
}

/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/

//module SingleRedBlackTree;