HashMap

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


template<class KeyType, class ValueType, class Hash = std::hash<KeyType> >
class HashMap {
private:
    const size_t max_buckets = 3; // should be prime
    struct element {
        std::pair<const KeyType, ValueType> pair;
        element() = default;
        element(const element& other) = default;
        element(element&& other) = default;
        element& operator=(const element& other) {
            pair.second = other.pair.second;
            return *this;
        }
        element& operator=(element&& other) {
            pair = other.pair;
            return *this;
        }
    };
    std::list<size_t> used_buckets_list;
    std::vector<std::list<element>> data;
    std::vector<std::list<size_t>::iterator> list_pointers;
    Hash hasher;
    size_t num_objects;

    size_t shrink_hash(size_t hash) const {
        return hash % max_buckets;
    }

public:
    HashMap() {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators
    }

    HashMap(const Hash input_hasher): hasher(input_hasher) {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators
    }

    HashMap(const HashMap& other):
            data(other.data),
            list_pointers(other.list_pointers),
            used_buckets_list(other.used_buckets_list),
            num_objects(other.num_objects),
            hasher(other.hasher)
    {}
    HashMap(HashMap&& other) :
            data(std::move(other.data)),
            list_pointers(other.list_pointers),
            used_buckets_list(std::move(other.ids)),
            num_objects(other.num_objects),
            hasher(other.hasher)
    {}

    HashMap& operator = (const HashMap& other) {
        data = other.data;
        list_pointers = other.list_pointers;
        used_buckets_list = other.used_buckets_list;
        num_objects = other.num_objects;
        hasher = other.hasher;
        return *this;
    }
    HashMap& operator = (HashMap&& other) {
        data = std::move(other.data);
        list_pointers = std::move(other.list_pointers);
        used_buckets_list = std::move(other.used_buckets_list);
        num_objects = other.num_objects;
        hasher = other.hasher;
        return *this;
    }

    template<class Container = HashMap>
    HashMap(typename Container::iterator first, typename Container::iterator last) {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators

        for (auto it = first; it != last; ++it) {
            insert(*it);
        }
    }
    template<class Container = HashMap>
    HashMap(typename Container::iterator first, typename Container::iterator last, const Hash input_hasher): hasher(input_hasher)  {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators

        for (auto it = first; it != last; ++it) {
            insert(*it);
        }
    }
    template<class Container = HashMap>
    HashMap(typename Container::const_iterator first, typename Container::const_iterator last) {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators

        for (auto it = first; it != last; ++it) {
            insert(*it);
        }
    }
    template<class Container = HashMap>
    HashMap(typename Container::const_iterator first, typename Container::const_iterator last, const Hash input_hasher): hasher(input_hasher)  {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators

        for (auto it = first; it != last; ++it) {
            insert(*it);
        }
    }

    HashMap(std::initializer_list<std::pair<KeyType, ValueType>> _data) {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators

        for (auto elem: _data) {
            insert(elem);
        }
    }
    HashMap(std::initializer_list<std::pair<KeyType, ValueType>> _data, const Hash input_hasher): hasher(input_hasher)  {
        num_objects = 0;
        data.resize(max_buckets + 1);
        list_pointers.resize(max_buckets + 1); // +1 is for iterators

        for (auto elem : _data) {
            insert(elem);
        }
    }

    size_t size() const {
        return num_objects;
    }

    bool empty() const {
        if (num_objects == 0) {
            return true;
        } else {
            return false;
        }
    }

    size_t hash_function(const ValueType value) const {
        return hasher(value);
    }

    void insert(const std::pair<const KeyType, ValueType> input) {
        size_t bucket_id = shrink_hash(hasher(input.first));

        for (auto it = data[bucket_id].begin(); it != data[bucket_id].end(); ++it) {
            if (it->pair.first == input.first) {
                return;
            }
        }

        if (data[bucket_id].empty()) {
            used_buckets_list.push_back(bucket_id);
            list_pointers[bucket_id] = std::prev(used_buckets_list.end());
        }
        data[bucket_id].push_back({{input.first, input.second}});
        ++num_objects;
    }

