#ifndef HASH_TABLE_HASHSET_H
#define HASH_TABLE_HASHSET_H

#include <iostream>
#include <vector>
#include <iterator>
#include <list>

template <typename ValueType, typename KeyType, typename Hash>
class HashSetIterator;

template <typename ValueType, typename KeyType, typename Hash>
class HashSet {
    using iterator = HashSetIterator<ValueType, KeyType, Hash>;
    using const_iterator = HashSetIterator<const ValueType, const KeyType, const Hash>;

    friend class HashSetIterator<ValueType, KeyType, Hash>;

private:
    std::vector<std::list<std::pair<KeyType, ValueType>>> HashTable;
    unsigned int hashTableCapacity;
    unsigned int used;

    unsigned int hashToIndex (KeyType key);

public:
    HashSet();
    explicit HashSet(unsigned int size);
    HashSet(const HashSet &) = default;
    ~HashSet() = default;

    HashSetIterator<ValueType, KeyType, Hash> insert(ValueType value);

    HashSetIterator<ValueType, KeyType, Hash> begin();

    unsigned int size() const;
    unsigned int capacity() const;
    bool empty() const;
    double fillFactor() const;
};


// iterator
template <typename ValueType, typename KeyType, typename Hash>
class HashSetIterator : std::iterator<std::bidirectional_iterator_tag, std::pair<KeyType, ValueType>>{
    friend class HashSet<ValueType, KeyType, Hash>;

private:
    HashSet<ValueType, KeyType, Hash> * from;
    unsigned int line;
    typename std::list<std::pair<KeyType, ValueType>>::iterator position;

public:
    HashSetIterator(HashSet<ValueType, KeyType, Hash> & from, unsigned int line,
                    typename std::list<std::pair<KeyType, ValueType>>::iterator position);
    explicit HashSetIterator(HashSet<ValueType, KeyType, Hash> & it);
    HashSetIterator(const HashSetIterator &) = default;
    ~HashSetIterator() = default;

    HashSetIterator& operator=(const HashSetIterator &) = default;
    bool operator!=(HashSetIterator & other) const;
    bool operator==(HashSetIterator & other) const;
    std::pair<KeyType, ValueType> & operator * ();
    HashSetIterator &operator++();
    HashSetIterator &operator--();
};

template <typename ValueType, typename KeyType, typename Hash>
HashSetIterator<ValueType, KeyType, Hash>::HashSetIterator(
        HashSet<ValueType, KeyType, Hash> & from, unsigned int line,
        typename std::list<std::pair<KeyType, ValueType>>::iterator position) {
    this->from = &from;
    this->line = line;
    this->position = position;
}

template <typename ValueType, typename KeyType, typename Hash>
HashSetIterator<ValueType, KeyType, Hash>::HashSetIterator(HashSet<ValueType, KeyType, Hash> &it) {
    from = &it;

    for(unsigned int i = 0; i < it.capacity(); ++i) {
        if (!it.HashTable[i].empty()) {
            line = i;
            position = from->HashTable[i].begin();
            return;
        }
    }

    line = it.hashTableCapacity;
}

template <typename ValueType, typename KeyType, typename Hash>
bool HashSetIterator<ValueType, KeyType, Hash>::operator==(HashSetIterator &other) const {
    if(line == other.line)
        return (position == other.position);
    else
        return false;
}

template <typename ValueType, typename KeyType, typename Hash>
bool HashSetIterator<ValueType, KeyType, Hash>::operator!=(HashSetIterator &other) const {
    if(line == other.line)
        return position != other.position;
    else
        return false;
}

template <typename ValueType, typename KeyType, typename Hash>
std::pair<KeyType, ValueType>& HashSetIterator<ValueType, KeyType, Hash>::operator*(){
    return *position;
}

