/*
	This file is part of Fennix Kernel.

	Fennix Kernel is free software: you can redistribute it and/or
	modify it under the terms of the GNU General Public License as
	published by the Free Software Foundation, either version 3 of
	the License, or (at your option) any later version.

	Fennix Kernel is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with Fennix Kernel. If not, see <https://www.gnu.org/licenses/>.
*/

#pragma once

#include <initializer_list>
#include <functional>
#include <stdexcept>
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
#include <memory>
#include <cmath>
#include <list>

namespace std
{
	template <class Key, class T, class Hash = std::hash<Key>,
			  class KeyEqual = std::equal_to<Key>,
			  class Allocator = std::allocator<std::pair<const Key, T>>>
	class unordered_multimap;

	template <class Key, class T, class Hash = std::hash<Key>,
			  class KeyEqual = std::equal_to<Key>,
			  class Allocator = std::allocator<std::pair<const Key, T>>>
	class unordered_map
	{
	public:
		using key_type = Key;
		using mapped_type = T;
		using value_type = std::pair<const Key, T>;
		using size_type = std::size_t;
		using difference_type = std::ptrdiff_t;
		using hasher = Hash;
		using key_equal = KeyEqual;
		using allocator_type = Allocator;
		using reference = value_type &;
		using const_reference = const value_type &;
		using pointer = typename std::allocator_traits<Allocator>::pointer;
		using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
		// using iterator = typename std::vector<std::list<value_type>>::iterator;
		// using const_iterator = typename std::vector<std::list<value_type>>::const_iterator;
		// using local_iterator = typename std::list<value_type>::iterator;
		// using const_local_iterator = typename std::list<value_type>::const_iterator;
		using node_type = std::list<value_type>;

		template <class Iter, class NodeType>
		struct __insert_return_type
		{
			Iter position;
			bool inserted;
			NodeType node;
		};

		class iterator
		{
			friend class unordered_map;

		public:
			using difference_type = std::ptrdiff_t;
			using value_type = std::pair<const Key, T>;
			using pointer = value_type *;
			using reference = value_type &;
			using iterator_category = std::bidirectional_iterator_tag;

		private:
			std::vector<node_type> &buckets;
			std::vector<std::list<value_type>>::iterator bucket;
			std::list<value_type>::iterator element;

		public:
			iterator(std::vector<node_type> &buckets, std::vector<std::list<value_type>>::iterator bucket, std::list<value_type>::iterator element)
				: buckets(buckets),
				  bucket(bucket),
				  element(element)
			{
			}

			iterator &operator++()
			{
				if (element != bucket->end())
					++element;
				if (element == bucket->end())
				{
					++bucket;
					while (bucket != buckets.end() && bucket->empty())
						++bucket;
					if (bucket != buckets.end())
						element = bucket->begin();
				}
				return *this;
			}

			iterator operator++(int)
			{
				auto copy = *this;
				++(*this);
				return copy;
			}

			iterator &operator--()
			{
				if (element != bucket->begin())
					--element;
				if (element == bucket->begin())
				{
					--bucket;
					while (bucket != buckets.begin() && bucket->empty())
						--bucket;
					if (bucket != buckets.begin())
						element = --bucket->end();
				}
				return *this;
			}

			iterator operator--(int)
			{
				auto copy = *this;
				--(*this);
				return copy;
			}

			reference operator*() { return *element; }
			const_reference operator*() const { return *element; }
			pointer operator->() { return &(*element); }
			const_pointer operator->() const { return &(*element); }

			bool operator==(const iterator &other) const
			{
				return bucket == other.bucket && element == other.element;
			}

			bool operator!=(const iterator &other) const
			{
				return !(*this == other);
			}
		};

		class const_iterator
		{
			friend class unordered_map;

		public:
			using difference_type = std::ptrdiff_t;
			using value_type = std::pair<const Key, T>;
			using pointer = const value_type *;
			using reference = const value_type &;
			using iterator_category = std::bidirectional_iterator_tag;

		private:
			const std::vector<node_type> &buckets;
			std::vector<std::list<value_type>>::const_iterator bucket;
			std::list<value_type>::const_iterator element;

