using System;
using System.Collections.Generic;

using Fields = edu.neu.ccs.demeterf.Fields;

namespace edu.neu.ccs.demeterf.lib{


/** Represents a Map of comparable Keys to any old Values, implemented with RBTrees.
 *    The Key requires a Comparator<Key>, but if Key is IComparable, you can simply
 *    supply the type to the createor functions. Also see <tt>Map.Entry</tt>. */
public class Map<Key, Val> : IEnumerable<Entry<Key,Val>>{
    protected readonly RBTree<Entry<Key,Val>> tree;
    private readonly Comparison<Key> comp;
    
    /** Field Class */
    public class treeF : Fields.any{}
    
    /** Function Class to help in the merging of Maps.  Merges Values associated to
     *    the same Key when calling merge(...). */
    public abstract class Merge{ public abstract Val merge(Val a, Val b); }
    
    class Transformer<NV> : List<Entry<Key,Val>>.Map<Entry<Key,NV>>{
        List<Val>.Map<NV> tr;
        Comparison<Key> comp;
        public Transformer(List<Val>.Map<NV> trr, Comparison<Key> c){ tr = trr; comp = c; }
        public override Entry<Key,NV> map(Entry<Key,Val> e){
            return Entry<Key,NV>.create(e.GetKey(), tr.map(e.GetVal()), comp);
        }
    }
    /** Transform Each of the Keys */
    public Map<Key,NVal> transformValues<NVal>(List<Val>.Map<NVal> tr){
        return Map<Key,NVal>.create(toList().map(new Transformer<NVal>(tr,comp)),comp);
    }
    
    /** Create an Empty Map of *IComparable* Elements. */
    private Map() : this(RBTree<Entry<Key,Val>>.create<Entry<Key,Val>>(), Entry<Key,Val>.CComp) { }
    /** Create an Empty Map using the given Comparison to compare elements. */
    private Map(Comparison<Key> c) : this(RBTree<Entry<Key,Val>>.create<Entry<Key,Val>>(), c) { }
    /** Create a Map from the given list of Entries using the given Comparison. */    
    private Map(List<Entry<Key,Val>> l, Comparison<Key> c) : this(RBTree<Entry<Key,Val>>.create<Entry<Key,Val>>(l),c) { }
    
    /** Create a Map from the given list of Entries. The <tt>Key</tt> <b>must</b> implement
     *    <tt>IComparable<Key></tt>*/
    public Map(List<Entry<Key,Val>> l) : this(l, Entry<Key,Val>.CComp) { }
    /** Create a Map from the given RBTree of Entries. */
    public Map(RBTree<Entry<Key,Val>> t) : this(t, Entry<Key,Val>.CComp) { }
    
    /** Create an Empty Map of *IComparable* Elements. */
    public static  Map<Key,Val> create<Key>() where Key : IComparable<Key> { return new Map<Key,Val>(); }
    /** Create an Empty Map using the given Comparison to compare elements. */
    public static Map<Key,Val> create(Comparison<Key> c){ return new Map<Key,Val>(c); }
    /** Create a Map from the given list of Entries, with IComparable Keys. */    
    public static Map<Key,Val> create<Key>(List<Entry<Key,Val>> l) where Key : IComparable<Key> {
        return new Map<Key,Val>(RBTree<Entry<Key,Val>>.create<Entry<Key,Val>>(l), Entry<Key,Val>.CComp);
    }
    /** Create a Map from the given list of Entries, with the given Comparison. */    
    public static Map<Key,Val> create(List<Entry<Key,Val>> l, Comparison<Key> c){
        return new Map<Key,Val>(RBTree<Entry<Key,Val>>.create<Entry<Key,Val>>(l),c);
    }
    /** Create a Map from the given list of Entries using the given Comparison. */    
    public static Map<Key,Val> create<Key>(List<Key> ks, List<Val> vs) where Key : IComparable<Key> {
        return Map<Key,Val>.create(ks,vs, Entry<Key,Val>.CComp);
    }
    
    class Zipper<K,V> : List<K>.Zip<V, Entry<K,V>>{
        Comparison<K> c;
        public Zipper(Comparison<K> cc){ c = cc; }
        public override Entry<K,V> zip(K k, V v){ return Entry<K,V>.create(k, v, c); }
    }
    /** Create a Map from the given list of Entries using the given Comparison. */    
    public static Map<Key,Val> create(List<Key> ks, List<Val> vs, Comparison<Key> c){
        return create(ks.zip(new Zipper<Key,Val>(c), vs), c);
    }
    
    public static int HashComp(Key k1, Key k2){
        return k1.GetHashCode()-k2.GetHashCode();
    }

