#ifndef TCG_HASH_H

#define TCG_HASH_H

// tcg includes

#include "list.h"

namespace tcg

{

//============================================================================================

/*!

  The hash class implements a hash map using tcg lists

*/

template <typename &)="" (*)(const="" hash_functor="size_t" k="" k,="" t,="" typename=""></typename>

class hash

{

public:

	typedef K key_type;

	typedef T value_type;

	typedef Hash_functor hash_type;

	struct BucketNode {

		K m_key;

		T m_val;

		size_t m_next;

		size_t m_prev;

		BucketNode(const K &key, const T &val) : m_key(key), m_val(val), m_next(-1), m_prev(-1) {}

		BucketNode(const std::pair<k, t=""> &pair) : m_key(pair.first), m_val(pair.second), m_next(-1), m_prev(-1) {}</k,>

		~BucketNode() {}

	};

	typedef typename tcg::list<bucketnode>::size_t size_t;</bucketnode>

	typedef typename tcg::list<bucketnode>::iterator iterator;</bucketnode>

	typedef typename tcg::list<bucketnode>::const_iterator const_iterator;</bucketnode>

private:

	std::vector<size_t> m_bucketsIdx;</size_t>

	tcg::list<bucketnode> m_items;</bucketnode>

	Hash_functor m_hash;

private:

	bool createItem(const K &key, const T &val)

	{

		m_items.push_back(BucketNode(key, val));

		size_t itemsCount = m_items.size(), bucketsCount = m_bucketsIdx.size();

		if (itemsCount > bucketsCount) {

			do

				bucketsCount = 2 * bucketsCount + 1; // Please, note that 2n here would be moronic

			while (itemsCount > bucketsCount);

			rehash(bucketsCount);

			return true;

		}

		return false;

	}

	size_t touchKey(const K &key, const T &val = T())

	{

		size_t hashValue = m_hash(key) % m_bucketsIdx.size();

		size_t bucketIdx = m_bucketsIdx[hashValue];

		size_t oldIdx = _neg;

		if (bucketIdx == _neg) {

			//A new bucket is created

			bool rehashed = createItem(key, val);

			bucketIdx = m_items.last().m_idx;

			if (!rehashed)

				//Need to manually update the stored bucket index

				m_bucketsIdx[hashValue] = bucketIdx;

			return bucketIdx;

		} else {

			//Bucket exists - search key in it

			for (;

				 bucketIdx != _neg && m_items[bucketIdx].m_key != key;

				 oldIdx = bucketIdx, bucketIdx = m_items[bucketIdx].m_next)

				;

		}

		if (bucketIdx == _neg) {

			//Key was not found - create an item and insert it

			bool rehashed = createItem(key, val);

			bucketIdx = m_items.last().m_idx;

			if (!rehashed && oldIdx != _neg) {

				//Need to relink manually

				m_items[oldIdx].m_next = bucketIdx;

				m_items[bucketIdx].m_prev = oldIdx;

			}

		}

		return bucketIdx;

	}

public:

	// NOTE: The defaulted 89 is a *good* initial buckets size when expanding by the (2n+1) rule.

	// See http://www.concentric.net/~ttwang/tech/hashsize.htm for details

	hash(const Hash_functor &func = Hash_functor(), size_t bucketsCount = 89)

		: m_bucketsIdx(bucketsCount, _neg), m_hash(func) {}

	template <typename forit=""></typename>

	hash(ForIt begin, ForIt end, const Hash_functor &func = Hash_functor(), size_t bucketsCount = 89)

		: m_items(begin, end), m_hash(func)

	{

		for (size_t nCount = m_items.nodesCount(); bucketsCount < nCount;

			 bucketsCount = 2 * bucketsCount + 1)

			;

		rehash(bucketsCount);

	}

	//! Constructs from a range of (index, value) item pairs

	template <typename bidit=""></typename>

	hash(BidIt begin, BidIt end, size_t nodesCount, const Hash_functor &func = Hash_functor(), size_t bucketsCount = 89)

		: m_items(begin, end, nodesCount), m_hash(func)

	{

		for (size_t nCount = m_items.nodesCount(); bucketsCount < nCount;

			 bucketsCount = 2 * bucketsCount + 1)

			;

		rehash(bucketsCount);

	}

	//--------------------------------------------------------------------------

	void rehash(size_t newSize)

	{

		m_bucketsIdx.clear();

		m_bucketsIdx.resize(newSize, _neg);

		size_t bucketIdx;

		iterator it, iEnd = end();

		for (it = begin(); it != iEnd; ++it) {

			bucketIdx = m_hash(it->m_key) % newSize;

			size_t &idx = m_bucketsIdx[bucketIdx];

			it->m_next = idx;

			it->m_prev = _neg;

			if (idx != _neg)

				m_items[idx].m_prev = it.m_idx;

			idx = it.m_idx;

		}

	}

	//--------------------------------------------------------------------------

	size_t size() const { return m_items.size(); }

	bool empty() { return size() == 0; }

	void clear()

	{

		m_items.clear();

		m_bucketsIdx.clear();

		m_bucketsIdx.resize(1, _neg);

	}

	//--------------------------------------------------------------------------

	iterator begin() { return m_items.begin(); }

	iterator last() { return m_items.last(); }

	iterator end() { return m_items.end(); }

	//--------------------------------------------------------------------------

	const_iterator begin() const { return m_items.begin(); }

	const_iterator last() const { return m_items.last(); }

	const_iterator end() const { return m_items.end(); }

	//--------------------------------------------------------------------------

	iterator find(const K &key)

	{

		size_t hashValue = m_hash(key) % m_bucketsIdx.size();

		size_t bucketIdx = m_bucketsIdx[hashValue];

		if (bucketIdx == _neg)

			return end();

		for (;

			 bucketIdx != _neg && m_items[bucketIdx].m_key != key;

			 bucketIdx = m_items[bucketIdx].m_next)

			;

		return bucketIdx == _neg ? end() : iterator(&m_items, bucketIdx);

	}

	const_iterator find(const K &key) const

	{

		return const_iterator(&m_items, const_cast<hash *="">(this)->find(key).m_idx);</hash>

	}

	//--------------------------------------------------------------------------

	iterator insert(const K &key, const T &val)

	{

		size_t idx = touchKey(key);

		m_items[idx].m_val = val;

		return iterator(&m_items, idx);

	}

	//--------------------------------------------------------------------------

	//!\warning Assignment of the kind hash_map[i1] = hash_map[i2] are DANGEROUS! The

	//!reference returned on the right may be INVALIDATED if the first key is inserted!

	T &operator[](const K &key)

	{

		return m_items[touchKey(key)].m_val;

	}

	//--------------------------------------------------------------------------

	//!\warning The same remark of operator[] applies here!

	T &touch(const K &key, const T &val)

	{

		return m_items[touchKey(key, val)].m_val;

	}

	//--------------------------------------------------------------------------

	iterator insert(const std::pair<k, t=""> &pair)</k,>

	{

		return insert(pair.first, pair.second);

	}

	//--------------------------------------------------------------------------

	void erase(iterator it)

	{

		BucketNode &node = *it;

		if (node.m_next != _neg)

			m_items[node.m_next].m_prev = node.m_prev;

		if (node.m_prev != _neg)

			m_items[node.m_prev].m_next = node.m_next;

		else

			m_bucketsIdx[m_hash(node.m_key) % m_bucketsIdx.size()] = _neg;

		m_items.erase(it);

	}

	//--------------------------------------------------------------------------

	void erase(const K &key)

	{

		iterator it = find(key);

		if (it != end())

			erase(it);

	}

	//--------------------------------------------------------------------------

	friend void swap(hash &a, hash &b)

	{

		using std::swap;

		a.m_bucketsIdx.swap(b.m_bucketsIdx);

		swap(a.m_items, b.m_items);

		swap(a.m_hash, b.m_hash);

	}

	//--------------------------------------------------------------------------

	const tcg::list<bucketnode> &items() const { return m_items; }</bucketnode>

	//--------------------------------------------------------------------------

	const std::vector<size_t> &buckets() const { return m_bucketsIdx; }</size_t>

	//--------------------------------------------------------------------------

	const Hash_functor &hashFunctor() const { return m_hash; }

	//!Remember to rehash() if the hash functor changes

	Hash_functor &hashFunctor() { return m_hash; }

};

} //namespace tcg

#endif // TCG_HASH_H