package hash;

/**
 * Probing based Hash Table Implementation
 * The collision is resolved through quadratic probing
 * @author Winston Prakash
 */
public class ProbingHashTable<K, V> implements HashTable<K, V>{
    private transient  Entry<K, V>[] data;
    private int currentSize = 0;
    
    public ProbingHashTable() {
        data = new Entry[11];
    }
    
    /**
     * Put the value at the index of the table based on hash code of key
     */
    public void put(K key, V value){
        int index = getIndex(key);
        data[index] =  new Entry<K, V>(key, value);
        if (currentSize++ > data.length - 3){
            rehash();
        }
    }
    
    /**
     * Check if the hash table contains the key
     */
    public boolean contains(K key){
        int index = getIndex(key);
        return data[index] != null;
    }
    
    /**
     * Remove the entry corresponding to the key
     */
    public void remove(K key){
        int index = getIndex(key);
        data[index] = null;
    }
    
    /**
     * Get the value from the index of the table based on hash code of key
     */
    public V get(K key){
        int index = getIndex(key);
        return data[index].getValue();
    }
    
    public void display(){
        System.out.println("Probing Hash Table data");
        for (int i = 0; i < data.length; i++){
            if (data[i] != null){
                System.out.println(data[i]);
            }
        }
    }
    
    /*
     * The table is almost full. Rehash the table with new table data
     * Increase the length of the new table data to prime number next
     * to the twice the length of current table size
     */
    private void rehash(){
        Entry<K, V>[] oldData = data;
        int newSize = findNextPrime(oldData.length * 2);
        data = new Entry[newSize];
        for (int i = 0; i < oldData.length; i++){
            if (oldData[i] != null){
                put(oldData[i].getKey(), oldData[i].getValue());
            }
        }
    }
    
    /**
     * Get the index of the table based on hash code
     * The simple algorithm is to find the reminder after diving the hash
     * code with table length, so table length being prime number may be
     * useful
     */
    private int getIndex(K key){
        int offset = 1;
        int index = key.hashCode() % data.length;
        while ((data[index] != null) && !data[index].getKey().equals(key)){
            index = offset;
            offset += 2;
            if (index >= data.length){
                index -= data.length;
            }
        }
        return index;
    }
    
    public int findNextPrime(int num){
        if ((num % 2) == 0){
            num++;
        }
        for (; !(isPrime(num)); num+= 2){
            ;
        }
        return num;
    }
    
    public boolean isPrime(long number){
        boolean isPrime = true;
        if ((number % 2) == 0 ) return false;
        for(long i = 3; i < number/2; i += 2){
            if ((number % i) == 0) {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }
    
    /**
     * HashTable entry
     */
    private static class Entry<K, V>{
        K key;
        V value;
        Entry(K key, V value){
            this.key = key;
            this.value = value;
        }
        
        void setValue(V value){
            this.value = value;
        }
        V getValue(){
            return value;
        }
        void setKey(K key){
            this.key = key;
        }
        K getKey(){
            return key;
        }
        
        public String toString(){
            return "[key = " + key + " , " + value + "]";
        }
    }
}