/*
Closed hash table with hashcount vector, non-polymorphic and polymorphic
versions.  Find public class CIHash in the middle of file.
*/
class student  // some boring class for boring data
{
    public final String name;  // final means read-only
    public final int id;
    protected double gpa;
    public student(String n)
    {
	name = n;
	id = 700000000 + (int)(Math.random()*10000000);
	gpa = ((int)(Math.random()*401))/100.0;
    }
    public String toString()
    { return "student "+name+", id "+id+" has gpa "+gpa; }
    // boring stuff skipped
}

class schash // non-polymorphic hash table
{
    protected student[] H; // the hash array
    protected int size; // != H.length, which is capacity
    public int size() { return size; }
    public int remainingCapacity() { return H.length - size; }
    protected int[] hcount; // hashcount array, 0 = never used
    public schash(int n) // contructor sets capacity
    {
	H = new student[n];  // initiall all null
	size = 0;
	hcount = new int[n]; // initially all 0
    }//constructor

    protected int hash(String n) // hash function on student name
    {
	int h = 0;
	// take sum of all ascii values of name string
	for(int i=0;i<n.length();i++) h += (int)n.charAt(i);
	return h % H.length;  // always % H.length!
    }
    protected int rehash(int h) { return (h+1)%H.length; }

    protected String getkey(student s) { return s.name; }
    // do later!

    public void add(student s) // add/insert new student into hash table
    {
	if (size>=H.length) throw new RuntimeException("table full");
	if (s==null) throw new RuntimeException("can't add null student");
	// compute index to add s
	int hi = hash(getkey(s)); // initial hash value
	int fi = hi; // remember hi before changing it
	int sc = 1; // hash count
	// find empty slot:
	while (H[hi]!=null) { hi = rehash(hi); sc++; }
	H[hi] = s; // add student and set sc
	if (hcount[fi]<sc) hcount[fi] = sc; // hash count only increases
System.out.println("hcount == "+hcount[fi]); // trace	
	size++;
    }//add
    public void insert(student s) { add(s); } // alias for add

    
    protected int findi(String n) // find student index by name, -1 if not found
    {
	int ax = -1;
	int hi = hash(n);
	int hlimit = hcount[hi];
	int hc = 1;
	while (hc<=hlimit && ax== -1)
	    {
		if (H[hi]==null || !n.equals(H[hi].name))
		    { hc++;  hi = rehash(hi); }
		else ax = hi;
	    }
System.out.println("hc == "+hc); // trace
	return ax;
    }

    public student find(String n)// find student, null if not found
    {
	int i = findi(n);
	if (i<0) return null;
	else return H[i];
    }

    public student delete(String n)
    {
	int i = findi(n);
	if (i<0) return null;
	student ax = H[i];
	H[i] = null;
	return ax;
    }
	
}//schash

/********* public class **********/
public abstract class CIHash<KT,DT> // KT=key type, DT = value type
{
    protected DT[] H; // the hash array
    protected int size; // != H.length, which is capacity
    public int size() { return size; }
    public int remainingCapacity() { return H.length - size; }
    protected int[] hcount; // hashcount array, 0 = never used

    protected abstract int hash(KT key);
    protected abstract KT getkey(DT s);

    protected int rehash(int h) { return (h+1)%H.length; }

    public boolean add(DT s) // add/insert new student into hash table
    {                        // return true if replaced previous entry
  	if (size>=H.length) throw new RuntimeException("table full");
	if (s==null) throw new RuntimeException("can't add null student");
	boolean ax = false;
	// compute index to add s
	int hi = hash(getkey(s)); // initial hash value
	int fi = hi; // remember hi before changing it
	int sc = 1; // hash count
	// find empty slot:
	while (H[hi]!=null && !s.equals(getkey(H[hi])))
	       { hi = rehash(hi);  sc++; }
	if (H[hi]!=null) ax = true;	       
	H[hi] = s; // add s and set sc
	if (hcount[fi]<sc) hcount[fi] = sc; // hash count only increases
	//System.out.println("hcount == "+hcount[fi]); // trace	
	size++;
	return ax;
    }//add
    public void insert(DT s) { add(s); } // alias for add

    
    protected int findi(KT key) // find student index by name, -1 if not found
    {
	int ax = -1;
	int hi = hash(key);
	int hlimit = hcount[hi];
	int hc = 1;
	while (hc<=hlimit && ax== -1)
	    {
		if (H[hi]==null || !key.equals(getkey(H[hi])))
		    { hc++;  hi = rehash(hi); }
		else ax = hi;
	    }
	//System.out.println("hc == "+hc); // trace
	return ax;
    }

    public DT find(KT n)// find student, null if not found
    {
	int i = findi(n);
	if (i<0) return null;
	else return H[i];
    }

    public DT delete(KT n)
    {
	int i = findi(n);
	if (i<0) return null;
	DT ax = H[i];
	H[i] = null;
	return ax;
    }
}//CIHash


/* sample concrete subclass: */
class sihash extends CIHash<String,student>
{
    public sihash(int n) // contructor sets capacity
    {
	H = new student[n];  // ignore compiler warning
	size = 0;
	hcount = new int[n]; // initially all 0
    }//constructor
    protected int hash(String n) // hash function on student name
    {
	int h = 0;
	// take sum of all ascii values of name string
	for(int i=0;i<n.length();i++) h += (int)n.charAt(i);
	return h % H.length;  // always % H.length!
    }
    protected String getkey(student s) { return s.name; }    
}//sihash