#include "../../Scene/Container/RuContainer_Quadtree_DS.h"

#include "../../Scene/Controller/RuController_DistanceFader.h"

#include "../../Gaia/RuGaia_Base.h"

#pragma unmanaged

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

ruRTTI_DEFINE_SUBCLASS(CRuContainer_Quadtree_DS, IRuEntity_Container)
ruHEAP_DEFINE_SUBCLASS(CRuContainer_Quadtree_DS, "CRuContainer_Quadtree_DS", "IRuEntity_Container")
ruCLASSGUID_DEFINE(CRuContainer_Quadtree_DS, 0x586967E0, 0x31B04942, 0x9FCA6257, 0x9163C363)

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

/*!
	Standard constructor.
*/
CRuContainer_Quadtree_DS::EntityDesc::EntityDesc()
:	m_resourceName(NULL),
	m_entity(NULL),
	m_beingControlled(FALSE),
	m_fullyVisible(FALSE),
	m_isDirty(TRUE),
	m_loadFailed(FALSE)
{
	m_guid.Generate();
}

/*!
	Standard destructor. Frees all resources used by the descriptor.
*/
CRuContainer_Quadtree_DS::EntityDesc::~EntityDesc()
{
	delete[] m_resourceName;
	ruSAFE_RELEASE(m_entity);
}

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

/*!
	Standard constructor for TreeNode.
*/
CRuContainer_Quadtree_DS::TreeNode::TreeNode()
:	m_loaded(FALSE)
{
}

/*!
	Standard destructor for TreeNode. Frees all resources used by the node.
*/
CRuContainer_Quadtree_DS::TreeNode::~TreeNode()
{
	// Delete entity descriptors
	for(INT32 i = 0; i < m_entities.Count(); ++i)
	{
		delete m_entities[i];
	}
}

/*!
	Initializes the node. Should only be called at once per node.

	@param bounds Bounding box for the node.
*/
void CRuContainer_Quadtree_DS::TreeNode::Initialize(const CRuAABB &bounds)
{
	m_bounds = bounds;
}

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

CRuContainer_Quadtree_DS::Tree::Tree(CRuDataStore_Base *dataStore, const CRuAABB &bounds, const CRuVector3 &maxLeafExtents)
:	m_dataStore(NULL),
	m_readOnly(FALSE),
	m_depth(0),
	m_treeArray(NULL)
{
	if(dataStore)
	{
		// Initialize utility objects
		m_streamCompressor = ruNEW CRuStreamCompressor();
		m_compressedChunkStream = ruNEW CRuMemoryStream();
		m_decompressedChunkStream = ruNEW CRuMemoryStream();

		// Save reference to data store
		m_dataStore = dataStore;
		m_dataStore->AddRef();

		// Create data tables
		m_tableHandle_Header = m_dataStore->CreateTable("qds_header", 4);
		m_tableHandle_Entity = m_dataStore->CreateTable("qds_entities", 16);

		// Save tree settings
		m_decompressedChunkStream->SetStreamSize(0);
		m_decompressedChunkStream->Write(&bounds.Minima().x, sizeof(REAL));
		m_decompressedChunkStream->Write(&bounds.Minima().y, sizeof(REAL));
		m_decompressedChunkStream->Write(&bounds.Minima().z, sizeof(REAL));
		m_decompressedChunkStream->Write(&bounds.Maxima().x, sizeof(REAL));
		m_decompressedChunkStream->Write(&bounds.Maxima().y, sizeof(REAL));
		m_decompressedChunkStream->Write(&bounds.Maxima().z, sizeof(REAL));
		m_decompressedChunkStream->Write(&maxLeafExtents.x, sizeof(REAL));
		m_decompressedChunkStream->Write(&maxLeafExtents.y, sizeof(REAL));
		m_decompressedChunkStream->Write(&maxLeafExtents.z, sizeof(REAL));

		INT32 dummyKey = 0;
		m_dataStore->Store(m_tableHandle_Header, reinterpret_cast<BYTE *>(&dummyKey), m_decompressedChunkStream);

		m_bounds = bounds;
		m_maxLeafExtents = maxLeafExtents;

		// Determine tree depth and array size
		float curXExtent = bounds.Maxima().x - bounds.Minima().x;
		float curZExtent = bounds.Maxima().z - bounds.Minima().z;
		while(curXExtent > maxLeafExtents.x || curZExtent > maxLeafExtents.z)
		{
			// Reduce extents for next tree level by a factor of 2
			curXExtent = curXExtent / 2.0f;
			curZExtent = curZExtent / 2.0f;

			// Increment tree depth
			++m_depth;
		}

		// Initialize tree array
		m_numNodes = GetDepthNodeCount(m_depth);
		m_treeArray = ruNEW TreeNode [m_numNodes];
		Initialize(0, 0, bounds);

		// Initialize instancing queue
		m_entityQueue = ruNEW CRuLRUQueue<DWORD, InstanceDesc>(2048, 8192);
	}
}

CRuContainer_Quadtree_DS::Tree::Tree(CRuDataStore_Base *dataStore)
:	m_dataStore(NULL),
	m_readOnly(FALSE),
	m_depth(0),
	m_treeArray(NULL)
{
	if(dataStore)
	{
		CRuAABB bounds;
		CRuVector3 maxLeafExtents;

		// Initialize utility objects
		m_streamCompressor = ruNEW CRuStreamCompressor();
		m_compressedChunkStream = ruNEW CRuMemoryStream();
		m_decompressedChunkStream = ruNEW CRuMemoryStream();

		// Save reference to data store
		m_dataStore = dataStore;
		m_dataStore->AddRef();

		// Get data tables
		m_tableHandle_Header = m_dataStore->GetTableHandle("qds_header");
		m_tableHandle_Entity = m_dataStore->GetTableHandle("qds_entities");

		// Load tree settings
		INT32 dummyKey = 0;
		IRuStream *stream = m_dataStore->Retrieve(m_tableHandle_Header, reinterpret_cast<BYTE *>(&dummyKey));

		if(stream)
		{
			stream->Read(&bounds.Minima().x, sizeof(REAL));
			stream->Read(&bounds.Minima().y, sizeof(REAL));
			stream->Read(&bounds.Minima().z, sizeof(REAL));
			stream->Read(&bounds.Maxima().x, sizeof(REAL));
			stream->Read(&bounds.Maxima().y, sizeof(REAL));
			stream->Read(&bounds.Maxima().z, sizeof(REAL));
			stream->Read(&maxLeafExtents.x, sizeof(REAL));
			stream->Read(&maxLeafExtents.y, sizeof(REAL));
			stream->Read(&maxLeafExtents.z, sizeof(REAL));

			delete stream;
		}

		m_bounds = bounds;
		m_maxLeafExtents = maxLeafExtents;

		// Determine tree depth and array size
		float curXExtent = bounds.Maxima().x - bounds.Minima().x;
		float curZExtent = bounds.Maxima().z - bounds.Minima().z;
		while(curXExtent > maxLeafExtents.x || curZExtent > maxLeafExtents.z)
		{
			// Reduce extents for next tree level by a factor of 2
			curXExtent = curXExtent / 2.0f;
			curZExtent = curZExtent / 2.0f;

			// Increment tree depth
			++m_depth;
		}

		// Initialize tree array
		m_numNodes = GetDepthNodeCount(m_depth);
		m_treeArray = ruNEW TreeNode [m_numNodes];
		Initialize(0, 0, bounds);

		// Initialize instancing queue
//		m_entityQueue = ruNEW CRuLRUQueue<DWORD, InstanceDesc>(2048, 8192);
		m_entityQueue = ruNEW CRuLRUQueue<DWORD, InstanceDesc>(4096, 8192);

		// Load
		Load();
	}
}