		public:
			const_iterator(const std::vector<node_type> &buckets, std::vector<std::list<value_type>>::const_iterator bucket, std::list<value_type>::const_iterator element)
				: buckets(buckets),
				  bucket(bucket),
				  element(element)
			{
			}

			const_iterator(const iterator &it)
				: bucket(it.bucket), element(it.element)
			{
			}

			const_iterator &operator++()
			{
				if (element != bucket->end())
					++element;
				if (element == bucket->end())
				{
					++bucket;
					while (bucket != buckets.end() && bucket->empty())
						++bucket;
					if (bucket != buckets.end())
						element = bucket->begin();
				}
				return *this;
			}

			const_iterator operator++(int)
			{
				auto copy = *this;
				++(*this);
				return copy;
			}

			const_iterator &operator--()
			{
				if (element != bucket->begin())
					--element;
				if (element == bucket->begin())
				{
					--bucket;
					while (bucket != buckets.begin() && bucket->empty())
						--bucket;
					if (bucket != buckets.begin())
						element = --bucket->end();
				}
				return *this;
			}

			const_iterator operator--(int)
			{
				auto copy = *this;
				--(*this);
				return copy;
			}

			reference operator*() const { return *element; }
			pointer operator->() const { return &(*element); }

			bool operator==(const const_iterator &other) const
			{
				return bucket == other.bucket && element == other.element;
			}

			bool operator!=(const const_iterator &other) const
			{
				return !(*this == other);
			}
		};

		class local_iterator
		{
			friend class unordered_map;

		public:
			using difference_type = std::ptrdiff_t;
			using value_type = std::pair<const Key, T>;
			using pointer = value_type *;
			using reference = value_type &;
			using iterator_category = std::bidirectional_iterator_tag;

		private:
			std::list<value_type>::iterator element;

		public:
			local_iterator(std::list<value_type>::iterator element)
				: element(element)
			{
			}

			local_iterator &operator++()
			{
				++element;
				return *this;
			}

			local_iterator operator++(int)
			{
				auto copy = *this;
				++(*this);
				return copy;
			}

			local_iterator &operator--()
			{
				--element;
				return *this;
			}

			local_iterator operator--(int)
			{
				auto copy = *this;
				--(*this);
				return copy;
			}

			reference operator*() { return *element; }
			pointer operator->() { return &(*element); }

			bool operator==(const local_iterator &other) const
			{
				return element == other.element;
			}

			bool operator!=(const local_iterator &other) const
			{
				return !(*this == other);
			}
		};

		class const_local_iterator
		{
			friend class unordered_map;

		public:
			using difference_type = std::ptrdiff_t;
			using value_type = std::pair<const Key, T>;
			using pointer = const value_type *;
			using reference = const value_type &;
			using iterator_category = std::bidirectional_iterator_tag;

		private:
			std::list<value_type>::const_iterator element;

		public:
			const_local_iterator(std::list<value_type>::const_iterator element)
				: element(element)
			{
			}

			const_local_iterator &operator++()
			{
				++element;
				return *this;
			}

			const_local_iterator operator++(int)
			{
				auto copy = *this;
				++(*this);
				return copy;
			}

			const_local_iterator &operator--()
			{
				--element;
				return *this;
			}

			const_local_iterator operator--(int)
			{
				auto copy = *this;
				--(*this);
				return copy;
			}

			reference operator*() const { return *element; }
			pointer operator->() const { return &(*element); }

			bool operator==(const const_local_iterator &other) const
			{
				return element == other.element;
			}

			bool operator!=(const const_local_iterator &other) const
			{
				return !(*this == other);
			}
		};

		using insert_return_type = __insert_return_type<iterator, node_type>;

	private:
		std::vector<node_type> buckets;
		Hash hashFunction;
		double maxLoadFactor = 0.75;
		size_type elementsCount = 0;

	public:
#pragma region Member Functions

		unordered_map() = default;

		unordered_map(const unordered_map &other)
			: buckets(other.buckets)
		{
		}

		unordered_map(unordered_map &&other)
			: buckets(std::move(other.buckets))
		{
		}

