#ifndef HASH_HPP
#define HASH_HPP
#include <cassert>
#include <cstdlib>
#include <functional>
#include <memory>
#include <utility>
template<typename Key, typename Value>
class Hash {
public:
using Object = std::pair<const Key, Value>;
private:
struct Node;
using NodePtr = std::shared_ptr<Node>;
struct Node {
Node(Object object) : object(std::move(object)) {
}
Node(Object object, NodePtr next) :
object(std::move(object)), next(next) {
}
Object object;
NodePtr next;
};
const std::size_t dim;
std::shared_ptr<NodePtr[]> bucket;
std::hash<Key> hash;
std::size_t count;
public:
class Iterator {
public:
friend Hash;
Iterator() : dim(0), index(0) {
}
Iterator(Hash& hash) :
dim(hash.dim), bucket(hash.bucket), index(0) {
advance();
}
Iterator(Hash& hash, std::size_t index, NodePtr prev, NodePtr node) :
dim(hash.dim), bucket(hash.bucket), index(index),
prev(prev), node(node) {
assert(node && index < dim);
}
Object& operator*() {
return node.lock()->object;
}
const Object& operator*() const {
return node.lock()->object;
}
Object* operator->() {
return &node.lock()->object;
}
Iterator& operator++() {
advance();
return *this;
}
bool operator==(const Iterator& other) {
bool end1 = index >= dim;
bool end2 = other.index >= other.dim;
if (end1 && end2) return true;
if (end1 || end2) return false;
return
bucket.lock() == other.bucket.lock() &&
index == other.index &&
node.lock() == other.node.lock();
}
bool operator!=(const Iterator& other) {
return !(*this == other);
}
private:
void advance() {
auto b = bucket.lock();
if (b) {
auto n = node.lock();
if (n) {
node = n->next;
n = node.lock();
if (!n) ++index;
}
if (!n) {
while (index < dim && !b[index]) {
++index;
}
if (index < dim) {
node = b[index];
}
}
} else {
node = NodePtr(); index = dim;
}
}
std::size_t dim;
std::weak_ptr<NodePtr[]> bucket;
std::size_t index;
std::weak_ptr<Node> prev;
std::weak_ptr<Node> node;
};
Hash(std::size_t dim) :
dim(dim), bucket(new NodePtr[dim]), count(0) {
}
std::pair<Iterator, bool> insert(Object object) {
auto index = hash(object.first) % dim;
auto ptr = bucket[index];
NodePtr prev;
while (ptr && ptr->object.first != object.first) {
prev = ptr; ptr = ptr->next;
}
bool inserted;
if (ptr) {
inserted = false;
} else {
ptr = std::make_shared<Node>(std::move(object), bucket[index]);
bucket[index] = ptr;
prev = nullptr;
inserted = true;
++count;
}
return std::make_pair(Iterator(*this, index, prev, ptr), inserted);
}
Iterator find(Key key) {
auto index = hash(key) % dim;
auto ptr = bucket[index];
NodePtr prev;
while (ptr && ptr->object.first != key) {
prev = ptr; ptr = ptr->next;
}
if (ptr) {
return Iterator(*this, index, prev, ptr);
} else {
return Iterator();
}
}
void erase(Iterator it) {
if (it.bucket.lock() == bucket && it.index < dim) {
auto node = it.node.lock();
auto prev = it.prev.lock();
if (node) {
if (prev) {
prev->next = node->next;
} else {
bucket[it.index] = node->next;
}
--count;
}
}
}
template<typename F>
void for_each(F&& f) {
for (std::size_t index = 0; index < dim; ++index) {
auto ptr = bucket[index];
while (ptr) {
f(ptr->object);
ptr = ptr->next;
}
}
}
Iterator begin() {
return Iterator(*this);
}
Iterator end() {
return Iterator();
}
std::size_t size() const {
return count;
}
};
#endif