/*
Java Polymorphic, (open addressing) hash map as an abstract class.  This
technique is also called "closed hashing", although our map is resizable.

Enhanced technique keeps track of all positions with non-empty keys
with int[] Keyloc array of key locations, keycount-1 is index of last keyloc
*/

public abstract class CHMap<KT,VT> // KeyType -> ValueType
{
    protected KT[] Keys;
    protected VT[] Vals;
    protected int valcount=0;  // number of non-null values
    protected int keycount=0; // number of keys; invariant valcount<=keycount
    protected int[] Keyloc; // location of keys (with possible null Vals)
    protected int defaultcap = 4;
    protected double maxlf = 0.75; // max load factor before resize
    protected double targetlf = 0.25; // target load factor for resize
    public int size() { return valcount; }
    public int capacity() { return Keys.length; }

    
    // this is costly as each non-empty key is re-inserted,
    // does "manual memory management"
    public void increasecap() 
    {
	int newcap = (int)(keycount/targetlf + 0.5);
	if (newcap<Keys.length) return; // don't allow size to decrease
	CHMap<KT,VT> newmap = makemap(newcap);
	for(int i=0;i<keycount;i++)
	    {
		int k = Keyloc[i]; // location of ith key
		if (Vals[k]!=null)
			newmap.set(Keys[k],Vals[k]); //re-insert
	    }//for i
	Keys = newmap.Keys;
	Vals = newmap.Vals;
	Keyloc = newmap.Keyloc;
	valcount = newmap.valcount;   // shouldn't be necessary
	keycount = newmap.keycount;
    }// later

    // abstract methods
    protected abstract int hash(KT key);
    protected abstract CHMap<KT,VT> makemap(int cap); // creates new map
    protected abstract KT[] makeKarray(int n); // avoid generic array creation
    protected abstract VT[] makeVarray(int n);

    // with makeKarray, makeVarray abstract, we can write a constructor
    // in the superclass and avoid the generic array creation problem.
    // But you still can't create an instance of the abstract class, so we
    // still need makemap to be abstract
    public CHMap(int cap)
	{
	    if (cap<defaultcap) cap=defaultcap;
	    Keys = makeKarray(cap);
	    Vals = makeVarray(cap);
	    Keyloc = new int[cap];
	    valcount=keycount=0;
	}


    // rehash hash value h after c number of collisions
    protected int rehash(int h, int c)
    {
	//return (int)(h + 0.5*c + 0.5*c*c); // Quadratic probing
	return (h+c) % Keys.length;  // default is "linear probing" 
    }

    // set (insert or change value), returns previous value
    public VT set(KT key, VT val)
    {
	if (key==null) throw new RuntimeException("invalid key");
        //based on statistical studies, when load factor reaches .75
	if (keycount*1.0/Keys.length >= maxlf) increasecap();
	int h0 = hash(key); // compute initial hash value
	int h = h0;   // final hash value (may change from initial)
	int collisions = 0;
	while (!(Keys[h]==null || key.equals(Keys[h])))
	    h = rehash(h0,++collisions); // find new slot
	// at this point, may have found empty slot, or found previous entry
	if (Keys[h]==null) // insert new value 
	    {
		Keyloc[keycount++] = h; // record new key
		if (val!=null) valcount++;
		Keys[h] = key;  Vals[h] = val; 
		return null; // means no previous value with key
	    }
	else // replace existing value associated with key
	    {
		VT previous = Vals[h];
		Vals[h] = val;
		if (val==null && previous!=null) valcount--;
		else if (previous==null && val!=null) valcount++;
		return previous;		
	    }
    }//set
    // note: keys are never deleted: their presence indicates need to rehash
    public VT remove(KT key) { return set(key,null); }

    // get (lookup value by key, returns null if no value associated with key
    public VT get(KT key)
    {
	int h0 = hash(key); // initial hash value
	int h = h0;   // final hash value (may change from initial)
	int collisions = 0;	
	while (Keys[h]!=null && !key.equals(Keys[h])) // while slot occupied:
	    h = rehash(h0,++collisions); // find new slot
	return Vals[h];
    }

    // The following version of set assumes that there's no current
    // value associated with the key.  It's up to the caller to guarantee
    // that this is true.  This procedure will simply find the first
    // null value in the Vals array and insert the key and values there.
    // But this could result in duplicate keys in the array as a result
    // of previous rehashing.  
    // Assume ABC, BCA and CBA are keys with same hash value:
    //  key  value
    //  ABC    1
    //  BCA   null
    //  CBA    2
    // add("CBA",3) will change the BCA entry to CBA-3, resulting
    // in two entries for CBA (deleting the first won't delete the second).
    // This function will also not replace an existing entry, only adds a
    // new one
    public void addnew(KT key, VT val)
    {
	if (key==null) throw new RuntimeException("invalid key");
	// if load factor is too large, copy entire table to new array
	if (keycount*1.0/Keys.length > maxlf) increasecap();
	int h0 = hash(key); // initial hash value
	int h = h0;   // final hash value
	int collisions = 0;
	while (Vals[h]!=null) h = rehash(h0,++collisions);
	if (Keys[h]==null) Keyloc[keycount++]=h;
	if (val!=null) valcount++;
	Keys[h] = key;  Vals[h] = val;
    }//addnew

    // function to return array of all active keys
    public KT[] allKeys()  // return array with all active keys
    {
	KT[] K = makeKarray(valcount);
	int ki = 0; // indexes K array
	for(int i=0;i<keycount;i++)
	    {
		int k = Keyloc[i];
		if (Vals[k]!=null) K[ki++] = Keys[k];
	    }
	return K;
    }//allKeys

    // function to return array of all non-null values
    public VT[] allVals()  // return array with all active keys
    {
	VT[] V = makeVarray(valcount); 
	int vi = 0; // indexes K array
	for(int i=0;i<keycount;i++)
	    {
		int k = Keyloc[i];
		if (Vals[k]!=null) V[vi++] = Vals[k];
	    }
	return V;
    }//allKeys


    // for DEBUGGING only
    void printtable()
    {
	System.out.printf("\nIndex:\t Key:\t Value:\n");
	System.out.printf("-----------------------------------------\n");
	for(int i=0;i<keycount;i++)
         {  int k = Keyloc[i];
	    if (Keys[k]!=null || Vals[k]!=null)
		System.out.println(k+"\t "+Keys[k]+"\t "+Vals[k]);
	 }
    }
}//CHMap