    /** Create a Map that uses Hashcode to compare Keys. */
    public static Map<Key,Val> hashMap(){ return new Map<Key,Val>(HashComp); }
    /** Create a Map from the given Entry List that uses Hashcode to compare Keys. */
    public static Map<Key,Val> hashMap(List<Entry<Key,Val>> l){
        return new Map<Key,Val>(l, HashComp);
    }
    /** Create a Map from the given Key and Value Lists that uses Hashcode to compare Keys. */
    public static Map<Key,Val> hashMap(List<Key> ks, List<Val> vs){
        return create(ks,vs, HashComp);
    }
    /** Create a Map from the given Java HashMap. */
    public static Map<Key,Val> hashMap(IEnumerable<KeyValuePair<Key, Val>> hash){
        Map<Key,Val> m = Map<Key,Val>.hashMap();
        foreach(KeyValuePair<Key, Val> p in hash)
            m = m.put(p.Key, p.Value);
        return m;
    }
    
    
    /** Create a Map from the given RBTree of Entries using the given Comparison. */
    private Map(RBTree<Entry<Key,Val>> t, Comparison<Key> c){ tree = t; comp = c; }
    private Map<Key,Val> make(RBTree<Entry<Key,Val>> t){ return new Map<Key,Val>(t,comp); }
    
    /** Return the number of elements in this Map */
    public int size(){ return tree.size(); }
    /** Does this Map contain the given Key? */
    public bool containsKey(Key k){ return tree.contains(Entry<Key,Val>.create(k,default(Val),comp)); }
    /** Is this Map Empty? */
    public bool isEmpty(){ return tree.isLeaf(); }
    /** Return a new Map with the given Mapping (Entry) added. */
    public Map<Key,Val> put(Key k, Val v){ return make(tree.insert(Entry<Key,Val>.create(k,v,comp))); }
    /** Return a new Map with the given Mapping added or updated if it exists. */
    public Map<Key,Val> remap(Key k, Val v){
        Entry<Key,Val> e = Entry<Key,Val>.create(k,v,comp);
        return make(!containsKey(k)?tree.insert(e):tree.replace(e));
    }
    /** Get the Value that the given Key is mapped to. */
    public Val get(Key k){ return tree.find(Entry<Key,Val>.create(k,default(Val),comp)).GetVal(); }
    /** Return a new Map that does not include the given key */
    public Map<Key,Val> remove(Key k){ return make(tree.remove(Entry<Key,Val>.create(k,default(Val),comp))); }
    
    /** Merge the given Map into this one, ignoring duplicate mappings. */
    public Map<Key,Val> merge(Map<Key,Val> s){ return make(tree.insertAll(s.tree)); }
    
    class Merger : List<Entry<Key,Val>>.Fold<RBTree<Entry<Key,Val>>>{
        Merge m;
        Comparison<Key> comp;
        public Merger(Merge mm, Comparison<Key> c){ m = mm; comp = c; }
        public override RBTree<Entry<Key,Val>> fold(Entry<Key,Val> e, RBTree<Entry<Key,Val>> t){
            if(!t.contains(e))return t.insert(e);
            return t.replace(Entry<Key,Val>.create(e.GetKey(),m.merge(e.GetVal(),t.find(e).GetVal()),comp));
        }
    }
    /** Merge the given Map into this one, using the given Merge function object
     *    to merge the elements of matching Keys */
    public Map<Key,Val> merge(Map<Key,Val> s, Merge m){
        return make(s.toList().fold(new Merger(m,comp), tree));
    }
    /** Merge the given Map into this one, using the given Merge function object
     *    to merge the elements of matching Keys */
    public Map<Key,Val> merge(Key k, Val v, Merge m){
        Entry<Key,Val> e = Entry<Key,Val>.create(k,v,comp); 
        if(!tree.contains(e))return make(tree.insert(e));
        return make(tree.replace(Entry<Key,Val>.create(e.GetKey(),m.merge(v,tree.find(e).GetVal()),comp)));
    }
    
    class Keyer : List<Entry<Key,Val>>.Map<Key>{
        public override Key map(Entry<Key,Val> e){ return e.GetKey(); }
    }
    /** Reutrn a List of the Keys contained in this Map. */
    public List<Key> keys(){ return toList().map(new Keyer()); }
    
    class Valer : List<Entry<Key,Val>>.Map<Val>{
        public override Val map(Entry<Key,Val> e){ return e.GetVal(); }
    }
    /** Reutrn a List of the Values contained in this Map. */
    public List<Val> values(){ return toList().map(new Valer()); }
    /** Return all the Entries in this Map as a list, in Key order. */
    public List<Entry<Key,Val>> toList(){ return tree.toList(); }
    /** Support foreach over elements */
    public IEnumerator<Entry<Key,Val>> GetEnumerator(){ return toList().GetEnumerator(); }
    /** Support foreach over elements */
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator(){ return GetEnumerator(); }
    /** Produce a String representation of this Map. */
    public override String ToString(){ return "[ "+toList().ToString(" ","")+" ]"; }
    /** Produce a String representation of this Map. */
    public String toTreeString(){ return "[ "+tree+" ]"; }
    
    /** Convert this Map into a java.util.Map */
    public Dictionary<Key,Val> toDictionary(){
        Dictionary<Key,Val> m = new Dictionary<Key,Val>();
        foreach(Entry<Key,Val> e in this)m.Add(e.GetKey(), e.GetVal());
        return m;
    }
    
    /** Retur this Maps HashCode */
    public override int GetHashCode(){ return 3*tree.GetHashCode(); }

    /** Is this map equal to the given object */
    public override bool Equals(Object o){
        if(!(o is Map<Key,Val>))return false;
        Map<Key,Val> m = (Map<Key,Val>)o;
        return toList().Equals(m.toList());
    }
}

}