package com.wrox.algorithms.sets;

import com.wrox.algorithms.hashing.HashtableIterator;
import com.wrox.algorithms.iteration.ArrayIterator;
import com.wrox.algorithms.iteration.Iterator;

public class HashSet implements Set {
    /** domyślny rozmiar początkowy porcji */
    public static final int DEFAULT_CAPACITY = 17;

    /** domyślna wartość progowa współczynnika zapełnienia */
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /** początkowa liczba porcji */
    private final int _initialCapacity;

    /** wartość progowa współczynnika zapełnienia */
    private final float _loadFactor;

    /** tablica porcji przechowujących elementy */
    private ListSet[] _buckets;

    /** liczba elementów w tablicy */
    private int _size;

    /** Domyślny konstruktor. Ustala początkowy rozmiar tablicy na 17 porcji
     *  i progową wartość zapełnienia na 75% 
     */
    public HashSet() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Konstruktor. Ustala progową wartość zapełnienia na 75%
     * Parametr: początkowy rozmiar tablicy porcji
     */
    public HashSet(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Konstruktor
     *
     * Parametry:
     *  - początkowy rozmiar tablicy porcji
     *  - progowa wartość współczynnika zapełnienia
     */
    public HashSet(int initialCapacity, float loadFactor) {
        assert initialCapacity > 0 : "początkowy rozmiar tablicy musi być dodatni";
        assert loadFactor > 0 : "progowa wartość zapełnienia musi być dodatnia";

        _initialCapacity = initialCapacity;
        _loadFactor = loadFactor;
        clear();
    }

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

    public boolean add(Object value) {
        ListSet bucket = bucketFor(value);

        if (bucket.add(value)) {
            ++_size;
            maintainLoad();
            return true;
        }

        return false;
    }

    public boolean delete(Object value) {
        int bucketIndex = bucketIndexFor(value);
        ListSet bucket = _buckets[bucketIndex];
        if (bucket != null && bucket.delete(value)) {
            --_size;
            if (bucket.isEmpty()) {
                _buckets[bucketIndex] = null;
            }
            return true;
        }

        return false;
    }

    public Iterator iterator() {
        return new HashtableIterator(new ArrayIterator(_buckets));
    }

    public void clear() {
        _buckets = new ListSet[_initialCapacity];
        _size = 0;
    }

    public int size() {
        return _size;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * odnajduje porcję zawierającą wskazaną wartość
     *
     * Parametr: szukana wartość
     * Wynik: porcja zawierająca wartość
     */
    private ListSet bucketFor(Object value) {
        int bucketIndex = bucketIndexFor(value);

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

        return bucket;
    }

    /**
     * Wylicza indeks dla porcji zawierającej wskazaną wartość
     *
     * Parametr: wartość
     * Wynik: indeks porcji
     */
    private int bucketIndexFor(Object value) {
        assert value != null : "podano pustą wartość";
        return Math.abs(value.hashCode() % _buckets.length);
    }

    /**
     * Utrzymuje rozmiar tablicy na odpowiednim poziomie
     */
    private void maintainLoad() {
        if (loadFactorExceeded()) {
            resize();
        }
    }

    /**
     * Sprawdza, czy przekroczono progową wartość zapełnienia
     *
     */
    private boolean loadFactorExceeded() {
        return size() > _buckets.length * _loadFactor;
    }

    /**
     * Reorganizuje tablicę, podwajając jej rozmiar
     */
    private void resize() {
        HashSet copy = new HashSet(_buckets.length * 2, _loadFactor);

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

        _buckets = copy._buckets;
    }

    /**
     * Dodaje do tablicy wszystkie wartości danej porcji
     *
     * Parametr: porcja zawierająca wartości
     */
    private void addAll(Iterator values) {
        assert values != null : "nie określono porcji";

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