///////////////////////////////////////////////////////////////////////////////
/// @file deHash.hpp
///
/// @brief String, integer, and functor based hash tables
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Jan 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEHASH_HPP
#define DEHASH_HPP

#include "deGlobalTypes.hpp"
#include "deArray.hpp"

#ifndef NULL
#define NULL (0)
#endif

#pragma warning (disable : 4710)

template <class T>
class deTHashString
{
public:
	class HashNode
	{
	public:
		char * m_IndexString;
		T m_Data;
		HashNode *Prev, *Next;
		deTHashString * m_Hash;

		HashNode(const T & data, const char * s, HashNode * NextNode, deTHashString * Hash)
			: m_Data(data)
		{
			if (s)
			{
				m_IndexString = new char[strlen(s)+1];
				strcpy(m_IndexString, s);
			}
			else
				m_IndexString = NULL;
			Next = NextNode;
			Prev = NULL;
			m_Hash = Hash;
			if (NextNode)
				NextNode->Prev = this;
		}
		~HashNode()
		{
			if (m_IndexString)
				delete[] m_IndexString;
			if (Prev)
				Prev->Next = Next;
			if (Next)
				Next->Prev = Prev;
		}
	};

	deTHashString(DWORD size)
	: m_Elements(max(size,1)), m_HashSize(max(size,1))
	{
		DWORD i;
		m_ElementNum = 0;
		for (i = 0; i < m_HashSize; i++)
			m_Elements[i] = NULL;
	}
/*	deTHashString(const deTHashString <T> & ref)
	: m_HashSize(ref.m_HashSize)
	{
		m_ElementNum = 0;
	}
*/	~deTHashString()
	{
		RemoveAllElements();
	}

	DWORD Length()
	{
		return m_ElementNum;
	}
	T * AddElement(const T & element, const char * string)
	{
		DWORD index = HashString(string);
		HashNode * Node = new HashNode(element, string, m_Elements[index], this);
		if (!Node)
			return NULL;
		m_Elements[index] = Node;
		m_ElementNum++;
		return &(Node->m_Data);
	}
	T * FindElement(const char * string, DWORD * Index = NULL) const
	{
		HashNode * p;
		return FindElement(string, p, Index);
	}
	deBoolean RemoveElement(const char * string)
	{
		HashNode * Node;
		DWORD index;
		FindElement(string, Node, &index);
		if (Node && Node->m_Hash == this)
		{
			if (Node->Prev == NULL)
				m_Elements[index] = Node->Next;
			else
				Node->Prev->Next = Node->Next;
			delete Node;
			m_ElementNum--;
			return deTRUE;
		}
		return deFALSE;
	}
	void GetAllElements(deTArray <T*> &array)
	{
		DWORD i, j=0;
		HashNode * Node;
		array.Resize(m_ElementNum);
		for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
		{
			Node = m_Elements[i];
			while (Node)
			{
				array[j] = &(Node->m_Data);
				j++;
				Node = Node->Next;
			}
		}
	}
	void RemoveAllElements()
	{
		DWORD i, j=0;
		HashNode *Node, *Node2;
		for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
		{
			Node = m_Elements[i];
			while (Node)
			{
				Node2 = Node->Next;
				delete Node;
				Node = Node2;
				j++;
			}
			m_Elements[i] = NULL;
		}
		m_ElementNum = 0;
	}
	void operator=(const deTHashString <T> &ref)
	{
		throw "don't copy me";
		if (&ref == NULL)
			return;
	}
	T * operator[](const char * string)
	{
		HashNode * p;
		return FindElement(string, p, NULL);
	}
	
private:
	T * FindElement(const char * string, HashNode *&Node, DWORD * Index) const
	{
		DWORD index = HashString(string);
		if (Index)
			*Index = index;
		Node = m_Elements[index];
		while (Node)
		{
			if (!strcmp(Node->m_IndexString, string))
				return &(Node->m_Data);
			Node = Node->Next;
		}
		return NULL;
	}
	DWORD HashString(const char * string) const
	{
		DWORD i, length;
		if (string == NULL)
			return 0;
		for (i = 0; string[i]; i++);
		length = (i > 255) ? 255 : i;
		unsigned long * dword = (unsigned long *)string, total = 0;
		for (i = 0; i < length/4; i++)
		{
			total += *dword;
			dword++;
		}
		i *= 4;
		for (; i < length; i++)
			total += string[i];
		return total % m_HashSize;
	}
	DWORD m_ElementNum;
	const DWORD m_HashSize;
	deTArray <HashNode*> m_Elements;
};

