//------------------------- CSPMap.h --------------------------

//*************************************************************
//*****       Copyright ©2002 - 2004 Micronovae Ltd       *****
//*****                All rights reserved                *****
//*************************************************************


#ifndef _CSPMAP
#define _CSPMAP

#include "CSPConf.h"
#include "CSPLib.h"
#include "CSPThread.h"

#define Max(a,b) ( ( ( a ) >= ( b ) ) ? ( a ) : ( b ) )
#define Min(a,b) ( ( ( a ) <= ( b ) ) ? ( a ) : ( b ) )

#define DEFAULT_MAP_SIZE	10

#pragma warning ( disable : 4251 )

template< class K, class T >
class CSPMap : public CSPObject
{
	public:
		CSPMap();
		CSPMap( const CSPMap& Map );
		virtual ~CSPMap();

		void Add( const K& Key, T* pElement );
		bool Remove( const K& Key );
		bool RemoveByIndex( unsigned long ulIndex );
		bool Replace( const K& Key, T* pElement );
		bool ReplaceByIndex( unsigned long ulIndex, T* pElement );
		CSPMap& operator = ( const CSPMap& Map );
		T* operator () ( const K& Key ) const;
		T* operator [] ( unsigned long ulIndex ) const;
		unsigned long GetCount() const;
		void RemoveAll( bool bDelete = true );

	protected:

		struct PAIR
		{
			PAIR() : pElement( 0 ) {};
			~PAIR(){ delete pElement; }
			K Key;
			T* pElement;
		};

		PAIR** ppPairs;
		unsigned long ulSize;
		unsigned long ulElemCount;

		void ReAllocMem( unsigned long ulNewSize );
		bool GetIndex( const K& Key, unsigned long& ulIndex ) const;
};



//----------------- CSPLockMap template class ------------------

template <class K, class T>
class CSPLockMap: public CSPMap< K, T >, public CSPThreadLock
{
	public:
		CSPLockMap();
		CSPLockMap( const CSPLockMap& LockMap );
		CSPLockMap( const CSPMap< K, T >& Map );
		virtual ~CSPLockMap();

		CSPLockMap& operator = ( const CSPLockMap& LockMap );
		CSPLockMap& operator = ( const CSPMap< K, T >& Map );
};


//---------------- CSPMap template class implementation ---------------

template< class K, class T >
CSPMap< K, T >::CSPMap() : ppPairs( 0 ), ulElemCount( 0 ), ulSize( 0 )
{
}

template< class K, class T >
CSPMap< K, T >::CSPMap( const CSPMap< K, T >& Map ) : ppPairs( 0 ), ulElemCount( 0 ), ulSize( 0 )
{
	ReAllocMem( Map.ulSize );
	
	for( unsigned long x = 0; x < Map.ulElemCount; x++ )
	{
		CSPPtr< PAIR > spPair( new PAIR );
		if( !spPair )ThrowOutOfMemory();
		spPair->pElement = new T( *Map.ppPairs[ x ]->pElement );
		if( !spPair->pElement )ThrowOutOfMemory();
		spPair->Key = Map.ppPairs[ x ]->Key;		
		
		ppPairs[ x ] = spPair.Detach();		

		ulElemCount++;
	}
}

template< class K, class T >
CSPMap< K, T >::~CSPMap()
{
	for( unsigned long x = 0; x < ulElemCount ; x++ )delete ppPairs[x];
	free( ppPairs );
}

template< class K, class T >
CSPMap< K, T >& CSPMap< K, T >::operator = ( const CSPMap< K, T >& Map )
{
	RemoveAll();

	ReAllocMem( Map.ulSize );

	for( unsigned long x = 0; x < Map.ulElemCount; x++ )
	{
		CSPPtr< PAIR > spPair( new PAIR );
		if( !spPair )ThrowOutOfMemory();
		spPair->pElement = new T( *Map.ppPairs[ x ]->pElement );
		if( !spPair->pElement )ThrowOutOfMemory();
		spPair->Key = Map.ppPairs[ x ]->Key;		
		
		ppPairs[ x ] = spPair.Detach();		

		ulElemCount++;
	}

	return *this;
}


template< class K, class T >
void CSPMap< K, T >::Add( const K& Key, T* pElement )
{
	unsigned long ulIndex;
	if( GetIndex( Key, ulIndex ) )
	{
		delete ppPairs[ ulIndex ]->pElement;
		ppPairs[ ulIndex ]->pElement = pElement;
	}
	else
	{
		if( ulSize <= ulElemCount )ReAllocMem( Max( ( unsigned long )DEFAULT_MAP_SIZE, ulSize * 2 ) );

		CSPPtr<PAIR> spNewPair( new PAIR );
		if( !spNewPair )ThrowOutOfMemory();
		
		spNewPair->pElement = pElement;
		spNewPair->Key = Key;

		memmove( ppPairs + ulIndex + 1, ppPairs + ulIndex, ( ulElemCount - ulIndex ) * sizeof( PAIR** ) );
		ppPairs[ ulIndex ] = spNewPair.Detach();

		ulElemCount++;
	}
}


