import java.util.Iterator;

/**
  * 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.
  *
  * Cheung's notes:
  *   1. The hashCode() is provided by the function K.hashCode() in the class K
  *   2. It uses MAD compression
  *
  * @author Roberto Tamassia, Michael Goodrich, Eric Zamore
  */

public class MyMap<K,V> implements Map<K,V> 
{
  /** Nested class for an entry in a hash table. */

  public static class HashEntry<K,V> implements Entry<K,V> 
  {
    protected K key;
    protected V value;

    public HashEntry(K k, V v) 
    { 
      key = k; 
      value = v; 
    }

    public V getValue() 
    { 
      return value; 
    }

    public K getKey() 
    { return key; 
    }

    public V setValue(V val) 
    {
      V oldValue = value;
      value = val;
      return oldValue;
    }

    public boolean equals(Object o) 
    {
      HashEntry<K,V> ent;

      try 
      { 
        ent = (HashEntry<K,V>) o;    // Test if o is a HashEntry...
      }
      catch (ClassCastException ex) 
      { 
	return false; 
      }

      return (ent.getKey() == key) && (ent.getValue() == value);
    }

    public String toString() 
    {
      return "(" + key + "," + value + ")";
    }
  }



  protected Entry<K,V> AVAILABLE = new HashEntry<K,V>(null, null);
					// Dummy entry to occupy DELETE slots

  protected int n = 0; 		   // number of entries in the dictionary

  protected int prime;	           // Prime number used in the hash function
  protected int capacity;          // = N (capacity of bucket array)

  public Entry<K,V>[] bucket;      // bucket array

				   // Made it public to print !

  protected long scale;		// Scaling factor (a)
  protected long shift;         // Shift factor   (b)

  /* ---------------
     Constructors...
     --------------- */
  public MyMap()     // Default constructor...
  { 
    this(109345121,1000);   // Calls the actual constructor below
  }

  public MyMap(int cap) 
  { 
     this(109345121, cap);   // Calls the actual constructor below
  }

  public MyMap(int p, int cap) 
  {
    prime = p;
    capacity = cap;

    bucket = (Entry<K,V>[]) new HashEntry[capacity];   // Give bucket a correct type
						   // It's a safe cast

    java.util.Random rand = new java.util.Random();

    scale = rand.nextInt(prime-1) + 1;  // integer from range [1..(p-1)]
    shift = rand.nextInt(prime);        // integer from range [0..(p-1)]
  }

  /** Determines whether a key is valid. */
  protected void checkKey(K k) 
  {
    if (k == null) 
    {
       throw new InvalidKeyException("Invalid key: null.");
    }
  }

  /** -----------------------------------------------------------
      Hash function applying MAD method to default hash code. 

        h(k) = ( (scale*hashCode(k) + shift) % p )
      ----------------------------------------------------------- */
  public int hashValue(K key) 
  {
     return (int) ((Math.abs(key.hashCode()*scale + shift) % prime) % capacity);
  }

  /** 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); 
  }

  /** Returns an iterable object containing all of the keys. */
  public Iterable<K> keySet() 
  {
    PositionList<K> keys = new NodePositionList<K>();

    for (int i=0; i < capacity; i++) 
    {
      if ((bucket[i] != null) && (bucket[i] != AVAILABLE)) 
      {
	keys.addLast(bucket[i].getKey());
      }
    }

    return keys;
  }

  /** ---------------------------------------------------------------
      Helper search method:

         - when key is found, it returns index >= 0
	 - when key is not found, it returns -(a + 1),
                where a is the index of the first empty/available 
		slot found. 
    ------------------------------------------------------------------ */
  protected int findEntry(K key) throws InvalidKeyException 
  {
    int avail = -1;		// Flag indicating an initial search

    int i;
    int j;

    checkKey(key);		// Make sure "key" is correct type of object

    i = hashValue(key);		// Hash index
    j = i;			// Stop criteria... stop when i == j

    do 
    {
      Entry<K,V> e = bucket[i];  // Hash location

      if ( e == null) 
      { /* Reach an EMPTY slot */
	if (avail < 0)
	{
	  avail = i;	// Remember the first EMPTY slot
	}
	break;
      }

      if (key.equals(e.getKey())) // we have found our key
      {
	return i;	// key found, return index of array that stores the key
      }

      if (e == AVAILABLE) 
      {	// bucket is deactivated
	if (avail < 0)
	  avail = i;	// remember that FIRST available (EMPTY) slot
      }

      i = (i + 1) % capacity;	// Linear probe, look at the next location

    } while (i != j);

    /* --------------------------------------------
       At this point:

          1. k is NOT found
          1. avail = index of the FIRST empty slot
       -------------------------------------------- */

    return -(avail + 1);  // Return indication of not found and the index
			  // of the first empty/available slot
  }


  /** Returns the value associated with a key. */
  public V get (K key) throws InvalidKeyException 
  {
    int i;

    i = findEntry(key);  // Call helper method to finding a key

    if (i < 0) 
      return null;       // there is no value for this key, so reutrn null

    return bucket[i].getValue();     // return the found value in this case
  }

  /** Put a key-value pair in the map, replacing previous one if it exists. */
  public V put (K key, V value) throws InvalidKeyException 
  {
    int i;

    i = findEntry(key); //find the appropriate spot for this entry

    if (i >= 0)	//  this key has a previous value
      return ((HashEntry<K,V>) bucket[i]).setValue(value); // set new value 
    if (n >= capacity/2) {
      rehash(); // rehash to keep the load factor <= 0.5
      i = findEntry(key); //find again the appropriate spot for this entry
    }
    bucket[-i-1] = new HashEntry<K,V>(key, value); // convert to proper index
    n++;
    return null; 	// there was no previous value
  }
  /** Doubles the size of the hash table and rehashes all the entries. */
  protected void rehash() {
    capacity = 2*capacity;
    Entry<K,V>[] old = bucket;
    bucket = (Entry<K,V>[]) new Entry[capacity]; // new bucket is twice as big 
    java.util.Random rand = new java.util.Random();
    scale = rand.nextInt(prime-1) + 1;    	// new hash scaling factor
    shift = rand.nextInt(prime); 		// new hash shifting factor
    for (int i=0; i<old.length; i++) {
      Entry<K,V> e = old[i];
      if ((e != null) && (e != AVAILABLE)) { // a valid entry
	int j = - 1 - findEntry(e.getKey());
	bucket[j] = e;
      }
    }
  }
  /** Removes the key-value pair with a specified key. */
  public V remove (K key) throws InvalidKeyException {
    int i = findEntry(key);  	// find this key first
    if (i < 0) return null;  	// nothing to remove
    V toReturn = bucket[i].getValue();
    bucket[i] = AVAILABLE; 		// mark this slot as deactivated
    n--;
    return toReturn;
  }
//end#fragment Linear2
  /** Returns an iterable object containing all of the entries. */
  public Iterable<Entry<K,V>> entrySet() {
    PositionList<Entry<K,V>> entries = new NodePositionList<Entry<K,V>>();
    for (int i=0; i<capacity; i++) 
      if ((bucket[i] != null) && (bucket[i] != AVAILABLE)) 
	entries.addLast(bucket[i]);
    return entries;
  }
  /** Returns an iterable object containing all of the values. */
  public Iterable<V> values() {
    PositionList<V> values = new NodePositionList<V>();
    for (int i=0; i<capacity; i++) 
      if ((bucket[i] != null) && (bucket[i] != AVAILABLE)) 
	values.addLast(bucket[i].getValue());
    return values;
  }
//begin#fragment Linear2
} 
//end#fragment Linear2