		unordered_map(std::initializer_list<value_type> il)
		{
			insert(il);
		}

		~unordered_map() = default;

		unordered_map &operator=(const unordered_map &other)
		{
			buckets = other.buckets;
			return *this;
		}

		unordered_map &operator=(unordered_map &&other) /* noexcept(std::allocator_traits<Allocator>::is_always_equal::value && std::is_nothrow_move_assignable<Hash>::value && std::is_nothrow_move_assignable<Pred>::value) */
		{
			buckets = std::move(other.buckets);
			return *this;
		}

		unordered_map &operator=(std::initializer_list<value_type> ilist)
		{
			clear();
			insert(ilist);
			return *this;
		}

		allocator_type get_allocator() const noexcept
		{
			return allocator_type();
		}

#pragma endregion Member Functions

#pragma region Iterators

		iterator begin() noexcept
		{
			auto it = buckets.begin();
			while (it != buckets.end() && it->empty())
				++it;
			return iterator(buckets, it, it == buckets.end() ? typename node_type::iterator() : it->begin());
		}

		const_iterator begin() const noexcept
		{
			auto it = buckets.begin();
			while (it != buckets.end() && it->empty())
				++it;
			return const_iterator(buckets, it, it == buckets.end() ? typename node_type::const_iterator() : it->begin());
		}

		const_iterator cbegin() const noexcept
		{
			return begin();
		}

		iterator end() noexcept
		{
			return iterator(buckets, buckets.end(), typename node_type::iterator());
		}

		const_iterator end() const noexcept
		{
			return const_iterator(buckets, buckets.end(), typename node_type::const_iterator());
		}

		const_iterator cend() const noexcept
		{
			return end();
		}

#pragma endregion Iterators

#pragma region Capacity

		[[nodiscard]] bool empty() const noexcept
		{
			return elementsCount == 0; /* begin() == end() */
		}

		size_type size() const noexcept
		{
			return elementsCount; /* std::distance(begin(), end()) */
		}

		size_type max_size() const noexcept
		{
			return std::numeric_limits<difference_type>::max();
		}

#pragma endregion Capacity

#pragma region Modifiers

		void clear() noexcept
		{
			foreach (auto &bucket in buckets)
				bucket.clear();
			elementsCount = 0;
		}

