#ifndef HASH_HPP
#define HASH_HPP

#include <cstdlib>
#include <functional>
#include <memory>
#include <utility>

template<typename Key, typename Value>
class Hash {
   public:
      using Object = std::pair<const Key, Value>;
      Hash(std::size_t dim) :
	 dim(dim), bucket(std::make_unique<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;
	    }
	 }
      }
   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::unique_ptr<NodePtr[]> bucket;
      std::hash<Key> hash;
};

#endif