// open hash table of students, second version, polymorphic, and oop.
import java.util.*;   // for ArrayList

abstract class hashtable<ValueTy,KeyTy>
{
    // HT is an array of linked lists!
    protected ArrayList<ValueTy>[] HT; // can't be ArrayList<ValueTy> unfortunately

    // no constructor in abstract class

    // The hash function given a key:
    public abstract int hash(KeyTy S);

    // The following function extracts the Key from the Value:
    public abstract KeyTy getkey(ValueTy v);



    // inserting a new student object into the table:
    public void insert(ValueTy S)
    {
	int h = hash(getkey(S));
	HT[h].add(S); // add student to array list at hashed position
    }


    // searching for a student by key
    public ValueTy search(KeyTy key)
    {
	ArrayList<ValueTy> L = HT[ hash(key) ];
	ValueTy answer = null;
	for(int i=0;i<L.size() && answer==null;i++)
	    {
		ValueTy s = L.get(i);
		if (getkey(s).equals(key)) answer = s;
	    }
	return answer;
    }

    // delete a student record by id number // return student deleted
    // or null there is no such student.
    public ValueTy delete(KeyTy key)
    {
	ArrayList<ValueTy> L = HT[ hash(key) ];
	ValueTy answer = null;
	for(int i=0;i<L.size() && answer==null;i++)
	    {
		ValueTy s = L.get(i);
		if (getkey(s).equals(key)) { answer = s; L.remove(i); }
	    }	
	return answer;
    }

    public void printall() // print entire table
    {
	for (ArrayList<ValueTy> R : HT)
	    for(int i=0;i<R.size();i++)
		System.out.println(R.get(i));
    }
}// abstract hashtable


// concrete hash table class
class studenthash extends hashtable<student,Integer>
{
    public int hash(Integer id) { return id % HT.length; }

    public Integer getkey(student v) { return v.id; }

    public studenthash(int max)
    {
	ArrayList<?>[] HTw = new ArrayList<?>[max];
	HT = (ArrayList<student>[])HTw;
	for(int i=0;i<max;i++)
	    HT[i] = new ArrayList<student>();
    }
}// studenthash concrete class


public class polyhash
{
    /* uncomment main for testing: */
    public static void main(String[] args)
    {
	studenthash SH = new studenthash(100);
	SH.insert(new student("mary",700234123,3.5,1));
	SH.insert(new student("larz",700555123,2.0,3));
	SH.insert(new student("narx",700444223,2.8,0));
	for(int i=0;i<10;i++) SH.insert(new student()); // random student
	
	student l = SH.search(700555123);
	SH.delete(700234123);
	student m = SH.search(700234123);
	System.out.println(l);
	System.out.println(m);
	SH.printall();
    }
}