// CMap.h: interface for the CMap class.
//
//////////////////////////////////////////////////////////////////////

#ifndef _GOS_MAP_H_
#define _GOS_MAP_H_

#define BEFORE_START_POSITION POSITION(-1)
#define DEFAULT_HASHTABLESIZE 31
#define DEFAULT_HASHKEY(key) (*PDWORD(&key) >> 4)

/////////////////////////////////////////////////////////////////////////////
// CMap<KEY,VALUE> inline functions

template<class KEY,class VALUE>
__inline int CMap<KEY,VALUE>::GetSize() const
	{ return m_nCount; }

template<class KEY,class VALUE>
__inline BOOL CMap<KEY,VALUE>::IsEmpty() const
	{ return m_nCount == 0; }

template<class KEY,class VALUE>
__inline void CMap<KEY,VALUE>::SetAt(const KEY& key, const VALUE& newValue)
	{ (*this)[key] = newValue; }

template<class KEY,class VALUE>
__inline POSITION CMap<KEY,VALUE>::GetStartPosition() const
	{ return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }

template<class KEY,class VALUE>
__inline UINT CMap<KEY,VALUE>::GetHashTableSize() const
	{ return _msize(m_pHashTable)/sizeof(CAssoc**); }

/////////////////////////////////////////////////////////////////////////////
// CMap<KEY,VALUE> out-of-line functions

template<class KEY,class VALUE>
CMap<KEY,VALUE>::CMap(int nBlockSize)
{
	m_pHashTable = NULL;
	m_nCount = 0;
	m_pFreeList = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
	DEBUG_ONLY(nBlockSize=CHeap::ElementCount(sizeof(CAssoc),nBlockSize,sizeof(CPlex*)));
	ASSERT(m_nBlockSize==nBlockSize);
}

template<class KEY,class VALUE>
void CMap<KEY,VALUE>::InitHashTable(UINT nHashSize)
//
// Used to force allocation of a hash table or to override the default
//   hash table size of (which is fairly small)
{
	ASSERT(m_nCount == 0);
	ASSERT(nHashSize > 0);

	if (m_pHashTable != NULL)
	{
		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;
	}

	m_pHashTable = new CAssoc* [nHashSize];
	memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
}

template<class KEY,class VALUE>
void CMap<KEY,VALUE>::RemoveAll()
{
	// free hash table
	delete[] m_pHashTable;
	m_pHashTable = NULL;

	m_nCount = 0;
	m_pFreeList = NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

template<class KEY,class VALUE>
CMap<KEY,VALUE>::~CMap()
{
	RemoveAll();
	ASSERT(m_nCount == 0);
}

template<class KEY,class VALUE>
typename CMap<KEY,VALUE>::CAssoc*
CMap<KEY,VALUE>::NewAssoc(const KEY& key)
{
	if (m_pFreeList == NULL)
	{
		// add another block
		CMap::CAssoc* pAssoc = (CMap::CAssoc*)CPlex::CreateHead(m_pBlocks,
			m_nBlockSize*sizeof(CMap::CAssoc));
		// free in reverse order to make it easier to debug
		pAssoc += m_nBlockSize - 1;
		for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
		{
			pAssoc->pNext = m_pFreeList;
			m_pFreeList = pAssoc;
		}
	}
	ASSERT(m_pFreeList != NULL);  // we must have something

	CMap::CAssoc* pAssoc = m_pFreeList;
	pAssoc->key=key;

	m_pFreeList = m_pFreeList->pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow
	return pAssoc;
}

template<class KEY,class VALUE>
void CMap<KEY,VALUE>::FreeAssoc(CAssoc* pAssoc)
{
	pAssoc->pNext = m_pFreeList;
	m_pFreeList = pAssoc;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)
		RemoveAll();
}

template<class KEY,class VALUE>
PVOID CMap<KEY,VALUE>::GetAssocAt(const KEY& key, UINT& nHash) const
// find association (or return NULL)
{
	if (m_pHashTable == NULL)
	{
		nHash = DEFAULT_HASHKEY(key)%DEFAULT_HASHTABLESIZE;
		return NULL;
	}
	nHash = DEFAULT_HASHKEY(key)%GetHashTableSize();

	// see if it exists
	CAssoc* pAssoc;
	for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if(pAssoc->key==key)
			return pAssoc;
	}
	return NULL;
}

template<class KEY,class VALUE>
BOOL CMap<KEY,VALUE>::Lookup(const KEY& key, VALUE& rValue) const
{
	UINT nHash;
	CAssoc* pAssoc = (CAssoc*)GetAssocAt(key, nHash);
	if (pAssoc == NULL)
		return FALSE;  // not in map

	rValue = pAssoc->value;
	return TRUE;
}

template<class KEY,class VALUE>
VALUE& CMap<KEY,VALUE>::operator[](const KEY& key)
{
	UINT nHash;
	CAssoc* pAssoc;
	if ((pAssoc = (CAssoc*)GetAssocAt(key, nHash)) == NULL)
	{
		if (m_pHashTable == NULL)
			InitHashTable(DEFAULT_HASHTABLESIZE);

		// it doesn't exist, add a new Association
		pAssoc = NewAssoc(key);

		// put into hash table
		pAssoc->pNext = m_pHashTable[nHash];
		m_pHashTable[nHash] = pAssoc;
	}
	return pAssoc->value;  // return new reference
}

template<class KEY,class VALUE>
BOOL CMap<KEY,VALUE>::RemoveKey(const KEY& key)
// remove key - return TRUE if removed
{
	if (m_pHashTable == NULL)
		return FALSE;  // nothing in the table

	CAssoc** ppAssocPrev;
	UINT nHash = DEFAULT_HASHKEY(key)%GetHashTableSize();
	ppAssocPrev = &m_pHashTable[nHash];

	CAssoc* pAssoc;
	for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if(pAssoc->key=key)
		{
			// remove it
			*ppAssocPrev = pAssoc->pNext;  // remove from list
			FreeAssoc(pAssoc);
			return TRUE;
		}
		ppAssocPrev = &pAssoc->pNext;
	}
	return FALSE;  // not found
}

template<class KEY,class VALUE>
void CMap<KEY,VALUE>::GetNextAssoc(POSITION& rNextPosition,
	KEY& rKey, VALUE& rValue) const
{
	ASSERT(m_pHashTable != NULL);  // never call on empty map

	UINT nHash;
	UINT nHSize=GetHashTableSize();
	CAssoc* pAssocRet = (CAssoc*)rNextPosition;
	ASSERT(pAssocRet != NULL);

	if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
	{
		// find the first association
		for (nHash=0 ; nHash < nHSize; nHash++)
			if ((pAssocRet = m_pHashTable[nHash]) != NULL)
				break;
		ASSERT(pAssocRet != NULL);  // must find something
	}

	// find next association
	CAssoc* pAssocNext;
	if ((pAssocNext = pAssocRet->pNext) == NULL)
	{
		// go to next bucket
		nHash = DEFAULT_HASKKEY(pAssocRet->key)%nHSize;
		for (++nHash ; nHash < nHSize; nHash++)
			if ((pAssocNext = m_pHashTable[nHash]) != NULL)
				break;
	}

	rNextPosition = (POSITION) pAssocNext;

	// fill in return data
	rKey = pAssocRet->key;
	rValue = pAssocRet->value;
}

#endif _GOS_MAP_H_