package  com.wrox.algorithms.hashing;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.lists.LinkedList;
import com.wrox.algorithms.lists.List;

public class BucketingHashtable implements Hashtable {
    /** graniczny stopień wypełnienia tablicy, po przekroczeniu którego 
     *  konieczna jest reorganizacja 
     */
    private final float _loadFactor;

    /** porcje danych */
    private List[] _buckets;

    /**
     * Konstruktor.
     *
     * Parametry: 
     *    - początkowa liczba porcji
     *    - graniczny stopień wypełnienia tablicy
     */
    public BucketingHashtable(int initialCapacity, float loadFactor) {
        assert initialCapacity > 0 : "początkowa liczba porcji musi być dodatnia";
        assert loadFactor > 0 : "graniczny stopień wypełnienia musi być dodatni";

        _loadFactor = loadFactor;
        _buckets = new List[initialCapacity];
    }

    public void add(Object value) {
        List bucket = bucketFor(value);

        if (!bucket.contains(value)) {
            bucket.add(value);
            maintainLoad();
        }
    }

    public boolean contains(Object value) {
        List bucket = _buckets[bucketIndexFor(value)];
        return bucket != null && bucket.contains(value);
    }

    public int size() {
        int size = 0;
        for (int i = 0; i < buckets.length; ++i) {
            if (_buckets[i] != null) {
                size += _buckets[i].size;
            }
        }
        return size;
    }
   
    /**
     * Odszukuje porcję zawierającą wskazaną wartość
     * 
     * Parametr: szukana wartość
     * Wynik: porcja zawierająca tę wartość
     */
    private List bucketFor(Object value) {
        int bucketIndex = bucketIndexFor(value);

        List bucket = _buckets[bucketIndex];
        if (bucket == null) {
            bucket = new LinkedList();
            _buckets[bucketIndex] = bucket;
        }

        return bucket;
    }

    /**
     * Wylicza indeks porcji, do której należy zapisać podaną wartość
     *
     * Parametr: wartość, dla której obliczany jest indeks
     * Wynik: indeks porcji
     */
    private int bucketIndexFor(Object value) {
        assert value != null : "podano pustą wartość";
        return Math.abs(value.hashCode() % _buckets.length);
    }

    /**
     * Zapewnienie właściwych rozmiarów tablicy 
     */
    private void maintainLoad() {
        if (loadFactorExceeded()) {
            resize();
        }
    }

    /**
     * Sprawdzenie, czy osiągnięto lub przekroczono graniczny stopień wypełnienia
     *
     */
    private boolean loadFactorExceeded() {
        return size() > _buckets.length * _loadFactor;
    }

    /**
     * Zwiększenie rozmiarów tablicy po przekroczeniu granicznego stopnia wypełnienia
     */
    private void resize() {
        BucketingHashtable copy = 
                new BucketingHashtable(_buckets.length * 2, _loadFactor);

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

        _buckets = copy._buckets;
    }

    /**
     * Dodanie do tablicy wszystkich wartości danej porcji
     *
     * Parametry: dodawane wartości
     */
    private void addAll(Iterator values) {
        assert values != null : "nie określono wartości";

        for (values.first(); !values.isDone(); values.next()) {
            add(values.current());
        }
    }
}
