#ifndef __MCHash__
#define __MCHash__
/************************************************************************************************************

  		MCHash.h

  		Copyright: (c) 2001 Eovia Corp. All rights reserved.

  		Author:	Arnaud
		Date:	10/6/98

  		Revision History

  		when		who			what & why
		==========	==========	=====================================================================================
		12/23/98	Frh			Set found parameter correctly

************************************************************************************************************/

#if CP_PRAGMA_ONCE
#pragma once
#endif


#include "MCArray.h"
#include "MCClassArray.h"
#include "MCPtrArray.h"
#include "MCException.h"


#define kNotFound -1


/*
 *  TMCHashCommon
 */

template <class Key, class T> class TMCHashCommon
{
	public:	
		
		typedef Key	TKeyType;

		TMCHashCommon(uint32 size); //size must be > 0
		~TMCHashCommon();
		
		// Set the number of elements to have memory allocated for.
		virtual boolean SetElemSpace(const uint32 n);		
		
		inline T&			operator[](uint32 i) {return fHashData[i];}
		inline uint32		GetElemCount(void) const {return fHashData.GetElemCount();}

		inline virtual void	ResetDatas() {fHashData.SetElemCount(0); for(uint32 ii=0; ii < fSize; ii++){fHashTable[ii]->SetElemCount(0);}}
		
	protected:
		inline virtual boolean AreKeysEqual(const TKeyType& key1,const TKeyType& key2) const {return (key1 == key2);}
		
		//just a remind : must be consistent with the == class operator and Result MUST be in [0..fSize[
		virtual uint32		HashFunction(const TKeyType& key) const; 
				
		//returns the array corresponding to the hash value of elem
		const TMCArray<uint32>*		GetElemArray(const TKeyType& key) const { return fHashTable[ HashFunction(key) ]; }
		TMCArray<uint32>*			GetElemArray(const TKeyType& key) { return fHashTable[ HashFunction(key) ]; }
				
	protected:
		//the number of possible hash values
		uint32							fSize;		
		
		TMCPtrArray< TMCArray<uint32> > fHashTable; //the hash table itself : it only contains indexes		
		TMCClassArray<T>				fHashData;  //the data are stored here.
};

template<class Key, class T> TMCHashCommon<Key, T>::TMCHashCommon(uint32 size)
: fHashTable(size, true)
{
	MCAssert(size > 0);	
	fSize= size;

	for(uint32 ii=0; ii < fSize; ii++)
	{
		fHashTable[ii]= new TMCArray<uint32>;
	}
}

template<class Key, class T> TMCHashCommon<Key, T>::~TMCHashCommon()
{
	for(uint32 ii=0; ii < fSize; ii++)
	{
		delete fHashTable[ii];  
	}
}

template<class Key, class T> boolean TMCHashCommon<Key, T>::SetElemSpace(uint32 n)
{
	boolean result= true;
	uint32 arraySpace= (n / fSize) + 1;
	for(uint32 ii=0; ii < fSize; ii++)
	{
		result= result&&(fHashTable[ii]->SetElemSpace(arraySpace));
	}
	return result && fHashData.SetElemSpace(n);
}

template<class Key, class T> uint32 TMCHashCommon<Key, T>::HashFunction(const TKeyType& key) const
{
	uint8* vector = (uint8*)(&key);
	int32 summ = 0;

	for (int16 i = 0; i < sizeof(Key); i++)
	{
		summ += *(vector + i);
	}	
	return (summ % fSize );
}



/*
 *  TMCHash
 */

template <class T> class TMCHash : public TMCHashCommon<T, T>
{
	public:	
		TMCHash(uint32 size); //size must be > 0
		
		// returns a pointer on the table's element which is  equal to elem. (NULL if not found)
		// fromStart is to begin search by the begining or the end.
		const T*	FindElem(const T& elem, boolean fromStart= true) const;

		//returns the index of the found element, kNotFound otherwise
		int32		FindElemIndex(const T& elem, boolean fromStart= true) const;
		
		//Returns the index of the inserted element if it didn't exist, of the existing elem if existed		
		uint32		AddElem(const T&  elem, boolean& found, const boolean fromStart= true);				

	private:
		int32		FindInArray(const TMCArray<uint32>* array, const T& elem, const boolean fromStart) const;
};


template<class T> TMCHash<T>::TMCHash(uint32 size)
: TMCHashCommon<T, T>(size)
{
}

template<class T> inline const T* TMCHash<T>::FindElem(const T& elem, boolean fromStart) const
{	
	int32 index = FindInArray(GetElemArray(elem), elem, fromStart);	
	if (index != kNotFound)
		return &(this->fHashData[index]);
	else return NULL;
}

template<class T> inline int32 TMCHash<T>::FindElemIndex(const T& elem, boolean fromStart) const
{	
	return FindInArray(GetElemArray(elem), elem, fromStart);		
}

template<class T> inline uint32 TMCHash<T>::AddElem(const T&  elem, boolean& found, boolean fromStart)											
{
	TMCArray<uint32>* array= GetElemArray(elem);
	int32 index= FindInArray(array, elem, fromStart);

	if (index == kNotFound) 
	{
		int32 newIndex= this->fHashData.GetElemCount();
		this->fHashData.AddElem(elem);
		array->AddElem(newIndex);
		found = false;
		return newIndex;
	}
	else 
	{
		found = true;
		return index;
	}
}