template <typename ValueType, typename KeyType, typename Hash>
HashSetIterator<ValueType, KeyType, Hash>& HashSetIterator<ValueType, KeyType, Hash>::operator++() {
    if(*position == from->HashTable[line].back()){
        if(line == from->hashTableCapacity)
            ++line;
        else{
            unsigned int i;
            for(i = line + 1; i < from->hashTableCapacity; ++i){
                if(!from->HashTable[i].empty()) {
                    position = from->HashTable[i].begin();
                    line = i;
                    break;
                }}

            if(line != i)
                line = from->hashTableCapacity + 1;
        }
    } else
        ++position;

    return *this;
}

template <typename ValueType, typename KeyType, typename Hash>
HashSetIterator<ValueType, KeyType, Hash>& HashSetIterator<ValueType, KeyType, Hash>::operator--() {
    if(*position == from->HashTable[line].front()){
        if(!line)
            --line;
        else{
            unsigned int i;
            for(i = line - 1; i >= 0; --i){
                if(!from->HashTable[i].empty()) {
                    position = from->HashTable[i].begin();
                    line = i;
                    break;
                }}

            if(line != i)
                line = -1;
        }
    } else
        --position;

    return *this;
}


// constructors
template <typename ValueType, typename KeyType, typename Hash>
HashSet<ValueType, KeyType, Hash>::HashSet() {
    HashTable.resize(0);
    hashTableCapacity = (unsigned int)0;
    used = 0;
}

template <typename ValueType, typename KeyType, typename Hash>
HashSet<ValueType, KeyType, Hash>::HashSet(unsigned int size) {
    HashTable.resize(size, std::list<std::pair<KeyType, ValueType>> ());
    hashTableCapacity = size;
    used = 0;
}


// hash
template <typename ValueType, typename KeyType, typename Hash>
unsigned int HashSet<ValueType, KeyType, Hash>::hashToIndex(KeyType key) {
    if(key > 0) // must be competatible
        return (unsigned int) key % capacity();
    else
        return (unsigned int) (-key) % capacity();
}


// operations
template <typename ValueType, typename KeyType, typename Hash>
HashSetIterator<ValueType, KeyType, Hash> HashSet<ValueType, KeyType, Hash>::insert(ValueType value) {
    KeyType tempKey = Hash(value);
    unsigned int line = hashToIndex(tempKey);

    std::pair<KeyType, ValueType> insertion = std::make_pair(tempKey, value);

    if(HashTable[line].empty()){
        HashTable[line].push_front(insertion);
        return HashSetIterator<ValueType, KeyType, Hash> (*this, line, HashTable[line].begin());
    }

    typename std::list<std::pair<KeyType, ValueType>>::iterator liner;
    for(liner = HashTable[line].begin(); liner != HashTable[line].end(); ++liner){
        if(*liner == insertion)
            return HashSetIterator<ValueType, KeyType, Hash> (*this, line, liner);
    }

    HashTable[line].push_front(insertion);
    return HashSetIterator<ValueType, KeyType, Hash> (*this, line, HashTable[line].begin());
}


// access
template <typename ValueType, typename KeyType, typename Hash>
HashSetIterator<ValueType, KeyType, Hash> HashSet<ValueType, KeyType, Hash>::begin() {
    return HashSetIterator<ValueType, KeyType, Hash> (*this);
}


// statistic
template <typename ValueType, typename KeyType, typename Hash>
unsigned int HashSet<ValueType, KeyType, Hash>::size() const{
    return used;
}

template <typename ValueType, typename KeyType, typename Hash>
unsigned int HashSet<ValueType, KeyType, Hash>::capacity() const{
    return hashTableCapacity;
}

template <typename ValueType, typename KeyType, typename Hash>
bool HashSet<ValueType, KeyType, Hash>::empty() const{
    return !used;
}

template <typename ValueType, typename KeyType, typename Hash>
double HashSet<ValueType, KeyType, Hash>::fillFactor() const{
    return hashTableCapacity ? used * 1.0/hashTableCapacity : 1;
}

#endif