		std::pair<iterator, bool> insert(const value_type &value)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(value.first) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == value.first)
					return std::make_pair(iterator(buckets, buckets.begin() + index, it), false);
			}

			bucket.push_back(value);
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(value.first) % buckets.size();
			}

			return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true);
		}

		std::pair<iterator, bool> insert(value_type &&value)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(value.first) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == value.first)
					return std::make_pair(iterator(buckets, buckets.begin() + index, it), false);
			}

			bucket.push_back(std::move(value));
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(value.first) % buckets.size();
			}

			return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true);
		}

		template <class P>
		std::pair<iterator, bool> insert(P &&value)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(value.first) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == value.first)
					return std::make_pair(iterator(buckets, buckets.begin() + index, it), false);
			}

			bucket.push_back(std::forward<P>(value));
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(value.first) % buckets.size();
			}

			return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true);
		}

		iterator insert(const_iterator hint, const value_type &value)
		{
			fixme("hint %p", &hint);
			return insert(value).first;
		}

		iterator insert(const_iterator hint, value_type &&value)
		{
			fixme("hint %p", &hint);
			return insert(std::move(value)).first;
		}

		template <class P>
		iterator insert(const_iterator hint, P &&value)
		{
			fixme("hint %p", &hint);
			return insert(std::forward<P>(value)).first;
		}

		template <class InputIt>
		void insert(InputIt first, InputIt last)
		{
			for (auto it = first; it != last; ++it)
				insert(*it);
		}

		void insert(std::initializer_list<value_type> ilist)
		{
			foreach (const auto &value in ilist)
				insert(value);
		}

		insert_return_type insert(node_type &&nh)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(nh.front().first) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == nh.front().first)
					return {iterator(buckets, buckets.begin() + index, it), false, std::move(nh)};
			}

			bucket.splice(bucket.end(), nh);
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(nh.front().first) % buckets.size();
			}

			return {iterator(buckets, buckets.begin() + index, --bucket.end()), true, std::move(nh)};
		}

		iterator insert(const_iterator hint, node_type &&nh)
		{
			fixme("hint %p", &hint);
			return insert(std::move(nh)).position;
		}

		template <class M>
		std::pair<iterator, bool> insert_or_assign(const Key &k, M &&obj)
		{
			if (auto it = find(k); it != end())
			{
				it->second = std::forward<M>(obj);
				return std::make_pair(it, false);
			}

			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(k) % buckets.size();
			auto &bucket = buckets[index];

			bucket.push_back(std::make_pair(k, std::forward<M>(obj)));
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(k) % buckets.size();
			}

			return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true);
		}

		template <class M>
		std::pair<iterator, bool> insert_or_assign(Key &&k, M &&obj)
		{
			if (auto it = find(k); it != end())
			{
				it->second = std::forward<M>(obj);
				return std::make_pair(it, false);
			}

			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(k) % buckets.size();
			auto &bucket = buckets[index];

			bucket.push_back(std::make_pair(std::move(k), std::forward<M>(obj)));
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(k) % buckets.size();
			}

			return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true);
		}

		template <class M>
		iterator insert_or_assign(const_iterator hint, const Key &k, M &&obj)
		{
			fixme("hint %p", &hint);
			return insert_or_assign(k, std::forward<M>(obj)).first;
		}

		template <class M>
		iterator insert_or_assign(const_iterator hint, Key &&k, M &&obj)
		{
			fixme("hint %p", &hint);
			return insert_or_assign(std::move(k), std::forward<M>(obj)).first;
		}

		template <class... Args>
		__deprecated_msg("Function not implemented") std::pair<iterator, bool> emplace(Args &&...args)
		{
			assert(!"std::tuple : Function not implemented");
			// size_type index = hashFunction(std::get<0>(std::forward_as_tuple(args...))) % buckets.size();
			// auto &bucket = buckets[index];

			// for (auto it = bucket.begin(); it != bucket.end(); ++it)
			// {
			// 	if (it->first == std::get<0>(std::forward_as_tuple(args...)))
			// 		return std::make_pair(iterator(buckets, buckets.begin() + index, it), false);
			// }

			// bucket.push_back(std::make_pair(std::get<0>(std::forward_as_tuple(args...)), std::get<1>(std::forward_as_tuple(args...))));
			// ++elementsCount;

			// if (elementsCount > max_load_factor() * buckets.size())
			// {
			// 	rehash(buckets.size() * 2);
			// 	index = hashFunction(std::get<0>(std::forward_as_tuple(args...))) % buckets.size();
			// }

			// return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true);
		}

		template <class... Args>
		__deprecated_msg("Function not implemented") iterator emplace_hint(const_iterator hint, Args &&...args)
		{
			fixme("hint %p", &hint);
			return emplace(std::forward<Args>(args)...).first;
		}

		template <class... Args>
		__deprecated_msg("Function not implemented") std::pair<iterator, bool> try_emplace(const Key &k, Args &&...args)
		{
			assert(!"Function not implemented");
		}

		template <class... Args>
		__deprecated_msg("Function not implemented") std::pair<iterator, bool> try_emplace(Key &&k, Args &&...args)
		{
			assert(!"Function not implemented");
		}

		template <class K, class... Args>
		__deprecated_msg("Function not implemented") std::pair<iterator, bool> try_emplace(K &&k, Args &&...args)
		{
			assert(!"Function not implemented");
		}

		template <class... Args>
		__deprecated_msg("Function not implemented") iterator try_emplace(const_iterator hint, const Key &k, Args &&...args)
		{
			assert(!"Function not implemented");
		}

		template <class... Args>
		__deprecated_msg("Function not implemented") iterator try_emplace(const_iterator hint, Key &&k, Args &&...args)
		{
			assert(!"Function not implemented");
		}

		template <class K, class... Args>
		__deprecated_msg("Function not implemented") iterator try_emplace(const_iterator hint, K &&k, Args &&...args)
		{
			assert(!"Function not implemented");
		}

		iterator erase(iterator pos)
		{
			auto &bucket = *pos.bucket;
			auto it = bucket.erase(pos.element);
			--elementsCount;
			return iterator(buckets, pos.bucket, it);
		}

		__deprecated_msg("Function not implemented") iterator erase(const_iterator pos)
		{
			assert(!"Function not implemented");
			// auto &bucket = *pos.bucket;
			// auto it = bucket.erase(pos.element);
			// --elementsCount;
			// return iterator(pos.bucket, it);
		}

		__deprecated_msg("Function not implemented") iterator erase(const_iterator first, const_iterator last)
		{
			assert(!"Function not implemented");
			// for (auto it = first; it != last; ++it)
			// 	erase(it);

			// return iterator(last.bucket, last.element);
		}

		size_type erase(const Key &key)
		{
			if (buckets.empty())
				return 0;

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
				{
					bucket.erase(it);
					--elementsCount;
					return 1;
				}
			}

			return 0;
		}

		void swap(unordered_map &other) /* noexcept(std::allocator_traits<Allocator>::is_always_equal::value && std::is_nothrow_swappable<Hash>::value && std::is_nothrow_swappable<key_equal>::value) */
		{
			std::swap(buckets, other.buckets);
		}

		__deprecated_msg("Function not implemented") node_type extract(const_iterator position)
		{
			assert(!"Function not implemented");
		}

		__deprecated_msg("Function not implemented") node_type extract(const Key &k)
		{
			assert(!"Function not implemented");
		}

		template <class H2, class P2>
		__deprecated_msg("Function not implemented") void merge(std::unordered_map<Key, T, H2, P2, Allocator> &source)
		{
			assert(!"Function not implemented");
		}

		template <class H2, class P2>
		__deprecated_msg("Function not implemented") void merge(std::unordered_map<Key, T, H2, P2, Allocator> &&source)
		{
			assert(!"Function not implemented");
		}

		template <class H2, class P2>
		__deprecated_msg("Function not implemented") void merge(std::unordered_multimap<Key, T, H2, P2, Allocator> &source)
		{
			assert(!"Function not implemented");
		}

		template <class H2, class P2>
		__deprecated_msg("Function not implemented") void merge(std::unordered_multimap<Key, T, H2, P2, Allocator> &&source)
		{
			assert(!"Function not implemented");
		}

