package com.wrox.algorithms.hashing;

public class LinearProbingHashtable implements Hashtable {
    /** Magazyn wartości */
    private Object[] _values;

    /**
     * Konstruktor
     * Parametr: początkowy rozmiar tablicy
     */
    public LinearProbingHashtable(int initialCapacity) {
        assert initialCapacity > 0 : "rozmiar początkowy musi być dodatni";
        _values = new Object[initialCapacity];
    }

    public void add(Object value) {
        ensureCapacityForOneMore();

        int index = indexFor(value);

        if (_values[index] == null) {
            _values[index] = value;
        }
    }

    public boolean contains(Object value) {
        return indexOf(value) != -1;
    }

    public int size() {
        int size = 0;
        for (int i = 0; i < _values.length; ++i)  {
            if (_values[i] != null) {
                ++size;
            }
        }
        return size;
    }
        


    /**
     * Wylicza indeks dla podanej wartości
     *
     * Parametr: wartość do zapamiętania
     * Wynik: indeks pozycji dla wartości
     */
    private int indexFor(Object value) {
        int start = startingIndexFor(value);

        int index = indexFor(value, start, _values.length);
        if (index == -1) {
            index = indexFor(value, 0, start);
            assert index == -1 : "tablica całkowicie zapełniona";
        }

        return index;
    }

    /**
     * Wylicza indeks dla podanej wartości
     *
     * Parametry: 
     *   - wartość do zapamiętania
     *   - początkowy indeks poszukiwania
     *   - końcowy indeks poszukiwania  
     * Wynik: indeks pozycji dla wartości
     */

    private int indexFor(Object value, int start, int end) {
        assert value != null : "podano pustą wartość";

        for (int i = start; i < end; ++i) {
            if (_values[i] == null || value.equals(_values[i])) {
                return i;
            }
        }

        return -1;
    }

    /**
     * Wylicza indeks dla istniejącej wartości
     *
     * Parametr: poszukiwana wartość
     * Wynik: indeks szukanej wartości lub -1, gdy nieznaleziona
     */
    private int indexOf(Object value) {
        int start = startingIndexFor(value);

        int index = indexOf(value, start, _values.length);
        if (index == -1) {
            index = indexOf(value, 0, start);
        }
        return index;
    }

    /**
     * Wylicza indeks dla szukanej wartości
     *
     * Parametry: 
     *   - wartość do zapamiętania
     *   - początkowy indeks poszukiwania
     *   - końcowy indeks poszukiwania  
     * Wynik: indeks pozycji dla wartości lub -1, gdy nieznaleziona
     */


    private int indexOf(Object value, int start, int end) {
        assert value != null : "podano pustą wartość";

        for (int i = start; i < end; ++i) {
            if (value.equals(_values[i])) {
                return i;
            }
        }

        return -1;
    }

    /**
     * Wylicza naturalny indeks dla podanej wartości, bazując na jej skrócie haszowym
     *
     * Parametr: wartość, dla której wyliczany jest indeks
     * Wynik: indeks dla wartości
     */
    private int startingIndexFor(Object value) {
        assert value != null : "podano pustą wartość";
        return Math.abs(value.hashCode() % _values.length);
    }

    /**
     * Zapewnienie miejsca w tablicy na co najmniej jeszcze jedną wartość
     */
    private void ensureCapacityForOneMore() {
        if (size() == _values.length) {
            resize();
        }
    }

    /**
     * reorganizacja tablicy
     */
    private void resize() {
        LinearProbingHashtable copy = new LinearProbingHashtable(_values.length * 2);

        for (int i = 0; i < _values.length; ++i) {
            if (_values[i] != null) {
                copy.add(_values[i]);
            }
        }

        _values = copy._values;
    }
}
