package hash;

import java.util.LinkedList;

/**
 * Probing based Hash Table Implementation
 * The collision is resolved through separate chaining
 * @author Winston Prakash
 */
public class ChainingHashTable<K, V> implements HashTable<K, V>{
    private transient Entry<K, V>[] data;
    private int currentSize = 0;
    
    public ChainingHashTable() {
        data = new Entry[11];
    }
    
    /**
     * Find the index corresponding to the hashcode
     * and get the current entry. Create a new entry
     * add the key and value to it as well as current
     * index entry as new entry. The new entry is the
     * current index value
     */
    public void put(K key, V value){
        int index = getIndex(key);
        Entry<K, V> entry = data[index];
        data[index] = new Entry<K, V>(key, value, entry);
        if (currentSize++ > data.length - 3){
            rehash();
        }
    }
    
    /**
     * Get the collision chain and iterate the chain to find
     * the Entry whose key is equal to the key and then return
     * the value from that entry
     */
    public V get(K key){
        int index = getIndex(key);
        for (Entry<K, V> e = data[index]; e != null; e = e.getNext()){
            if (e.getKey().equals(key)){
                return e.getValue();
            }
        }
        return null;
    }
    
    /**
     * 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;
    }
    
    /*
     * The table is almost full. Rehash the table with new table data
     * Increase the length of the new table data to twice the length
     * of current table size
     */
    private void rehash(){
        Entry<K, V>[] oldData = data;
        int newSize = 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());
            }
        }
    }
    
    /**
     * Print the data in this hash table
     */
    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]);
            }
        }
    }
    
    /**
     * Find the index of the table based on the hash code
     */
    private int getIndex(K key){
        return key.hashCode() % data.length;
    }
    
    /**
     * Collision resolution chain
     */
    private static class Entry<K, V>{
        K key;
        V value;
        Entry<K, V> next;
        Entry(K key, V value, Entry<K, V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
        
        void setNext(Entry<K, V> next){
            this.next = next;
        }
        Entry<K, V> getNext(){
            return next;
        }
        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 + "]";
        }
    }
}