template <class T>
class deTHashInt
{
private:
	class HashNode
	{
	public:
		T m_Data;
		DWORD m_IndexInt;
		HashNode *Prev, *Next;
	#ifdef _DEBUG
		deTHashInt * m_Hash;

		HashNode(const T & data, DWORD i, HashNode * NextNode, deTHashInt * Hash)
			: m_Data(data)
		{
			m_IndexInt = i;
			Next = NextNode;
			Prev = NULL;
			m_Hash = Hash;
			if (NextNode)
				NextNode->Prev = this;
		}
	#else
		HashNode(const T & data, DWORD i, HashNode * NextNode)
		{
			m_Data = data;
			m_IndexInt = i;
			Next = NextNode;
			Prev = NULL;
			if (NextNode)
				NextNode->Prev = this;
		}
	#endif
		~HashNode()
		{
			m_IndexInt = 0;
			if (Prev)
				Prev->Next = Next;
			if (Next)
				Next->Prev = Prev;
		}
	};
public:
	class iterator
	{
	private:
		deTHashInt<T>* mHash;
		long mIndex;
		HashNode* mNode;
	protected:
		friend class deTHashInt<T>;
		iterator(deTHashInt<T>* hash, DWORD index, HashNode* node)
			: mHash(hash), mIndex(index), mNode(node) {}
		void operator++()
		{	
			mNode = mNode->Next;
			while (mNode == NULL)
			{	++mIndex;
			if (mIndex >= mHash->m_Elements.size())
				break;
			mNode = mHash->m_Elements[mIndex];
			}
		}
	public:
		iterator() : mHash(NULL), mIndex(0), mNode(NULL) {}
		iterator(const iterator& ref) : mHash(ref.mHash), mIndex(ref.mIndex), mNode(ref.mNode) {}
		T& operator*() const
		{
			DE_ASSERT (mNode != 0);
			return mNode->m_Data;
		}
		T* operator->() const { return &operator*(); }
		bool operator==(const iterator & other) const
		{ return (mIndex == other.mIndex) && (mNode == other.mNode); }
		bool operator!=(const iterator & other) const
		{ return (mIndex != other.mIndex) || (mNode != other.mNode); }
	};

	deTHashInt(DWORD size)
	: m_Elements(max(size,1)), m_HashSize(max(size,1))
	{
		DWORD i;
		m_ElementNum = 0;
		for (i = 0; i < m_HashSize; i++)
			m_Elements[i] = NULL;
	}
/*	deTHashInt(const deTHashInt <T> & ref)
	: m_HashSize(ref.m_HashSize)
	{
		m_ElementNum = 0;
	}
*/	~deTHashInt()
	{
		RemoveAllElements();
	}

