// polymorphic closed hash table 3/2008

class account
{
    String owner;  // owner of bank account
    int ssn;       // social security number 
    double balance; // current balance;
    String address; // other info ...    
    static double interest_rate = 0.01;

    void withdraw(double amt) { balance -= amt; }
    void deposit(double amt) { balance += amt; }

    public account(String o, int s) // constructor
    {  owner=o;  ssn=s;  balance = 100; }

} // class account


// a closed hash table is parameterized by a value type and a key type
abstract class pchash<Vtype,Ktype>  
{
    Vtype[] HT; // the array that implements the table
    boolean[] Occupied; 
    int size;

    abstract int hash(Ktype x); // abstract hash function
    abstract Ktype getkey(Vtype v); // gets type from value

    // We can't write a constructor for an abstract class.

    // But we can have polymorphic functions:
    
    int rehash(int i) { return (i+1)%HT.length; }

    // Insert new value into table:
    public void insert(Vtype v) throws Exception
    {
	if (size>=HT.length) throw new Exception("table full");
	Ktype k = getkey(v);
	int i = hash(k);  // initial hash index
	while (HT[i]!=null) i = rehash(i);
        HT[i] = v; // insert
	Occupied[i] = true;
	size++;
    }//insert

    // lookup a record given a key, returns null if not found
    public Vtype lookup(Ktype key)
    {
	int i = hash(key);
	Vtype answer = null; // return value
	int counter = 0; // prevents infinite loop
	while (counter<size && answer==null)
	    {
		if (HT[i]==null)
		    {
			if (!Occupied[i]) counter=size; //stops loop
			else i = rehash(i);
		    }
		else // HT[i] not null
		    {
			if (getkey(HT[i]).equals(key))
			    answer = HT[i];
			else i = rehash(i);
		    }
		counter++;
	    }//while
	return answer;
    }//lookup

    // delete a record given a key - similar to lookup
    public void delete(Ktype key)
    {
	int i = hash(key);
	int counter = 0; // prevents infinite loop
	while (counter<size)
	    {
		if (HT[i]==null)
		    {
			if (!Occupied[i]) counter=size; //nothing to delete
			else i = rehash(i);
		    }
		else // HT[i] not null
		    {
			if (getkey(HT[i]).equals(key))
			    {
				HT[i] = null; //deletes but still "Occupied"
				size--;
				counter =size; // stops loop
			    }
			else i = rehash(i);
		    }
		counter++;
	    }//while
    }//delete
    
}// pchash


// an "account hash table" is a subclass of pchash.
class accountht extends pchash<account,Integer>
{
    int hash(Integer x) { return x%HT.length; }
    Integer getkey(account a) {return a.ssn;}
    
    accountht(int maxsize) // constructor
    {
	HT = new account[maxsize];
	Occupied = new boolean[maxsize];
	size = 0;
    }
}

public class chash
{
    public static void main(String[] args) throws Exception
    {
	accountht H = new accountht(100);
	H.insert(new account("mary",123456789));
	H.insert(new account("lary",987654321));
	H.insert(new account("larz",432156789));
    }
}