#include<iostream>
#include<list>
#include<string>

using namespace std;

const double multiplier_up = 0.6;
const double multiplier_down = 0.2;

template<typename V>
class Hashmap
{
	using HashType = size_t;

	struct Item
	{
		HashType hash1, hash2, hash3;
		V value;
		Item(HashType _h1, HashType _h2, HashType _h3, V _v = V())
			: hash1(_h1), hash2(_h2), hash3(_h3), value(_v) {}
		bool operator==(const Item& o)
		{
			return hash1 == o.hash1 &&
				hash2 == o.hash2 &&
				hash3 == o.hash3;
		}
	};

	using Bucket = std::list<Item>;

	Bucket* data;
	size_t _size;
	// ако capacity е степен на двойката, то
	// вместо h1 % capacity ще използваме h1&(capacity-1)
	size_t _capacity;

	// http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
	/* Fowler-Noll-Vo hash */
	HashType hash1(const string& key) const
	{
		HashType h = 2166136261;
		for (size_t i = 0; i < key.size(); i++) h = (h * 16777619) ^ key[i];
		return h;
	}
	/* One-at-a-time hash by Jenkins */
	HashType hash2(const string& key) const
	{
		HashType h = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			h += key[i];
			h += (h << 10);
			h ^= (h >> 6);
		}
		h += (h << 3);
		h ^= (h >> 11);
		h += (h << 15);
		return h;
	}
	/* Shift-Add-XOR hash */
	HashType hash3(const string& key) const
	{
		HashType h = 0;
		for (size_t i = 0; i < key.size(); i++) h ^= (h << 5) + (h >> 2) + key[i];
		return h;
	}

	typename Bucket::iterator _find(HashType h1, HashType h2, HashType h3)
	{
		size_t position = h1&(_capacity - 1);
		return find(data[position].begin(),
					data[position].end(),
					Item(h1, h2, h3));
	}

	void resize(bool up)
	{
		size_t newCapacity = up ? (_capacity * 2) : (_capacity / 2);
		Bucket* newData = new Bucket[newCapacity];
		for (size_t i = 0; i < _capacity; i++)
		{
			for (auto& item : data[i])
			{
				size_t newPosition = item.hash1 & (newCapacity - 1);
				newData[newPosition].push_back(item);
			}
			data[i].clear();
		}
		delete[] data;
		data = newData;
		_capacity = newCapacity;
	}
public:
	Hashmap()
	{
		data = new Bucket[4];
		_size = 0;
		_capacity = 4;
	}
	~Hashmap() { delete[] data; }
	Hashmap(const Hashmap&) = delete;
	Hashmap& operator=(const Hashmap&) = delete;

	bool containsKey(const string& key) const
	{
		HashType h1 = hash1(key),
			h2 = hash2(key),
			h3 = hash3(key);
		size_t position = h1&(_capacity - 1);
		return _find(h1, h2, h3) != data[position].end();
	}

	void insert(const string& key, const V& value)
	{
		HashType h1 = hash1(key),
			h2 = hash2(key),
			h3 = hash3(key);
		size_t position = h1&(_capacity - 1);
		auto it = _find(h1, h2, h3);
		if (it != data[position].end()) return;
		data[position].push_back(Item(h1, h2, h3, value));
		++_size;
		if (double(_size) >= multiplier_up * double(_capacity)) resize(true);
	}

	void remove(const string& key)
	{
		HashType h1 = hash1(key),
			h2 = hash2(key),
			h3 = hash3(key);
		size_t position = h1&(_capacity - 1);
		auto it = _find(h1, h2, h3);
		if (it == data[position].end()) return;
		data[position].remove(it);
		--_size;
		if (double(_size) <= multiplier_down * double(_capacity)) resize(false);
	}

	V& operator[](const string& key)
	{
		auto it = _find(hash1(key), hash2(key), hash3(key));
		return it->value;
	}

	const V& operator[](const string& key) const
	{
		auto it = _find(hash1(key), hash2(key), hash3(key));
		return it->value;
	}

	size_t size() const
	{
		return _size;
	}

	size_t capacity() const
	{
		return _capacity;
	}

	bool empty() const
	{
		return _size == 0;
	}

	template<typename V>
	friend ostream& operator<<(ostream& os, const Hashmap<V>& hm)
	{
		if (hm._capacity > 100) return os << "Hashmap too large for printing!\n";
		os << "Distribution by buckets:\n";
		for (size_t i = 0; i < hm._capacity; i++)
		{
			os << "#" << i << ":";
			for (auto& item : hm.data[i]) os << " " << item.value;
			os << "\n";
		}
		return os << "\n";
	}
};

int main()
{
	size_t myHash(const string& str);
	Hashmap<size_t> hm;
	auto keys = { "ivancho","username123","123xyz","qwerty","lorem","ipsum" };
	for (const string& str : keys) hm.insert(str, myHash(str));
	cout << hm;

	for (const string& str : keys) cout << str << ": " << hm[str] << "\n";
}

size_t myHash(const string& str)
{
	size_t res = 0;
	for (auto c : str)
	{
		res += c;
		res <<= 2;
		res *= c;
		res = res << 32 | res >> 32;
	}
	return res;
}