	DWORD Length()
	{
		return m_ElementNum;
	}
	T * AddElement(const T & element, DWORD Int)
	{
		DWORD index = HashInt(Int);
		HashNode * Node;
	#ifdef _DEBUG
			Node = new HashNode(element, Int, m_Elements[index], this);
	#else
			Node = new HashNode(element, Int, m_Elements[index]);
	#endif
		if (!Node)
			return NULL;
		m_Elements[index] = Node;
		m_ElementNum++;
		return &(Node->m_Data);
	}
	T * FindElement(DWORD Int, DWORD * Index = NULL) const
	{
		HashNode * p;
		return FindElement(Int, p, Index);
	}
	deBoolean RemoveElement(DWORD Int)
	{
		HashNode * Node;
		DWORD index;
		FindElement(Int, Node, &index);
	#ifdef _DEBUG
		if (Node->m_Hash != this)
			return deFALSE;
	#endif
		if (Node)
		{
			if (Node->Prev == NULL)
				m_Elements[index] = Node->Next;
			else
				Node->Prev->Next = Node->Next;
			delete Node;
			m_ElementNum--;
			return deTRUE;
		}
		return deFALSE;
	}
	void GetAllElements(deTArray <T*> &array)
	{
		DWORD i, j=0;
		HashNode * Node;
		array.Resize(m_ElementNum);
		for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
		{
			Node = m_Elements[i];
			while (Node)
			{
				array[j] = &(Node->m_Data);
				j++;
				Node = Node->Next;
			}
		}
	}
	void RemoveAllElements()
	{
		DWORD i, j=0;
		HashNode *Node, *Node2;
		for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
		{
			Node = m_Elements[i];
			while (Node)
			{
				Node2 = Node->Next;
				delete Node;
				Node = Node2;
				j++;
			}
			m_Elements[i] = NULL;
		}
		m_ElementNum = 0;
	}

	void operator=(const deTHashInt <T> &ref)
	{
		if (&ref || !&ref)
			throw "don't copy me";
	}
	T * operator[](DWORD Int) const
	{
		void * p;
		return FindElement(Int, p, NULL);
	}


	iterator find(DWORD key)
	{
		DWORD index = HashInt(key);
		HashNode* Node;
		Node = m_Elements[index];
		while (Node)
		{
			if (Node->m_IndexInt == key)
				return iterator(this, index, Node);
			Node = Node->Next;
		}
		return end();
	}
	iterator erase(iterator & entry)
	{
		iterator next = entry;
		++next;
		HashNode* current = entry.mNode;
		if (current->Prev)
			current->Prev->Next = current->Next;
		else
			m_Elements[entry.mIndex] = current->Next;
		if (current->Next)
			current->Next->Prev = current->Prev;
		delete current;
		return next;
	}
	iterator begin()
	{
		iterator first(this, -1, NULL);
		++first;
		return first;
	}
	iterator end()
	{
		return iterator(this, m_Elements.size(), NULL);
	}
	
	
private:
	T * FindElement(DWORD Int, HashNode *&Node, DWORD * Index = NULL) const
	{
		DWORD index = HashInt(Int);
		if (Index)
			*Index = index;
		Node = m_Elements[index];
		while (Node)
		{
			if (Node->m_IndexInt == Int)
				return &(Node->m_Data);
			Node = Node->Next;
		}
		return NULL;
	}
	DWORD HashInt(DWORD Int) const
	{
		return Int % m_HashSize;
	}
	DWORD m_ElementNum;
	const DWORD m_HashSize;
	deTArray <HashNode*> m_Elements;
	friend class deTHashInt<T>::iterator;
};

template <class T, class K> // T is data stored, K is key
class deTHashFunctor
{
public:
/*
	class HashExample // for use in a deTHashFunctor object
	{
	u32 m_Value;
	public:
	inline HashExample(u16 index1, u16 index2)
	{
		m_Value = index1 | (index2<<16);
	}
	inline u32 Hash() const
	{
		return m_Value;
	}
	};
*/
	class HashNode
	{
	public:
		T m_Data;
		K m_Key;
		DWORD m_HashValue;
		HashNode *Prev, *Next;
	#ifdef _DEBUG
		deTHashFunctor * m_Hash;