template<class T> int32 TMCHash<T>::FindInArray(const TMCArray<uint32>* array, const T& elem, const boolean fromStart) const
{	
	ThrowIfNil(array);
	int32 count= array->GetElemCount();
	
	if (count == 0) return kNotFound;
	
	if (fromStart)
	{
		for(int32 ii=0; ii<count; ii++)
		{			
			if ( AreKeysEqual(elem,this->fHashData[(*array)[ii]])) 
				return (*array)[ii];
		}
	}
	else
	{
		for(int32 ii= (count - 1); ii >= 0; ii--)
		{
			if ( AreKeysEqual(elem,this->fHashData[(*array)[ii]])) 
				return (*array)[ii];
		}
	}
	return kNotFound;
}


/*
 *  TMCHashMap
 */

template <class Key, class T> class TMCHashMap : public TMCHashCommon<Key, T>
{
	public:	
		
		TMCHashMap(uint32 size); //size must be > 0
		
		// Set the number of elements to have memory allocated for.
		virtual boolean		SetElemSpace(const uint32 n);		
		
		// returns a pointer on the table's element which is  equal to elem. (NULL if not found)
		// fromStart is to begin search by the begining or the end.
		const T*			FindElem(const Key& key, boolean fromStart= true) const;

		//returns the index of the found element, kNotFound otherwise
		int32				FindElemIndex(const Key& key, boolean fromStart= true) const;

		//remove one element
		void				EraseElem(const Key& key);
		
		//Returns the index of the inserted element if it didn't exist, of the existing elem if existed		
		uint32				AddElem(const Key& key, const T& elem, boolean& found, const boolean fromStart= true);				

		inline virtual void	ResetDatas() {fHashKey.SetElemCount(0); TMCHashCommon<Key, T>::ResetDatas();}
		
	private:
		int32				FindInArray(const TMCArray<uint32>* array, const Key& key, const boolean fromStart) const;

		TMCClassArray<Key>	fHashKey;
};


template<class Key, class T> TMCHashMap<Key, T>::TMCHashMap(uint32 size)
: TMCHashCommon<Key, T>(size)
{
}

template<class Key, class T> boolean TMCHashMap<Key, T>::SetElemSpace(uint32 n)
{
	return TMCHashCommon<Key, T>::SetElemSpace(n) && fHashKey.SetElemSpace(n);
}

template<class Key, class T> inline const T* TMCHashMap<Key, T>::FindElem(const Key& key, boolean fromStart) const
{	
	int32 index = FindInArray(GetElemArray(key), key, fromStart);	
	if (index != kNotFound)
		return &(this->fHashData[index]);
	else return NULL;
}

template<class Key, class T> inline int32 TMCHashMap<Key, T>::FindElemIndex(const Key& elem, boolean fromStart) const
{
	return FindInArray(GetElemArray(elem), elem, fromStart);		
}

template<class Key, class T> inline void TMCHashMap<Key, T>::EraseElem(const Key& key)
{
	TMCArray<uint32>* array = GetElemArray(key);
	int32 count= array->GetElemCount();
	
	for(int32 ii=0; ii<count; ii++)
	{			
		if (key == fHashKey[(*array)[ii]])
		{
			const uint32 index = (*array)[ii];

			const int32 arraySize = (*array).GetElemCount();
			if (ii != arraySize-1)
			{
				(*array)[ii] = (*array)[arraySize-1];
			}
			(*array).SetElemCount(arraySize-1);

			const uint32 elemCount = fHashKey.GetElemCount();
			MCAssert(elemCount > 0);
			MCAssert(elemCount == this->fHashData.GetElemCount());

			if (index != elemCount-1)
			{
				fHashKey[index] = fHashKey[elemCount-1];
				this->fHashData[index] = this->fHashData[elemCount-1];

				// the index 'elemCount-1' is now 'index'
				TMCArray<uint32>* rnArray = GetElemArray(fHashKey[index]);
				const uint32 foundElem = rnArray->FindElem(elemCount-1);
				if (MCVerify(foundElem != kUnusedIndex))
					(*rnArray)[foundElem] = index;
			}

			fHashKey.SetElemCount(elemCount-1);
			this->fHashData.SetElemCount(elemCount-1);

			return;
		}
	}
}

template<class Key, class T> inline uint32 TMCHashMap<Key, T>::AddElem(const Key& key, const T& elem, boolean& found, boolean fromStart)
{
	TMCArray<uint32>* array= GetElemArray(key);
	int32 index= FindInArray(array, key, fromStart);

	if (index == kNotFound) 
	{
		int32 newIndex= this->fHashData.GetElemCount();
		this->fHashData.AddElem(elem);
		fHashKey.AddElem(key);
		array->AddElem(newIndex);
		found = false;
		return newIndex;
	}
	else 
	{
		found = true;
		return index;
	}
}

template<class Key, class T> int32 TMCHashMap<Key, T>::FindInArray(const TMCArray<uint32>* array, const Key& key, const boolean fromStart) const
{	
	ThrowIfNil(array);
	int32 count= array->GetElemCount();
	
	if (count == 0) return kNotFound;

	if (fromStart)
	{
		for(int32 ii=0; ii<count; ii++)
		{			
			if ( AreKeysEqual(key,fHashKey[(*array)[ii]])) 
				return (*array)[ii];
		}
	}
	else
	{
		for(int32 ii= (count - 1); ii >= 0; ii--)
		{
			if ( AreKeysEqual(key,fHashKey[(*array)[ii]])) 
				return (*array)[ii];
		}
	}
	return kNotFound;
}


#endif
