#ifndef hash_map_h
#define hash_map_h


#endif

#include <iostream>
#include <functional>
#include <list>
#include <vector>
#include <stdexcept>

template<class KeyType, class ValueType, class Hash = std::hash<KeyType>>
class HashMap {
public:
    using const_iterator = typename std::list<std::pair<const KeyType, ValueType>>::const_iterator;
    using iterator = typename std::list<std::pair<const KeyType, ValueType>>::iterator;

    HashMap() {
        table.resize(8, lst.end());
        hasher = std::hash<KeyType>();
        way = 0;
    }

    template<class Iterator>
    HashMap(Iterator left, Iterator right, Hash hasher = std::hash<KeyType>()) : hasher(hasher) {
        while (left != right) {
            insert(*left);
            ++left;
        }
    }

    HashMap(const std::initializer_list<std::pair<KeyType, ValueType>>& list,
            Hash hasher = std::hash<KeyType>()) : hasher(hasher) {
        for (auto x : list)
            insert(x);
    }

    HashMap(const HashMap<KeyType, ValueType>& other) {
        for (auto x : other)
            insert(x);
    }

    HashMap<KeyType, ValueType, Hash>& operator=(const HashMap<KeyType, ValueType>& other) {
        for (auto x : other)
            insert(x);
        return *this;
    }

    size_t size() const {
        return lst.size();
    }

    bool empty() const {
        return size() == 0;
    }

    Hash hash_function() const {
        return hasher;
    }

    void erase(const KeyType& el) {
        size_t i = hasher(el) % table.size();
        if (table[i] == lst.end()) {
            return;
        } else {
            auto it = table[i];
            while (it != lst.end() && hasher(it->first) % table.size() == i) {
                if (it->first == el) {
                    if (it == table[i]) {
                        auto nextIt = it;
                        ++nextIt;
                        if (nextIt == lst.end()) {
                            table[i] = lst.end();
                        } else {
                            if (hasher(nextIt->first) % table.size() == i)
                                table[i] = nextIt;
                            else
                                table[i] = lst.end();
                        }
                    }
                    lst.erase(it);
                    return;
                }
                ++it;
            }
        }
        return;
    }

    void insert(const std::pair<const KeyType, ValueType>& el, bool fl = true) {
        if (fl && way > MAX_WAY)
            recalc();

        size_t i = hasher(el.first) % table.size();
        if (table[i] == lst.end()) {
            lst.push_front(el);
            table[i] = lst.begin();
        } else {
            size_t curWay = 0;
            auto it = table[i];
            while (it != lst.end() && hasher(it->first) % table.size() == i) {
                if (it->first == el.first)
                    break;
                ++it;
                ++curWay;
            }
            way = std::max(curWay, way);
        }
    }

    iterator<KeyType, ValueType> begin() {
        return lst.begin();
    }

    const_iterator<KeyType, ValueType> begin() const {
        return lst.begin();
    }

    iterator<KeyType, ValueType> end() {
        return lst.end();
    }

    const_iterator<KeyType, ValueType> end() const {
        return lst.end();
    }

    iterator<KeyType, ValueType> find(const KeyType& el) {
        size_t i = hasher(el) % table.size();
        if (table[i] == lst.end()) {
            return lst.end();
        } else {
            auto it = table[i];
            while (it != lst.end() && hasher(it->first) % table.size() == i) {
                if (it->first == el)
                    return it;
                ++it;
            }
        }
        return l.end();
    }

    const_iterator<KeyType, ValueType> find(const KeyType& el) const {
        auto it = find(el);
        return it;
    }

    ValueType& operator[](const KeyType& key) {
        auto it = find(key);
        if (it == end()) {
            insert(std::make_pair(key, 0));
            return (find(key))->second;
        } else {
            return it->second;
        }
    }

    const ValueType& at(const KeyType& key) const {
        auto it = find(key);
        if (it == end())
            throw std::out_of_range("out_of_range");

        return (find(key))->second;
    }

    void clear() {
        table.clear();
        lst.clear();
        table.resize(8, lst.end());
    }

private:
    std::vector<typename std::list<std::pair<const KeyType, ValueType>>::iterator> table;
    std::list<std::pair<const KeyType, ValueType>> lst;
    Hash hasher;
    size_t way;
    size_t MAX_WAY = 50;

    void recalc() {
        std::vector<std::pair<const KeyType, ValueType>> tmp;
        for (auto x : lst)
            tmp.push_back(x);

        lst.clear();
        table.resize(table.size() * 2, lst.end());
        for (auto x : tmp)
            insert(x, false);
    }
};