hash_table.h

#ifndef HASH_TABLE_H
#define HASH_TABLE_H
 
#ifdef __cplusplus
#include <functional>
#include <iostream>
#include <list>
#include <optional>
#include <string>
#include <unordered_map>
#include <vector>
#include <cstdint>
#endif
 
template <typename KeyType, typename ValueType> class hash_table {
    public:
    using BucketType = std::unordered_map<size_t, std::list<std::pair<KeyType, ValueType>>>;
 
    hash_table(std::vector<std::pair<KeyType, ValueType>> v = {}) {
        if (!v.empty()) {
            for (auto &x : v) {
                this->insert(x.first, x.second);
            }
        }
    }
 
    hash_table(const hash_table &h) : bucketList(h.bucketList), hash(h.hash) {
 
 
    }
 
    hash_table &operator=(const hash_table &h) {
        if(&this == h){
            return *this;
        }
        bucketList = h.bucketList;
        hash = h.hash;
        return *this;
    }
 
    ~hash_table() { bucketList.clear(); }
 
    void insert(const KeyType &key, const ValueType &value) {
        auto &list = bucketList[hash(key)];
        for (auto &pair : list) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        list.emplace_back(key, value);
    }
 
    std::optional<ValueType> retrieve(const KeyType &key) {
        auto &list = bucketList[hash(key)];
        for (auto &pair : list) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return std::nullopt;
    }
 
    void remove(const KeyType &key) {
        auto &list = bucketList[hash(key)];
        list.remove_if([key](const auto &pair) { return pair.first == key; });
    }
 
    class Iterator;
 
    Iterator begin() {
        auto startIterator = bucketList.begin();
        while (startIterator != bucketList.end() && startIterator->second.empty())
        startIterator++;
        return Iterator(startIterator, bucketList.end());
    }
 
    Iterator end() {
        return Iterator(bucketList.end(), bucketList.end());
    }
 
    friend std::ostream &operator<<(std::ostream &out, hash_table<KeyType, ValueType> &h) {
        out << '[';
        for (auto &[key, list] : h.bucketList) {
            for (auto &pair : h.bucketList[key]) {
                out << "{" << pair.first << ", " << pair.second << "} ";
            }
            out << '\n';
        }
        out << ']';
        return out;
    }
 
    private:
    std::hash<KeyType> hash;
    BucketType bucketList;
};
 
template <typename KeyType, typename ValueType>
class hash_table<KeyType, ValueType>::Iterator {
    private:
    using BucketIterator = typename BucketType::iterator;
    using ListIterator = typename std::list<std::pair<KeyType, ValueType>>::iterator;
    BucketIterator bucketIter, bucketEnd;
    ListIterator listIter;
 
    std::unordered_map<size_t, std::list<std::pair<KeyType, ValueType>>>
    bucketList;
    std::vector<size_t> key_values;
    int64_t index{};
 
    public:
    explicit Iterator(BucketIterator start, BucketIterator end)
    : bucketIter(start), bucketEnd(end) {
        if (bucketIter != bucketEnd) {
            listIter = bucketIter->second.begin();
        }
    }
 
    Iterator &operator=(
        const std::unordered_map<size_t, std::list<std::pair<KeyType, ValueType>>>
        &bucket) {
            this->bucketList = bucket;
            return *(this);
        }
 
        Iterator& operator++() {
            if (++listIter == bucketIter->second.end()) {
                while (++bucketIter != bucketEnd && bucketIter->second.empty());
                if (bucketIter != bucketEnd) {
                    listIter = bucketIter->second.begin();
                }
            }
            return *this;
        }
 
        Iterator operator++(int) {
            Iterator it = *this;
            ++*(this);
            return it;
        }
 
        Iterator &operator--() {
            if (this->index > 0) {
                this->index--;
            }
            return *(this);
        }
 
        Iterator operator--(int) {
            Iterator it = *this;
            --*(this);
            return it;
        }
 
        bool operator!=(const Iterator& it) const {
            return this->bucketIter != it.bucketIter
            || (bucketIter != bucketEnd && this->listIter != it.listIter);
        }
 
        std::pair<KeyType, ValueType>& operator*() {
            return *listIter;
        }
};
 
#endif // HASH_TABLE_H