    void erase(const KeyType key) {
        size_t bucket_id = shrink_hash(hasher(key));

        if (data[bucket_id].empty()) {
            return;
        }

        if (data[bucket_id].size() == 1) {
            if (data[bucket_id].front().pair.first == key) {
                used_buckets_list.erase(list_pointers[bucket_id]);
                data[bucket_id].pop_front();
                --num_objects;
            }
        } else {
            for (auto it = data[bucket_id].begin(); it != data[bucket_id].end(); ++it) {
                if (it->pair.first == key) {
                    data[bucket_id].erase(it);
                    --num_objects;
                    return;
                }
            }
        }
    }

    ValueType &operator[](const KeyType key) {
        size_t bucket_id = shrink_hash(hasher(key));

        for (auto it = data[bucket_id].begin(); it != data[bucket_id].end(); ++it) {
            if (it->pair.first == key) {
                return it->pair.second;
            }
        }
        if (data[bucket_id].empty()) {
            used_buckets_list.push_back(bucket_id);
            list_pointers[bucket_id] = std::prev(used_buckets_list.end());
        }
        data[bucket_id].push_back({{key, ValueType()}});
        ++num_objects;
        return data[bucket_id].back().pair.second;
    }

    const ValueType & at(KeyType key) const {
        size_t bucket_id = shrink_hash(hasher(key));

        for (auto it = data[bucket_id].begin(); it != data[bucket_id].end(); ++it) {
            if (it->pair.first == key) {
                return it->pair.second;
            }
        }
        throw std::out_of_range("bad key");
    }

    void clear() {
        for (auto bucket_id : used_buckets_list) {
            data[bucket_id].clear();
        }
        num_objects = 0;
        used_buckets_list.clear();
    }

    Hash hash_function() const {
        return hasher;
    }

    class iterator {
    private:
        std::vector<std::list<element>> *data;
        std::list<size_t> *used_buckets_list;

        std::list<size_t>::iterator  current_bucket_iterator; // used_buckets_list
        typename std::list<element>::iterator  in_bucket_iterator; // in data list

    public:
        iterator() = default;
        iterator(const iterator &) = default;
        iterator(iterator &&) = default;
        iterator(
                std::vector<std::list<element>> *input_data,
                std::list<size_t>::iterator  input_current_bucket_iterator,
                typename std::list<element>::iterator  input_in_bucket_iterator,
                std::list<size_t> *input_used_buckets_list
        ) :
                data(input_data),
                current_bucket_iterator(input_current_bucket_iterator),
                in_bucket_iterator(input_in_bucket_iterator),
                used_buckets_list(input_used_buckets_list){}

        iterator &operator++() {
            ++in_bucket_iterator;
            if (in_bucket_iterator == (*data)[*current_bucket_iterator].end()) {
                ++current_bucket_iterator;
                if (current_bucket_iterator != (*used_buckets_list).end())
                    in_bucket_iterator = (*data)[*current_bucket_iterator].begin();
                else
                    in_bucket_iterator = (*data)[*(*used_buckets_list).begin()].begin();
            }
            return *this;
        }

        iterator operator++(int) {
            auto temp = *this;
            ++(*this);
            return temp;
        }

        std::pair<const KeyType, ValueType> operator*() const {
            return in_bucket_iterator->pair;
        }

        std::pair<const KeyType, ValueType> *operator->() const {
            return &(in_bucket_iterator->pair);
        }

        friend bool operator==(const iterator &it1,
                               const iterator &it2) {
            return it1.current_bucket_iterator == it2.current_bucket_iterator &&
                   it1.in_bucket_iterator == it2.in_bucket_iterator;
        }

        bool operator!=(const iterator &it1) const {
            return !((*this) == it1);
        }

        iterator& operator=(const iterator& other) {
            data = other.data;
            used_buckets_list = other.used_buckets_list;
            current_bucket_iterator = other.current_bucket_iterator;
            in_bucket_iterator = other.in_bucket_iterator;
            return *this;
        }

        iterator& operator=(iterator&& other) {
            data = other.data;
            used_buckets_list = other.used_buckets_list;
            current_bucket_iterator = other.current_bucket_iterator;
            in_bucket_iterator = other.in_bucket_iterator;
            return *this;
        }

    };

    class const_iterator {
    private:
        const std::vector<std::list<element>> *data;
        const std::list<size_t> *used_buckets_list;

        std::list<size_t>::const_iterator  current_bucket_iterator; // used_buckets_list
        typename std::list<element>::const_iterator  in_bucket_iterator; // in data list

