/*
	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.
*/

//=====================================================================================================================
/// @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.
//=====================================================================================================================

#include "Precompiled.h"
#include "Game\QuadTreeAlgo.h"
#include "Game\QuadTree.h"
#include "Game\QuadTreeNode.h"
#include "Game\QuadTreeEntry.h"
#include "Game\GameCore.h"
#include "GameObjects\PositionalObject.h"
#include "Graphics\PrimitivesRenderer.h"
#include "Graphics\Camera2D.h"

using namespace Game;

//=====================================================================================================================
/// @brief		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.
/// @param		stack - stack where the rsults can be saved to
/// @param		tree - quad tree to search for objects in
/// @param		p - position of top bottom left of search rectangle
/// @param		s - size of search rectangle
/// @returns	The number of objects found in the given search area
/// @pre		Given tree must not be null
/// @pre		Given tree must have a root node
/// @pre		Given rectangle must have a valid size
/// @remarks	This function automatically wraps the search rectangle, so it can be used with the map's wrapping
///				system.
///							
///				The layout of the stack is as follows after this function ends:
///
///				PositionalObject *	- result 1
///				PositionalObject *	- result 2
///				PositionalObject *	- result n .. 
//=====================================================================================================================

unsigned QuadTreeAlgo::FindInRectangle( const QuadTree * tree , Stack & stack , const Vec2f & p , const Vec2f & s )
{
	// Make sure everything is ok:
	
	ENSURE( tree != 0	, "Given tree must not be null"				);
	ENSURE( s.x > 0		, "Given rectangle must have a valid size"	);
	ENSURE( s.y > 0		, "Given rectangle must have a valid size"	);
	
	// Right: get the root node:
	
	const QuadTreeNode * node = tree->GetRoot();
	
	// Wrap the bottom left point of the rectangle:
	
	Vec2f p_wrapped = PositionalObject::WrapCoordinates(p);
	
	// Make sure ok:
	
	ENSURE( node , "Given tree must have a root node" );
	
	// Search recursively throughout the quad tree, starting at the root: push the number of objects found onto the stack
	
	return FindInRectangleRecursive(node,stack,p_wrapped,s);
}

//=====================================================================================================================
/// @brief		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.
/// @param		stack - stack that the results can be saved to
/// @param		node - node to start search from
/// @param		p - position of top bottom left of search rectangle
/// @param		s - size of search rectangle
/// @returns	The number of results from this recursive search
/// @pre		Given tree node cannot be null
/// @remarks	This function expects the given point coordinates to be within map bounds.
//=====================================================================================================================

