// Sample solutions to lab 6, combined into one file for convenience:


// Hash Set:
import java.util.ArrayList;
interface FiniteSet<D>  // finite set of elements of type D
{
    boolean add(D x); // add x to set, returns true if not a duplicate
    boolean contains(D x); // search for x in set
    boolean remove(D x); // remove x, returns true if something was removed
    int size();  // returns cardinality of set
}

/*public*/ class CHSet<T> implements FiniteSet<T>
{
    /*  alternative:
    class bmap extends CHMap<T,Boolean>
    {
	@SuppressWarnings("unchecked")
	public bmap(int cap)
	{
	    super(cap);
	}
	protected Boolean[] makeVarray(int n) { return new Boolean[n]; }
	protected T[] makeKarray(int n)
	{
	    return (T[]) new Object[n];
	}
	public int hash(T key)
	{ return Math.abs(key.hashCode()) % Keys.length; }
	public bmap makemap(int cap)
	{ return new bmap(cap); }
    }//internal class bmap

    protected bmap smap;
    */
    protected HMap<T,Boolean> smap;
    protected int size=0;
    public CHSet() {smap= new HMap<T,Boolean>(64); }
    //{ smap=new bmap(64); } // constructor
    public boolean add(T x)
    {   Boolean previous = smap.set(x,true);
	if (previous!=null && previous==true) return false;
	else { size++; return true; }
    }//add
    public boolean contains(T x)
    { Boolean result=smap.get(x);
	return result!=null && result==true;
    }
    public boolean remove(T x)
    {
	Boolean previous =smap.set(x,false);
	if (previous==null || previous==false) return false;
	else { size--; return true; }
    }//remove
    public int size() { return size; }

    // main for testing
    public static void main(String[] av)
    {
	CHSet<String> S = new CHSet<String>();
	S.add("abc"); S.add("bac"); S.add("cba"); S.add("bac"); S.add("cab");
	System.out.println(S.contains("cba")); // true
	S.remove("cba");
	System.out.println(S.contains("cba"));	//false
	System.out.println(S.size());
    }//main
}//CHSet


// Bijective hashmap

/*public*/ class Bimap<KT,VT>
{
    protected HMap<KT,VT> KVmap; // forward and backward maps
    protected HMap<VT,KT> VKmap;
    public int size() { return KVmap.size(); }
    
    public Bimap(int cap)
    {
	KVmap = new HMap<KT,VT>(cap);
	VKmap = new HMap<VT,KT>(cap);
    }//constructor

    public void set(KT key, VT val)
    {
	if (key==null || val==null) throw new RuntimeException("illegal args");
	VT pval = KVmap.get(key); // previous key
	KT pkey = VKmap.get(val); // previous val
	if (pkey!=null) KVmap.remove(pkey);
	if (pval!=null) VKmap.remove(pval);
	KVmap.set(key,val);
	VKmap.set(val,key);
    }
    public void removekey(KT key) // remove entry for key
    {
	VT pval = KVmap.remove(key);
	if (pval!=null) VKmap.remove(pval);
    }
    public void removeval(VT val) // remove using val
    {
	KT pkey = VKmap.remove(val);
	if (pkey!=null) KVmap.remove(pkey); 
    }
    public VT getval(KT key)
    {
	return KVmap.get(key);
    }
    public VT get(KT key) { return getval(key); } // alias
    public KT getkey(VT val)
    {
	return VKmap.get(val);
    }
    public KT revget(VT val) { return getkey(val); } //alias

    //for testing
    public static void main(String[] av)
    {
	// bijective map between letter grades and grade point values
	Bimap<String,Double> GP = new Bimap<String,Double>(16);
	String[] Grades = {"A","A-","B+","B","B-","C+","C","C-","D+","D","F"};
	Double[] Points = {4.0,3.7,3.3,3.0,2.7,2.3,2.0,1.7,1.3,1.0,0.0};
	for(int i=0;i<Grades.length;i++) GP.set(Grades[i],Points[i]);

	for(String g:Grades) System.out.println(GP.get(g));
	for(Double p:Points) System.out.println(GP.revget(p));	

	GP.set("A-",3.75); // CHANGE mappings:
	GP.set("B+",3.25);
	GP.removeval(1.3); // remove the D+ grade

	System.out.println(GP.get("A-")); // should print 3.75
	System.out.println(GP.revget(3.75)); // should print A-
	System.out.println(GP.get("D+")); // should print null

	/// this is the most important point to test:
	System.out.println(GP.revget(3.7)); // should print null****

	//GP.set("A+",4.0); // this will also erase value for "A". why?
	
	System.out.println(GP.size());  // should print 10
    }//main
}//Bimap