#pragma endregion Modifiers

#pragma region Lookup

		T &at(const Key &key)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return it->second;
			}

			throw std::out_of_range("Key not found");
		}

		const T &at(const Key &key) const
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return it->second;
			}

			throw std::out_of_range("Key not found");
		}

		T &operator[](const Key &key)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return it->second;
			}

			bucket.push_back(std::make_pair(key, T()));
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(key) % buckets.size();
			}

			return bucket.back().second;
		}

		T &operator[](Key &&key)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return it->second;
			}

			bucket.push_back(std::make_pair(std::move(key), T()));
			++elementsCount;

			if (elementsCount > max_load_factor() * buckets.size())
			{
				rehash(buckets.size() * 2);
				index = hashFunction(key) % buckets.size();
			}

			return bucket.back().second;
		}

		size_type count(const Key &key) const
		{
			if (buckets.empty())
				return 0;

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return 1;
			}

			return 0;
		}

		template <class K>
		size_type count(const K &x) const
		{
			if (buckets.empty())
				return 0;

			size_type index = hashFunction(x) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == x)
					return 1;
			}

			return 0;
		}

		iterator find(const Key &key)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return iterator(buckets, buckets.begin() + index, it);
			}

			return end();
		}

		const_iterator find(const Key &key) const
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return const_iterator(buckets, buckets.begin() + index, it);
			}

			return end();
		}

		template <class K>
		iterator find(const K &x)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(x) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == (Key)x)
					return iterator(buckets, buckets.begin() + index, it);
			}

			return end();
		}

		template <class K>
		const_iterator find(const K &x) const
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(x) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == x)
					return const_iterator(buckets, buckets.begin() + index, it);
			}

			return end();
		}

		bool contains(const Key &key) const
		{
			if (buckets.empty())
				return false;

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return true;
			}

			return false;
		}

		template <class K>
		bool contains(const K &x) const
		{
			if (buckets.empty())
				return false;

			size_type index = hashFunction(x) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == x)
					return true;
			}

			return false;
		}

		std::pair<iterator, iterator> equal_range(const Key &key)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return std::make_pair(iterator(buckets, buckets.begin() + index, it), iterator(buckets, buckets.begin() + index, it));
			}

			return std::make_pair(end(), end());
		}

		std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(key) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == key)
					return std::make_pair(const_iterator(buckets, buckets.begin() + index, it), const_iterator(buckets, buckets.begin() + index, it));
			}

			return std::make_pair(end(), end());
		}

		template <class K>
		std::pair<iterator, iterator> equal_range(const K &x)
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(x) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == x)
					return std::make_pair(iterator(buckets, buckets.begin() + index, it), iterator(buckets, buckets.begin() + index, it));
			}

			return std::make_pair(end(), end());
		}

		template <class K>
		std::pair<const_iterator, const_iterator> equal_range(const K &x) const
		{
			if (buckets.empty())
				rehash(16);

			size_type index = hashFunction(x) % buckets.size();
			auto &bucket = buckets[index];

			for (auto it = bucket.begin(); it != bucket.end(); ++it)
			{
				if (it->first == x)
					return std::make_pair(const_iterator(buckets, buckets.begin() + index, it), const_iterator(buckets, buckets.begin() + index, it));
			}

			return std::make_pair(end(), end());
		}

