/* Abstract version of hash table, depends on concrete implementations
   of the hash, getkey and makecollection functions.

   In this "design", we choose to create an abstract class which assumes
   that these functions are implemented in "concrete" subclasses.
   There are alternative designs that we can discuss later.
*/


import java.util.*; // for ArrayList, Collection, etc

public abstract class ahash<KT,VT>
{
    protected Collection<VT>[] H;
    protected int size;
    public int size() { return size; }
    public ahash(int buckets)
    {
	H = new Collection[buckets]; // expect compiler warning
    }
    protected abstract int hash(KT key);
    protected abstract KT getkey(VT s);

    // insert, lookup, delete

    // insert should also replace previous record for student with
    // new record

    protected abstract Collection<VT> makecollection(); // why?

    public boolean insert(VT s) // returns true if something replaced.
    {
	boolean answer = false;
	KT key = getkey(s);
	int hi = hash(key);
	if (H[hi]==null) H[hi] = makecollection(); // differ to subclass
	else if (H[hi].remove(s)) { size--;  answer=true; }// remove old record
	H[hi].add(s);
	size++;
	return answer;
    }

    protected VT search(KT key, boolean del)
    {
	VT answer = null;
	if (key==null) return null;
	int hi = hash(key);
	if (H[hi]==null) return null;
	for(VT s:H[hi])
	    if (key.equals(getkey(s))) // can call .equals on all objects
		{
		    answer = s;
		    if (del) { H[hi].remove(s); size--; }
		    return answer; //break;
		}
        return answer;
    }
    public VT lookup(KT key) { return search(key,false); }
    public VT delete(KT key) { return search(key,true); }
    

    // main for testing (see student, shash class below)
    public static void main(String[] av)
    {
	ahash<String,student> HT = new sthash(1000);
	HT.insert(new student("mary",702123456));
	HT.insert(new student("larz",701654321));
	HT.insert(new student("narx",702111111));
	HT.delete("larz");
	System.out.println( HT.lookup("mary"));
	System.out.println( HT.lookup("narx"));
	System.out.println( HT.lookup("larz"));		
    }
    
}//ahash


/// Now to reproduce a student hash table as a subclass of ahash:

class student implements Comparable<student>  // generic boring class
{
    public final String name;   // used as "key"
    public final int id;
    protected double gpa;
    protected String major;
    // ... other boring stuff skipped
    public student(String n, int i)
    {   name=n; id=i;
	gpa = ((int)(Math.random()*401))/100.0;
	major = "cs";
    }
    public String toString()
    {return name+" has id "+id+" and gpa "+gpa; }
    public int compareTo(student s) { return id -s.id; } //default compare
}//student


// studenthash table as subclass of ahash
class sthash extends ahash<String,student>
{
    public sthash(int b) { super(b); }
    protected int hash(String key) 
    { return Math.abs(key.hashCode()) % H.length; }
    protected String getkey(student s) { return s.name; }

    protected Collection<student> makecollection() 
    {
	return new TreeSet<student>();  // treeset is another kind of Collection
    }
}

/*
Alternative Designs:

There are some alternatives that we can consider which would more or less
create the same level of abstraction.

1. Instead of an abstract class, create a concrete class but with some "dummy"
methods such as
 
KT getkey(VT v) { return null; }
int hash(KT key) { return 0; }

With the understanding that these methods will be overriden in subclasses.
While this approach would "work", it will also produce things that shouldn't
work, such as creating an instance of a class where getkey always returns
null.  If you don't know how to define a function, THEN DON'T DEFINE IT.
Leave it abstract.

2. Delegate (at least) the hash and getkey functions to the type VT instead:
Create an 
interface HashValue<KT>  // values that can be hashed
{
   int hash(KT key);
}
and implement 
(abstract) class hashtable<KT,VT extends HashValue<KT>>
...

Then instead of calling hash(value), we call value.hash(), and 
presumably the concrete implementation of hash would know which key to use.
With this design, if you wish to change the hash function you would have
to create a new subclass of the values you want to hash.  For example,
if you produce 
class hashablestudent extends student implements HashValue<Integer>
{
public int hash() { ... return ? % ?}
}
In the implementation of re-queable heap, we used a similar design, but
there we really had no choice: the heap indices must be closely coupled with
the objects inside the heap.  One consequence of this design is that 
it may be more difficult to integrate your code with existing code, which
use students, not hashable students.  For example, if another function
returned a list of students that you would need to hash, you will first
have to convert them to hashablestudents. 

Java itself actually uses a variant of this design: the Object super class
contains a function .hashCode(), which everyone inherits, and can override.
This is a carry-over from the earliest days of Java, before there were 
generics (type variables like <T>).  Because hashing is such a common 
algorithmic element, all objects in java are assumed to have this function.
However, there are also langugages (Kotlin) without an overall superclass,
so you should be aware of other designs.

3. Pass in the hash, getkey functions as lambda expressions.

Treating a function as a value that can be assigned to a variable,
passed to another function as a parameter, or returned by another function
is called functional programming.  This is another way to abstract over
an algorithm.  This is the *functional programming* approach as opposed
to the *object oriented* approach.  There are merits to this approach,
and although Java has recently adopted some functional programming features,
it is still primarily an object oriented language.  It cannot support (yet)
full-scale functional programming.  
*/