//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;

//import RedBlackTree;


import tango.util.collection.model.SortedValues;





/******************************************************************************
    An Iterator that iterates over the elements of a RedBlackTree.

    Params:
    Node = the node type of the collection.

    Remarks:
    Iterates over the elements of a RedBlackTree in the direction specified in
    the constructor. If the tree changes, iteration will stop even if there are
    more elements to enumerate.
 ******************************************************************************/
class RBIterator(KeyType, Node, ParentIterator) : ParentIterator {
    mixin RBIterMixins!(KeyType, Node, ParentIterator);

    /****************************************************************
        Apply a delegate to the rest of the elements in the enumeration.
        
        Params:
        dg = a delegate to apply to each element of the iteration.
        
        Remarks:
        Although the paramater to the delegate is an inout, changing
        the value will not change the value in the underlying collection.
        This is to maintain order in the collection and speed in the
        enumeration.
        
        Returns:
        If the delegate returns a non-zero value, that value is returned.
        Otherwise, when all elements have been enumerated, 0 is returned.
     ****************************************************************/
    int opApply(int delegate(inout KeyType value) dg) {
        while (more()) {
            KeyType t = get();
            int ret = dg(t);
            if (ret) return ret;
        }
        return 0;
    }
}







/*
 */
class Node(V) : public BasicNode!(V, Node!(V)) {
    

    /*
     */
    this(V v) {
        super(v);
    }
    

    /*
     */
    this () {
    }
    

    /*
     */
    V value() {
        return key;
    }
}






/*
 */
template SingleRedBlackTreeTraitsMixin(V) {
    alias V KeyTypeT;
    alias V ValueTypeT;
    alias Node!(V) NodeT;
    alias RBIterator!(V, NodeT, Iterator!(V)) IteratorT;
    alias RBIterator!(V, NodeT, GuardIterator!(V)) GuardIteratorT;
    const bool DUAL_ITERATION = false;
}
    




/*
 */
abstract class SingleRedBlackTree(alias Traits) :
    RedBlackTree!(Traits), SortedValues!(Traits.KeyTypeT) {
    

    /*
     */
    this() {}
    

    /*
     */
    this(ComparatorT cmp, Node tree, uint size) {
        super(cmp, tree, size);
    }
    
    /*
     */
    bool contains(ValueType v) {
        return contains_(v);
    }
    

    /*
     */
    ComparatorT comparator() {
        return mComparator;
    }


    /*
     */
    void add(KeyType obj) {
        insert_(obj, new Node(obj), SINGLETON);
    }
    

    /*
     */
    void replace(KeyType oldElement, KeyType newElement) {
        uint size = count;
        remove(oldElement);
        if (count != size) {
            add(newElement);
        }
    }
    

    /*
     */
    void replaceAll(KeyType oldElement, KeyType newElement) {
        scope auto iter = new IteratorT(getFirstElement(oldElement));
        while (iter.more()) {
            KeyType v = iter.get();
            if (v != oldElement)
                break;
            remove(v);
            add(newElement);
        }
    }
    

    /*
     */
    void removeAll(KeyType obj) {
        int startSize = 0;
        while (startSize != count) {
            startSize = count;
            remove(obj);
        }
    }
    

    /*
     */
    ValueType take() {
        checkIndex(0);
        KeyType value = mRoot.key;
        remove(value);
        return value;
    }
    

    /*
     */
    uint instances(ValueType obj) {
        scope auto iter = new IteratorT(getFirstElement(obj));
        uint count = 0;
        while (iter.more()) {
            ValueType t = iter.get();
            if (mComparator(t, obj))
                break;
            count++;
        }
        return count;
    }
}

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







    

//import  SingleRedBlackTree;

import  tango.util.collection.impl.BagCollection;

    

/*
 */
template BagTraits(V) {
    mixin SingleRedBlackTreeTraitsMixin!(V);
    alias BagCollection!(V) ParentCollectionT;
    const bool SINGLETON = false;
}






    

/*
 */
class BagTree(V) : SingleRedBlackTree!(BagTraits!(V)) {
    

    /*
     */
    BagTree!(KeyType) duplicate() {
        if (drained()) {
            return new BagTree(mComparator, null, 0);
        }
        return new BagTree(mComparator, mRoot.copyOf(), count);
    }
    

    /*
     */
    this() {}
    

    /*
     */
    protected this(ComparatorT c, Node tree, uint size) {
        super(c, tree, size);
    }
    

    /*
     */
    void addIf(KeyType obj) {
        insert_(obj, new Node(obj), true);
    }
}

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

//import SingleRedBlackTree;

import tango.util.collection.impl.SetCollection;



    

/*
 */
template SetTraits(V) {
    mixin SingleRedBlackTreeTraits!(V);
    alias SetCollection!(V) ParentCollectionT;
    const bool SINGLETON = true;
}

    

/*
 */
class SetTree(V) : SingleRedBlackTree!(SetTraits!(V)) {

    

    /*
     */
    this(ComparatorT c) {
        super(c, null, 0);
    }
    

    /*
     */
    private this(ComparatorT cmp, Node tree, uint size) {
        super(cmp, tree, size);
    }
    

    /*
     */
    this() { }
    

    /*
     */
    SetTree!(KeyType) duplicate() {
        if (drained()) {
            return new SetTree(mComparator, null, 0);
        }
        return new SetTree(mComparator, mRoot.copyOf(), count);
    }
}
/+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/

/*
module  MapTree;
import  RedBlackTree;
*/