template< class K, class T >
bool CSPMap< K, T >::Remove( const K& Key )
{
	unsigned long ulIndex;
	if( !GetIndex( Key, ulIndex ) )return false;

	delete ppPairs[ ulIndex ];
	ulElemCount--;

	memmove( ppPairs + ulIndex, ppPairs + ulIndex + 1, ( ulElemCount - ulIndex ) * sizeof( PAIR** ) );

	return true;
}

template< class K, class T >
bool CSPMap< K, T >::RemoveByIndex( unsigned long ulIndex )
{
	if( ulIndex >= ulElemCount )return false;

	delete ppPairs[ ulIndex ];
	ulElemCount--;

	memmove( ppPairs + ulIndex, ppPairs + ulIndex + 1, ( ulElemCount - ulIndex ) * sizeof( PAIR** ) );	

	return true;
}

template< class K, class T >
bool CSPMap< K, T >::Replace( const K& Key, T* pElement )
{
	unsigned long ulIndex;
	if( GetIndex( Key, ulIndex ) )
	{
		ppPairs[ ulIndex ]->pElement = pElement;
	}
	else
	{
		if( ulSize <= ulElemCount )ReAllocMem( Max( DEFAULT_MAP_SIZE, ulSize * 2 ) );
		
		CSPPtr<PAIR> spNewPair( new PAIR );
		if( !spNewPair )ThrowOutOfMemory();

		spNewPair->pElement = pElement;
		spNewPair->Key = Key;

		memmove( ppPairs + ulIndex + 1, ppPairs + ulIndex, ( ulElemCount - ulIndex ) * sizeof( PAIR** ) );
		ppPairs[ ulIndex ] = spNewPair.Detach();

		ulElemCount++;
	}

	return true;
}


template< class K, class T >
T* CSPMap< K, T >::operator () ( const K& Key ) const
{
	unsigned long ulIndex;
	if( !GetIndex( Key, ulIndex ) )return 0;
	return ppPairs[ ulIndex ]->pElement;
}


template< class K, class T >
T* CSPMap< K, T >::operator [] ( unsigned long ulIndex ) const
{
	return ppPairs[ ulIndex ]->pElement;
}


template< class K, class T >
unsigned long CSPMap< K, T >::GetCount() const
{
	return ulElemCount;
}


template< class K, class T >
void CSPMap< K, T >::RemoveAll( bool bDelete )
{
	if( bDelete )for( unsigned long x = 0; x < ulElemCount ; x++ )delete ppPairs[x];
	free( ppPairs );

	ppPairs = 0;
	ulElemCount = 0;
	ulSize = 0;
}


template< class K, class T >
void CSPMap< K, T >::ReAllocMem( unsigned long ulNewSize )
{
	if( !ulNewSize )
	{
		RemoveAll();
		return;
	}

	PAIR** ppTemp = (PAIR**)realloc( ppPairs, ulNewSize * sizeof( PAIR** ) );
	if( !ppTemp )ThrowOutOfMemory();

	ppPairs = ppTemp;
	ulElemCount = Min( ulElemCount, ulNewSize );
	ulSize = ulNewSize;
}

template< class K, class T >
bool CSPMap< K, T >::GetIndex( const K& Key, unsigned long& ulIndex ) const
{
	if( !ulElemCount ){ ulIndex = 0; return false; }

	unsigned long ulLeft, ulRight, ulMid;

	for( ulLeft = 0, ulRight = ulElemCount - 1, ulMid = ulElemCount / 2; ulMid != ulRight; )
	{
		if( Key > ppPairs[ ulMid ]->Key )ulLeft = ulMid, ulMid = ( ulRight + ulLeft + 1 ) / 2;
		else ulRight = ulMid, ulMid = ( ulRight + ulLeft ) / 2;
	}
	
	if( Key == ppPairs[ ulRight ]->Key ){ ulIndex = ulRight; return true; }
	if( Key == ppPairs[ ulLeft ]->Key ){ ulIndex = ulLeft; return true; }
	if( Key > ppPairs[ ulRight ]->Key ){ ulIndex = ulRight + 1; return false; }
	if( Key > ppPairs[ ulLeft ]->Key ){ ulIndex = ulRight; return false; }

	ulIndex = ulLeft;
	return false;
}


//---------------- CSPLockMap template class implementation ---------------


template< class K, class T >
CSPLockMap< K, T >::CSPLockMap() : CSPMap< K, T >(), CSPThreadLock()
{ 
}

template< class K, class T >
CSPLockMap< K, T >::CSPLockMap( const CSPLockMap< K, T >& LockMap ) : CSPMap< K, T >( LockMap ), CSPThreadLock()
{
}

template< class K, class T >
CSPLockMap< K, T >::CSPLockMap( const CSPMap< K, T >& Map ) : CSPMap< K, T >( Map ), CSPThreadLock()
{
}


template<class K, class T>
CSPLockMap< K, T >::~CSPLockMap()
{
}

template< class K, class T >
CSPLockMap< K, T >& CSPLockMap< K, T >::operator = ( const CSPLockMap< K, T >& LockMap )
{
	CSPMap< K, T >::operator = ( LockMap );
	return *this;
}

template< class K, class T >
CSPLockMap< K, T >& CSPLockMap< K, T >::operator = ( const CSPMap< K, T >& Map )
{
	CSPMap< K, T >::operator = ( Map );
	return *this;
}

#undef Max
#undef Min
#endif