    public:
        const_iterator() = default;
        const_iterator(const const_iterator &) = default;
        const_iterator(const_iterator &&) = default;
        const_iterator(
                const std::vector<std::list<element>> *input_data,
                std::list<size_t>::const_iterator  input_current_bucket_iterator,
                typename std::list<element>::const_iterator  input_in_bucket_iterator,
                const std::list<size_t> *input_used_buckets_list
        ) :
                data(input_data),
                current_bucket_iterator(input_current_bucket_iterator),
                in_bucket_iterator(input_in_bucket_iterator),
                used_buckets_list(input_used_buckets_list){}

        const_iterator &operator++() {
            ++in_bucket_iterator;
            if (in_bucket_iterator == (*data)[*current_bucket_iterator].end()) {
                ++current_bucket_iterator;
                if (current_bucket_iterator != (*used_buckets_list).end())
                    in_bucket_iterator = (*data)[*current_bucket_iterator].begin();
                else
                    in_bucket_iterator = (*data)[*(*used_buckets_list).begin()].begin();
            }
            return *this;
        }

        const_iterator operator++(int) {
            auto temp = *this;
            ++(*this);
            return temp;
        }

        const std::pair<const KeyType, ValueType> operator*() const {
            return in_bucket_iterator->pair;
        }

        const std::pair<const KeyType, ValueType> *operator->() const {
            return &(in_bucket_iterator->pair);
        }

        friend bool operator==(const const_iterator &it1,
                               const const_iterator &it2) {
            return it1.current_bucket_iterator == it2.current_bucket_iterator &&
                   it1.in_bucket_iterator == it2.in_bucket_iterator;
        }

        bool operator!=(const const_iterator &it1) const {
            return !((*this) == it1);
        }

        const_iterator& operator=(const const_iterator& other) {
            data = other.data;
            used_buckets_list = other.used_buckets_list;
            current_bucket_iterator = other.current_bucket_iterator;
            in_bucket_iterator = other.in_bucket_iterator;
            return *this;
        }

        const_iterator& operator=(const_iterator&& other) {
            data = other.data;
            used_buckets_list = other.used_buckets_list;
            current_bucket_iterator = other.current_bucket_iterator;
            in_bucket_iterator = other.in_bucket_iterator;
            return *this;
        }
    };

    iterator begin() {
        if (num_objects != 0) {
            return iterator{&data, used_buckets_list.begin(), data[*used_buckets_list.begin()].begin(), &used_buckets_list};
        }
        return iterator{&data, used_buckets_list.begin(), data[max_buckets].begin(), &used_buckets_list};
    }

    iterator end() {
        if (num_objects != 0) {
            return iterator{&data, used_buckets_list.end(), data[*used_buckets_list.begin()].begin(), &used_buckets_list};
        }
        return iterator{&data, used_buckets_list.begin(), data[max_buckets].begin(), &used_buckets_list};
    }

    const_iterator begin() const {
        if (num_objects != 0) {
            return const_iterator{&data, used_buckets_list.begin(), data[*used_buckets_list.begin()].begin(), &used_buckets_list};
        }
        return const_iterator{&data, used_buckets_list.begin(), data[max_buckets].begin(), &used_buckets_list};
    }

    const_iterator end() const {
        if (num_objects != 0) {
            return const_iterator{&data, used_buckets_list.end(), data[*used_buckets_list.begin()].begin(), &used_buckets_list};
        }
        return const_iterator{&data, used_buckets_list.begin(), data[max_buckets].begin(), &used_buckets_list};
    }

    iterator find(KeyType key) {
        size_t bucket_id = shrink_hash(hasher(key));

        for (auto it = data[bucket_id].begin(); it != data[bucket_id].end(); ++it) {
            if (it->pair.first == key) {
                return iterator(&data, list_pointers[bucket_id], it, &used_buckets_list);
            }
        }
        return end();
    }

    const_iterator find(KeyType key) const {
        size_t bucket_id = shrink_hash(hasher(key));

        for (auto it = data[bucket_id].begin(); it != data[bucket_id].end(); ++it) {
            if (it->pair.first == key) {
                return const_iterator(&data, list_pointers[bucket_id], it, &used_buckets_list);
            }
        }
        return end();
    }

};