#ifndef _RUCONTAINER_QUADTREE_DS_H_
#define _RUCONTAINER_QUADTREE_DS_H_

// Container base
#include "../../Scene/Base/RuEntityContainer.h"
#include "../../Scene/Controller/RuController_DistanceFader.h"
#include "../../Core/DataStore/RuDataStore_Base.h"

#pragma unmanaged

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

class CRuController_DistanceFader;

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

class CRuContainer_Quadtree_DS : public IRuEntity_Container
{
	ruRTTI_DECLARE
	ruHEAP_DECLARE
	ruCLASSGUID_DECLARE

protected:
	class EntityDesc
	{
	public:
		CRuGUID								m_guid;								//!< GUID of this entity instance
		char*								m_resourceName;						//!< Resource name of the entity
		CRuVector3							m_scale;							//!< Scale of the entity
		CRuQuaternion						m_rotation;							//!< Rotation of the entity
		CRuVector3							m_translation;						//!< Translation of the entity
		CRuSphere							m_bounds;							//!< Bounds of the entity
		UINT32								m_zoneFlags;						//!< Zone flags -- see RuGaia_Base for details

		// Run-time information
		CRuEntity*							m_entity;							//!< Instanced entity

		REAL								m_distanceToCamera;					//!< Distance to camera
		BOOL								m_beingControlled;					//!< Is the entity being controlled by a fader?
		BOOL								m_fullyVisible;						//!< Is the entity fully visible?
		BOOL								m_isDirty;
		BOOL								m_loadFailed;						//!< Has the entity failed loading?

	public:
											EntityDesc();
											~EntityDesc();
	};

	class TreeNode
	{
	public:
		INT32								m_iterationNumber;					//!< Node iteration number
		CRuAABB								m_bounds;							//!< Bounding box of the node

		// Run-time information
		BOOL								m_loaded;							//!< Has node data been loaded?
		CRuArrayList<EntityDesc *>			m_entities;							//!< Entities at the node

	public:
											TreeNode();
											~TreeNode();

		void								Initialize(const CRuAABB &bounds);
	};

	class Tree
	{
	protected:
		struct InstanceDesc
		{
			INT32							m_nodeIndex;						//!< Node that contains the instanced entity
			EntityDesc*						m_entityDesc;						//!< Entity descriptor
			CRuEntity*						m_entity;							//!< Instanced entity
		};

		// Settings
		BOOL								m_readOnly;

		// Data store
		CRuDataStore_Base*					m_dataStore;
		INT32								m_tableHandle_Header;
		INT32								m_tableHandle_Entity;

		// Tree data
		CRuAABB								m_bounds;
		CRuVector3							m_maxLeafExtents;
		INT32								m_depth;							//!< Depth of the tree
		INT32								m_numNodes;							//!< Number of nodes in the tree
		TreeNode*							m_treeArray;						//!< Tree stored as an array

		// Instancing data
		CRuLRUQueue<DWORD, InstanceDesc>*	m_entityQueue;						//!< LRU queue of entities

		CRuArrayList<CRuGUID>				m_deletedEntities;

		// Utility objects
		CRuStreamCompressor*				m_streamCompressor;					//!< Stream compression/decompression utility object
		CRuMemoryStream*					m_compressedChunkStream;			//!< Temporary buffer space for compressed streams
		CRuMemoryStream*					m_decompressedChunkStream;			//!< Temporary buffer space for decompressed streams

	public:
											Tree(CRuDataStore_Base *dataStore, const CRuAABB &bounds, const CRuVector3 &maxLeafExtents);
											Tree(CRuDataStore_Base *dataStore);
											~Tree();

		BOOL								CopyToDataStore(CRuDataStore_Base *targetDataStore);

		BOOL								Load();
		BOOL								Save();

		BOOL								AddEntity(const char *resName, const CRuMatrix4x4 &transform, const CRuSphere &bounds);
		BOOL								AddEntity(EntityDesc *entityDescriptor);
		BOOL								RemoveEntity(EntityDesc *entityDescriptor);
		BOOL								RemoveEntity(CRuEntity *entity);
		INT32								RemoveEntitiesByResourceName(const char *resourceName, INT32 curNodeIndex = 0, INT32 curDepth = 0);
		INT32								ReplaceEntitiesByResourceName(const char *oldResourceName, const char *newResourceName, INT32 curNodeIndex = 0, INT32 curDepth = 0);
		BOOL								UpdateEntityDescriptor(CRuEntity *entity);
		BOOL								UpdateEntityDescriptor(CRuEntity *entity, const CRuMatrix4x4 &transform);

