/*
 * HashMap
 */

#ifndef __HASHMAP_H__
#define __HASHMAP_H__

#include "Types.h"
#include "HashMapIterator.h"

/*
 * DefaultHash
 */
template<typename Key>
struct DefaultHash
{
	/*
	 * operator()
	 */
	uint32 operator()(const Key& kKey)
	{
		return (uint32)(&kKey);
	}
};

/*
 * HashMap
 */
template<typename Key, typename Value, typename HashFunction = DefaultHash<Key>, uint32 Size = 97>
class HashMap
{
	/*
	 * Iterator
	 */
	friend class HashMapIterator<HashMap<Key, Value, HashFunction, Size>, Key, Value>;

	/*
	 * Node
	 */
	struct Node
	{
		/*
		 * kKey
		 */
		Key kKey;

		/*
		 * kValue
		 */
		Value kValue;

		/*
		 * pNext
		 */
		Node* pNext;

		/*
		 * Node
		 */
		Node(const Key& kNodeKey) : kKey(kNodeKey), pNext(NULL)
		{
			uint8* pData = (uint8*)&kValue;
			for(uint32 i = 0; i < sizeof(kValue); ++i)
				*pData++ = 0;
		}
	};

public:

	/*
	 * KeyType
	 */
	typedef Key KeyType;

	/*
	 * ValueType
	 */
	typedef Value ValueType;

	/*
	 * Iterator
	 */
	typedef HashMapIterator<HashMap<Key, Value, HashFunction, Size>, Key, Value> Iterator;

private:

	/*
	 * pTable
	 */
	Node* pTable[Size];

	/*
	 * kHash
	 */
	HashFunction kHash;

public:

	/*
	 * HashMap
	 */
	HashMap()
	{
		for(uint32 i = 0; i < Size; ++i)
		{
			pTable[i] = 0;
		}
	}

	/*
	 * ~HashMap
	 */
	~HashMap()
	{
		Clear();
	}

	/*
	 * Add
	 */
	Value* Add(const Key& kKey)
	{
		const uint32 nSlot = GetSlot(kKey);

		Node* pNode = new Node(kKey);
		pNode->pNext = pTable[nSlot];
		pTable[nSlot] = pNode;

		return &pNode->kValue;
	}

	/*
	 * Remove
	 */
	void Remove(const Key& kKey)
	{
		const uint32 nSlot = GetSlot(kKey);

		Node* pNode = pTable[nSlot];
		Node* pLast = NULL;

		while(pNode)
		{
			if(pNode->kKey == kKey)
				break;

			pLast = pNode;
			pNode = pNode->pNext;
		}

		if(pNode)
		{
			if(pLast)
			{
				pLast->pNext = pNode->pNext;
			}
			else
			{
				pTable[nSlot] = pNode->pNext;
			}

			delete pNode;
		}
	}

	/*
	 * Clear
	 */
	void Clear()
	{
		for(uint32 i = 0; i < Size; ++i)
		{
			Node* pNode = pTable[i];

			while(pNode)
			{
				Node* pItem = pNode;
				pNode = pNode->pNext;

				delete pItem;
			}

			pTable[i] = NULL;
		}
	}

	/*
	 * Find
	 */
	Value* Find(const Key& kKey)
	{
		uint32 nSlot = GetSlot(kKey);

		Node* pNode = pTable[nSlot];
		while(pNode)
		{
			if(pNode->kKey == kKey)
			{
				return &pNode->kValue;
			}
			
			pNode = pNode->pNext;
		}

		return NULL;
	}

	/*
	 * Begin
	 */
	Iterator Begin()
	{
		return Iterator(this, Size);
	}

	/*
	 * End
	 */
	Iterator End()
	{
		return Iterator(this, Size, Size);
	}

private:

	/*
	 * GetSlot
	 */
	uint32 GetSlot(const Key& kKey)
	{
		return kHash(kKey) % Size;
	}
};

#endif //__HASHMAP_H__