#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;
   public:

      class Iterator {
	 public:
	    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 node) :
		  dim(hash.dim), bucket(hash.bucket), index(index), node(node) {
	       assert(node && index < dim);
	    }
	    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> 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]) {
      }
      bool insert(Object object) {
	 auto index = hash(object.first) % dim;
	 auto ptr = bucket[index];
	 while (ptr && ptr->object.first != object.first) {
	    ptr = ptr->next;
	 }
	 if (ptr) return false;
	 bucket[index] = std::make_shared<Node>(std::move(object),
	    bucket[index]);
	 return true;
      }
      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();
      }
};

#endif