CRuContainer_Quadtree_DS::Tree::~Tree()
{
	// Flush the entity queue
	FlushEntityQueue();

	ruSAFE_RELEASE(m_dataStore);

	delete[] m_treeArray;
	delete m_entityQueue;
	delete m_streamCompressor;
	delete m_compressedChunkStream;
	delete m_decompressedChunkStream;
}

BOOL CRuContainer_Quadtree_DS::Tree::CopyToDataStore(CRuDataStore_Base *targetDataStore)
{
	// Create data tables
	INT32 target_TableHandle_Header = targetDataStore->CreateTable("qds_header", 4);
	INT32 target_TableHandle_Entity = targetDataStore->CreateTable("qds_entities", 16);

	// Save tree settings
	m_decompressedChunkStream->SetStreamSize(0);
	m_decompressedChunkStream->Write(&m_bounds.Minima().x, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_bounds.Minima().y, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_bounds.Minima().z, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_bounds.Maxima().x, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_bounds.Maxima().y, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_bounds.Maxima().z, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_maxLeafExtents.x, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_maxLeafExtents.y, sizeof(REAL));
	m_decompressedChunkStream->Write(&m_maxLeafExtents.z, sizeof(REAL));

	INT32 dummyKey = 0;
	targetDataStore->Store(target_TableHandle_Header, reinterpret_cast<BYTE *>(&dummyKey), m_decompressedChunkStream);

	// Clear entity headers
	targetDataStore->DeleteAllRecords(target_TableHandle_Entity);

	// Iterate through entire tree
	for(INT32 i = 0; i < m_numNodes; ++i)
	{
		CRuArrayList<EntityDesc *> &entities = m_treeArray[i].m_entities;

		for(INT32 j = 0; j < entities.Count(); ++j)
		{
			// Reset temporary stream's size
			m_decompressedChunkStream->SetStreamSize(0);

			EntityDesc *entityDesc = entities[j];

			m_decompressedChunkStream->Write(entityDesc->m_guid.Data(), entityDesc->m_guid.Size());

			// Write signature
			INT32 signature = 0xFFFFFFFF;
			m_decompressedChunkStream->Write(&signature, sizeof(INT32));

			// Write version
			INT32 version = 2;
			m_decompressedChunkStream->Write(&version, sizeof(INT32));

			if(entityDesc->m_resourceName)
			{
				// Write length of the resource name string (including NULL)
				INT32 resNameLength = strlen(entityDesc->m_resourceName) + 1;
				m_decompressedChunkStream->Write(&resNameLength, sizeof(INT32));

				// Write the resource name string
				m_decompressedChunkStream->Write(entityDesc->m_resourceName, resNameLength);
			}
			else
			{
				// Write length of the resource name string (including NULL)
				INT32 resNameLength = 1;
				m_decompressedChunkStream->Write(&resNameLength, sizeof(INT32));

				// Write the resource name string
				m_decompressedChunkStream->Write("", resNameLength);
			}

			m_decompressedChunkStream->Write(&entityDesc->m_scale.x, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_scale.y, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_scale.z, sizeof(float));

			m_decompressedChunkStream->Write(&entityDesc->m_rotation.x, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_rotation.y, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_rotation.z, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_rotation.w, sizeof(float));

			m_decompressedChunkStream->Write(&entityDesc->m_translation.x, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_translation.y, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_translation.z, sizeof(float));

			m_decompressedChunkStream->Write(&entityDesc->m_bounds.Center().x, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_bounds.Center().y, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_bounds.Center().z, sizeof(float));
			m_decompressedChunkStream->Write(&entityDesc->m_bounds.Radius(), sizeof(float));

			// Write zone flags
			m_decompressedChunkStream->Write(&entityDesc->m_zoneFlags, sizeof(UINT32));

			// Store into data store
			targetDataStore->Store(target_TableHandle_Entity, entityDesc->m_guid.Data(), m_decompressedChunkStream);
		}
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Tree::Load()
{
	// Get number of entities
	INT32 numEntities = m_dataStore->GetNumRecords(m_tableHandle_Entity);

	// Iterate through each descriptor
	for(INT32 i = 0; i < numEntities; ++i)
	{
		// Retrieve descriptor record
		IRuStream *stream = m_dataStore->RetrieveByIndex(m_tableHandle_Entity, i);

		if(stream == NULL)
			continue;

		EntityDesc *entityDesc = ruNEW EntityDesc();

		// Read entity guid
		RuReadGUID(stream, entityDesc->m_guid);

		// Read signature
		INT32 signature;
		INT32 version;
		stream->Read(&signature, sizeof(INT32));
		if(signature != 0xFFFFFFFF)
		{
			// No signature, this is an old version, rewind
			stream->Seek(- (INT32) sizeof(INT32), ruSSM_Current);
			version = 1;
		}
		else
		{
			// Read version
			stream->Read(&version, sizeof(INT32));
		}

		switch(version)
		{
			case 1:
				{
					// Read length of the resource name string (including NULL)
					INT32 resNameLength = 0;
					stream->Read(&resNameLength, sizeof(INT32));

					if(resNameLength > 0 && resNameLength <= 512)
					{
						// Read the resource name string
						entityDesc->m_resourceName = ruNEW char [resNameLength];
						stream->Read(entityDesc->m_resourceName, resNameLength);

						stream->Read(&entityDesc->m_scale.x, sizeof(float));
						stream->Read(&entityDesc->m_scale.y, sizeof(float));
						stream->Read(&entityDesc->m_scale.z, sizeof(float));

						stream->Read(&entityDesc->m_rotation.x, sizeof(float));
						stream->Read(&entityDesc->m_rotation.y, sizeof(float));
						stream->Read(&entityDesc->m_rotation.z, sizeof(float));
						stream->Read(&entityDesc->m_rotation.w, sizeof(float));

						stream->Read(&entityDesc->m_translation.x, sizeof(float));
						stream->Read(&entityDesc->m_translation.y, sizeof(float));
						stream->Read(&entityDesc->m_translation.z, sizeof(float));

						stream->Read(&entityDesc->m_bounds.Center().x, sizeof(float));
						stream->Read(&entityDesc->m_bounds.Center().y, sizeof(float));
						stream->Read(&entityDesc->m_bounds.Center().z, sizeof(float));
						stream->Read(&entityDesc->m_bounds.Radius(), sizeof(float));

						entityDesc->m_zoneFlags = 0;
					}
				}

				break;
			case 2:
				{
					// Read length of the resource name string (including NULL)
					INT32 resNameLength = 0;
					stream->Read(&resNameLength, sizeof(INT32));

					if(resNameLength > 0 && resNameLength <= 512)
					{
						// Read the resource name string
						entityDesc->m_resourceName = ruNEW char [resNameLength];
						stream->Read(entityDesc->m_resourceName, resNameLength);

						stream->Read(&entityDesc->m_scale.x, sizeof(float));
						stream->Read(&entityDesc->m_scale.y, sizeof(float));
						stream->Read(&entityDesc->m_scale.z, sizeof(float));

						stream->Read(&entityDesc->m_rotation.x, sizeof(float));
						stream->Read(&entityDesc->m_rotation.y, sizeof(float));
						stream->Read(&entityDesc->m_rotation.z, sizeof(float));
						stream->Read(&entityDesc->m_rotation.w, sizeof(float));

						stream->Read(&entityDesc->m_translation.x, sizeof(float));
						stream->Read(&entityDesc->m_translation.y, sizeof(float));
						stream->Read(&entityDesc->m_translation.z, sizeof(float));

						stream->Read(&entityDesc->m_bounds.Center().x, sizeof(float));
						stream->Read(&entityDesc->m_bounds.Center().y, sizeof(float));
						stream->Read(&entityDesc->m_bounds.Center().z, sizeof(float));
						stream->Read(&entityDesc->m_bounds.Radius(), sizeof(float));

						// Read zone flags
						stream->Read(&entityDesc->m_zoneFlags, sizeof(UINT32));
					}
					else
					{
					}
				}

				break;
		}

		entityDesc->m_isDirty = FALSE;

		delete stream;

		// Add descriptor to the tree
		if(entityDesc->m_resourceName == NULL || AddEntity(entityDesc) == FALSE)
		{
/*
			// Failed to add entity -- log it
			char logString[1024];
			if(entityDesc->m_resourceName)
			{
				sprintf(logString, "Failed to load %s at index %d.\n", entityDesc->m_resourceName, i);
			}
			else
			{
				sprintf(logString, "Failed to load unknown entity at index %d.\n", i);
			}

			OutputDebugString(logString);
*/
			// Delete entity descriptor
			delete entityDesc;
		}
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Tree::Save()
{
	for(INT32 i = 0; i < m_numNodes; ++i)
	{
		CRuArrayList<EntityDesc *> &entities = m_treeArray[i].m_entities;

		for(INT32 j = 0; j < entities.Count(); ++j)
		{
			if(entities[j]->m_isDirty)
			{
				// Reset temporary stream's size
				m_decompressedChunkStream->SetStreamSize(0);

				EntityDesc *entityDesc = entities[j];

				// Write entity GUID
				m_decompressedChunkStream->Write(entityDesc->m_guid.Data(), entityDesc->m_guid.Size());

				// Write signature
				INT32 signature = 0xFFFFFFFF;
				m_decompressedChunkStream->Write(&signature, sizeof(INT32));

				// Write version
				INT32 version = 2;
				m_decompressedChunkStream->Write(&version, sizeof(INT32));

				if(entityDesc->m_resourceName)
				{
					// Write length of the resource name string (including NULL)
					INT32 resNameLength = strlen(entityDesc->m_resourceName) + 1;
					m_decompressedChunkStream->Write(&resNameLength, sizeof(INT32));

					// Write the resource name string
					m_decompressedChunkStream->Write(entityDesc->m_resourceName, resNameLength);
				}
				else
				{
					// Write length of the resource name string (including NULL)
					INT32 resNameLength = 1;
					m_decompressedChunkStream->Write(&resNameLength, sizeof(INT32));

					// Write the resource name string
					m_decompressedChunkStream->Write("", resNameLength);
				}

				// Write entity scale
				m_decompressedChunkStream->Write(&entityDesc->m_scale.x, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_scale.y, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_scale.z, sizeof(float));

				// Write entity rotation
				m_decompressedChunkStream->Write(&entityDesc->m_rotation.x, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_rotation.y, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_rotation.z, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_rotation.w, sizeof(float));

				// Write entity translation
				m_decompressedChunkStream->Write(&entityDesc->m_translation.x, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_translation.y, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_translation.z, sizeof(float));

				// Write entity bounds
				m_decompressedChunkStream->Write(&entityDesc->m_bounds.Center().x, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_bounds.Center().y, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_bounds.Center().z, sizeof(float));
				m_decompressedChunkStream->Write(&entityDesc->m_bounds.Radius(), sizeof(float));

				// Write zone flags
				m_decompressedChunkStream->Write(&entityDesc->m_zoneFlags, sizeof(UINT32));

				// Store into data store
				m_dataStore->Store(m_tableHandle_Entity, entityDesc->m_guid.Data(), m_decompressedChunkStream);

				// Reset dirty flag
				entities[j]->m_isDirty = FALSE;
			}
		}
	}

	// Remove deleted entities
	for(INT32 i = 0; i < m_deletedEntities.Count(); ++i)
	{
		if(m_dataStore->Delete(m_tableHandle_Entity, m_deletedEntities[i].Data()) == FALSE)
		{
			char errorStr[200];
			sprintf(errorStr, "Object GUID %x %x %x %x cannot be deleted.", (UINT32) &m_deletedEntities[i].Data()[0], (UINT32) &m_deletedEntities[i].Data()[4], (UINT32) &m_deletedEntities[i].Data()[8], (UINT32) &m_deletedEntities[i].Data()[12]);
			MessageBox(NULL, errorStr, errorStr, MB_OK);
		}
	}

	m_deletedEntities.Clear();

	return TRUE;
}

/*!
	Adds an entity descriptor to the tree. An attempt will be made to first add the entity
	descriptor to the tree's leaf nodes. An entity descriptor can be added to a tree if and
	only if the tree completely encloses the entity's bounding box.

	@param resName Resource name of the entity.
	@param scale Scale.
	@param rotation Rotation.
	@param translation Translation.
	@param bounds Bounds.

	@retval TRUE The operation succeeded.
	@retval FALSE The operation failed.
*/
BOOL CRuContainer_Quadtree_DS::Tree::AddEntity(const char *resName, const CRuMatrix4x4 &transform, const CRuSphere &bounds)
{
	INT32 bestFitNodeIndex = FindBestFitNode(0, 0, bounds);

	if(bestFitNodeIndex >= 0)
	{
		// Decompose orientation transform
		CRuVector3 scale, shear, rotation, translation;
		CRuQuaternion rotationQuat;

		transform.GetDecomposition(scale, shear, rotation, translation);
		rotationQuat.MakeEulerRotation(rotation);

		// Create new entity descriptor
		EntityDesc *desc = ruNEW EntityDesc();

		desc->m_resourceName = ruNEW char [strlen(resName) + 1];
		strcpy(desc->m_resourceName, resName);
		desc->m_scale = scale;
		desc->m_rotation = rotationQuat;
		desc->m_translation = translation;
		desc->m_bounds = bounds;
		desc->m_isDirty = TRUE;

		// Add entity descriptor to the best fit node
		m_treeArray[bestFitNodeIndex].m_entities.Add(desc);

		return TRUE;
	}
	
	return FALSE;
}

BOOL CRuContainer_Quadtree_DS::Tree::AddEntity(EntityDesc *entityDescriptor)
{
	INT32 bestFitNodeIndex = FindBestFitNode(0, 0, entityDescriptor->m_bounds);

	if(bestFitNodeIndex >= 0)
	{
		// Add entity descriptor to the best fit node
		m_treeArray[bestFitNodeIndex].m_entities.Add(entityDescriptor);

		return TRUE;
	}

	return FALSE;
}

/*!
	Removes an entity descriptor from the tree.

	@param entityDescriptor Entity descriptor to remove.

	@retval TRUE The operation succeeded.
	@retval FALSE The operation failed.
*/
BOOL CRuContainer_Quadtree_DS::Tree::RemoveEntity(EntityDesc *entityDescriptor)
{
	INT32 bestFitNodeIndex = FindBestFitNode(0, 0, entityDescriptor->m_bounds);

	if(bestFitNodeIndex >= 0)
	{
		// Check to see if this node contains the entity
		for(INT32 i = 0; i < m_treeArray[bestFitNodeIndex].m_entities.Count(); ++i)
		{
			if(m_treeArray[bestFitNodeIndex].m_entities[i] == entityDescriptor)
			{
				// Append the entity GUID to the list of deleted entities
				m_deletedEntities.Add(entityDescriptor->m_guid);

				// Delete the entity descriptor
				delete entityDescriptor;

				// Remove the entity descriptor from the entity list
				m_treeArray[bestFitNodeIndex].m_entities.RemoveAt(i);

				return TRUE;
			}
		}
	}

	return FALSE;
}

/*!
	Removes the entity descriptor for the given instanced entity.

	@param entity Instanced entity.

	@retval TRUE The operation succeeded.
	@retval FALSE The operation failed.
*/
BOOL CRuContainer_Quadtree_DS::Tree::RemoveEntity(CRuEntity *entity)
{
	DWORD key = reinterpret_cast<DWORD>(entity);
	DWORD keyHash = RuGlobalHashGen().GetHashCode(key);

	// Attempt to locate the entity in the instanced entity queue
	InstanceDesc instanceDesc;
	if(m_entityQueue->Get(key, keyHash, instanceDesc))
	{
		// Remove entity descriptor
		return RemoveEntity(instanceDesc.m_entityDesc);
	}

	return FALSE;
}

INT32 CRuContainer_Quadtree_DS::Tree::RemoveEntitiesByResourceName(const char *resourceName, INT32 curNodeIndex, INT32 curDepth)
{
	INT32 removedEntityCount = 0;

	// If the current node is not a leaf
	if(curDepth < m_depth)
	{
		// Recursively invoke into children (NOTE: Child 0's index is calculated by nodeIndex * 4 + 1)
		for(INT32 i = 0, childIndex = curNodeIndex * 4 + 1, childDepth = curDepth + 1; i < 4; ++i, ++childIndex)
		{
			removedEntityCount += RemoveEntitiesByResourceName(resourceName, childIndex, childDepth);
		}
	}

	for(INT32 i = 0; i < m_treeArray[curNodeIndex].m_entities.Count(); ++i)
	{
		if(strcmp(m_treeArray[curNodeIndex].m_entities[i]->m_resourceName, resourceName) == 0)
		{
			// If the entity is instanced, remove it from the instanced entity queue
			if(m_treeArray[curNodeIndex].m_entities[i]->m_entity)
			{
				DWORD key = reinterpret_cast<DWORD>(m_treeArray[curNodeIndex].m_entities[i]->m_entity);
				DWORD keyHash = RuGlobalHashGen().GetHashCode(key);

				// Attempt to locate the entity in the instanced entity queue
				InstanceDesc instanceDesc;
				if(m_entityQueue->Get(key, keyHash, instanceDesc))
				{
					// Release instance queue's reference on the entity
					ruSAFE_RELEASE(instanceDesc.m_entity);

					// Remove entity from instance queue
					m_entityQueue->Remove(key, keyHash);
				}
			}

			// Append the entity GUID to the list of deleted entities
			m_deletedEntities.Add(m_treeArray[curNodeIndex].m_entities[i]->m_guid);

			// Delete the entity descriptor
			delete m_treeArray[curNodeIndex].m_entities[i];

			// Remove the entity descriptor from the entity list
			m_treeArray[curNodeIndex].m_entities.RemoveAt(i);

			// Increment removed entity count
			++removedEntityCount;
			--i;
		}
	}

	return removedEntityCount;
}

INT32 CRuContainer_Quadtree_DS::Tree::ReplaceEntitiesByResourceName(const char *oldResourceName, const char *newResourceName, INT32 curNodeIndex, INT32 curDepth)
{
	INT32 replacedEntityCount = 0;

	// If the current node is not a leaf
	if(curDepth < m_depth)
	{
		// Recursively invoke into children (NOTE: Child 0's index is calculated by nodeIndex * 4 + 1)
		for(INT32 i = 0, childIndex = curNodeIndex * 4 + 1, childDepth = curDepth + 1; i < 4; ++i, ++childIndex)
		{
			replacedEntityCount += ReplaceEntitiesByResourceName(oldResourceName, newResourceName, childIndex, childDepth);
		}
	}

	for(INT32 i = 0; i < m_treeArray[curNodeIndex].m_entities.Count(); ++i)
	{
		if(strcmp(m_treeArray[curNodeIndex].m_entities[i]->m_resourceName, oldResourceName) == 0)
		{
			// If the entity is instanced, remove it from the instanced entity queue
			if(m_treeArray[curNodeIndex].m_entities[i]->m_entity)
			{
				DWORD key = reinterpret_cast<DWORD>(m_treeArray[curNodeIndex].m_entities[i]->m_entity);
				DWORD keyHash = RuGlobalHashGen().GetHashCode(key);

				// Attempt to locate the entity in the instanced entity queue
				InstanceDesc instanceDesc;
				if(m_entityQueue->Get(key, keyHash, instanceDesc))
				{
					// Release instance queue's reference on the entity
					ruSAFE_RELEASE(instanceDesc.m_entity);

					// Remove entity from instance queue
					m_entityQueue->Remove(key, keyHash);
				}
			}

			// Release instance queue's reference on the entity
			ruSAFE_RELEASE(m_treeArray[curNodeIndex].m_entities[i]->m_entity);

			// Replace name
			delete[] m_treeArray[curNodeIndex].m_entities[i]->m_resourceName;
			m_treeArray[curNodeIndex].m_entities[i]->m_resourceName = ruNEW char [strlen(newResourceName) + 1];
			strcpy(m_treeArray[curNodeIndex].m_entities[i]->m_resourceName, newResourceName);
			m_treeArray[curNodeIndex].m_entities[i]->m_isDirty = TRUE;

/*
			// Append the entity GUID to the list of deleted entities
			m_deletedEntities.Add(m_treeArray[curNodeIndex].m_entities[i]->m_guid);

			// Delete the entity descriptor
			delete m_treeArray[curNodeIndex].m_entities[i];

			// Remove the entity descriptor from the entity list
			m_treeArray[curNodeIndex].m_entities.RemoveAt(i);
*/
			// Increment replaced entity count
			++replacedEntityCount;
		}
	}

	return replacedEntityCount;
}

BOOL CRuContainer_Quadtree_DS::Tree::UpdateEntityDescriptor(CRuEntity *entity)
{
	DWORD key = reinterpret_cast<DWORD>(entity);
	DWORD keyHash = RuGlobalHashGen().GetHashCode(key);

	// Attempt to locate the entity in the instanced entity queue
	InstanceDesc instanceDesc;
	if(m_entityQueue->Get(key, keyHash, instanceDesc))
	{
		// Get the entity's bounds
		instanceDesc.m_entityDesc->m_bounds = entity->GetWorldBounds();

		// NOTES: The entity possibly needs to be moved to a different node
		// Re-insert the entity into the tree
		INT32 descriptorIndex = m_treeArray[instanceDesc.m_nodeIndex].m_entities.IndexOf(instanceDesc.m_entityDesc);

		if(descriptorIndex >= 0)
		{
			INT32 bestFitNodeIndex = FindBestFitNode(0, 0, instanceDesc.m_entityDesc->m_bounds);

			if(bestFitNodeIndex >= 0)
			{
				// Move entity descriptor to the best fit node
				m_treeArray[instanceDesc.m_nodeIndex].m_entities.RemoveAt(descriptorIndex);
				m_treeArray[bestFitNodeIndex].m_entities.Add(instanceDesc.m_entityDesc);

				// Mark entity as dirty
				instanceDesc.m_entityDesc->m_isDirty = TRUE;

				// Alter instance descriptor
				instanceDesc.m_nodeIndex = bestFitNodeIndex;
				m_entityQueue->Set(key, keyHash, instanceDesc);

				return TRUE;
			}
			else
			{
				// Cannot re-insert the entity, abort update
				MessageBox(NULL, "Unable to reinsert entity", "", MB_OK);
			}
		}

		return FALSE;
	}

	return FALSE;
}

/*!
	Updates the entity descriptor for the given instanced entity with new orientation
	transforms.

	@param entity Instanced entity.
	@param scale Scale.
	@param rotation Rotation.
	@param translation Translation.

	@retval TRUE The operation succeeded.
	@retval FALSE The operation failed.
*/
BOOL CRuContainer_Quadtree_DS::Tree::UpdateEntityDescriptor(CRuEntity *entity, const CRuMatrix4x4 &transform)
{
	DWORD key = reinterpret_cast<DWORD>(entity);
	DWORD keyHash = RuGlobalHashGen().GetHashCode(key);

	// Attempt to locate the entity in the instanced entity queue
	InstanceDesc instanceDesc;
	if(m_entityQueue->Get(key, keyHash, instanceDesc))
	{
		CRuVector3 scale, shear, rot, translation;
		CRuQuaternion rotation;

		transform.GetDecomposition(scale, shear, rot, translation);
		rotation.MakeEulerRotation(rot);

		// Preserve old orientation
		CRuVector3 oldScale = instanceDesc.m_entityDesc->m_scale;
		CRuQuaternion oldRotation = instanceDesc.m_entityDesc->m_rotation;
		CRuVector3 oldTranslation = instanceDesc.m_entityDesc->m_translation;

		// Update orientation
		instanceDesc.m_entityDesc->m_scale = scale;
		instanceDesc.m_entityDesc->m_rotation = rotation;
		instanceDesc.m_entityDesc->m_translation = translation;

		// Build old orientation transform
		CRuMatrix4x4 oldOrientationTransform;
		oldOrientationTransform.Scale(oldScale);
		oldOrientationTransform.Rotate(oldRotation);
		oldOrientationTransform.Translate(oldTranslation);

		oldOrientationTransform = oldOrientationTransform.GetInverse();

		// Build orientation transform
		CRuMatrix4x4 orientationTransform;
		orientationTransform.Scale(scale);
		orientationTransform.Rotate(rotation);
		orientationTransform.Translate(translation);

		// Calculate new entity bounding sphere
		// Problem: the entity, at this point, is instanced somewhere in the world and has its own world coordinate.
		//          this means its bounding volume is also already in world coordinates.......
		// Solution: a big hack, just calculate the bounding box as a concatenation of the inverted old orientation and the new orientation..
		//           possible numerical stability implications!

		orientationTransform = oldOrientationTransform * orientationTransform;

		instanceDesc.m_entityDesc->m_bounds = entity->GetWorldBounds();
		orientationTransform.TransformPoint(instanceDesc.m_entityDesc->m_bounds.Center());

		// NOTES: The entity possibly needs to be moved to a different node

		// Re-insert the entity into the tree
		INT32 descriptorIndex = m_treeArray[instanceDesc.m_nodeIndex].m_entities.IndexOf(instanceDesc.m_entityDesc);

		if(descriptorIndex >= 0)
		{
			INT32 bestFitNodeIndex = FindBestFitNode(0, 0, instanceDesc.m_entityDesc->m_bounds);

			if(bestFitNodeIndex >= 0)
			{
				// Move entity descriptor to the best fit node
				m_treeArray[instanceDesc.m_nodeIndex].m_entities.RemoveAt(descriptorIndex);
				m_treeArray[bestFitNodeIndex].m_entities.Add(instanceDesc.m_entityDesc);

				// Mark entity as dirty
				instanceDesc.m_entityDesc->m_isDirty = TRUE;

				// Alter instance descriptor
				instanceDesc.m_nodeIndex = bestFitNodeIndex;
				m_entityQueue->Set(key, keyHash, instanceDesc);

				return TRUE;
			}
			else
			{
				instanceDesc.m_entityDesc->m_scale = oldScale;
				instanceDesc.m_entityDesc->m_rotation = oldRotation;
				instanceDesc.m_entityDesc->m_translation = oldTranslation;

				instanceDesc.m_entity->ResetLocalTransform();
				instanceDesc.m_entity->Scale(oldScale);
				instanceDesc.m_entity->Rotate(oldRotation);
				instanceDesc.m_entity->Translate(oldTranslation);
			}
		}

		// Cannot re-insert the entity, abort update
		MessageBox(NULL, "Unable to reinsert entity", "", MB_OK);

		return FALSE;
	}

	return FALSE;
}

BOOL CRuContainer_Quadtree_DS::Tree::UpdateAllEntityBounds()
{
	// Iterate through each node and update each contained entity's cached bounds
	for(INT32 i = 0; i < m_numNodes; ++i)
	{
		// Iterate through all entities at the node
		for(INT32 j = 0; j < m_treeArray[i].m_entities.Count(); ++j)
		{
			// Instance and update the entity descriptor
			CRuEntity *entity = InstanceEntity(i, j);

			if(entity)
			{
				UpdateEntityDescriptor(entity);
			}
		}
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Tree::EnumerateEntities(const CRuAABB &bounds, CRuArrayList<EntityDesc *> &entityListOut, INT32 curNodeIndex, INT32 curDepth)
{
	// Make sure the node at curNodeIndex intersects the bounding box
	if(Intersects(bounds, m_treeArray[curNodeIndex].m_bounds))
	{
		// If the current node is not a leaf
		if(curDepth < m_depth)
		{
			// Recursively invoke into children (NOTE: Child 0's index is calculated by nodeIndex * 4 + 1)
			for(INT32 i = 0, childIndex = curNodeIndex * 4 + 1, childDepth = curDepth + 1; i < 4; ++i, ++childIndex)
			{
				EnumerateEntities(bounds, entityListOut, childIndex, childDepth);
			}
		}

		for(INT32 i = 0; i < m_treeArray[curNodeIndex].m_entities.Count(); ++i)
		{
			// Make sure the entity actually intersects the bounding box
			if(Intersects(bounds, m_treeArray[curNodeIndex].m_entities[i]->m_bounds))
			{
				// Instance the entity
				CRuEntity *entity = InstanceEntity(curNodeIndex, i);

				if(entity)
				{
					entityListOut.Add(m_treeArray[curNodeIndex].m_entities[i]);
				}
			}
		}
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Tree::EnumerateEntities(const CRuPlane4 *frustumPlanes, CRuArrayList<EntityDesc *> &entityListOut, INT32 curNodeIndex, INT32 curDepth)
{
	// Make sure the node at curNodeIndex intersects the frustum
	if(IntersectsFrustum(frustumPlanes, m_treeArray[curNodeIndex].m_bounds))
	{
		// If the current node is not a leaf
		if(curDepth < m_depth)
		{
			// Recursively invoke into children (NOTE: Child 0's index is calculated by nodeIndex * 4 + 1)
			for(INT32 i = 0, childIndex = curNodeIndex * 4 + 1, childDepth = curDepth + 1; i < 4; ++i, ++childIndex)
			{
				EnumerateEntities(frustumPlanes, entityListOut, childIndex, childDepth);
			}
		}

		for(INT32 i = 0; i < m_treeArray[curNodeIndex].m_entities.Count(); ++i)
		{
			// Make sure the entity actually intersects the frustum
			if(IntersectsFrustum(frustumPlanes, m_treeArray[curNodeIndex].m_entities[i]->m_bounds))
			{
				// Instance the entity
				CRuEntity *entity = InstanceEntity(curNodeIndex, i);

				if(entity)
				{
					entityListOut.Add(m_treeArray[curNodeIndex].m_entities[i]);
				}
			}
		}
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Tree::EnumerateEntityDescriptors(CRuArrayList<char *> &resNameList, CRuArrayList<CRuMatrix4x4> &transformList, CRuArrayList<CRuSphere> &boundsList)
{
	for(INT32 curNodeIndex = 0; curNodeIndex < m_numNodes; ++curNodeIndex)
	{
		for(INT32 i = 0; i < m_treeArray[curNodeIndex].m_entities.Count(); ++i)
		{
			resNameList.Add(m_treeArray[curNodeIndex].m_entities[i]->m_resourceName);

			CRuMatrix4x4 transform;
			transform.SetToIdentity();
			transform.Scale(m_treeArray[curNodeIndex].m_entities[i]->m_scale);
			transform.Rotate(m_treeArray[curNodeIndex].m_entities[i]->m_rotation);
			transform.Translate(m_treeArray[curNodeIndex].m_entities[i]->m_translation);

			transformList.Add(transform);

			boundsList.Add(m_treeArray[curNodeIndex].m_entities[i]->m_bounds);
		}
	}

	return TRUE;
}

/*!
	Initializes the tree.

	@param curNodeIndex Current node index. Must be 0.
	@param curDepth Current depth. Must be 0.
	@param bounds Bounding box for the tree

	@retval TRUE The operation succeeded.
	@retval FALSE The operation failed.
*/
BOOL CRuContainer_Quadtree_DS::Tree::Initialize(INT32 curNodeIndex, INT32 curDepth, const CRuAABB &bounds)
{
	// Initialize current node
	m_treeArray[curNodeIndex].m_bounds = bounds;

	// If the current node is not a leaf
	if(curDepth < m_depth)
	{
		// Recursively invoke into children (NOTE: Child 0's index is calculated by nodeIndex * 4 + 1)
		CRuAABB childBounds;
		for(INT32 i = 0, childIndex = curNodeIndex * 4 + 1, childDepth = curDepth + 1; i < 4; ++i, ++childIndex)
		{
			// Set child bounds to the i-th quadrant
			childBounds.SetBoundsToQuadrantXZ(bounds, i);

			// Recursively invoke Initialize on child
			if(Initialize(childIndex, childDepth, childBounds) == FALSE)
			{
				return FALSE;
			}
		}
	}

	return TRUE;
}

/*!
	Calculates and returns the total number of nodes in a tree with the specified depth.

	@param depth Depth of the tree. Depth of 0 specifies a tree with exactly 1 node.

	@return The number of nodes in the tree.
*/
INT32 CRuContainer_Quadtree_DS::Tree::GetDepthNodeCount(INT32 depth)
{
	INT32 depthNodes = 0;

	for(INT32 i = 0; i <= depth; ++i)
	{
		// Accumulate the number of nodes needed for the next tree level
		depthNodes += static_cast<INT32>(pow(4.0f, i));
	}

	return depthNodes;
}

INT32 CRuContainer_Quadtree_DS::Tree::FindBestFitNode(INT32 curNodeIndex, INT32 curDepth, const CRuSphere &bounds)
{
	// Make sure the node at curNodeIndex contains the specified bounding box
	if(m_treeArray[curNodeIndex].m_bounds.Contains(bounds))
	{
		// If the current node is not a leaf
		if(curDepth < m_depth)
		{
			// Recursively invoke into children (NOTE: Child 0's index is calculated by nodeIndex * 4 + 1)
			for(INT32 i = 0, childIndex = curNodeIndex * 4 + 1, childDepth = curDepth + 1; i < 4; ++i, ++childIndex)
			{
				// Check if child node is the best fit node for the bounding box
				INT32 childBestFitNode = FindBestFitNode(childIndex, childDepth, bounds);
				if(childBestFitNode >= 0)
				{
					return childBestFitNode;
				}
			}
		}

		// Current node is the best fit for the bounding box
		return curNodeIndex;
	}

	return -1;
}

CRuEntity *CRuContainer_Quadtree_DS::Tree::InstanceEntity(INT32 nodeIndex, INT32 entityIndex)
{
	// Load the entity or something
	if(m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity == NULL && m_treeArray[nodeIndex].m_entities[entityIndex]->m_loadFailed == FALSE)
	{
		CRuEntity *entity = g_ruResourceManager->LoadEntity(m_treeArray[nodeIndex].m_entities[entityIndex]->m_resourceName);

		if(entity)
		{
			m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity = entity;

			// Setup frame orientation
			m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity->ResetLocalTransform();
			m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity->Scale(m_treeArray[nodeIndex].m_entities[entityIndex]->m_scale);
			m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity->Rotate(m_treeArray[nodeIndex].m_entities[entityIndex]->m_rotation);
			m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity->Translate(m_treeArray[nodeIndex].m_entities[entityIndex]->m_translation);

			// Store instance descriptor (Note that the entity queue itself keeps one reference to the entity's frame)
			InstanceDesc instanceDesc;

			instanceDesc.m_nodeIndex = nodeIndex;
			instanceDesc.m_entityDesc = m_treeArray[nodeIndex].m_entities[entityIndex];
			instanceDesc.m_entity = m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity;
			instanceDesc.m_entity->AddRef();

			DWORD key = reinterpret_cast<DWORD>(entity);
			DWORD keyHash = RuGlobalHashGen().GetHashCode(key);

			InstanceDesc reclaimedInstanceDesc;
			while(m_entityQueue->Reclaim(key, keyHash, 1, reclaimedInstanceDesc))
			{
				// Release instanced entity
				ruSAFE_RELEASE(reclaimedInstanceDesc.m_entity);
				ruSAFE_RELEASE(reclaimedInstanceDesc.m_entityDesc->m_entity);
			}

			m_entityQueue->Add(key, keyHash, instanceDesc, 1);

			// Force update of the entity (temporary)
			m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity->Update(0.0f);
		}
		else
		{
			// Entity load failed
			m_treeArray[nodeIndex].m_entities[entityIndex]->m_loadFailed = TRUE;
		}
	}

	return m_treeArray[nodeIndex].m_entities[entityIndex]->m_entity;
}

BOOL CRuContainer_Quadtree_DS::Tree::FlushEntityQueue()
{
	if(m_entityQueue)
	{
		// Iterate through all instanced entities
		m_entityQueue->ForAllElements(FlushEntityQueueCallback, this);

		// Clear instanced entity queue
		m_entityQueue->Clear();
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Tree::FlushEntityQueueCallback(const void *key, const void *data, void *userData)
{
	InstanceDesc &cd = *((InstanceDesc *) data);

	ruSAFE_RELEASE(cd.m_entity);

	return TRUE;
}

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

CRuContainer_Quadtree_DS::CRuContainer_Quadtree_DS()
:	m_tree(NULL)
{
}

CRuContainer_Quadtree_DS::~CRuContainer_Quadtree_DS()
{
	delete m_tree;
}

BOOL CRuContainer_Quadtree_DS::Bind(CRuDataStore_Base *dataStore, const CRuAABB &bounds, const CRuVector3 &maxLeafExtents)
{
	// Build initial tree
	m_tree = ruNEW CRuContainer_Quadtree_DS::Tree(dataStore, bounds, maxLeafExtents);

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Bind(CRuDataStore_Base *dataStore)
{
	// Build tree from the data store
	m_tree = ruNEW CRuContainer_Quadtree_DS::Tree(dataStore);

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::CopyToDataStore(CRuDataStore_Base *dataStore)
{
	if(m_tree)
	{
		return m_tree->CopyToDataStore(dataStore);
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::AddEntity(const char *resName, const CRuMatrix4x4 &transform, const CRuSphere &bounds)
{
	return m_tree->AddEntity(resName, transform, bounds);
}

BOOL CRuContainer_Quadtree_DS::RemoveEntity(CRuEntity *entityFrame)
{
	return m_tree->RemoveEntity(entityFrame);
}

INT32 CRuContainer_Quadtree_DS::RemoveEntitiesByResourceName(const char *resourceName)
{
	m_entities.Clear();
	return m_tree->RemoveEntitiesByResourceName(resourceName);
}

INT32 CRuContainer_Quadtree_DS::ReplaceEntitiesByResourceName(const char *oldResourceName, const char *newResourceName)
{
	m_entities.Clear();
	return m_tree->ReplaceEntitiesByResourceName(oldResourceName, newResourceName);
}

BOOL CRuContainer_Quadtree_DS::UpdateEntity(CRuEntity *entityFrame)
{
	return m_tree->UpdateEntityDescriptor(entityFrame, entityFrame->GetLocalTransform());
}

BOOL CRuContainer_Quadtree_DS::UpdateAllEntityBounds()
{
	return m_tree->UpdateAllEntityBounds();
}

BOOL CRuContainer_Quadtree_DS::Save()
{
	return m_tree->Save();
}

BOOL CRuContainer_Quadtree_DS::EnumerateEntityDescriptors(CRuArrayList<char *> &resNameList, CRuArrayList<CRuMatrix4x4> &transformList, CRuArrayList<CRuSphere> &boundsList)
{
	return m_tree->EnumerateEntityDescriptors(resNameList, transformList, boundsList);
}

BOOL CRuContainer_Quadtree_DS::EnumerateVisibleEntityDescriptors(CRuArrayList<char *> &resNameList, CRuArrayList<INT32> &zoneList, CRuArrayList<CRuGUID *> &guidList)
{
	// Iterate through each enumerated, visible entity
	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		resNameList.Add(m_entityDescriptors[i]->m_resourceName);
		zoneList.Add(0);
		guidList.Add(&m_entityDescriptors[i]->m_guid);
	}

	return TRUE;
}

const CRuGUID &CRuContainer_Quadtree_DS::GetEntityGUID(CRuEntity *entity)
{
	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		if(m_entityDescriptors[i]->m_entity == entity)
		{
			return m_entityDescriptors[i]->m_guid;
		}
	}

	return CRuGUID::Invalid;
}

CRuEntity *CRuContainer_Quadtree_DS::GetEntityByGUID(const CRuGUID &guid)
{
	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		if(m_entityDescriptors[i]->m_guid == guid)
		{
			return m_entityDescriptors[i]->m_entity;
		}
	}

	return NULL;
}

const char *CRuContainer_Quadtree_DS::GetEntityResourceName(const CRuGUID &guid)
{
	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		if(m_entityDescriptors[i]->m_guid == guid)
		{
			return m_entityDescriptors[i]->m_resourceName;
		}
	}

	return "";
}

UINT32 CRuContainer_Quadtree_DS::GetEntityZoneFlags(const CRuGUID &guid)
{
	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		if(m_entityDescriptors[i]->m_guid == guid)
		{
			return m_entityDescriptors[i]->m_zoneFlags;
		}
	}

	return 0;
}

BOOL CRuContainer_Quadtree_DS::SetEntityZoneFlags(const CRuGUID &guid, UINT32 zoneFlags)
{
	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		if(m_entityDescriptors[i]->m_guid == guid)
		{
			m_entityDescriptors[i]->m_zoneFlags = zoneFlags;
			return TRUE;
		}
	}

	return FALSE;
}

void CRuContainer_Quadtree_DS::SetCamera(CRuCamera *viewCamera)
{
	m_entityDescriptors.Clear();

	// Enumerate all entities within sweeping radius of the view camera
	m_tree->EnumerateEntities(viewCamera->GetSweepBounds(), m_entityDescriptors);

	CRuVector3 eyePosition = viewCamera->GetCameraPosition();

	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		if(m_entityDescriptors[i]->m_entity)
		{
			// Store distance to camera
			m_entityDescriptors[i]->m_distanceToCamera = SquaredDistance(eyePosition, m_entityDescriptors[i]->m_bounds);
		}
	}
}

BOOL CRuContainer_Quadtree_DS::ResetStates()
{
	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::Update(float elapsedTime)
{
	float distanceClasses[16][3] =
	{
		{	2500.0f,	3000.0f,	4000.0f },
		{	2500.0f,	3000.0f,	4000.0f },
		{	2500.0f,	3000.0f,	4000.0f },
		{	2500.0f,	3000.0f,	4000.0f },
		{	 700.0f,	1050.0f,	1200.0f },
		{	 700.0f,	1050.0f,	1200.0f },
		{	 700.0f,	1050.0f,	1200.0f },
		{	 700.0f,	1050.0f,	1200.0f },
		{	 400.0f,	 800.0f,	 950.0f },
		{	 400.0f,	 800.0f,	 950.0f },
		{	 400.0f,	 800.0f,	 950.0f },
		{	 400.0f,	 800.0f,	 950.0f },
		{	 100.0f,	 500.0f,	 700.0f },
		{	 100.0f,	 500.0f,	 700.0f },
		{	 100.0f,	 500.0f,	 700.0f },
		{	 100.0f,	 500.0f,	 700.0f }
	};

	// Pre-square all of the distance class distances
	for(INT32 i = 0; i < 16; ++i)
	{
		for(INT32 j = 0; j < 3; ++j)
		{
			distanceClasses[i][j] *= distanceClasses[i][j];
		}
	}

	// Update fade controllers
	for(INT32 i = 0; i < m_fadeControllers.Count(); ++i)
	{
		// Update fade controller
		m_fadeControllers[i].m_fadeController->Update(elapsedTime);

		// Check fade controller status
		if(m_fadeControllers[i].m_fadeController->HasExpired())
		{
			if(m_fadeControllers[i].m_isFadeOutController)
			{
				m_fadeControllers[i].m_targetEntity->m_fullyVisible = FALSE;
			}
			else
			{
				m_fadeControllers[i].m_targetEntity->m_fullyVisible = TRUE;
			}

			m_fadeControllers[i].m_targetEntity->m_beingControlled = FALSE;

			// Release controller
			ruSAFE_RELEASE(m_fadeControllers[i].m_fadeController);

			// TODO: possibly release ref to entity

			// Remove controller
			m_fadeControllers.RemoveAt(i);
			--i;
		}
	}

	m_entities.Clear();
	for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
	{
		if(m_entityDescriptors[i]->m_entity)
		{
			INT32 distanceClass = m_entityDescriptors[i]->m_entity->GetOption(ruENTITYOPTION_DISTANCECLASS);

			if(m_entityDescriptors[i]->m_beingControlled == TRUE)
			{
				// If the entity is already being controlled by a controller, simply add it to the visible entity list
				m_entities.Add(m_entityDescriptors[i]->m_entity);
			}
			// If the entity was not visible before...
			else if(m_entityDescriptors[i]->m_fullyVisible == FALSE)
			{
/*				if(m_entityDescriptors[i]->m_distanceToCamera <= distanceClasses[distanceClass][0])
				{
					// If the distance is less than the absolute visibility distance, do nothing and mark it visible
					m_entityDescriptors[i]->m_fullyVisible = TRUE;

					m_entities.Add(m_entityDescriptors[i]->m_entity);
				}
				else if(m_entityDescriptors[i]->m_distanceToCamera <= distanceClasses[distanceClass][1])*/
				if(m_entityDescriptors[i]->m_distanceToCamera <= distanceClasses[distanceClass][1])
				{
					m_entityDescriptors[i]->m_beingControlled = TRUE;

					// If the distance is less than the fade in distance, put a fadein controller on it
					FadeDesc fadeDesc;

					fadeDesc.m_targetEntity = m_entityDescriptors[i];
					fadeDesc.m_isFadeOutController = FALSE;

					fadeDesc.m_fadeController = ruNEW CRuController_DistanceFader();
					fadeDesc.m_fadeController->SetTarget(fadeDesc.m_targetEntity->m_entity);
					fadeDesc.m_fadeController->SetFadeType(fadeDesc.m_isFadeOutController);
					fadeDesc.m_fadeController->SetDuration(1.0f);
					fadeDesc.m_fadeController->Update(0.0f);

					m_fadeControllers.Add(fadeDesc);

					m_entities.Add(m_entityDescriptors[i]->m_entity);
				}
			}
			else
			{
				if(m_entityDescriptors[i]->m_distanceToCamera >= distanceClasses[distanceClass][2])
				{
					m_entityDescriptors[i]->m_beingControlled = TRUE;

					// If the distance is greater than the fade out distance, put a fadeout controller on it
					FadeDesc fadeDesc;

					fadeDesc.m_targetEntity = m_entityDescriptors[i];
					fadeDesc.m_isFadeOutController = TRUE;

					fadeDesc.m_fadeController = ruNEW CRuController_DistanceFader();
					fadeDesc.m_fadeController->SetTarget(fadeDesc.m_targetEntity->m_entity);
					fadeDesc.m_fadeController->SetFadeType(fadeDesc.m_isFadeOutController);
					fadeDesc.m_fadeController->SetDuration(1.0f);
					fadeDesc.m_fadeController->Update(0.0f);

					m_fadeControllers.Add(fadeDesc);
				}

				m_entities.Add(m_entityDescriptors[i]->m_entity);
			}
		}
	}

	// Update visible entities
	for(INT32 i = 0; i < m_entities.Count(); ++i)
	{
		m_entities[i]->Update(elapsedTime);
	}

	return TRUE;
}

BOOL CRuContainer_Quadtree_DS::QueryCollision(CRuCollisionQuery *colQuery)
{
	// If collision query is disabled, return immediately
	if(colQuery->m_ignoreCollisionFlag == FALSE && GetOption(ruENTITYOPTION_COLLISION) == 0)
		return TRUE;

	BOOL retVal = TRUE;

	switch(colQuery->m_queryType)
	{
		default:
		case ruCOLQUERY_RAY:
		case ruCOLQUERY_RAY_HITTEST:
		case ruCOLQUERY_RAY_NEAREST:
		case ruCOLQUERY_RAY_PICK:
		case ruCOLQUERY_RAY_TRIPICK:
			{
				CRuCollisionQuery_Ray_Base *rayQuery = static_cast<CRuCollisionQuery_Ray_Base *>(colQuery);

				for(INT32 i = 0; i < m_entities.Count(); ++i)
				{
					m_entities[i]->QueryCollision(colQuery);
				}
			}

			break;

		case ruCOLQUERY_SEGMENT:
		case ruCOLQUERY_SEGMENT_HITTEST:
		case ruCOLQUERY_SEGMENT_NEAREST:
			{
				CRuCollisionQuery_Segment_Base *segQuery = static_cast<CRuCollisionQuery_Segment_Base *>(colQuery);

				for(INT32 i = 0; i < m_entities.Count(); ++i)
				{
					m_entities[i]->QueryCollision(colQuery);
				}
			}

			break;

		case ruCOLQUERY_AABB_TRIENUM:
			{
				CRuCollisionQuery_AABB_TriEnum *enumQuery = static_cast<CRuCollisionQuery_AABB_TriEnum *>(colQuery);

				// Enumerate all entities within sweeping radius of the view camera
				CRuArrayList<EntityDesc *> entityDescriptors;
				m_tree->EnumerateEntities(enumQuery->m_colAABB, entityDescriptors);

				for(INT32 i = 0; i < entityDescriptors.Count(); ++i)
				{
					if(entityDescriptors[i]->m_entity)
					{
						// Record the last flag count so we can modify the newly queried triangle flags later
						INT32 startFlagIndex = enumQuery->m_colTriFlags->Count();

						// Query
						entityDescriptors[i]->m_entity->QueryCollision(colQuery);

						// Modify flags to fit the object's zone ID
						INT32 zoneID = RuGaia_ZoneFlags_GetID(entityDescriptors[i]->m_zoneFlags);
						if(zoneID > 0)
						{
							for(INT32 j = startFlagIndex; j < enumQuery->m_colTriFlags->Count(); ++j)
							{
								enumQuery->m_colTriFlags->Get(j) = RuGaia_ZoneFlags_SetID(enumQuery->m_colTriFlags->Get(j), zoneID);
							}
						}
					}
				}
			}

			break;

		case ruCOLQUERY_SPHERE_SLIDETEST:
		case ruCOLQUERY_SPHERE_ANCHOR:
		case ruCOLQUERY_SPHERE_TRIENUM:
			{
				CRuCollisionQuery_Sphere_Base *sphereQuery = static_cast<CRuCollisionQuery_Sphere_Base *>(colQuery);

				for(INT32 i = 0; i < m_entities.Count(); ++i)
				{
					m_entities[i]->QueryCollision(colQuery);
				}
			}

			break;

		case ruCOLQUERY_GAIA_CAMTEST:
			{
				CRuCollisionQuery_Gaia_CamTest *camQuery = static_cast<CRuCollisionQuery_Gaia_CamTest *>(colQuery);

				for(INT32 i = 0; i < m_entities.Count(); ++i)
				{
					m_entities[i]->QueryCollision(colQuery);
				}
			}

			break;

		case ruCOLQUERY_USER_FLAG_GET_SEGMENT:
			{
				CRuCollisionQuery_User_Flag_Get_Segment *flagQuery = static_cast<CRuCollisionQuery_User_Flag_Get_Segment *>(colQuery);
				CRuCollisionQuery_User_Flag_Get_Segment curFlagQuery = *flagQuery;

				for(INT32 i = 0; i < m_entityDescriptors.Count(); ++i)
				{
					// NOTE: Should reset query results each time -- allow the query to return info from the
					//       entity in case the entity has a preset zone ID. Then, if there is an override
					//       specified for the entity, replace that information!

					if(m_entityDescriptors[i]->m_entity)
					{
						curFlagQuery.m_positiveHit = FALSE;
						curFlagQuery.m_collisionT = FLT_MAX;
						m_entityDescriptors[i]->m_entity->QueryCollision(&curFlagQuery);
						if(curFlagQuery.m_positiveHit)
						{
							if(flagQuery->m_positiveHit == FALSE || curFlagQuery.m_collisionT < flagQuery->m_collisionT)
							{
								flagQuery->m_positiveHit = TRUE;
								flagQuery->m_collisionT = curFlagQuery.m_collisionT;
								flagQuery->m_collisionPoint = curFlagQuery.m_collisionPoint;
								flagQuery->m_flag = curFlagQuery.m_flag;

								// Override zone ID
								flagQuery->m_flag = RuGaia_ZoneFlags_SetID(flagQuery->m_flag, RuGaia_ZoneFlags_GetID(m_entityDescriptors[i]->m_zoneFlags));
							}
						}
					}
				}
			}

			break;

		case ruCOLQUERY_RAY_SUBOBJECT:
			{
				// Cast collision query to CRuCollisionQuery_Ray_SubObject
				CRuCollisionQuery_Ray_SubObject *subObjQuery = static_cast<CRuCollisionQuery_Ray_SubObject *>(colQuery);

				// Copy ray query parameters
				CRuCollisionQuery_Ray rayQuery;
				rayQuery.m_ignoreCollisionFlag = subObjQuery->m_ignoreCollisionFlag;
				rayQuery.m_worldTransform = subObjQuery->m_worldTransform;
				rayQuery.m_invWorldTransform = subObjQuery->m_invWorldTransform;
				rayQuery.m_colRay = subObjQuery->m_colRay;

				for(INT32 i = 0; i < m_entities.Count(); ++i)
				{
					// Clear query results
					rayQuery.m_colPoints->Clear();
					rayQuery.m_colDistances->Clear();

					// Test collision with the current entity
					if(m_entities[i]->QueryCollision(&rayQuery))
					{
						if(rayQuery.m_colPoints->Count() > 0)
						{
							// Sort the results using insertion sort
							m_insertionSort.Sort(rayQuery.m_colDistances->GetArray(), rayQuery.m_colDistances->Count());
							UINT32 *sortedIndices = m_insertionSort.GetSortedIndices();

							// Insert sub-object entry into results
							subObjQuery->m_colObjects->Add(m_entities[i]);
							subObjQuery->m_colDistances->Add(rayQuery.m_colDistances->Get(sortedIndices[0]));
						}
					}
				}
			}

			break;
	}	

	return retVal;
}

INT32 CRuContainer_Quadtree_DS::GetNumEntities()
{
	return m_entities.Count();
}

CRuEntity *CRuContainer_Quadtree_DS::GetEntity(INT32 index)
{
	if(index >= 0 && index < m_entities.Count())
	{
		return m_entities[index];
	}

	return NULL;
}

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

#pragma managed