import  tango.util.collection.impl.MapCollection,
        tango.util.collection.model.SortedKeys,
        tango.util.collection.model.Iterator,
        tango.util.collection.model.GuardIterator;


class PairNode(K, V) : public BasicNode!(K, PairNode!(K, V)) {
    V mValue;
    this(K k, V v) {
        super(k);
        mValue = v;
    }
    this() {
        super();
    }
    V value() {
        return mValue;
    }
}



class PairRedBlackIterator(KeyType, ValueType, Node, ParentIterator) : ParentIterator {
    mixin RBIterMixins!(ValueType, Node, ParentIterator);

    ValueType get() {
        KeyType k;
        return get(k);
    }
    ValueType get(inout KeyType key) {
        assert(more());
        ValueType data = mNode.mValue;
        key = mNode.key;
        advanceNode();
        return data;
    }

    int opApply(int delegate(inout KeyType, inout ValueType) dg) {
        while (more()) {
            auto curNode = mNode;
            KeyType t = curNode.key;
            advanceNode();
            int ret = dg(t, curNode.mValue);
            if (ret) return ret;
        }
        return 0;
    }
    int opApply(int delegate(inout ValueType) dg) {
        while (more()) {
            auto curNode = mNode;
            advanceNode();
            int ret = dg(curNode.mValue);
            if (ret) return ret;
        }
        return 0;
    }
}



template MapTraits(K, V) {
    alias K KeyTypeT;
    alias V ValueTypeT;
    alias PairNode!(K, V) NodeT;
    alias PairRedBlackIterator!(K, V, NodeT, Iterator!(V)) IteratorT;
    alias PairRedBlackIterator!(K, V, NodeT, PairIterator!(K, V)) GuardIteratorT;
    
    alias MapCollection!(K, V) ParentCollectionT;
    const bool SINGLETON = true;
    const bool DUAL_ITERATION = true;
}

class MapTree(KeyType, V) : RedBlackTree!(MapTraits!(KeyType, V)), SortedKeys!(KeyType, V) {
    this() {}
    protected this(ComparatorT cmp, Node n, int size) {
        super(cmp, n, size);
    }
 
    void add(KeyType k, ValueType v) {
        uint startCount = count;
        Node n = insert_(k, new Node(k, v));
        if (count == startCount) {
            n.mValue = v;
        }
    }

    ComparatorT comparator() {
        return mComparator;
    }
    

    void removeKey(KeyType k) {
        return super.remove(k);
    }

    bool containsKey(KeyType k) {
        return contains_(k);
    }


    GuardIteratorT keys() {
        return elements;
    }
    
    uint instances(ValueType obj) {
        scope auto iter = iterator();
        uint count = 0;
        while (iter.more()) {
            ValueType v = iter.get();
            if (v == obj) {
                count++;
            }
        }
        return count;
    }
    
    bool contains(ValueType obj) {
        scope auto iter = iterator();
        while (iter.more()) {
            ValueType v = iter.get();
            if (v == obj)
                return true;
        }
        return false;
    }

    bool get(KeyType k, inout ValueType v) {
        auto n = getFirstElement(k);
        if (n is null)
            return false;
        v = n.mValue;
        return true;
    }

    ValueType get(KeyType k) {
        ValueType v;
        if (!get(k, v))
            checkIndex(count);
        return v;
    }

    bool containsPair(KeyType k, ValueType v) {
        auto n = getFirstElement(k);
        return !(n is null || v == n.mValue) ;
    }
    
    bool keyOf(inout KeyType k, ValueType v) {
        scope auto iter = iterator();
        while (iter.more()) {
            ValueType ov = iter.get(k);
            if (ov == v)
                return true;
        }
        return false;
    }
    
    MapTree!(KeyType, ValueType) duplicate() {
        if (drained()) {
            return new MapTree(mComparator, null, 0);
        }
        return new MapTree(mComparator, mRoot.copyOf(), count);
    }
    
    void remove(ValueType v) {
        foreach (k, ov; this) {
            if (ov == v) {
                removeKey(k);
                break;
            }
        }
    }
    
    void replacePair(KeyType key, ValueType oldValue, ValueType newValue) {
        Node n = getFirstElement(key);
        if (n is null)
            return;
        if (n.mValue == oldValue) {
            n.mValue = newValue;
        }
    }
    
    ValueType take() {
        checkIndex(0);
        ValueType v = mRoot.mValue;
        removeKey(mRoot.key);
        return v;
    }
    
    void removeAll(ValueType v) {
        foreach (k, ov; iterator()) {
            if (ov == v) {
                removeKey(k);
            }
        }
    }
    
    void replace(ValueType oldElement, ValueType newElement) {
        foreach (k, ov; this) {
            if (ov == oldElement) {
                ov = newElement;
                break;
            }
        }
    }
    
    void replaceAll(ValueType oldElement, ValueType newElement) {
        foreach (k, ov; this) {
            if (ov == oldElement) {
                ov = newElement;
            }
        }
    }
}


import tango.io.Stdout;
int main() {
    auto t = new MapTree!(int, double);
    t.add(1, 4.1);
    t.add(2, 4.1);
    t.add(2, 5.1);
    t[4] = 5;
    t.removeAll(4.1);
    double v;
    foreach_reverse (i, j; t)
        Stdout(i)(' ')(j).newline;
    foreach (i; t)
        Stdout(i).newline;
    Stdout("Size =")(t.size).newline;
    try {
        foreach (j;t) {
            t.remove(j);
            Stdout("removing! Size=")(t.size).newline;
        }
    } catch {
        Stdout("Caught!");
    }
    return 0;
}