		BOOL								UpdateAllEntityBounds();

		BOOL								EnumerateEntities(const CRuAABB &bounds, CRuArrayList<EntityDesc *> &entityListOut, INT32 curNodeIndex = 0, INT32 curDepth = 0);
		BOOL								EnumerateEntities(const CRuPlane4 *frustumPlanes, CRuArrayList<EntityDesc *> &entityListOut, INT32 curNodeIndex = 0, INT32 curDepth = 0);

		BOOL								EnumerateEntityDescriptors(CRuArrayList<char *> &resNameList, CRuArrayList<CRuMatrix4x4> &transformList, CRuArrayList<CRuSphere> &boundsList);

	protected:
		BOOL								Initialize(INT32 curNodeIndex, INT32 curDepth, const CRuAABB &bounds);
		INT32								GetDepthNodeCount(INT32 depth);
		INT32								FindBestFitNode(INT32 curNodeIndex, INT32 curDepth, const CRuSphere &bounds);
		CRuEntity*							InstanceEntity(INT32 nodeIndex, INT32 entityIndex);

		BOOL								FlushEntityQueue();
		static BOOL							FlushEntityQueueCallback(const void *key, const void *data, void *userData);
	};

	class FadeDesc
	{
	public:
		EntityDesc*							m_targetEntity;						//!< Target entity descriptor
		CRuController_DistanceFader*		m_fadeController;					//!< Fade controller
		BOOL								m_isFadeOutController;				//!< Is this a fadeout controller?
	};

	// Settings
	float									m_fadeInDistance;
	float									m_fadeOutDistance;

	// Entity tree
	Tree*									m_tree;								//!< The entity tree

	CRuArrayList<FadeDesc>					m_fadeControllers;					//!< List of active fade controllers

	// Visible entities
	CRuArrayList<EntityDesc *>				m_entityDescriptors;
	CRuArrayList<CRuEntity *>				m_entities;

	// Workspace
	CRuInsertionSort						m_insertionSort;

public:
											CRuContainer_Quadtree_DS();
	virtual									~CRuContainer_Quadtree_DS();

	BOOL									Bind(CRuDataStore_Base *dataStore, const CRuAABB &bounds, const CRuVector3 &maxLeafExtents);
	BOOL									Bind(CRuDataStore_Base *dataStore);
	BOOL									CopyToDataStore(CRuDataStore_Base *dataStore);

	BOOL									AddEntity(const char *resName, const CRuMatrix4x4 &transform, const CRuSphere &bounds);
	BOOL									RemoveEntity(CRuEntity *entityFrame);
	INT32									RemoveEntitiesByResourceName(const char *resourceName);
	INT32									ReplaceEntitiesByResourceName(const char *oldResourceName, const char *newResourceName);
	BOOL									UpdateEntity(CRuEntity *entityFrame);

	BOOL									UpdateAllEntityBounds();

	BOOL									Save();

	BOOL									EnumerateEntityDescriptors(CRuArrayList<char *> &resNameList, CRuArrayList<CRuMatrix4x4> &transformList, CRuArrayList<CRuSphere> &boundsList);
	BOOL									EnumerateVisibleEntityDescriptors(CRuArrayList<char *> &resNameList, CRuArrayList<INT32> &zoneList, CRuArrayList<CRuGUID *> &guidList);

	const CRuGUID&							GetEntityGUID(CRuEntity *entity);
	CRuEntity*								GetEntityByGUID(const CRuGUID &guid);
	const char*								GetEntityResourceName(const CRuGUID &guid);
	UINT32									GetEntityZoneFlags(const CRuGUID &guid);
	BOOL									SetEntityZoneFlags(const CRuGUID &guid, UINT32 zoneFlags);

	// LOD selection and frustum culling
	void									SetCamera(CRuCamera *viewCamera);

	// Entity interface
	virtual BOOL							ResetStates();
	virtual BOOL							Update(float elapsedTime);

	// Collision
	virtual BOOL							QueryCollision(CRuCollisionQuery *colQuery);

	// IRuEntity_Container interface
	virtual INT32							GetNumEntities();
	virtual CRuEntity*						GetEntity(INT32 index);
};

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

#pragma managed

#endif
