#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() {
	       /* move to next object */
	       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; /* current location in bucket table */
	    std::weak_ptr<Node> prev; /* previous object, if any in the same list */
	    std::weak_ptr<Node> node; /* current object at bucket[index] */
      };

      Hash(std::size_t dim) :
	 // dim(dim), bucket(std::make_shared<NodePtr[]>(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