package DataStructures;

/**
 * <p>A probing hash table implementation of a LookupTable 
 * with collisions resolved by <i>quadratic probing</i>. </p>
 *
 * <p>Tables may be constructed, for example, by
 * <pre>
 *      LookupTable&ltString,Integer&gt t = new QuadraticProbingTable&ltString,Integer&gt();
 *      t.add("one", 1);
 *      t.add("two", 2);
 *      t.add("three", 3);
 * </pre>
 * <p>To retrieve a value use for example:
 * <pre>
 *      try {
 *        System.out.println(t.lookup("two"));
 *      } catch (NoSuchElementException e) {
 *        System.err.println(e);
 *      }
 * </pre>
 *
 * <p>Entries can be read in sequence as follows:
 * <pre>
 *      for (LookupTable.Entry&ltString,Integer&gt entry : t) {
 *          System.out.println(entry);
 *      }
 *
 * @see LookupTable
 * @see ProbingHashTable
 * @param <K> the type of objects serving as keys
 * @param <V> the type of objects serving as values
 * 
 * @author Peter Williams
 */

public class QuadraticProbingTable<K,V> extends ProbingHashTable<K,V> {
    /*
     * default values of size and load factor
     */
    private static final int SIZE = 1;
    private static final double LOADFACTOR = 0.5;

    /**
     * Constructs a hash table initially capable of holding the given 
     * number of entries subject to the give loadfactor.
     * The table will grow if necessary to ensure the load factor is not
     * exceeded.  The specified load factor must lie between 0 and 0.5.
     * @param size the minimum number of entries to be made initially
     * @param loadFactor the maximum loading before the table must grow
     * @exception IllegalArgumentException if the specified load factor is
     * out of range
     */  
    public QuadraticProbingTable(int size, double loadFactor) {
        super(size, loadFactor);
        if (loadFactor > 0.5) {
            throw new IllegalArgumentException("load factor exceeds 0.5");
        }
    }
 
    /**
     * Constructs a hash table with specified initial size and default load factor.
     * @param size the minimum number of entries to be made initially
     */  
    public QuadraticProbingTable(int size) {
        super(size, LOADFACTOR);
    }

    /**
     * Constructs a hash table with default initial size and load factor.
     */  
    public QuadraticProbingTable() {
        super(SIZE, LOADFACTOR);
    }

    /**
     * Method returning the index in <tt>ProbingHashTable.table</tt> of a key, 
     * if present, or the index at which to insert it, if absent.
     * Uses a version of double hashing.
     * @param key the key to search for
     * @return the position where the search terminates
     */
    protected final int findIndex(K key) {
        int code = key.hashCode() & Integer.MAX_VALUE;
        int length = table.length;
        int index = code % length;
        int probe = 1;
        while (table[index] != null && !table[index].key.equals(key)) {
            index += probe;
            if (index >= length) {
                index -= length;
            }
            probe += 2;
        }
        return index;
    }

}