using System;
using edu.neu.ccs.demeterf;
using Edge = edu.neu.ccs.demeterf.control.Edge;
using System.Collections.Generic;

namespace edu.neu.ccs.demeterf.lib{

    public abstract class RBTree<X> where X : IComparable<X>{
        protected static int CompComp(X a, X b){ return a.CompareTo(b); }

        public abstract bool isLeaf();
        public RBTree<X> insert(X x){ return insert(x, CompComp); }
        public RBTree<X> insert(X x, Comparison<X> comp){ return ins(x,comp).makeBlack(); }

        public RBTree<X> insertAll(RBTree<X> t){ return insertAll(t,CompComp); }
        public RBTree<X> insertAll(List<X> lst){ return insertAll(lst,CompComp); }
        public RBTree<X> insertAll(RBTree<X> t, Comparison<X> comp){ return insertAll(t.toList(),comp); }
        public RBTree<X> insertAll(List<X> lst, Comparison<X> comp){
            if(lst.isEmpty())return this;
            return insert(lst.top(),comp).insertAll(lst.pop(),comp);
        }

        public RBTree<X> remove(X x){ return remove(x,CompComp); }
        public abstract RBTree<X> remove(X x, Comparison<X> comp);

        internal abstract RBTree<X> del(X x, Comparison<X> comp);
        public abstract bool isBlack();
        public abstract bool isRed();
        public abstract RBNode<X> asNode();
        internal abstract RBTree<X> makeBlack();
        internal abstract RBTree<X> makeRed();
        internal abstract RBTree<X> ins(X x, Comparison<X> comp);

        public abstract X pred();
        public abstract X succ();
        public abstract X min();
        public abstract X max();
        public bool isBlackNode(){ return !isLeaf() && isBlack(); }
        public bool isRedNode(){ return !isLeaf() && isRed(); }
    
        public bool contains(X x){ return contains(x, CompComp); }
        public abstract bool contains(X x, Comparison<X> comp);

        public bool containsAll(RBTree<X> x){ return containsAll(x, CompComp); }
        public abstract bool containsAll(RBTree<X> x, Comparison<X> comp);
    
        public X find(X x){ return find(x, CompComp); }
        public abstract X find(X x, Comparison<X> comp);

        public RBTree<X> replace(X x){ return replace(x, CompComp); }
        public abstract RBTree<X> replace(X x, Comparison<X> comp);
        public abstract int size();
        
        public abstract List<X> toList();
    
        // A little messy... but better than keeping track of parents ;)
        internal static RBTree<X> balance<X>(X dat, RBTree<X> l, RBTree<X> r)
            where X : IComparable<X>{
            if(l.isRedNode() && r.isRedNode())
                return node(red(), dat, l.makeBlack(), r.makeBlack());
            if(l.isRedNode()){
                RBNode<X> L = l.asNode();
                if(L.GetLeft().isRedNode()){
                    RBNode<X> LL = L.GetLeft().asNode();
                    return node(red(), L.GetData(),
                                node(black(),LL.GetData(),LL.GetLeft(),LL.GetRight()),
                                node(black(),dat,L.GetRight(),r));
                }
                if(L.GetRight().isRedNode()){
                    RBNode<X> LR = L.GetRight().asNode();
                    return node(red(), LR.GetData(),
                                node(black(),L.GetData(),L.GetLeft(),LR.GetLeft()),
                                node(black(),dat,LR.GetRight(),r));
                }
            }
            if(r.isRedNode()){
                RBNode<X> R = r.asNode();
                if(R.GetLeft().isRedNode()){
                    RBNode<X> RL = R.GetLeft().asNode();
                    return node(red(), RL.GetData(),
                                node(black(),dat,l,RL.GetLeft()),
                                node(black(),R.GetData(),RL.GetRight(),R.GetRight()));
                }
                if(R.GetRight().isRedNode()){
                    RBNode<X> RR = R.GetRight().asNode();
                    return node(red(), R.GetData(),
                                node(black(),dat,l,R.GetLeft()),
                                node(black(),RR.GetData(),RR.GetLeft(),RR.GetRight()));
                }
            }
            return node(black(),dat,l,r);
        }
        internal static RBTree<X> balleft<X>(RBTree<X> l, X y, RBTree<X> r)
            where X : IComparable<X>{
            if(l.isRedNode())return node(red(),y,l.makeBlack(),r);
            if(r.isBlackNode())return balance(y,l,r.makeRed());
            RBNode<X> right = r.asNode();
            RBNode<X> rtlt = right.GetLeft().asNode();
            return node(red(),rtlt.GetData(),
                        node(black(),y,l,rtlt.GetLeft()),
                        balance(right.GetData(),rtlt.GetRight(),right.GetRight().makeRed()));
        }
        internal static RBTree<X> balright<X>(RBTree<X> l, X y, RBTree<X> r)
            where X : IComparable<X>{
            if(r.isRedNode())return node(red(),y,l,r.makeBlack());
            if(l.isBlackNode())return balance(y,l.makeRed(),r);
            RBNode<X> left = l.asNode();
            RBNode<X> ltrt = left.GetRight().asNode();
            return node(red(),ltrt.GetData(),
                        balance(left.GetData(),left.GetLeft().makeRed(),ltrt.GetLeft()),
                        node(black(),y,ltrt.GetRight(),r));
        }
        internal static RBTree<X> append<X>(RBTree<X> l, RBTree<X> r)
            where X : IComparable<X>{
            if(l.isLeaf())return r;
            if(r.isLeaf())return l;
            RBNode<X> left = l.asNode(),
                right = r.asNode();
            if(left.GetColor().Equals(right.GetColor())){
                RBColor c = left.GetColor();
                RBTree<X> rtlt = append(left.GetRight(),right.GetLeft());
                if(rtlt.isRedNode()){
                    RBNode<X> rln = rtlt.asNode();
                    return node(red(),rln.GetData(),
                                node(c,left.GetData(),left.GetLeft(),rln.GetLeft()),
                                node(c,right.GetData(),rln.GetRight(),right.GetRight()));
                }
                if(c.isRed())
                    return node(red(),left.GetData(),left.GetLeft(),
                                node(red(),right.GetData(),rtlt,right.GetRight()));
                return balleft(left.GetLeft(),left.GetData(),
                               node(black(),right.GetData(),rtlt,right.GetRight()));
            }
            if(right.isRed())
                return node(red(),right.GetData(),append(left,right.GetLeft()),right.GetRight());
            return node(red(),left.GetData(),left.GetLeft(),append(left.GetRight(),right));
        }
        public static RBColor black(){ return RBColor.black(); }
        public static RBColor red(){ return RBColor.red(); }
        public static RBTree<X> create<X>(params X[] xs) where X : IComparable<X>{
            return create<X>((IEnumerable<X>)xs);
        }
        public static RBTree<X> create<X>(List<X> xs) where X : IComparable<X>{
            return create<X>((IEnumerable<X>)xs);
        }
        public static RBTree<X> create<X>(IEnumerable<X> xs) where X : IComparable<X>{
            RBTree<X> t = new RBLeaf<X>();
            foreach(X x in xs)t = t.insert(x);
            return t;
        }
    
        public static RBLeaf<X> leaf<X>()
            where X : IComparable<X>{ return new RBLeaf<X>(); }
        public static RBNode<X> node<X>(RBColor c, X d, RBTree<X> l,RBTree<X> r)
            where X : IComparable<X>{
            return new RBNode<X>(c,d,l,r);
        }

        public abstract int GetHashCode();
        public abstract bool Equals(Object o);
    }
}