///////////////////////////////////////////////////////////////////////////////
/// @file deIDServer.cpp
///
/// @brief 32-bit UINT ID server
///
/// @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 Sept 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////


#include "deIDServer.hpp"
#include "deArray.hpp"
#include "deStack.hpp"

class deIDServer: public IdeIDServer
{
private:			// FINAL
	
	deTArray <void*>	m_DataStore;
	deTStack <deID_t>	m_Empties;
	int					m_NumEmpty;
	deID_t				m_HighestID;
	deBoolean			m_Recycle;
	
	deIDServer(deBoolean RecycleIDs, unsigned long int InitialSize);
	~deIDServer();
	
public:
	friend IdeIDServer * IdeIDServer_CreateServer(deBoolean RecycleIDs, int InitialSize);
	int			Release();
	deID_t		AddData(void * Data);
	deBoolean	AddDataWithID(void* Data, deID_t ID);
	void *		LookupData(deID_t ID);
	deBoolean	RemoveData(deID_t ID, void* Data);
	void *		WalkData(deID_t & ID);
	deBoolean	DoesRecycle();
	unsigned long int HighestID();
};

static unsigned long int LargestSmallerPow2(unsigned long int x)
{
	int retval = 0;
	if (x & 0xffff0000)
	{ retval += 16; x >>= 16; }
	if (x & 0x0000ff00)
	{ retval += 8; x >>= 8; }
	if (x & 0x000000f0)
	{ retval += 4; x >>= 4; }
	if (x & 0x00000003)
	{ retval += 2; x >>= 2; }
	if (x & 0x00000001)
	{ retval += 1; x >>= 1; }
	return (1 << retval);
}

IdeIDServer * IdeIDServer_CreateServer(deBoolean RecycleIDs, int InitialSize)
{
	return new deIDServer(RecycleIDs, InitialSize);
}

deIDServer::~deIDServer()
{
	// possibly release all the data? not sure how to release (void*)
}

deIDServer::deIDServer(deBoolean RecycleIDs, unsigned long int InitialSize)
:m_HighestID(0), m_Empties(m_Empties.FIFO_STACK), m_Recycle(RecycleIDs)
{
	InitialSize = LargestSmallerPow2(InitialSize);
	m_DataStore.ResizeQuick(InitialSize, deTRUE);
	m_NumEmpty = 0;
}

int deIDServer::Release()
{
	delete this;
	return 0;
}

deID_t deIDServer::AddData(void * Data)
{
	#pragma todo(perhaps redo this with a BST of empties to allow dynamic downsizing)
	// 4 billion ID's is nice, but it might run out after an extended session

	if (Data == NULL)
		return 0;
	
	// look at the empty list for untaken ID's
	if (m_Recycle && m_NumEmpty > 0)
	{
		#pragma todo(issue with re-using IDs - comments follow)
		// if an object destroys itself and doesn't notify objects that refer to it,
		// then they might get a reference to an object that has dropped into the spot
		// left behind by the prior object, which can cause an access violation
		
		deID_t ID;
		--m_NumEmpty;
		m_Empties.Pop(ID);
		return ID;
	}
	
	// If no untaken values available, increment HighestID
	++m_HighestID;
	
	// if HighestID is greater that DataStore can allow for, double DataStore's size
	deID_t len = m_DataStore.Length();
	while (m_HighestID >= len)
	{
		len *= 2;
		if (len == 0)
			len = 1;
		if (!m_DataStore.ResizeQuick(len, deTRUE))
			return 0;
	}
	
	// make sure the spot isn't already taken
	if (m_DataStore[m_HighestID-1] != NULL)
		return deFALSE;
	
	// store Data into DataStore[HighestID-1] because 0 is a "null" ID
	m_DataStore[m_HighestID-1] = Data;
	
	// return HighestID
	return m_HighestID;
}

