import net.datastructures.*;

/** A hash table with linear probing and the MAD hash function */
/**
  * A hash table data structure that uses linear probing to handle
  * collisions. The hash function uses the built-in hashCode method
  * and the multiply-add-and-divide method.  The load factor is alwyas
  * kept less than or equal to 0.5. When the load factor reaches 0.5,
  * the entries are rehashed into a new bucket array with twice the
  * capacity.
  *
  * @author Roberto Tamassia, Michael Goodrich, Eric Zamore
  */
public class HashTable implements Map {
  /** Nested class for an entry in a hash table. */
  protected static class HashEntry implements Entry {
    Object key, value;
    HashEntry () { /* default constructor */ }
    HashEntry(Object k, Object v) { key = k; value = v; }
    public Object key() { return key; }
    public Object value() { return value; }
    protected Object setValue(Object v) {  // set a new value, returning old
      Object temp = value;
      value = v;
      return temp;  // return old value
    }
  }
  /** Nested class for a default equality tester */
  /** An inner class for a simple equality tester.  It uses {@link
   * Object#equals(Object)} to make its equality comparisons. */
  protected static class DefaultEqualityTester implements EqualityTester {
    DefaultEqualityTester() { /* default constructor */ }
    /** Returns whether the two objects are equal.  */
    public boolean isEqualTo(Object a, Object b) { return a.equals(b); }
  }
  protected static Entry AVAILABLE = new HashEntry(null, null); // empty marker 
  protected int n = 0; 		// number of entries in the dictionary
  protected int N; 		// capacity of the bucket array
  protected Entry[] A;		// bucket array
  protected EqualityTester T;	// the equality tester
  protected int scale, shift;   // the shift and scaling factors
  /** Creates a hash table with initial capacity 1023. */
  public HashTable() { 		
    N = 1023; // default capacity
    A = new Entry[N];
    T = new DefaultEqualityTester(); // use the default equality tester
    java.util.Random rand = new java.util.Random();
    scale = rand.nextInt(N-1) + 1;
    shift = rand.nextInt(N);
  }
  /** Creates a hash table with the given capacity and equality tester. */
  public HashTable(int bN, EqualityTester tester) {
    N = bN;
    A = new Entry[N];
    T = tester;
    java.util.Random rand = new java.util.Random();
    scale = rand.nextInt(N-1) + 1;
    shift = rand.nextInt(N);
  }
  /** Determines whether a key is valid. */
  protected void checkKey(Object k) {
    if (k == null) throw new InvalidKeyException("Invalid key: null.");
  }
  /** Hash function applying MAD method to default hash code. */
  public int hashValue(Object key) {
    return Math.abs(key.hashCode()*scale + shift) % N;
  }
  /** Returns the number of entries in the hash table. */
  public int size() { return n; }
  /** Returns whether or not the table is empty. */
  public boolean isEmpty() { return (n == 0); }
  /** Helper search method - returns index of found key or -index-1,
   * where index is the index of an empty or available slot. */
  protected int findEntry(Object key) throws InvalidKeyException {
    int avail = 0;
    checkKey(key);
    int i = hashValue(key);
    int j = i;
    do {
      if (A[i] == null)   return -i - 1;  // entry is not found
      if (A[i] == AVAILABLE) {	// bucket is deactivated
	avail = i;		// remember that this slot is available
	i = (i + 1) % N;	// keep looking
      }
      else if (T.isEqualTo(key,A[i].key()))  // we have found our entry
	return i;
      else // this slot is occupied--we must keep looking
	i = (i + 1) % N;
    } while (i != j);
    return -avail - 1;  // entry is not found
  }
  /** Returns the value associated with a key. */
  public Object get (Object key) throws InvalidKeyException {
    int i = findEntry(key);  // helper method for finding a key
    if (i < 0) return null;  // there is no value for this key
    return A[i].value();     // return the found value in this case
  }
  /** Put a key-value pair in the map, replacing previous one if it exists. */
  public Object put (Object key, Object value) throws InvalidKeyException {
    if (n >= N/2) rehash(); // rehash to keep the load factor <= 0.5
    int i = findEntry(key); //find the appropriate spot for this entry
    if (i < 0) { 	// this key does not already have a value
      A[-i-1] = new HashEntry(key, value); // convert to the proper index
      n++;
      return null; 	// there was no previous value
    }
    else  		// this key has a previous value
      return ((HashEntry) A[i]).setValue(value); // set new value & return old
  }
  /** Doubles the size of the hash table and rehashes all the entries. */
  protected void rehash() {
    N = 2*N;
    Entry[] B = A;
    A = new Entry[N]; // allocate a new version of A twice as big as before
    java.util.Random rand = new java.util.Random();
    scale = rand.nextInt(N-1) + 1;    	// new hash scaling factor
    shift = rand.nextInt(N); 		// new hash shifting factor
    for (int i=0; i<B.length; i++)
      if ((B[i] != null) && (B[i] != AVAILABLE)) { // if we have a valid entry
	int j = findEntry(B[i].key());  // find the appropriate spot
	A[-j-1] = B[i];                 // copy into the new array
      }
  }
  /** Removes the key-value pair with a specified key. */
  public Object remove (Object key) throws InvalidKeyException {
    int i = findEntry(key);  	// find this key first
    if (i < 0) return null;  	// nothing to remove
    Object toReturn = A[i].value();
    A[i] = AVAILABLE; 		// mark this slot as deactivated
    n--;
    return toReturn;
  }
  /** Returns an iterator of keys. */
  public java.util.Iterator keys() {
    List keys = new NodeList();
    for (int i=0; i<N; i++) 
      if ((A[i] != null) && (A[i] != AVAILABLE)) 
	keys.insertLast(A[i].key());
    return keys.elements();
  }
  /** Returns an iterator of values. */
  public java.util.Iterator values() {
    List values = new NodeList();
    for (int i=0; i<N; i++) 
      if ((A[i] != null) && (A[i] != AVAILABLE)) 
	values.insertLast(A[i].value());
    return values.elements();
  }
  
  /* get the number of collisions before find an cell to insert */
  protected int getProbeNum(Object key) throws InvalidKeyException {
    int count = 1;  
    checkKey(key);
    int i = hashValue(key);
    int j = i;
    do {
      if (A[i] == null)  break;                       //found an empty cell
      if (A[i] == AVAILABLE)  break;                   //found an AVAILABLE cell
      if (T.isEqualTo(key,A[i].key()))  break;       //found the element;
      
      i = (i + 1) % N;
      count ++ ;
    } while (i != j);
    return count;  
  }
} // ... values() is similar to keys() and is omitted here ...