/**
  * Hash table
  * @author Pavel Micka
  * @param <KEY> type parameter of the key
  * @param <VALUE> type parameter of the value
  */
 public class HashTable<KEY, VALUE> {
 
     /**
      * Load factor, when reached, new (larger) table is allocated 
      */
     private final float LOAD_FACTOR = 0.75f;
     /**
      * Compress factor, when reached, the table is collapsed
      */
     private final float COLLAPSE_RATIO = 0.1f;
     /**
      * Capacity, under which the table will be never collapsed
      */
     private final int INITIAL_CAPACITY;
     /**
      * Number of elements stored
      */
     private int size = 0;
     private Entry<KEY, VALUE>[] table;
 
     /**
      * Constructs hash table with 10 capacity
      */
     public HashTable() {
         this(10); //vychozi kapacita
     }
 
     /**
      * Constructs hash table
      * @param initialCapacity initial capacity, the table will be never compressed bellow
      */
     public HashTable(int initialCapacity) {
         if (initialCapacity <= 0) {
             throw new IllegalArgumentException("Capacity must be a positive integer");
         }
         this.INITIAL_CAPACITY = initialCapacity;
         this.table = new Entry[initialCapacity];
     }
 
     /**
      * Inserts the value into the table. If some entry with the same key exists, it will be replaced.
      * @param key key
      * @param value value
      * @return null if value with the given key does not exist in the table, otherwise the replaced value
      * @throws IllegalArgumentException if the key is null
      */
     public VALUE put(KEY key, VALUE value) {
         if (key == null) {
             throw new IllegalArgumentException("Key must not be null");
         }
         VALUE val = performPut(key, value);
         if (val == null) {
             size++;
             resize();
         }
         return val;
     }
 
     /**
      * Removes element with the given key
      * @param key key
      * @return null if element with the given key is not stored in the table, otherwise the removed element
      */
     public VALUE remove(KEY key) {
         Entry<KEY, VALUE> e = getEntry(key);
         if (e == null) { //element does not exist
             return null;
         }
 
         VALUE val = e.value;
         e.key = null; //element is now a sentinel
         e.value = null; //remove the reference, so the GC may do its work
 
         size--;
         resize();
 
         return val; //return the value removed
     }
 
     /**
      * Retrieves the value associated with the given key
      * @param key key
      * @return value, null if the there is no value stored with the given key
      */
     public VALUE get(KEY key) {
         Entry<KEY, VALUE> e = getEntry(key);
         if (e == null) {
             return null;
         }
         return e.value;
     }
 
     /**
      * Query, if there is a value associated with the given key
      * @param key key
      * @return true, if there is a value associated with the given key, false otherwise
      */
     public boolean contains(KEY key) {
         return getEntry(key) != null;
     }
 
     /**
      * Returns number of stored elements 
      * @return number of stored elements
      */
     public int size() {
         return size;
     }
 
     /**
      * Returns collection of all stored values
      * @return collection of all stored values (order is not guaranteed)
      */
     public Collection<VALUE> values() {
         List<VALUE> values = new ArrayList<VALUE>(size);
         for (int i = 0; i < table.length; i++) {
             if (table[i] != null && table[i].key != null) {
                 values.add(table[i].value);
             }
         }
         return values;
     }
 
     /**
      * Returns collection of all keys
      * @return collection of all keys (order is not guaranteed)
      */
     public Collection<KEY> keys() {
         List<KEY> keys = new ArrayList<KEY>(size);
         for (int i = 0; i < table.length; i++) {
             if (table[i] != null && table[i].key != null) {
                 keys.add(table[i].key);
             }
         }
         return keys;
     }
 
     /**
      * Returns entry corresponding to the given key
      * @return the entry
      */
     private Entry getEntry(KEY key) {
         int index = key.hashCode() % table.length;
         //until we reach the empty space
         while (table[index] != null) {
             if (key.equals(table[index].key)) { //entry exists
                 return table[index];
             }
             index = (index + 1) % table.length; //continue with the next address
         }
         return null; //not found
     }
 
     /**
      * Performs the put operation itself
      *
      * If entry with the given key is already present, it will be replaced
      *
      * @param key key
      * @param value value
      * @return null if the entry was only added, otherwise value of the replaced entry
      */
     private VALUE performPut(KEY key, VALUE value) {
         Entry<KEY, VALUE> e = getEntry(key);
         if (e != null) {
             //entry is in the table
             VALUE val = e.value;
             e.value = value; //swap their values
             return val;
         }
         int index = key.hashCode() % table.length;
         while (table[index] != null && table[index].key != null) { //until we reach an empty space or a sentinel
             index = (index + 1) % table.length; //shift to the next address
         }
         if (table[index] == null) { //empty space
             table[index] = new Entry<KEY, VALUE>();
         }
         table[index].key = key;
         table[index].value = value;
 
         return null;
     }
 
     /**
      * Calculates the expected size of the table
      * @return expected size of the table
      */
     private int calculateRequiredTableSize() {
         if (this.size() / (double) table.length >= LOAD_FACTOR) { //table is overfull
             return table.length * 2;
         } else if (this.size() / (double) table.length <= COLLAPSE_RATIO) { //table should be collapsed
             return Math.max(this.INITIAL_CAPACITY, table.length / 2);
         } else {
             return table.length; //tabulka has a correct size
         }
     }
 
     /**
      * Changes the size of the table, if necessary
      */
     private void resize() {
         int requiredTableSize = calculateRequiredTableSize();
         if (requiredTableSize != table.length) { //if the table size should be changed
             Entry<KEY, VALUE>[] oldTable = table;
             table = new Entry[requiredTableSize]; //create new table
             for (int i = 0; i < oldTable.length; i++) {
                 if (oldTable[i] != null && oldTable[i].key != null) {
                     this.performPut(oldTable[i].key, oldTable[i].value); //reinsert the values
                 }
             }
         }
     }
 
     /**
      * Inner class representing the entries
      */
     private class Entry<KEY, VALUE> {
 
         /**
          * Key, null == entry is a sentinel
          */
         private KEY key;
         /**
          * Value
          */
         private VALUE value;
     }
 }