deBoolean deIDServer::AddDataWithID(void* Data, deID_t ID)
{
	if (Data == NULL || ID == 0)
		return deFALSE;

	// if HighestID is greater that DataStore can allow for, double DataStore's size
	deID_t len = m_DataStore.Length();
	while (ID >= len)
	{
		len *= 2;
		if (len == 0)
			len = 1;
		if (!m_DataStore.ResizeQuick(len, deTRUE))
			return 0;
	}
	
	// make sure the spot isn't already taken
	if (m_DataStore[ID-1] != NULL)
		return deFALSE;

	// store Data into DataStore
	m_DataStore[ID-1] = Data;
	
	// set the highest ID to what we just added, or keep it where it was
	m_HighestID = max(ID, m_HighestID);
	
	// return HighestID
	return deTRUE;	
}

void* deIDServer::LookupData(deID_t ID)
{
	// if we get the NULL ID or higher than we've handed out, return NULL
	if (ID == 0 || ID > m_HighestID)
		return NULL;
	
	// subtract 1 since 0 is the null ID
	return m_DataStore[ID-1];
}

deBoolean deIDServer::RemoveData(deID_t ID, void* Data)
{
	// if it's outside our expected ID range, fail
	if (ID == 0 || ID > m_HighestID)
		return deFALSE;
	
	// compare the existing pointer to make sure we're removing what we added
	void* ptr = m_DataStore[ID-1];
	if (Data != ptr)
		return deFALSE;

	if (m_Recycle)
	{
		// if this was the most-recently-added ID, just decrement HighestID
		if (ID == m_HighestID)
		{
			#pragma todo(make this continue going down until it gets to the real highest handed-out ID)
			--m_HighestID;
		}
		else
		{
			// if it was in the middle somewhere, add it to the empty list so it can be re-used
			m_Empties.Push(ID);
			++m_NumEmpty;
		}
	}
	m_DataStore[ID-1] = NULL;
	
	return deTRUE;
}

void * deIDServer::WalkData(deID_t & ID)
{
	void * ptr = NULL;

	// if we get the NULL ID or higher than we've handed out, return NULL
	if (ID >= m_HighestID)
		return NULL;

	while (ID <= m_HighestID)
	{
		++ID;
		ptr = m_DataStore[ID-1];
		if (ptr)
		{
			break;
		}
	}

	// subtract 1 since 0 is the null ID
	return ptr;
}

deBoolean deIDServer::DoesRecycle()
{
	return m_Recycle;
}

unsigned long int deIDServer::HighestID()
{
	return m_HighestID;
}


//================================================================

class deIDMapper : public IdeIDMapper
{
private:
	deTArray<deID_t> m_Mapper;

	deIDMapper();
	~deIDMapper();

public:
#if defined(DEUTIL_DLL_EXPORTS) || defined(DESTINY3D_EXPORT_ALL)
	friend __declspec(dllexport) IdeIDMapper * IdeIDServer_CreateMapper();
#else
	friend IdeIDMapper * IdeIDServer_CreateMapper();
#endif
	int			Release();
	
	IdeIDServer*GetMappedIDServer(IdeIDServer* Input);
	deID_t		MapID(deID_t InputID);
};

IdeIDMapper * IdeIDServer_CreateMapper()
{
	return new deIDMapper;
}

deIDMapper::deIDMapper()
{
}

deIDMapper::~deIDMapper()
{
}

int deIDMapper::Release()
{
	delete this;
	return 0;
}

IdeIDServer* deIDMapper::GetMappedIDServer(IdeIDServer* Input)
{
	deIDServer * Input2;
	IdeIDServer * MappedServer;

	Input2 = (deIDServer*)Input;
	MappedServer = IdeIDServer_CreateServer(Input2->DoesRecycle(), 0);
	if (!MappedServer)
		return NULL;

	m_Mapper.Resize(0);
	m_Mapper.Resize(Input2->HighestID());

	void * ptr;
	deID_t CurrentID;
	deID_t InsertionID;
	CurrentID = 0;
	ptr = Input->WalkData(CurrentID);
	while (ptr)
	{
		InsertionID = MappedServer->AddData(ptr);
		m_Mapper[CurrentID] = InsertionID;
		ptr = Input->WalkData(CurrentID);
	}

	return MappedServer;
}

deID_t deIDMapper::MapID(deID_t InputID)
{
	if (InputID == 0 || InputID > (deID_t)m_Mapper.Length())
		return 0;
	
	return m_Mapper[InputID];
}

