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


public class HashTableLP {
   
   private static final boolean trace = true; 
   
   private static final int neverUsed = -1;
   private static final int usedButEmpty = -2; 
   
   private static final int M = 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 N = 0;                   // number of keys
   
   // This next is the array of keys
   
   private static int[] A = new int[M]; 
   
   static {
     for(int i = 0; i < M; ++i) 
         A[i] = neverUsed;     
   }
   
   // find location for key and put new key there; if no empty slots, do nothing
   
    private static void insert(int key) {
        int loc = hash(key);
        for (int i = 0; i < M; ++i) {
            if (A[loc] == neverUsed || A[loc] == usedButEmpty) {           // found empty slot, used or unused
                A[loc] = key;
                ++N;
                return;
            }
            loc = (loc + 1) % M;
        }
    }
    
    
    private static boolean member(int key) {
        int loc = hash(key);
        for (int i = 0; i < M; ++i) {
            if (A[loc] == key) {
                return true;
            }
            else if (A[loc] == neverUsed) {
                return false;
            }
            loc = (loc + 1) % M;
        }
        return false;
    }
   
   // lookup returns location where key is stored, or -1 if not found
   
    private static int lookup(int key) {
        int loc = hash(key);
        for (int i = 0; i < M; ++i) {
            if (A[loc] == key) {
                return loc;
            }
            else if (A[loc] == neverUsed) {
                return -1;
            }
            loc = (loc + 1) % M;
        }
        return -1;
    }
   
   // delete just used lookup to insert usedButEmpty into the slot
   
   private static void delete(int key) {
      int loc = lookup(key);
      if(loc != -1) {
         A[loc] = usedButEmpty;
      }
   }
      
   
   // simple hash function on integers
   
   private static int hash(int key) {
      return (K*key) % M; 
   }
  
   
   // just debug routine
   
   private static void printTable() {
      for(int i = 0; i < A.length; ++i) {
         if(A[i] == usedButEmpty)
            System.out.println("A["+i+"]: -");
         else if(A[i] == neverUsed)
            System.out.println("A["+i+"]: *"); 
         else 
            System.out.println("A["+i+"]: " + A[i]); 
      }
      System.out.println();    
   }

   
   public static void main(String [] args) {
      

      insert(3);
      printTable();
      insert(2);
      printTable();
      insert(6);
      printTable();
      insert(10);
      printTable();
      insert( 8);
      printTable();
      insert( 1 );
      printTable();
      delete(6);
      printTable();
      delete(8);
       printTable();  
      insert( 8 );

      printTable();
 /*     delete( 1 );
      delete(23);
      insert(5);
      printTable();
      insert(5);
      insert(12);
      insert(11);
      insert(34);
      insert(7);
      printTable(); 
 */
   }
     
}