/*               CSC 17 Hash Table Lab

NOTE: description modified since first post: see main and hints sections.

For this lab you are going to implement a variant of polymorphic
hash tables by adopting my closed hash table implementation (find
CIHash.java on homepage).  A structure similar to the hash tables I
implemented is called a Hash Map: here the key is not extracted from the
value but is stored separately.  For example, if I want to associate
"Monday" with 1 and "Tuesday" with 2, etc. then my key type is String and
value type is Integer.  The key is not part of the value, which is just
an integer, and so we cannot extract the key using a getkey function.

For this assignment you must implement a hash map.  You may not use
any Java built-in hashing features but you may use the code I have in
CIHash.java (similar to code written in class).  However, you may NOT
edit any of my code: just use the class CIHash as defined.  You need
to adopt it to a new setting.

Specifically, you are to implement the following interface and protocol:
*/

interface Ihashmap<KT, DT>
{
    int size(); // return number of values currently in the table
    int remainingCapacity();  // return remaining capacity of the table

    boolean set(KT key, DT data); // insert new key,data pair
    // this function should return true if it replaced some existing data and
    // false if no data was previously associated with key.

    DT get(KT key); //search for data associated with key, null if not found

    boolean remove(KT key); // delete data associated with key.  This function
    // should return true if something was actually deleted, and false
    // if no data was previously associated with key.
}

/* Your class (assume it's called simap) must work with the following
   main. 
*/
public class hmlab17s
{
    public static void main(String[] av)
    { 
      // use a hash table to associate days of the week with numbers.
      Ihashmap<String,Integer> Dmap = new simap(7); 
      String[] D = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
      for(int i=0;i<7;i++) Dmap.set(D[i],i);

      System.out.println(Dmap.get("Tuesday")); // should print 2
      System.out.println(Dmap.get("abcd"));    // should print null
      System.out.println(Dmap.set("Sunday",7)); // should print true
      // because it replaced an existing entry. (see interface specs)
      System.out.println(Dmap.remove("xyz")); // should print false
      // because nothing was deleted.
    }//main
}

/*  
HINTS:

You might need the following class:
class kvpair<KT,VT>
{
    KT key;
    VT value;
    public kvpair(KT k, VT v) { key=k;  value=v; }
}

Then you can write:

abstract class Myhashmap<KT,VT> extends CIHash<KT,kvpair<KT,VT>> implements Ihashmap<KT,VT>
...
  ( yes an abstract class can extend another abstract class )

then

class simap extends Myhashmap<String,Integer>  //string to integer map
...
   (alternatively, you can leave "implements ..." out of the abstract class
    declaration but then simap must implement Ihashmap<String,Integer>)


Additional hints:

Java prohibits generic array creation:

     DT[] H = new DT[100]; 

   this will result in a compiler error.  To get around this problem, do
 
     DT[] H = (DT[]) new Object[100];

   This will result in only a compiler warning.  A compiler warning indicates
   that java does not have enough information to determine if the code is
   safe, and therefore the programmer must pay special attention.  But it does
   not mean that the code is wrong.  You'll need to use this trick to write
   your polymorphic class constructor.

   If DT extends Comparable<DT>, then you also must use
     DT[] H = (DT[]) new Comparable[100];
   However, we're NOT using the Comparable interface in this lab.


   EXTRA CREDIT

    Read about the "quadratic probing" method of implementing the 
    rehash function.  One problem with this function is that you might not
    be able to find an open slot even if the array is not full.  So to make
    it practical, you should default to "linear" probing if an open slot
    cannot be found.  Implement this refinement in another subclass.
*/