unsigned QuadTreeAlgo::FindInRectangleRecursive( const QuadTreeNode * node , Stack & stack , const Vec2f & p , const Vec2f & s )
{
	// Make sure ok:
	
	ENSURE( node != 0 , "Given tree node cannot be null" );

	// Save the number of results found here:
	
	unsigned num_results = 0;
	
	// Get the quad tree entry for this node:
	
	QuadTreeEntry * entry = node->m_entries;
	
	// Put all objects under this node into the stack
	
	while ( entry )
	{
		// Get the position of this object and unwrap it relative to the position of the search rectangle:
		
		Vec2f obj_p = PositionalObject::UnwrapCoordinates( p , entry->m_object->GetPosition() );
	
		// Make sure this position is within our search rectangle:
		
		if 
		( 
			obj_p.x >= p.x			&&
			obj_p.y >= p.y			&&
			obj_p.x <  p.x + s.x	&&
			obj_p.y <  p.y + s.y
		)
		{
			// One more search hit:
		
			num_results++;					
			
			// Put the object found onto the stack
			
			stack.Push( entry->m_object );			
		}
		
		// Next object
		
		entry = entry->m_next;
	}

	// Get which quadrant of this node the given rectangle is in:
	
	QuadTree::NodeQuadrant quadrant = QuadTree::GetQuadrant( p , node->m_center );
	
	// See what the result is:
	
	switch ( quadrant )
	{
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		// South west: This is the easiest case. We do not have to worry about wrapping with this one
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		
		case QuadTree::NQ_SW:
		{
			// See if we have a south west child node:
			
			if ( node->m_node_sw )
			{
				// Search this node and add to the results:
				
				num_results += FindInRectangleRecursive( node->m_node_sw , stack , p , s );
			}
			
			// See if the rectangle extends past the center of the node on the x and y axes
			
			bool past_center_x = p.x + s.x >= node->m_center.x;
			bool past_center_y = p.y + s.y >= node->m_center.y;
			
			// See if we are past the center on the x-axis
			
			if ( past_center_x )
			{
				// Can overlap the south east child of this node: see if there
				
				if ( node->m_node_se )
				{
					// Search this node and add to the results:
				
					num_results += FindInRectangleRecursive( node->m_node_se , stack , p , s );					
				}
			}
			
			// See if we are past the center on the y-axis
			
			if ( past_center_y )
			{
				// Can overlap the north west child of this node: see if there
				
				if ( node->m_node_nw )
				{
					// Search this node and add to the results:
				
					num_results += FindInRectangleRecursive( node->m_node_nw , stack , p , s );
				}
				
				// See if we can overlap the north east child:
				
				if ( past_center_x )
				{
					// Can overlap the north east child: see if there
					
					if ( node->m_node_ne )
					{
						// Search this node and add to the results:
					
						num_results += FindInRectangleRecursive( node->m_node_ne , stack , p , s );						
					}
				}
			}			
		
		}	break;
		
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		// South east: Need to worry about wrapping on the x axis only
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		
		case QuadTree::NQ_SE:
		{
			// See if we have a south east child node:
			
			if ( node->m_node_se )
			{
				// Search this node and add to the results:
				
				num_results += FindInRectangleRecursive( node->m_node_se , stack , p , s );
			}
			
			// See if the rectangle extends past the center of the node on the y axis. 
			
			bool past_center_y = p.y + s.y >= node->m_center.y;
			
			// For the x axis we need to add map size to the left side of node the and see if we are past that. This deals with wrapping.
			
			bool past_left_x = p.x + s.x >= node->m_center.x + GameCore::MAP_AREA.x - node->m_size.x;
			
			// See if we are past the left side of the node when wrapping is taken into account
			
			if ( past_left_x )
			{
				// Can overlap the south west child of this node: see if there
				
				if ( node->m_node_sw )
				{
					// Search this node and add to the results:
				
					num_results += FindInRectangleRecursive( node->m_node_sw , stack , p , s );					
				}
			}
			
			// See if we can overlap any of the top two nodes:
			
			if ( past_center_y )
			{
				// Good: we can definitely overlap the north east child. See if there
				
				if ( node->m_node_ne )
				{
					// Search this node and add to the results:
				
					num_results += FindInRectangleRecursive( node->m_node_ne , stack , p , s );
				}
				
				// We can only overlap the north west child if we are past the left x coord when wrapped:
				
				if ( past_left_x )
				{
					// Can overlap the nort west child: see if there
					
					if ( node->m_node_nw )
					{
						// Search this node and add to the results:
					
						num_results += FindInRectangleRecursive( node->m_node_nw , stack , p , s );						
					}
				}
			}
		
		}	break;
		
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		// North west: Need to worry about wrapping on the y axis only
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		
		case QuadTree::NQ_NW:
		{
			// See if we have a north west child node:
			
			if ( node->m_node_nw )
			{
				// Search this node and add to the results:
				
				num_results += FindInRectangleRecursive( node->m_node_nw , stack , p , s );
			}
			
			// See if the rectangle extends past the center of the node on the x axis. 
			
			bool past_center_x = p.x + s.x >= node->m_center.x;
			
			// For the y axis we need to add map size to the bottom side of node the and see if we are past that. This deals with wrapping.
			
			bool past_bottom_y = p.y + s.y >= node->m_center.y + GameCore::MAP_AREA.y - node->m_size.y;
			
			// See if we are past the x center of the node, if so then we can overlap the north east node:
			
			if ( past_center_x )
			{
				// Can overlap the north east node: see if there
				
				if ( node->m_node_ne )
				{
					// Search this node and add to the results:
					
					num_results += FindInRectangleRecursive( node->m_node_ne , stack , p , s );
				}
			}
			
			// See if we are past the wrapped bottom of the node: if so then we can overlap the bottom two nodes
			
			if ( past_bottom_y )
			{
				// We can definitely overlap the south west node: see if there
				
				if ( node->m_node_sw )
				{
					// Search this node and add to the results:
					
					num_results += FindInRectangleRecursive( node->m_node_sw , stack , p , s );
				}
				
				// Now see if we are past the x center. If so then we can overlap the south east node
				
				if ( past_center_x )
				{
					// Can overlap the south east node: see if there
					
					if ( node->m_node_se )
					{
						// Search this node and add to the results:
						
						num_results += FindInRectangleRecursive( node->m_node_se , stack , p , s );					
					}
				}
			}
		
		}	break;
		
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		// North east: Need to worry about wrapping on both the x and y axis
		//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
		
		case QuadTree::NQ_NE:
		{
			// See if we have a north east child node:
			
			if ( node->m_node_ne )
			{
				// Search this node and add to the results:
				
				num_results += FindInRectangleRecursive( node->m_node_ne , stack , p , s );
			}
			
			// For the x axis we need to add map size to the left side of node the and see if we are past that. This deals with wrapping.
			
			bool past_left_x = p.x + s.x >= node->m_center.x + GameCore::MAP_AREA.x - node->m_size.x;
			
			// For the y axis we need to add map size to the bottom side of node the and see if we are past that. This deals with wrapping.
			
			bool past_bottom_y = p.y + s.y >= node->m_center.y + GameCore::MAP_AREA.y - node->m_size.y;
			
			// See if we are past the left side of the node:
			
			if ( past_left_x )
			{
				// Can overlap the north west child node: see if there
				
				if ( node->m_node_nw )
				{
					// Search this node and add to the results:
					
					num_results += FindInRectangleRecursive( node->m_node_nw , stack , p , s );
				}
			}
			
			// See if we are past the bottom side of the node:
			
			if ( past_bottom_y )
			{
				// Can definitely overlap the south east node: see if there
				
				if ( node->m_node_se )
				{
					// Search this node and add to the results:
					
					num_results += FindInRectangleRecursive( node->m_node_se , stack , p , s );
				}
				
				// Now see if we are past the left side of the node:
				
				if ( past_left_x )
				{
					// Can overlap the south west node: see if there:
					
					if ( node->m_node_sw )
					{
						// Search this node and add to the results:
						
						num_results += FindInRectangleRecursive( node->m_node_sw , stack , p , s );						
					}
				}
			}
		
		}	break;
	}
	
	// Return the number of results found
	
	return num_results;
}

