/* File: HashTable.java
 * Author: Wayne Snyder
 * Date: March 24th, 2014
 * Purpose: This is the basic code for the lecture on Hash Tables 
 *          with separate chaining in CS 112
 */


public class HashTableSC {
   
   private static final int N = 7;             // prime number as big as you want your table to be
   private static final int K = 3;             // use a relatively large prime; these are just
   // for simple examples 
   
   private static int numItems = 0;            // count the number of keys in the table
   
   // Next we supply the code and data structures for linked lists, which will implement buckets
   
   // bucket node
   private static class Node{
      int key;
      Node next; 
      public Node(int k, Node n) { 
         key = k; next = n;
      }     
   }
   
   // standard recursive insert into a LL, takes a LL and returns a new LL with this node in it;
   //  does not insert duplicate keys
   
   private static Node insertInBucket(int key, Node n) {
      if(n == null) {
         ++numItems; 
         return new Node(key, null);
      }
      else if(key == n.key) {              // duplicate, don't insert
         return n;
      } else {
         n.next = insertInBucket(key, n.next);
         return n;
      }
   }
   
   // standard recursive delete in LL
   
   private static Node deleteFromBucket(int key, Node n) {
      if(n == null)
         return null;
      else if(key == n.key) {            // found it!
         --numItems; 
         return n.next;
      } else {
         n.next = deleteFromBucket(key,n.next);
         return n;
      }
   }
   
   // standard recursive find or lookup method: returns pointer to node of the key or null if
   // not found
   
   private static Node lookup(int key, Node n) {
      if(n == null) {
         return null;
      }
      else if(key == n.key) {              // found it!
         return n;
      } else {
         return lookup(key, n.next);
      }
   }
    
   
   // Next we provide the Hash Table methods which use the previous methods for the buckets
   
   // This is the table of pointers to LLs
   
   private static Node[] A = new Node[N];     // will be initialized to null
   
   // simple hash function on integers
   
   private static int hash(int key) {
      return (K*key) % N; 
   }
   
   // insert, delete, and member
   
   public static void insert(int key) {
      A[hash(key)] = insertInBucket(key, A[hash(key)]);       
   }  
   
   public static void delete(int key) {
      A[hash(key)] = deleteFromBucket(key,A[hash(key)]);
   }
   
   public static boolean member(int key) {
      return (lookup(key,A[hash(key)]) != null);
   }
   
      
   public static int size() {
      return numItems; 
   }
   
   public static boolean isEmpty() { 
      return numItems == 0;
   }
   
   // just debug routines
   
   private static void printBucket(Node n) {
      if( n == null)
         System.out.println(" -> .");
      else {
         System.out.print(" -> [" + n.key + "]");
         printBucket(n.next);
      }
   }
   
   private static void printTable() {
      for(int i = 0; i < A.length; ++i) {
         System.out.print("A["+i+"]");
         printBucket(A[i]); 
      }
      System.out.println();    
   }

   
   public static void main(String [] args) {
      insert(5);
      insert(12);
      insert(11);
      insert(34);
      insert(7);
      printTable(); 
      System.out.println("Key 7 is in table: " + member(7)); 
      System.out.println("Key 14 is in table: " + member(14)); 
      System.out.println("There are " + size() + " keys in the table.\n"); 
      insert(9);
      insert(17);
      delete(12);                
      delete(11);
      insert(45);
      delete(121);
      insert(75);
      delete(5);                   
      delete(9);
      insert( 29 );
      printTable();
      System.out.println("Key 7 is in table: " + member(7)); 
      System.out.println("Key 9 is in table: " + member(9)); 
      System.out.println("There are " + size() + " keys in the table.");      
   }
     
}