/*
  Polymorphic hash table - can store any data type

  A hash table has a key type (int, string), and a data type 
  (student, bank account, etc)
*/

public abstract class ohash<Keytype, Datatype>
{
    Datatype[] Table;
    // cannot write construtor "generic array creation error"
    
    public abstract int hash(Keytype id); // to be "overrident"
    public abstract Keytype getkey(Datatype x);
    public abstract Datatype next(Datatype x);
    public abstract void setnext(Datatype x, Datatype y);
    
    public void insert(Datatype s)
    {
	int h = hash( getkey(s) );
	setnext(s,Table[h]);
	Table[h] = s;  // insert in front of list
    }
    
    public Datatype lookup(Keytype key)
    {
	int h = hash(key);  
	Datatype i = Table[h];
	while (i!=null && !key.equals(getkey(i)))
	    { i = next(i); }
	return i;
    }

    public void delete(Keytype id)
    {
	int i = hash(id) % Table.length;
	Datatype A = Table[i];
	if (A==null) return;
	if (getkey(A).equals(id)) { Table[i] = next(A);  return; }
	while (next(A)!=null && !getkey(next(A)).equals(id))
	    setnext(A,next(A));
	if (next(A)!=null) setnext(A,next(next(A)));
    }

}  // ohash