#if !defined(__INT_HASH_H__)
#define __INT_HASH_H__

using namespace std;

#include <stdio.h>
#include <stdlib.h>

/* Hash element class entity */
template <class T>
class CHashElem
{
public:
	CHashElem<T> ()
	{
		key = 0;
		pAtom = 0;
		pNext = 0;
	}
	~CHashElem<T> ()
	{
		if (pAtom)
		{
			delete pAtom;
			pAtom = 0;
		}
	}
	
    int key;
    T *pAtom;
    CHashElem *pNext;
};

/* Hash table and its operaions */
template <class T>
class CIntHash
{
public:
	CIntHash<T>(int iSlots = 100);
	~CIntHash<T>();

	bool Insert(const int key, T *pObj);
	bool Find(const int key, T *&pObj);
	bool Remove(const int key);
	int  Size() {return m_iLength;}

 	CHashElem<T> **m_ppHashSlots;
	int m_iNumSlots;
	
private:
	int m_iLength;
};

template <class T>
CIntHash<T>::CIntHash(int iSlots)
{
	if (iSlots < 5)
	iSlots = 5;
    	
	m_ppHashSlots = (CHashElem<T> **)new char[sizeof(void *) * iSlots];
	if (0 == m_ppHashSlots)
	{
		printf("new CHashElem<T> ** failure! \n");
		exit(1);
	}
	for (int i=0; i<iSlots; i++)
		m_ppHashSlots[i] = 0;
	
	m_iNumSlots = iSlots;
	m_iLength = 0;
}

template <class T>
CIntHash<T>::~CIntHash() 
{
	if (m_ppHashSlots)
	{
		CHashElem<T> *pHe = 0;
		for (int i=0; i<m_iNumSlots; i++) 
		{
			pHe = m_ppHashSlots[i];
			while (pHe)
			{
				CHashElem<T> *pNext = pHe->pNext;
				delete pHe;
				pHe = pNext;
			}
		}
		delete [] m_ppHashSlots;
		m_ppHashSlots = 0;
	}
}

template <class T>
bool CIntHash<T>::Insert(const int key, T *pObj)
{
	unsigned int num = (unsigned int)key % m_iNumSlots;    
    if (num >= 0)
	{
		if (m_ppHashSlots[num]) 
		{
			CHashElem<T> *pIns = m_ppHashSlots[num];
			while (pIns->pNext)
			{
				pIns = pIns->pNext;
			}
			pIns->pNext = new CHashElem<T>;
			pIns->pNext->pNext = 0;
			pIns->pNext->pAtom = pObj;
			pIns->pNext->key = key;
			m_iLength++;
			
			return true;
		} 
		else 
		{
			m_ppHashSlots[num] = new CHashElem<T>;
			m_ppHashSlots[num]->pNext = 0;
			m_ppHashSlots[num]->pAtom = pObj;
			m_ppHashSlots[num]->key = key;
			m_iLength++;
			
			return true;
		}
	}
    
	printf("CIntHash Insert Failure! \n");
    
    return false;
}

template <class T>
bool CIntHash<T>::Find(const int key, T *&pObj)
{
	unsigned int num = (unsigned int)key % m_iNumSlots;    
	if (num >= 0)
	{
		CHashElem<T> *pElem = m_ppHashSlots[num];
		while (pElem) 
		{
			if (pElem->key == key) 
			{
				pObj = pElem->pAtom;
				
				return true;
			}
			pElem = pElem->pNext;
		}
    }
    
	printf("CIntHash Find Failure! \n");
    
    return false;
}

template <class T>
bool CIntHash<T>::Remove(const int key)
{
	unsigned int num = (unsigned int)key % m_iNumSlots;    
	if (num >= 0) 
	{
		CHashElem<T> *pElem = m_ppHashSlots[num];
		CHashElem<T> *pPrev = 0;
		while (pElem) 
		{
			if (pElem->key == key) 
			{
				if (pPrev) 
				{
					pPrev->pNext = pElem->pNext;
				}
				else 
				{
					m_ppHashSlots[num] = pElem->pNext;
				}
				delete pElem;
				m_iLength--;
				
				return true;
			}
			pPrev = pElem;
			pElem = pElem->pNext;
		}
	}
	
	printf("CIntHash Remove Failure! \n");
	
	return false;
}

#endif  //#if !defined(__INT_HASH_H__)