		HashNode(const T & data, const K& key, DWORD hash, HashNode * NextNode, deTHashFunctor * Hash)
			: m_Data(data), m_Key(key)
		{
			m_HashValue = hash;
			Next = NextNode;
			Prev = NULL;
			m_Hash = Hash;
			if (NextNode)
				NextNode->Prev = this;
		}
	#else
		HashNode(const T & data, const K& key, DWORD hash, HashNode * NextNode)
			: m_Data(data), m_Key(key)
		{
			m_HashValue = hash;
			Next = NextNode;
			Prev = NULL;
			if (NextNode)
				NextNode->Prev = this;
		}
	#endif
		~HashNode()
		{
		#ifdef _DEBUG
			m_HashValue = 0;
		#endif
			if (Prev)
				Prev->Next = Next;
			if (Next)
				Next->Prev = Prev;
		}
	};

	deTHashFunctor(const DWORD size)
	: m_Elements(max(size,1)), m_HashSize(max(size,1))
	{
		DWORD i;
		m_ElementNum = 0;
		for (i = 0; i < m_HashSize; i++)
			m_Elements[i] = NULL;
	}
/*	deTHashFunctor(const deTHashInt <T> & ref)
	: m_HashSize(ref.m_HashSize)
	{
		m_ElementNum = 0;
	}
*/	~deTHashFunctor()
	{
		RemoveAllElements();
	}

	DWORD Length()
	{
		return m_ElementNum;
	}
	T * AddElement(const T & element, const K & key)
	{
		DWORD hash = key.Hash(), index = hash%m_HashSize;
		HashNode * Node;
	#ifdef _DEBUG
			Node = new HashNode(element, key, hash, m_Elements[index], this);
	#else
			Node = new HashNode(element, key, hash, m_Elements[index]);
	#endif
		if (!Node)
			return NULL;
		m_Elements[index] = Node;
		m_ElementNum++;
		return &(Node->m_Data);
	}
	T * FindElement(const K & key, DWORD * Index = NULL) const
	{
		HashNode * p;
		return FindElement(key, p, Index);
	}
	deBoolean RemoveElement(const K & key)
	{
		HashNode * Node;
		DWORD index,hashval;
		FindElement(key, Node, &index, &hashval);
	#ifdef _DEBUG
		if (Node->m_Hash != this)
			return deFALSE;
	#endif
		if (Node)
		{
			if (Node->Prev == NULL)
				m_Elements[index] = Node->Next;
			else
				Node->Prev->Next = Node->Next;
			delete Node;
			m_ElementNum--;
			return deTRUE;
		}
		return deFALSE;
	}
	void GetAllElements(deTArray <T*> &array)
	{
		DWORD i, j=0;
		HashNode * Node;
		array.Resize(m_ElementNum);
		for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
		{
			Node = m_Elements[i];
			while (Node)
			{
				array[j] = &(Node->m_Data);
				j++;
				Node = Node->Next;
			}
		}
	}
	void RemoveAllElements()
	{
		DWORD i, j=0;
		HashNode *Node, *Node2;
		for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
		{
			Node = m_Elements[i];
			while (Node)
			{
				Node2 = Node->Next;
				delete Node;
				Node = Node2;
				j++;
			}
			m_Elements[i] = NULL;
		}
		m_ElementNum = 0;
	}

	void operator=(const deTHashFunctor <T,K> &ref)
	{
		if (&ref || !&ref)
			throw "don't copy me";
	}
	T * operator[](const K & key)
	{
		void * p;
		return FindElement(key, p, NULL);
	}
	
	
private:
	T * FindElement(const K & key, HashNode *&Node, DWORD * Index = NULL, DWORD *HashVal = NULL) const
	{
		DWORD HashValue = key.Hash();
		DWORD index = HashValue % m_HashSize;
		if (Index)
			*Index = index;
		if (HashVal)
			*HashVal = HashValue;
		Node = m_Elements[index];
		while (Node)
		{
			if (Node->m_Key == key)
				return &(Node->m_Data);
			
			Node = Node->Next;
		}
		return NULL;
	}
	DWORD m_ElementNum;
	const DWORD m_HashSize;
	deTArray <HashNode*> m_Elements;
};

//#pragma warning (default : 4710)

#endif
