package DataStructures;

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

/**
 * <p>An abstract class implementing the LookupTable interface
 * by means of a hash table.  Collisions are resolved by probing.</p>
 *
 * <p>This class must be extended to implement a particular probing
 * algorithm for the <code>findIndex</code> method, such as double
 * hashing or quadratic probing.</p>
 *
 * @see ProbingHashTable#findIndex
 * @see DoubleHashingTable
 * @see QuadraticProbingTable
 *
 * @author Peter Williams
 */

public abstract class ProbingHashTable implements LookupTable {
    /**
     * Abstract method returning the index in the <tt>table</tt> of a key, 
     * if present, or the index at which to insert it, if absent.  
     * @param <tt>key</tt> the key to search for
     * @return the position where the search terminates
     */
    protected abstract int findIndex(Object key);

    // the type of data entry stored in each element of the hash table
    /**
     * A class of objects returned by iteration over entries.
     * It represents a table entry as a (key, value) pair.
     */
    protected static class Entry implements LookupTable.Entry {
        Object key;
        Object value;
        private boolean deleted;
    
        Entry(Object key, Object value) {
            this.key = key;
            this.value = value;
            deleted = false;
        }
        public Object key() {
            return key;
        }
        public Object value() {
            return value;
        }
        public String toString() {
            return "(" + key + ", " + value + ")";
        }
    }
  
    /**
     * the underlying table of hash entries
     */
    protected Entry[] table;

    private int size;           // number of items currently stored
    private int occupied;       // number of items currently stored or deleted
    private double loadFactor;  // maximum permissible load factor
    private int threshold;      // maximum size before rehashing

    /**
     * Constructs the hash table with given initial capacity and load factor.
     * The table will grow if necessary to ensure the load factor is not
     * exceeded.  The load factor must lie between 0 and 1.  Some
     * implementations of collision resolution may be more restrictive.
     * The implementation guarantees that the table length is always a prime.
     * @param <tt>capacity</tt> the initial capacity of the table
     * @param <tt>loadFactor</tt> the maximum loading before the table must grow
     * @exception <tt>IllegalArgumentException</tt> if the given load factor is
     * out of range
     */  
    ProbingHashTable(int capacity, double loadFactor) {
        if ((loadFactor <= 0.0) || (loadFactor > 1.0)) {
            throw new IllegalArgumentException("load factor out of range");
        }
        this.loadFactor = loadFactor;
        capacity = nextPrime(capacity); // make sure table capacity is prime
        table = new Entry[capacity];
        size = 0;
        occupied = 0;
        threshold = (int) (table.length * loadFactor);
    }

    public final boolean isEmpty() {
        return size == 0;
    }  

    public final int size() {
        return size;
    }

    public final boolean contains(Object key) {
        Entry e = table[findIndex(key)];
        return (e != null && !e.deleted);
    }

    public final void add(Object key, Object value) {
        int index = findIndex(key);
        Entry e = table[index];
        if (e == null) { // make the new entry
            table[index] = new Entry(key, value);
            ++size;
            ++occupied;
        } else { // we must have found the key
            e.value = value; // overwrite the value
            if (e.deleted) {
                e.deleted = false;
                ++size;
            }
        } 
        // now rehash if necessary
        if (occupied >= threshold) {
            rehash();
        }
    }

    /* rehashing method for when the table occupancy grows too large
     */
    private void rehash() {
        int capacity = nextPrime(table.length * 2);
        Entry[] oldTable = table;
        table = new Entry[capacity];
        threshold = (int) (table.length * loadFactor);
        size = 0;
        occupied = 0;
        Entry e;
        for (int i = 0; i < oldTable.length; i++ ) {
            if ((e = oldTable[i]) != null && !e.deleted) {
                add(e.key, e.value);
            }
        }
    }

    public final void remove(Object key) {
        Entry e = table[findIndex(key)];
        if (e != null && !e.deleted) {
            e.deleted = true;
            --size;
        }
    }

    public final Object lookup(Object key) {
        Entry e = table[findIndex(key)];
        if (e != null && !e.deleted) {
            return e.value;
        } else {
            throw new NoSuchElementException();
        }
    }

    public Iterator iterator() {
        return new Iterator() {
            private int index;
            private Entry current;
            private boolean removeOk;
            {
                index = 0;
                nextIndex();
                removeOk = false;
            }
            public boolean hasNext() {
                return index < table.length;
            }
            public Object next() {
                if (index == table.length) {
                    throw new NoSuchElementException();
                } else {
                    current = table[index++]; // use current index
                    nextIndex(); // find next index for future use
                    removeOk = true;
                    return current;
                }
            }
            public void remove() {
                if (removeOk) {
                    current.deleted = true;
                    --size;
                    removeOk = false;
                } else {
                    throw new IllegalStateException();
                }
            }
            private void nextIndex() { // skip over unused places
                while (index < table.length &&
                       (table[index] == null || table[index].deleted)) {
                    ++index;
                }
            }
        };
    }
  
    // returns the smallest prime number greater than or equal to n
    private final static int nextPrime(int n) {
        if (n < 2) return 2;
        if (n % 2 == 0) ++n;
        for (int i; ; n += 2) {
            for (i = 3; i * i <= n && n % i != 0; i += 2) {}
            if (i * i > n) return n;
        }
    }
    
}