package edu.neu.ccs.demeterf.lib;

import java.util.Comparator;

import edu.neu.ccs.demeterf.Fields;
import edu.neu.ccs.demeterf.lib.Map.Merge;

/** Represents a Set of comparable Elements, implemented with RBTrees. */
public class ListSet<X> implements java.lang.Iterable<X>{
    protected final List<Wrap<X>> list;
    private final Comparator<X> comp;
    
    /** Field Class */
    public static class list extends Fields.any{}
    
    /** Construct a Set from a List with a separate Comparator.  Duplicates will be ignored. */
    private ListSet(List<X> l, final Comparator<X> c){
        this(c,l.map(new Set.Wrapper<X>(c)).removeDuplicates().sort(new Wrap.LComp<X>()));
    }
    
    /** Construct a Set from a List of <tt>Comparable</tt> elements.  Duplicates
     *    will be ignored. Left Public to support Parsing */
    public ListSet(List<Wrap<X>> l){
        this(new Wrap.CComp<X>(), l.removeDuplicates().sort(new Wrap.LComp<X>()));
    }
    
    /** Construct the <i>empty</i> Set of Comparable elements. */
    public static <X extends Comparable<X>> ListSet<X> create(){ return new ListSet<X>(List.<Wrap<X>>create()); }
    /** Construct the <i>empty</i> Set with a separate Comparator. */
    public static <X> ListSet<X> create(Comparator<X> c){ return new ListSet<X>(c,List.<Wrap<X>>create()); }
    /** Construct a Set from a List of <tt>Comparable</tt> elements.  Duplicates will be ignored. */
    public static <X extends Comparable<X>> ListSet<X> create(List<X> l)
    { return new ListSet<X>(l.map(new Set.Wrapper<X>(new Wrap.CComp<X>()))); }
    /** Construct a Set from a List with a separate Comparator.  Duplicates will be ignored. */
    public static <X> ListSet<X> create(List<X> l, Comparator<X> c){ return new ListSet<X>(l,c); }
    /** Construct a Set from a number of <tt>Comparable</tt> elements.  Duplicates will be ignored. */
    public static <X extends Comparable<X>> ListSet<X> create(X ... xs)
    { return new ListSet<X>(List.create(xs),new Wrap.CComp<X>()); }
    
    
    // Private Creators... reverse the order since the list/tree will be Wrapped elements
    private ListSet(Comparator<X> c, List<Wrap<X>> l){ comp = c; list = l; }
    private ListSet<X> make(List<Wrap<X>> lst){ return new ListSet<X>(comp,lst); }
    private List<Wrap<X>> toWrapList(){ return list; }
    
    /** Is the given element present in this Set? */
    public boolean contains(X x){ return list.contains(new Wrap<X>(x,comp)); }
    /** Is this set <i>empty</i>? */
    public boolean isEmpty(){ return list.isEmpty(); }
    /** Return the nuber of elements in this Set */
    public int size(){ return list.length(); }
    /** Returns a new Set that also contains the given element. */
    public ListSet<X> add(X x){
        Wrap<X> w = new Wrap<X>(x,comp);
        return list.contains(w) ? this : make(list.insert(new Wrap<X>(x,comp),new Wrap.LComp<X>()));    
    }
    /** Returns a new Set that no longer contains the given element. */
    public ListSet<X> remove(X x){ return make(list.remove(new Wrap<X>(x,comp))); }
    /** Is this Set a <i>subset</i> of (or equal to) the given set? */
    public boolean subseteq(ListSet<X> s){ return s.list.containsAll(this.list); }
    
    static class InList<X> extends List.Pred<Wrap<X>>{
        List<Wrap<X>> l;
        InList(List<Wrap<X>> ll){ l = ll; }
        public boolean huh(Wrap<X> x){ return l.contains(x); }
    }
    /** Returns a new Set that is the <i>union</i> of <b>this</b> and the given Set. */
    public ListSet<X> union(ListSet<X> s){
        return make(list.push(s.list.filterout(new InList<X>(s.list))));
    }
    /** Returns a new Set that is the <i>intersection</i> of <b>this</b> and the given Set. */
    public ListSet<X> intersect(final ListSet<X> s){
        return make(toWrapList().filter(new InList<X>(s.list)));
    }
    /** Returns a new Set that is the <i>difference</i> of <b>this</b> and the given Set. */
    public ListSet<X> difference(final ListSet<X> s){
        return make(toWrapList().filterout(new InList<X>(s.list)));
    }
    /** Returns this Set as a List, in the order defined by the Comparator. */
    public List<X> toList(){ return toWrapList().map(new Set.UnWrapper<X>()); }
    
    /** Returns an iterator for this Set, in the order defined by the Comparator. */
    public java.util.Iterator<X> iterator(){ return toList().iterator(); }
    
    class Merger extends List.Fold<Wrap<X>, List<Wrap<X>>>{
        Merge<X> m;
        Merger(Merge<X> mm){ m = mm; }
        public List<Wrap<X>> fold(Wrap<X> w, List<Wrap<X>> r){
            if(!r.contains(w))return r.insert(w, new Wrap.LComp<X>());
            int i = r.index(w);
            return r.replace(i,new Wrap<X>(m.merge(w.x,r.lookup(i).x),comp));
        }
    }
    /** Merge two sets with like elements merged by the given function object */
    public ListSet<X> merge(ListSet<X> s, final Merge<X> m){
        return make(s.toWrapList().fold(new Merger(m), list));
    }
    /** Merge a single element merged by the given function object */
    public ListSet<X> merge(X x, final Merge<X> m){
        Wrap<X> w = new Wrap<X>(x,comp);
        if(!list.contains(w))return make(list.insert(w, new Wrap.LComp<X>()));
        int i = list.index(w);
        return make(list.replace(i,new Wrap<X>(m.merge(w.x,list.lookup(i).x),comp)));
    }
    
    /** Set equality (s == t) is (s.subset(t) && t.subset(s)). */
    public boolean equals(Object o){
        if(!(o instanceof ListSet))return false;
        ListSet<X> s = (ListSet<X>)o;
        return (s.size() == this.size() && list.equals(s.list));
    }
    /** Produce a string representation of this Set. */
    public String toString(){ return "{ "+toList().toString(" ","")+" }"; }
    
    /** Return the combined underlying elements HashCode */
    public int hashCode(){ return 3*list.hashCode(); }
    
    // List style methods for Sets... */
    /** Map a function to each element, and collapse results */
    public <Y extends Comparable<Y>> ListSet<Y> map(List.Map<X,Y> m){
        return ListSet.create(toList().map(m));
    }
    /** Same as Map, but the resulting Set uses the given Comparator */
    public <Y> ListSet<Y> map(List.Map<X,Y> m, Comparator<Y> c){
        return ListSet.create(toList().map(m),c);
    }
}