/*
    We have seen how to use arrays and linked lists.  Each has its benefits.
    An array provides constant-time access.  A list is mutable: we can insert
    and delete from a list and a list can be arbitrarily large.  However,
    lists only offer O(n) (linear time) access in most cases.

    An open hash table is a data structure that combines arrays and lists,
    and tries combine the advantages of both.  Central to the concept of a
    hash table is a "hash function", which takes a piece of data and computes
    an integer that can be used to index an array.  For example, consider the
    following class to represent information for a student:
*/

class student
{
    public final String name;
    public int id;   //  700 number
    private double gpa;
    private int year;  // 0=freshman, 1= sophomore, etc...
    public student(String n, int i, double g, int y)
    { name=n; gpa=g; year=y; id = i; }
    public String toString()
    { String s;
      switch (year)
	  {
	    case 0 : s="freshman"; break;
	    case 1 : s="sophomore"; break;
	    case 2 : s="junior"; break;
  	    case 3 : s="senior"; break;
  	    default : s="unknown";
	  } //switch
      return name+" is a "+s+" and has a gpa of "+gpa;
    }// toString

    public student tail = null; // pointer to next student

} // student

/*
     In order to store student objects into a hash table we have to compute
some integer from the data.  For example, we can take the last 3 digits of
the id number, or we can compute the ascii sum of the first three letters of
the student's name.  We then store the student object into the array location
as indicated by the "hash value".  

Of course, it is possible for two student objects to yield the same hash
value.  For example, a student with id 700111345 and another with 700222345.
In such cases, we have to resort to storing the objects in a linked list
(using the tail pointer of the student class).  Thus each entry of our 
hash table array points to the first cell of a list of student records.

For a hash table to be efficient, the hash function has to be well chosen.
It should evenly distribute hash values across the table.  For example, 
using the first letter of a student's last name to compute the hash value
will not be a good choice, since there will be far more students with "A"
last names than "Q" last names.  Furthermore, the hash function should be
fast to compute.  Under the right conditions, hash tables can approach
constant-time performance for the basic insert, delete and lookup operations.

It is also possible to use a binary search tree instead of a list at each
table location, which will improve performance even further, but may be
overkill in some cases.

*/

public class openhash
{
    student[] Table;
    
    public openhash(int n)
    {
	Table = new student[n];  // creates array of null pointers
    }
    
    public int hash(int id)  // hash by last digits of id number
    {
	return id % Table.length;
    }

    public void insert(student s)
    {
	int h = hash(s.id);
	s.tail = Table[h];
	Table[h] = s;  // insert in front of list
    }
    
    public student lookup(int id)
    {
	int h = hash(id);
	student i = Table[h];
	while (i!=null && i.id != id) { i = i.tail; }
	return i;
    }

    public void delete(int id)
    {
	int h = hash(id);
	student i = Table[h];
	if (i==null)  return;
	if (i.id == id) { Table[h] = i.tail; return; }
	while (i.tail!=null && i.tail.id != id) { i=i.tail; }
	if (i.tail!=null) i.tail = i.tail.tail;
    }


    //// test:
    public static void main(String[] args)
    {
	openhash HT = new openhash(1000);
	student s1 = new student("mary",700123456,3.2,1);
	student s2 = new student("jane",700111111,2.7,2);
	student s3 = new student("lary",700111156,2.0,3);
	HT.insert(s1);
	HT.insert(s2);
	HT.insert(s3);
        System.out.println(HT.lookup(700111156));
    } //main

}  // openhash