#pragma endregion Lookup

#pragma region Bucket Interface

		local_iterator begin(size_type n)
		{
			return buckets[n].begin();
		}

		const_local_iterator begin(size_type n) const
		{
			return buckets[n].begin();
		}

		const_local_iterator cbegin(size_type n) const
		{
			return buckets[n].begin();
		}

		local_iterator end(size_type n)
		{
			return buckets[n].end();
		}

		const_local_iterator end(size_type n) const
		{
			return buckets[n].end();
		}

		const_local_iterator cend(size_type n) const
		{
			return buckets[n].end();
		}

		size_type bucket_count() const
		{
			return buckets.size();
		}

		size_type max_bucket_count() const
		{
			return buckets.max_size();
		}

		size_type bucket_size(size_type n) const
		{
			if (n >= buckets.size())
				return 0;

			return buckets[n].size();
		}

		size_type bucket(const Key &key) const
		{
			assert(!buckets.empty());

			return hashFunction(key) % buckets.size();
		}

#pragma endregion Bucket Interface

#pragma region Hash Policy

		float load_factor() const
		{
			return static_cast<float>(size()) / static_cast<float>(bucket_count());
		}

		float max_load_factor() const
		{
			return maxLoadFactor;
		}

		void max_load_factor(float ml)
		{
			maxLoadFactor = ml;
		}

		void rehash(size_type count)
		{
			debug("Rehashing to %d", count);

			size_type currentLoadFactor = size() / max_load_factor();
			if (count < currentLoadFactor)
			{
				debug("count %d => %d", count, currentLoadFactor);
				count = currentLoadFactor;
			}

			std::vector<node_type> newBuckets(count);
			for (const auto &bucket : buckets)
			{
				for (const auto &element : bucket)
				{
					size_type newIndex = hashFunction(element.first) % count;
					newBuckets[newIndex].push_back(element);
				}
			}

			buckets = std::move(newBuckets);
		}

		void reserve(size_type count)
		{
			rehash(std::ceil(count / max_load_factor()));
		}

#pragma endregion Hash Policy

#pragma region Observers

		hasher hash_function() const
		{
			return hashFunction;
		}

		key_equal key_eq() const
		{
			return key_equal();
		}

#pragma endregion Observers
	};

	template <class Key, class T, class Hash, class KeyEqual, class Alloc>
	bool operator==(const std::unordered_map<Key, T, Hash, KeyEqual, Alloc> &lhs,
					const std::unordered_map<Key, T, Hash, KeyEqual, Alloc> &rhs)
	{
		return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
	}
}