#ifdef USE_DEBUG_CONSOLE

//=====================================================================================================================
/// @brief		This function is only defined if the console is defined. It allows a debug draw of the quad tree 
///				FindInRectangle() function.
/// @param		tree - tree to do the search in
/// @param		stack - stack to use for saving results to
/// @param		p - bottom left corner of the search rectangle
/// @param		c - camera the game is being viewed from
/// @param		r - primitives renderer to draw with
/// @pre		Given tree must not be null
/// @pre		Given size must be valid
/// @pre		Given camera must not be null
/// @pre		Given renderer must not be null
//=====================================================================================================================

void QuadTreeAlgo::DrawFindInRectangleResults
( 
	const QuadTree *		tree	, 
	Stack &					stack	, 
	const Vec2f &			p		,
	const Vec2f &			s		,
	Camera2D *				c		,
	PrimitivesRenderer *	r
)
{
	// Make sure ok:
	
	ENSURE( tree	, "Given tree must not be null."	);
	ENSURE( s.x > 0	, "Given size must be valid."		);
	ENSURE( s.y > 0	, "Given size must be valid."		);
	ENSURE( c		, "Given camera must not be null"	);
	ENSURE( r		, "Given renderer must not be null"	);
	
	// Do a search:
	
	unsigned results = FindInRectangle( tree , stack , p , s );
	
	// Draw a rectanlge representing the search area:
	
	r->DrawQuadOutline
	(
		c,
		p,
		p + Vec2f(0,s.y),
		p + Vec2f(s.x,s.y),
		p + Vec2f(s.x,0),
		Color(1.0f,0.5f,1.0f).ToDxUnsigned()
	);
	
	// Draw each result:
	
	while ( results != 0 )
	{
		// Get this result:
		
		PositionalObject * obj = stack.Pop<PositionalObject*>();
		
		// Draw it:
		
		r->DrawPoint
		(
			c, 
			PositionalObject::UnwrapCoordinates
			( 
				PositionalObject::WrapCoordinates( c->GetPosition() ) , 
				obj->GetPosition()
			),
			Color::Red().ToDxUnsigned()
		);
		
		// One less result
		
		results--;
	}
}

#endif