/*
	Trig Wars.
	Copyright (c) 2008, Darragh Coy.
	All rights reserved.
	Original work(s), source code & author(s) details available at: http://www.darraghcoy.com

	Redistribution and use in source and binary forms, with or without modification, are permitted 
	provided that the following conditions are met:

		* 	Redistributions of source code must retain the above copyright notice, this list of 
			conditions and the following disclaimer.
		* 	Redistributions in binary form must reproduce the above copyright notice, this list of 
			conditions and the following disclaimer in the documentation.
		* 	Neither the name of the author nor the names of contributors may be used to endorse or 
			promote products derived from this software without specific prior written permission.
		* 	The use of any third party libraries, modules or data files provided with the source 
			form of the program must follow and respect the individual licensing terms of these 
			components. You do not have permission to modify or circumvent the licensing terms for 
			provided third party components unless the third party licenses specifically allow this. 
			If you do not agree to the terms of provided third party components then you do not have 
			permission to use them in your derived work(s).
		* 	The terms of this license do not apply to separate (but related) distributions if supplied 
			by the author(s), only to the contents of this source distribution, derived works, and the 
			binaries produced by either modified or unmodified versions of the source code. The terms 
			of this license do not also apply to any third party libraries or components provided with 
			the source distribution. Such third party elements are licensed under their own separate 
			agreements.

	THIS SOFTWARE IS PROVIDED BY DARRAGH COY ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, 
	BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
	ARE DISCLAIMED. IN NO EVENT SHALL DARRAGH COY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
	EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
	OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 
	OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
	IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef QUAD_TREE_H
#define QUAD_TREE_H

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

namespace Game
{
	//=================================================================================================================
	//=================================================================================================================
	
	class QuadTreeNode;
	class QuadTreeEntry;
	class PrimitivesRenderer;
	class Camera2D;
	class PositionalObject;

	//=================================================================================================================
	/// @brief		This class holds and maintains a quad tree. The quad tree maintains the basic structure for 
	///				the tree as well as providing functions for querying objects and searching.
	/// @remarks	For speed the quad tree makes use of a pooling system to maintain nodes and entries, and keep
	///				them for later use.
	//=================================================================================================================
	
	class QuadTree : public ObjectBase
	{
		public:
		
			//=========================================================================================================
			// Enums
			//=========================================================================================================

				/// Represents a sub node or quadrant under a given node

				enum NodeQuadrant
				{
					/// North east sub node

					NQ_NE ,

					/// South east sub node

					NQ_SE ,

					/// North west sub node

					NQ_NW ,

					/// South west sub node

					NQ_SW
				};		

			//=========================================================================================================
			// Functions
			//=========================================================================================================

				/// Creates the quad tree

				QuadTree
				( 
					const Vec2f &	position						, 
					const Vec2f &	size							, 
					unsigned		max_depth = 6					,
					unsigned		initial_node_pool_size = 512	,
					unsigned		initial_entry_pool_size = 1024
				);
				
				/// Destructor: cleans up
				
				~QuadTree();
				
				/// Returns the root of the quad tree
				
				inline const QuadTreeNode * GetRoot() const { return m_root; }

				/// Adds an object into the quad tree

				QuadTreeEntry * AddObject( PositionalObject * object , QuadTreeEntry * object_entry = 0 );

				/// Removes an object from the quad tree: need the quad tree entry for fast access!

				void RemoveObject( QuadTreeEntry * entry );

				/// Updates an entries position in the tree. Call this when the position of the entries object has changed.

				void UpdateEntry( QuadTreeEntry * entry );

				/// Gets the name of the object's class

				virtual const char * GetTypeName() const;
				
				//=====================================================================================================
				/// @brief		Gets a sub-node quadrant identifier for the given position and node center
				/// @param		pos - position to get the quadrant for
				/// @param		node_center - center of the node that contains the four quadrants
				/// @returns	Which sub quadrant of the node the given postion would be in
				//=====================================================================================================

				static inline NodeQuadrant GetQuadrant( const Vec2f & pos , const Vec2f & node_center )
				{
					if ( pos.x < node_center.x )
					{
						if ( pos.y < node_center.y )
						{
							return NQ_SW;
						}
						else
						{
							return NQ_NW;
						}
					}
					else
					{
						if ( pos.y < node_center.y )
						{
							return NQ_SE;
						}
						else
						{
							return NQ_NE;
						}
					}
				}				

				#ifdef USE_DEBUG_CONSOLE

					/// Renders a visualisation of the quad tree using the given primitives renderer: only used in debug

					void Render( Camera2D * c , PrimitivesRenderer * p );

				#endif
		
		private:
		
			//=========================================================================================================
			// Functions
			//=========================================================================================================
			
				/// Allocates a quad tree node from the pool and grows the pool size if out of spare objects
				
				QuadTreeNode * AllocNode();
				
				/// Allocates a quad tree entry from the pool and grows the pool size if out of spare objects
				
				QuadTreeEntry * AllocEntry();

				#ifdef USE_DEBUG_CONSOLE

					/// This recursive function recursively draws the quad tree.

					void RenderRecursive( Camera2D * c , PrimitivesRenderer * p , QuadTreeNode * node );

				#endif

				/// Returns which node a given point is is. This is the deepest tree node that the point is contained in.

				QuadTreeNode * GetNodeFromPoint( const Vec2f & p );
				
				/// Insert the given object into the head of the object list for the given node, if not present then this list is made
				
				QuadTreeEntry * InsertToObjectList( PositionalObject * object , QuadTreeNode * node , QuadTreeEntry * entry = 0 );
				
				/// Inserts the given object into a sub node of the given node: this sub node is created
				
				QuadTreeEntry * InsertToSubNode( PositionalObject * object , QuadTreeNode * node , QuadTreeEntry * entry = 0 );
				
				/// After removing a child node from a node, this function sess if there is just one other child node left and removes unecessary subdivisions
				
				void ConsolidateNode( QuadTreeNode * node );
				
				/// These are debug only functions
				
				#ifdef DEBUG
				
					/// Debug only function that validates the tree
				
					void ValidateTree();
					
					/// This validates the tree recursively
				
					void ValidateTreeRecursive( QuadTreeNode * node );
				
				#endif
			
			//=========================================================================================================
			// Variables
			//=========================================================================================================
			
				/// The root quad tree node. This always exists
				
				QuadTreeNode * m_root;
				
				/// A pool of spare quad tree nodes for use. Each time we run out of nodes this is doubled in size.
				
				Pool<QuadTreeNode> * m_node_pool;
				
				/// A pool of spare quad tree entries for use. Each time we run out of nodes this is doubled in size.
				
				Pool<QuadTreeEntry> * m_entry_pool;
				
				/// A list of node allocations made. Each entry is an array of nodes allocated
				
				std::list<QuadTreeNode*> m_node_allocs;
				
				/// A list of entry allocations made. Each entry is an array of nodes allocated
				
				std::list<QuadTreeEntry*> m_entry_allocs;
				
				/// Maximum depth of the tree: there cannot be more subdivisions than this
				
				unsigned m_max_depth;
	};

};

#endif 