/*
	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_ALGO_H
#define QUAD_TREE_ALGO_H

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

namespace Game
{
	//=================================================================================================================
	//=================================================================================================================
	
	class QuadTree;
	class QuadTreeNode;
	class Stack;
	class Camera2D;
	class PrimitivesRenderer;

	//=================================================================================================================
	/// @brief		This class contains algorithms for searching the quad tree. 
	///				Algorithms are stored here to minimize dependencies in the quad tree because some of them are 
	///				dependent on the type of game. For fast return of results, the algorithms all use a temporary 
	///				provided stack for returning results rather than stl lists or vectors. See each function's
	///				documentation for information on the order of pushes and pops.
	//=================================================================================================================
	
	class QuadTreeAlgo
	{
		public:

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

				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				/// Searches a given rectangular area in the given quad tree and returns all of the objects found in
				/// that rectangular area in the given stack.
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				
				static unsigned FindInRectangle( const QuadTree * tree , Stack & stack , const Vec2f & p , const Vec2f & s );
				
				#ifdef USE_DEBUG_CONSOLE
				
					/// This function is only defined if the console is defined. It allows a debug draw of the quad tree FindInRectangle() function				
					
					static void DrawFindInRectangleResults
					( 
						const QuadTree *		tree	, 
						Stack &					stack	, 
						const Vec2f &			p		,
						const Vec2f &			s		,
						Camera2D *				c		,
						PrimitivesRenderer *	r
					);
					
				#endif
				
		private:
		

			//=========================================================================================================
			// Functions
			//=========================================================================================================
			
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				/// This is the recursive version of FindInRectangle() which recurses throughout the quad tree, 
				///	returning search results for each node.
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				
				static unsigned FindInRectangleRecursive( const QuadTreeNode * node , Stack & stack , const Vec2f & p , const Vec2f & s );		
	};

};

#endif 