hash_table.h

#ifndef HASH_TABLE_H
#define HASH_TABLE_H
 
#ifdef __cplusplus
#include <cstdint>
#include <functional>
#include <iostream>
#include <list>
#include <optional>
#include <string>
#include <unordered_map>
#include <vector>
#endif

template <typename KeyType, typename ValueType> class hash_table {
  public:
    using BucketType = std::unordered_map<size_t, std::list<std::pair<KeyType, ValueType>>>;

    inline explicit hash_table(std::vector<std::pair<KeyType, ValueType>> v = {}) {
        if (!v.empty()) {
            for (auto& x : v) {
                this->insert(x.first, x.second);
            }
        }
    }

    inline hash_table(const hash_table& h) : bucketList(h.bucketList), hash(h.hash) {}

    inline hash_table& operator=(const hash_table& h) {
        if (&this == h) {
            return *this;
        }
        bucketList = h.bucketList;
        hash = h.hash;
        return *this;
    }

    inline ~hash_table() { bucketList.clear(); }

    inline 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);
    }

    inline 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;
    }

    inline void remove(const KeyType& key) {
        auto& list = bucketList[hash(key)];
        list.remove_if([key](const auto& pair) { return pair.first == key; });
    }
 
    class Iterator;
 
    inline Iterator begin() {
        auto startIterator = bucketList.begin();
        while (startIterator != bucketList.end() && startIterator->second.empty()) {
            startIterator++;
        }
        return Iterator(startIterator, bucketList.end());
    }
 
    inline Iterator end() { return Iterator(bucketList.end(), bucketList.end()); }

    inline 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