import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 A class that implements the ADT dictionary by using hashing and
 linear probing to resolve collisions.
 The dictionary is unsorted and has distinct search keys.
 Notes: Uses probe for add, but locate for remove and getValue.
 Uses linear probing, but includes code for quadratic probing.
 Has a display method for illustration and testing.
 
 @author Frank M. Carrano
 @author Timothy M. Henry
 @version 4.0
 */
public class HashedDictionary<K, V> implements DictionaryInterface<K, V>
{
   // The dictionary:
	private int numberOfEntries;
	private static final int DEFAULT_CAPACITY = 5; // Must be prime
	private static final int MAX_CAPACITY = 10000;
   
   // The hash table:
	private TableEntry<K, V>[] hashTable;
   private int tableSize;                         // Must be prime
   private static final int MAX_SIZE = 2 * MAX_CAPACITY;
   private boolean initialized = false;
	private static final double MAX_LOAD_FACTOR = 0.5; // Fraction of hash table
                                                      // that can be filled
	
	public HashedDictionary()
	{
		this(DEFAULT_CAPACITY); // Call next constructor
	} // end default constructor
   
	public HashedDictionary(int initialCapacity)
	{
      checkCapacity(initialCapacity);
		numberOfEntries = 0; // Dictionary is empty
      
      // Set up hash table:
		// Initial size of hash table is same as initialCapacity if it is prime;
		// otherwise increase it until it is prime size
		int tableSize = getNextPrime(initialCapacity);
      checkSize(tableSize);
		
		// The cast is safe because the new array contains null entries
      @SuppressWarnings("unchecked")
      TableEntry<K, V>[] temp = (TableEntry<K, V>[])new TableEntry[tableSize];
      hashTable = temp;
      
      initialized = true;
	} // end constructor

/* < Implementations of methods in DictionaryInterface are here. >
   . . .

   < Implementations of private methods are here. >
   . . . */

   private class TableEntry<S, T>
   {
      private S key;
      private T value;
      private States state; // Flags whether this entry is in the hash table
      private enum States {CURRENT, REMOVED} // Possible values of state
      
      private TableEntry(S searchKey, T dataValue)
      {
         key = searchKey;
         value = dataValue;
         state = States.CURRENT;
      } // end constructor
      
      /* < The methods getKey, getValue, setValue, isIn, isRemoved, setToIn,
       and setToRemoved are here. >
       . . . */

   } // end TableEntry
} // end HashedDictionary