/**
 * Hashovaci tabulka
 * @author Pavel Micka
 * @param <KEY> typovy parametr klice
 * @param <VALUE> typovy parametr hodnoty
 */
public class HashTable<KEY, VALUE> {

    /**
     * Pomer zaplneni pri kterem dojde k vytvoreni nove (vetsi) tabulky
     */
    private final float LOAD_FACTOR = 0.75f;
    /**
     * Pomer zaplneni pri kterem dojde k vytvoreni nove (mensi tabulky)
     */
    private final float COLLAPSE_RATIO = 0.1f;
    /**
     * Hodnota, pod kterou nikdy neklesne velikost tabulky
     */
    private final int INITIAL_CAPACITY;
    /**
     * Pocet ulozenych prvku
     */
    private int size = 0;
    private Entry<KEY, VALUE>[] table;

    /**
     * Zkonstruuje hashovaci tabulku s vychozi kapacitou 10
     */
    public HashTable() {
        this(10); //vychozi kapacita
    }

    /**
     * Zkonstruuje hashovaci tabulku
     * @param initialCapacity kapacita, pod kterou nikdy tabulka neklesne
     */
    public HashTable(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Kapacita nesmi byt nulova nebo zaporna");
        }
        this.INITIAL_CAPACITY = initialCapacity;
        this.table = new Entry[initialCapacity];
    }

    /**
     * Vlozi prvek do tabulky, pokud jiz prvek s danym klicem existuje, tak bude nahrazen
     * @param key klic
     * @param value hodnota
     * @return null pokud klic v tabulce neexistuje, v opacnem pripade nahrazena hodnota
     * @throws IllegalArgumentException pokud je klic null
     */
    public VALUE put(KEY key, VALUE value) {
        if (key == null) {
            throw new IllegalArgumentException("Klic nesmi byt null");
        }
        VALUE val = performPut(key, value);
        if (val == null) {
            size++;
            resize();
        }
        return val;
    }

    /**
     * Odstrani prvek odpovidajici danemu klici
     * @param key klic
     * @return null pokud klic v tabulce neexistuje, v opacnem pripade odstranena hodnota
     */
    public VALUE remove(KEY key) {
        Entry<KEY, VALUE> e = getEntry(key);
        if (e == null) { //prvek neexistuje
            return null;
        }

        VALUE val = e.value;
        e.key = null; //prvek je nyni sentinelem
        e.value = null; //odstranime referenci na hodnotu, aby GC mohl cinit svou praci

        size--;
        resize();

        return val; //vratime puvodni hodnotu
    }

    /**
     * Navrati hodnotu asociovanou s danym klicem
     * @param key klic
     * @return hodnota, @null pokud neni v tabulce obsazena
     */
    public VALUE get(KEY key) {
        Entry<KEY, VALUE> e = getEntry(key);
        if (e == null) {
            return null;
        }
        return e.value;
    }

    /**
     * Dotaz na pritomnost prvku s danym klicem
     * @param key klic
     * @return true, pokud tabulka obsahuje hodnotu asociovanou s danym klicem, false v opacnem pripade
     */
    public boolean contains(KEY key) {
        return getEntry(key) != null;
    }

    /**
     * Dotaz na pocet ulozenych prvku
     * @return pocet ulozenych prvku
     */
    public int size() {
        return size;
    }

    /**
     * Kolekce vsech ulozenych hodnot
     * @return kolekce ulozenych hodnot (poradi neni zadnym zpusobem zaruceno)
     */
    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;
    }

    /**
     * Kolekce vsech klicu
     * @return kolekce vsech klicu, ktere se vyskytuji v tabulce
     */
    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;
    }

    /**
     * Vrati zaznam, ktery odpovida danemu klice
     * @return
     */
    private Entry getEntry(KEY key) {
        int index = key.hashCode() % table.length;
        //dokud nenarazime na volne misto, existujici zaznam pro klic nebo sentinel
        while (table[index] != null) {
            if (key.equals(table[index].key)) { //zaznam existuje
                return table[index];
            }
            index = (index + 1) % table.length; //prejdeme na dalsi adresu
        }
        return null; //nenalezen
    }

    /**
     * Provede samotnou operace vlozeni, aniz by jakkoliv menil informaci o velikosti
     * pole (size), pripadne menil velikost pole (resize)
     *
     * Je-li klic jiz v tabulce obsazen, tak bude asociovana hodnota nahrazena
     *
     * @param key klic
     * @param value hodnota
     * @return byl-li klic v tabulce jiz obsazen, tak nahrazena hodnota, v opacnem pripade null
     */
    private VALUE performPut(KEY key, VALUE value) {
        Entry<KEY, VALUE> e = getEntry(key);
        if (e != null) {
            //prvek je v tabulce
            VALUE val = e.value;
            e.value = value; //zamenime hodnoty
            return val;
        }
        int index = key.hashCode() % table.length;
        while (table[index] != null && table[index].key != null) { //dokud nenarazime na prazdne misto nebo sentinel
            index = (index + 1) % table.length; //posuneme se o adresu dal
        }
        if (table[index] == null) { //prazdne misto
            table[index] = new Entry<KEY, VALUE>();
        }
        table[index].key = key;
        table[index].value = value;

        return null;
    }

    /**
     * Vypocte velikost, jakou by mela tabulka mit
     * @return velikost, jakou by mela tabulka mit
     */
    private int calculateRequiredTableSize() {
        if (this.size() / (double) table.length >= LOAD_FACTOR) { //tabulka je preplnena
            return table.length * 2;
        } else if (this.size() / (double) table.length <= COLLAPSE_RATIO) {
            //vratime vetsi z hodnot SOUCASNA_VELIKOST/2 a INITIAL_CAPACITY
            return Math.max(this.INITIAL_CAPACITY, table.length / 2);
        } else {
            return table.length; //tabulka ma spravnou velikost
        }
    }

    /**
     * Zmeni velikost tabulky, je-li to nutne
     */
    private void resize() {
        int requiredTableSize = calculateRequiredTableSize();
        if (requiredTableSize != table.length) { //pokud je treba zmenit velikost tabulky
            Entry<KEY, VALUE>[] oldTable = table;
            table = new Entry[requiredTableSize]; //tak vytvorime novou tabulku
            for (int i = 0; i < oldTable.length; i++) {
                if (oldTable[i] != null && oldTable[i].key != null) {
                    this.performPut(oldTable[i].key, oldTable[i].value); //a hodnoty do ni ulozime
                }
            }
        }
    }

    /**
     * Vnitrni trida reprezentujici zaznam tabulky
     */
    private class Entry<KEY, VALUE> {

        /**
         * Klic, null == prvek je sentinel
         */
        private KEY key;
        /**
         * Hodnota
         */
        private VALUE value;
    }
}