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

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

using namespace Game;

//=====================================================================================================================
/// @brief		Creates the quad tree
/// @param		position - position of the root node of the quad tree
/// @param		size - 'size' of the first node. Size determines the centers of sub nodes. This is half extent size.
/// @param		max_depth - maximum depth of the tree
/// @param		initial_node_pool_size - how many quad tree nodes to preallocate initially for later. this can affect
///				performance.
/// @param		initial_entry_pool_size - how many quad tree entries to preallocate initially for later. this can affect
///				performance.
/// @pre		Maximum depth must be at least 2
/// @pre		Initial node pool size must be at least 1
/// @pre		Initial entry pool size must be at least 1
//=====================================================================================================================

QuadTree::QuadTree
( 
	const Vec2f &	position				, 
	const Vec2f &	size					, 
	unsigned		max_depth				,
	unsigned		initial_node_pool_size	,
	unsigned		initial_entry_pool_size 
)
{
	// Make sure these are all ok:
	
	ENSURE( max_depth > 1				, "Maximum depth must be at least 2"			);
	ENSURE( initial_node_pool_size > 0	, "Initial node pool size must be at least 1"	);
	ENSURE( initial_entry_pool_size > 0 , "Initial entry pool size must be at least 1"	);
	
	// Save the max depth
	
	m_max_depth = max_depth;
	
	// Need to allocate our initial nodes and entries:
	
	QuadTreeNode * initial_nodes = new QuadTreeNode[ initial_node_pool_size ]();
	QuadTreeEntry * initial_entries = new QuadTreeEntry[ initial_entry_pool_size ]();
	
	m_node_allocs.push_back(initial_nodes);
	m_entry_allocs.push_back(initial_entries);
	
	// Make the two pools used by the quad tree:
	
	m_node_pool	= new Pool<QuadTreeNode>(initial_nodes,initial_node_pool_size);
	m_entry_pool = new Pool<QuadTreeEntry>(initial_entries,initial_entry_pool_size);

	// Allocate a node for the root:
	
	m_root = AllocNode();
	
	// Set the properties of the root:
	
	m_root->m_center	= position;
	m_root->m_size		= size;
	m_root->m_depth		= 1;
	m_root->m_node_nw	= 0;
	m_root->m_node_ne	= 0;
	m_root->m_node_sw	= 0;
	m_root->m_node_se	= 0;
	m_root->m_entries	= 0;
	m_root->m_parent	= 0;
}

//=====================================================================================================================
/// @brief		Destructor: cleans up the quad tree
//=====================================================================================================================

QuadTree::~QuadTree()
{
	// Destroy the two pools:
	
	m_node_pool->RemoveReference();
	m_entry_pool->RemoveReference();
	
	// Destroy all pooled objects:
	
	while ( m_node_allocs.size() > 0 )
	{
		delete[] m_node_allocs.front(); m_node_allocs.pop_front();
	}
	
	while ( m_entry_allocs.size() > 0 )
	{
		delete[] m_entry_allocs.front(); m_entry_allocs.pop_front();
	}	
}

//=====================================================================================================================
/// @brief		Allocates a quad tree node from the pool and grows the pool size if out of spare objects.
/// @returns	Returns the allocated tree node
/// @remarks	This is used instead of manually allocating from the pool since it grows the pool size.
/// @pre		The node pool must have been created
/// @pre		The size of the node pool must be at least 1 
//=====================================================================================================================

QuadTreeNode * QuadTree::AllocNode()
{
	// Make sure ok:
	
	ENSURE( m_node_pool					, "The node pool must have been created"			);
	ENSURE( m_node_pool->GetSize() > 0	, "The size of the node pool must be at least 1 "	);

	// See if there are spare objects in the pool:
	
	if ( m_node_pool->GetUsedCount() < m_node_pool->GetSize() )
	{
		#ifdef DEBUG

			// In debug mode, mark the quad tree the node belongs to

			QuadTreeNode * n = m_node_pool->Alloc();

			// Mark:

			n->m_tree = this;

			// Return:

			return n;

		#else

			// Free objects just alloc straight from the pool
			
			return m_node_pool->Alloc();			

		#endif
	}
	else
	{
		// No free objects: need to grow the pool. Do an alloc and grow the pool to double it's size
		
		QuadTreeNode * alloced = new QuadTreeNode[ m_node_pool->GetSize() ];
		
		// Add this to the list of allocated nodes:
		
		m_node_allocs.push_back(alloced);
		
		// Grow the node pool:
		
		m_node_pool->Grow(alloced,m_node_pool->GetSize());

		// In debug mode we need to set what tree the node belongs to:

		#ifdef DEBUG

			// In debug mode, mark the quad tree the node belongs to

			QuadTreeNode * n = m_node_pool->Alloc();

			// Mark:

			n->m_tree = this;

			// Return:

			return n;

		#else
			
			// Now get a free object
		
			return m_node_pool->Alloc();

		#endif	
	}
}

//=====================================================================================================================
/// @brief		Allocates a quad tree entry from the pool and grows the pool size if out of spare objects
/// @returns	Returns the allocated tree entry
/// @remarks	This is used instead of manually allocating from the pool since it grows the pool size.
/// @pre		The node pool must have been created
/// @pre		The size of the entry pool must be at least 1 
//=====================================================================================================================

QuadTreeEntry * QuadTree::AllocEntry()
{
	// Make sure ok:
	
	ENSURE( m_node_pool					, "The node pool must have been created"			);
	ENSURE( m_entry_pool->GetSize() > 0	, "The size of the entry pool must be at least 1 "	);

	// See if there are spare objects in the pool:
	
	if ( m_entry_pool->GetUsedCount() < m_entry_pool->GetSize() )
	{
		// Free objects just alloc straight from the pool
		
		return m_entry_pool->Alloc();
	}
	else
	{
		// No free objects: need to grow the pool. Do an alloc and grow the pool to double it's size
		
		QuadTreeEntry * alloced = new QuadTreeEntry[ m_entry_pool->GetSize() ];
		
		// Add this to the list of allocated nodes:
		
		m_entry_allocs.push_back(alloced);
		
		// Grow the node pool:
		
		m_entry_pool->Grow(alloced,m_entry_pool->GetSize());
		
		// Now get a free object
		
		return m_entry_pool->Alloc();
	}	
}

//=====================================================================================================================
/// @brief		Returns which node a given point is. 
///				This is the deepest tree node that the point is contained in.
/// @param		p - point to get the node from
/// @post		The returned node will not be null
//=====================================================================================================================

QuadTreeNode * QuadTree::GetNodeFromPoint( const Vec2f & p )
{
	// Start with the root node:

	QuadTreeNode * n = m_root;
	
	// Set this to false initially:
	
	bool reached_target = false;

	// Find which node of the quad tree the position is in:

	while ( reached_target == false )
	{
		// See what side of the center the object is in and move to that node:

		switch ( GetQuadrant(p,n->m_center) )
		{
			case NQ_NE: if ( n->m_node_ne ){ n = n->m_node_ne; } else { reached_target = true; }	break;
			case NQ_NW: if ( n->m_node_nw ){ n = n->m_node_nw; } else { reached_target = true; }	break;
			case NQ_SE: if ( n->m_node_se ){ n = n->m_node_se; } else { reached_target = true; }	break;
			case NQ_SW: if ( n->m_node_sw ){ n = n->m_node_sw; } else { reached_target = true; }	break;
		}
	}
	
	// Make sure all ok:
	
	ENSURE( n , "The returned node will not be null" );	
	
	// Return the node:
	
	return n;
}

//=====================================================================================================================
/// @brief		Adds an object into the quad tree
/// @param		object - object to add into the tree
/// @param		object_entry - an optional quad tree entry record to use for the given object. This is used internally
///				by the quad tree itself for the UpdateEntry() function. Not for use by anything else.
/// @returns	A quad tree entry for the given object, or the given entry if one was specified
/// @pre		Given object cannot be null
/// @pre		If an entry is given it must be allocated
//=====================================================================================================================

QuadTreeEntry * QuadTree::AddObject( PositionalObject * object , QuadTreeEntry * object_entry )
{
	// Cannot be null:

	ENSURE( object , "Given object cannot be null" );	
	
	// Must be alloced if there
	
	#ifdef DEBUG
	
		if ( object_entry ) ENSURE( object_entry->IsAlloced() == true , "If an entry is given it must be allocated" );
	
	#endif
	
	// Get what node the object is in:
	
	QuadTreeNode * node = GetNodeFromPoint( object->GetPosition() );

	// See if the current node list is empty:

	if ( node->m_entries == 0 )
	{
		// Not a leaf node: need to make a new sub node and insert there. Make sure not at max depth however

		if ( node->m_depth < m_max_depth )
		{
			// Ok: subdivide this node further

			QuadTreeEntry * entry = InsertToSubNode( object , node , object_entry );

			// Return the entry

			return entry;
		}
		else
		{
			// Can't insert at max depth: just insert to the object list for the node

			QuadTreeEntry * entry = InsertToObjectList( object , node , object_entry );

			// Return the entry

			return entry;
		}
	}
	else
	{
		// Not so easy case: see if we can subdivide this node further
		
		if ( node->m_depth < m_max_depth )
		{
			// Can subdivide: get the quadrant the current node in the list is at and the quadrant the object is in
			
			NodeQuadrant q1 = GetQuadrant( object->GetPosition()					, node->m_center );
			NodeQuadrant q2 = GetQuadrant( node->m_entries->m_object->GetPosition()	, node->m_center );
			
			// If they differ just create two new sub nodes and add each node to it's respective sub node
			
			if ( q1 != q2 )
			{
				// Insert the current object in the node entry list into it's own sub node:
				
				{			
					// Save the current entry for the object: we need to reuse this to avoid disrupting objects that are using it
					
					QuadTreeEntry * entry = node->m_entries;
				
					// Get the object in the current node entry list:								
					
					PositionalObject * obj = entry->m_object;
					
					// No more entries for this node: no longer a leaf
					
					node->m_entries = 0;
					
					// Now reinsert the object into a sub node: reuse the previous entry to avoid disrupting objects that reference it
					
					InsertToSubNode(obj,node,entry);
				}
				
				// Insert the new object into it's own sub node:
				
				QuadTreeEntry * entry = InsertToSubNode(object,node,object_entry);

				// Return answer:

				return entry;
			}
			else
			{
				// Hmmm.. This is more tricky. Keep subdividing until both objects are in a separate node, or we reach the max depth
				
					// Get the quad tree entry for the old object: it needs to be reused in case any objects reference it
					
					QuadTreeEntry * old_entry = node->m_entries;
				
					// Get the object in the current node entry list:								
					
					PositionalObject * old_object = old_entry->m_object;
					
					// No more entries for this node: now a leaf node
					
					node->m_entries = 0;
					
					// Continue going until we have reached a solution or we reach max depth
									
					bool continue_subdivision = true;
					
				// Keep going:
				
				do
				{
					// Make a new sub node for both:
					
					QuadTreeNode * new_node = AllocNode();
					
					// Fill in the basics:
					
					new_node->m_depth	= node->m_depth + 1;
					new_node->m_entries	= 0;
					new_node->m_node_ne	= 0;
					new_node->m_node_nw	= 0;
					new_node->m_node_se	= 0;
					new_node->m_node_sw	= 0;
					new_node->m_parent	= node;
					new_node->m_size	= node->m_size * 0.5f;
					
					// Position and let the parent know of the new node:
					
					switch ( q1 )
					{
						case NQ_NE:
						
							new_node->m_center = node->m_center + Vec2f( +new_node->m_size.x , +new_node->m_size.y );
							node->m_node_ne = new_node;
						
						break;
						
						case NQ_NW:
						
							new_node->m_center = node->m_center + Vec2f( -new_node->m_size.x , +new_node->m_size.y );
							node->m_node_nw = new_node;
						
						break;
						
						case NQ_SE:
						
							new_node->m_center = node->m_center + Vec2f( +new_node->m_size.x , -new_node->m_size.y );
							node->m_node_se = new_node;
						
						break;
						
						case NQ_SW:
						
							new_node->m_center = node->m_center + Vec2f( -new_node->m_size.x , -new_node->m_size.y );
							node->m_node_sw = new_node;
						
						break;
					}
					
					// Get which quadrant of the new node both objects are in:
					
					q1 = GetQuadrant( object->GetPosition()		, new_node->m_center );
					q2 = GetQuadrant( old_object->GetPosition()	, new_node->m_center );
					
					// See if they differ:
					
					if ( q1 != q2 )
					{
						// Different: found a solution. Make sure however the new node is not at the max depth
						
						if ( new_node->m_depth < m_max_depth )
						{						
							// Stop subdivision
						
							continue_subdivision = false;
							
							// Insert both objects underneath the new node: insert the old object using its current entry to avoid invalidating references to it
													
							InsertToSubNode( old_object	, new_node , old_entry );
							
							// Need to return the answer of this
							
							QuadTreeEntry * entry = InsertToSubNode( object , new_node , object_entry );

							// Return:

							return entry;
						}
						else
						{
							// Can't subdivide any further: insert the old object using its current entry to avoid invalidating references to it
							
							InsertToObjectList( old_object , new_node , old_entry );
							
							// Need to return this
							
							QuadTreeEntry * entry = InsertToObjectList( object , new_node , object_entry );

							// Return:

							return entry;
						}
					}
					else
					{
						// Not different: see if the new node is at the max depth already:
						
						if ( new_node->m_depth < m_max_depth )
						{
							// Can subdivide further: make this the current node
							
							node = new_node;
						}
						else
						{
							//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
							// Can't subdivide any further. Add both objects into the list of objects at this node.
							// Insert the old object using its current entry to avoid invalidating references to it
							//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
							
							InsertToObjectList( old_object , new_node , old_entry );
							
							// Need to return this
							
							QuadTreeEntry * entry = InsertToObjectList( object , new_node  , object_entry );

							// Return:

							return entry;						
						}
					}
				
				} while ( continue_subdivision );
			
			}	// END ELSE OF IF ( q1 != q2 )
			
			// We should never reach here !
			
			#pragma warning(disable:4127)
			
				ENSURE( 0 , "The quad tree algorithm reached a place it should never be in. Revise." ); 
				
			#pragma warning(default:4127)
			
			// Just return zero in release.. What can you do ?
			
			return 0;			
			
		}	// END ELSE OF IF ( node->m_depth < m_max_depth )
		
		else
		{
			// Can't subdivide this node any further: just add the object to the list of objects in this node
			
			QuadTreeEntry * entry = InsertToObjectList( object , node , object_entry );

			// Return it:

			return entry;
		}
		
	}	// END ELSE OF IF ( node->m_entries == 0 )
}

//=====================================================================================================================
/// @brief		Inserts the given object into a sub node of the given node
/// @param		object - object to insert into a sub node
/// @param		node - node to insert the sub node for the object into
/// @param		entry - an optional entry to use as the objects entry into the quad tree. Some algorithms that rearrange
///				the tree rely on re-use of this entry to avoid invalidating any references objects using the QuadTree
///				might have to this reference.
/// @returns	The quad tree entry for the object
/// @pre		Given node cannot be null
/// @pre		Given object cannot be null
/// @pre		The given node must not be at the maximum depth
/// @pre		When a sub node is being made, this node must not already be present on the given node
//=====================================================================================================================

QuadTreeEntry * QuadTree::InsertToSubNode( PositionalObject * object , QuadTreeNode * node , QuadTreeEntry * entry )
{
	// Make sure everthing is in order
	
	ENSURE( node != 0						, "Given node cannot be null"						);
	ENSURE( object != 0						, "Given object cannot be null"						);
	ENSURE( node->m_depth < m_max_depth		, "The given node must not be at the maximum depth" );

	// Make a new node for the sub node:
	
	QuadTreeNode * new_node = AllocNode();
	
	// Find what quadrant of the current node the object is in:
	
	NodeQuadrant q = GetQuadrant( object->GetPosition() , node->m_center );
	
	// Calc size of new node
	
	new_node->m_size = node->m_size * 0.5f;
	
	// Do the insertion:
	
	switch ( q )
	{
		case NQ_NE:
		
			// Make sure this is ok:
		
			ENSURE( node->m_node_ne == 0 , "When a sub node is being made, this node must not already be present on the given node" );
		
			node->m_node_ne = new_node;	
			new_node->m_center = node->m_center + Vec2f( +new_node->m_size.x , +new_node->m_size.y );						
			
		break;
		
		case NQ_SE:	
		
			// Make sure this is ok:
		
			ENSURE( node->m_node_se == 0 , "When a sub node is being made, this node must not already be present on the given node" );		
		
			node->m_node_se = new_node;	
			new_node->m_center = node->m_center + Vec2f( +new_node->m_size.x , -new_node->m_size.y );
			
		break;
		
		case NQ_NW:	
		
			// Make sure this is ok:
		
			ENSURE( node->m_node_nw == 0 , "When a sub node is being made, this node must not already be present on the given node" );		
		
			node->m_node_nw = new_node;
			new_node->m_center = node->m_center + Vec2f( -new_node->m_size.x , +new_node->m_size.y );
		
		break;
		
		case NQ_SW:
		
			// Make sure this is ok:
		
			ENSURE( node->m_node_sw == 0 , "When a sub node is being made, this node must not already be present on the given node" );		
		
			node->m_node_sw = new_node;
			new_node->m_center = node->m_center + Vec2f( -new_node->m_size.x , -new_node->m_size.y );
			
		break;
	}
	
	// Set parent of new node and it's depth
	
	new_node->m_depth	= node->m_depth + 1;
	new_node->m_parent	= node;
	
	// Clear everything else on the new node:
	
	new_node->m_entries = 0;
	new_node->m_node_ne = 0;
	new_node->m_node_nw = 0;
	new_node->m_node_se = 0;
	new_node->m_node_sw = 0;
				
	// Insert to node object list
	
	return InsertToObjectList( object , new_node , entry );
}

//=====================================================================================================================
/// @brief		Inserts the given object into the head of object list for the given node
/// @param		object - object to insert at the head of the object list
/// @param		node - node which contains the object list
/// @param		entry - an optional entry to use as the objects entry into the quad tree. Some algorithms that rearrange
///				the tree rely on re-use of this entry to avoid invalidating any references objects using the QuadTree
///				might have to this reference.
/// @returns	The quad tree entry for this object
/// @pre		Given object cannot be null
/// @pre		Given node cannot be null
/// @pre		Node must have no children (i.e be a leaf node)
//=====================================================================================================================

QuadTreeEntry * QuadTree::InsertToObjectList( PositionalObject * object , QuadTreeNode * node , QuadTreeEntry * entry )
{
	// Assertions
		
	ENSURE( object != 0				, "Given object cannot be null"						);
	ENSURE( node!= 0				, "Given node cannot be null"						);
	ENSURE( node->m_node_ne == 0	, "Node must have no children (i.e be a leaf node)" );
	ENSURE( node->m_node_nw == 0	, "Node must have no children (i.e be a leaf node)" );
	ENSURE( node->m_node_se == 0	, "Node must have no children (i.e be a leaf node)" );
	ENSURE( node->m_node_sw == 0	, "Node must have no children (i.e be a leaf node)" );

	// See if there is a node list firsly:

	if ( node->m_entries )
	{
		// Already an entry list: insert at list head:
		
		if ( entry == 0 ) entry = AllocEntry();

		// This should never be the case:

		ENSURE( entry->IsAlloced() == true , "Entry should be marked as being alloced!!");
		
		entry->m_parent	= node;
		entry->m_object = object;
		entry->m_next	= node->m_entries;
		entry->m_prev	= 0;
		
		// Make the head of the entry list for this node:

		node->m_entries->m_prev = entry;
		node->m_entries			= entry;

		// Return the entry

		return entry;
	}
	else
	{
		// No entry list: alloc the the first element

		if ( entry == 0 ) entry = AllocEntry();

		// This should never be the case:

		ENSURE( entry->IsAlloced() == true , "Entry should be marked as being alloced!!");

		// Fill it in:

		entry->m_parent	= node;
		entry->m_object = object;
		entry->m_next	= 0;
		entry->m_prev	= 0;

		// Set the entries on the node:

		node->m_entries = entry;

		// Return the entry

		return entry;
	}
}

//=====================================================================================================================
/// @brief		Removes a given quad tree entry from the tree and automatically deletes
///				all empty nodes that are left in the tree.
/// @pre		Given entry cannot be null
/// @pre		Given entry must be part of a quad tree node
/// @pre		The given entry must belong to this quad tree
/// @pre		The node the entry is attached to must have a parent
//=====================================================================================================================

void QuadTree::RemoveObject( QuadTreeEntry * entry )
{
	// Make sure ok:

	ENSURE( entry							, "Given entry cannot be null"						);
	ENSURE( entry->m_parent					, "Given entry must be part of a quad tree node"	);
	ENSURE( entry->m_parent->m_tree == this	, "The given entry must belong to this quad tree"	);

	// Save the node the object is attached to:

	QuadTreeNode * node = entry->m_parent;
	
	// Make sure ok:
	
	ENSURE( entry->m_parent->m_parent != 0 , "The node the entry is attached to must have a parent" );

	// See if there is an object after this:

	if ( entry->m_next )
	{	
		// There is an object after this: therefore not the only node in the list

		entry->m_next->m_prev = entry->m_prev;

		// If this this the start of the list then we need to assign the new start:

		if ( entry->m_prev )
		{
			// Have an object before this

			entry->m_prev->m_next = entry->m_next;
		}
		else
		{
			// No object before this: make the next object the new start of the list

			node->m_entries = entry->m_next;
		}
	}
	else
	{
		// No object after this: see if there is one before us

		if ( entry->m_prev == 0 )
		{
			//=========================================================================================================
			// No object before it: only object in the list and it needs to be removed. 
			// Continue removing until we reach the top node in the tree or we find a 
			// parent node with other child nodes.
			//=========================================================================================================

			// Save the parent node:

			QuadTreeNode * parent = node->m_parent;

			// Remove this node from the parent

			NodeQuadrant q = GetQuadrant( node->m_center , node->m_parent->m_center );

			// Do it:

			switch ( q )
			{
				case NQ_NE:	parent->m_node_ne = 0;	break;
				case NQ_NW:	parent->m_node_nw = 0;	break;
				case NQ_SE:	parent->m_node_se = 0;	break;
				case NQ_SW:	parent->m_node_sw = 0;	break;
			}			
			
			// Free the node:		

			m_node_pool->Dealloc(node);
			
			// Clean up the parent node and remove any subdivisions that are not needed:
			
			ConsolidateNode( node->m_parent );
		}
		else
		{
			// There is an object before us. Just set it's next pointer to null.

			entry->m_prev->m_next = 0;
		}
	}

	// Done with this quad tree entry: dealloc:
	
	m_entry_pool->Dealloc(entry);
}

//=====================================================================================================================
/// @brief		After removing a child node from a node, this function sess if there is just one other child node left 
///				and removes unecessary subdivisions.
/// @param		node - node to optimise
/// @pre		The given node should be null
/// @pre		The given node must not be a leaf node
/// @pre		The given node should not have been deallocated from the pool
//=====================================================================================================================

void QuadTree::ConsolidateNode( QuadTreeNode * node )
{
	// Make sure ok:
	
	ENSURE( node , "The given node should be null" );
	
	// Make sure ok:
	
	ENSURE( node->m_entries == 0 , "The given node must not be a leaf node" );
	
	// Make sure ok:
	
	ENSURE( node->IsAlloced() == true , "The given node should not have been deallocated from the pool" );
	
	// If this is the parent node then do nothing:
	
	if ( node->m_parent == 0 ) return;
	
	// Search for a node to remove in the given node:
	
	NodeQuadrant	remove_quad = NQ_NE;
	QuadTreeNode *	remove_node = 0;
	
	// Now see what's left: only optimise if there is one node left
	
	if ( node->m_node_ne )
	{
		// Remove the north east node
	
		remove_node = node->m_node_ne;
	}
	
	if ( node->m_node_nw )
	{
		// If we already found another node then bail: we are done our optimisation
		
		if ( remove_node ) return;
		
		// Remove the north west node
		
		remove_node = node->m_node_nw;
		remove_quad = NQ_NW;	
	}
	
	if ( node->m_node_sw )
	{
		// If we already found another node then bail: we are done our optimisation
		
		if ( remove_node ) return;
		
		// Remove the north south west node
		
		remove_node = node->m_node_sw;
		remove_quad = NQ_SW;	
	}	

	if ( node->m_node_se )
	{
		// If we already found another node then bail: we are done our optimisation
		
		if ( remove_node ) return;
		
		// Remove the south east node
		
		remove_node = node->m_node_se;
		remove_quad = NQ_SE;	
	}	
	
	// See if we found a node to remove:
	
	if ( remove_node )
	{
		// Found a node to remove: do nothing if it has any children though:
		
		if 
		( 
			remove_node->m_node_ne == 0 &&
			remove_node->m_node_nw == 0 &&
			remove_node->m_node_se == 0 &&
			remove_node->m_node_sw == 0
		)
		{
			// The child node has no sub nodes: see if it has one or no entries within it
			
			if ( QuadTreeEntry * entry = remove_node->m_entries )
			{
				// Has entries: make sure there is only 1. Otherwise we need to leave this child node alone
				
				if ( entry->m_next == 0 )
				{
					// Good: make this entry a child of the given node
					
					entry->m_parent = node;
					node->m_entries = entry;
					
					// Remove this sub node of the given node:
					
					switch ( remove_quad )
					{
						case NQ_NE:	node->m_node_ne = 0;	break;
						case NQ_NW:	node->m_node_nw = 0;	break;
						case NQ_SE:	node->m_node_se = 0;	break;
						case NQ_SW:	node->m_node_sw = 0;	break;						
					}
					
					// Dealloc the node
					
					m_node_pool->Dealloc(remove_node);
					
					// Continue this process upwards
					
					ConsolidateNode(node->m_parent);								
				}
			}
			else
			{
				// The node to remove has no entries: remove it
				
				switch ( remove_quad )
				{
					case NQ_NE:	node->m_node_ne = 0;	break;
					case NQ_NW:	node->m_node_nw = 0;	break;
					case NQ_SE:	node->m_node_se = 0;	break;
					case NQ_SW:	node->m_node_sw = 0;	break;
				}
				
				// Dealloc the node:
				
				m_node_pool->Dealloc(remove_node);
				
				// Continue the process upwards
				
				ConsolidateNode(node->m_parent);
			}
		}
	}
	else
	{
		// Found no nodes to remove: remove the given node from it's parent
		
			// Get the parent
			
			QuadTreeNode * parent = node->m_parent;
		
			// Get what quadrant it's in:
			
			NodeQuadrant q = GetQuadrant( node->m_center , parent->m_center );
			
			// Remove from the parent:
			
			switch ( q )
			{
				case NQ_NE: parent->m_node_ne = 0;	break;
				case NQ_NW: parent->m_node_nw = 0;	break;
				case NQ_SE: parent->m_node_se = 0;	break;
				case NQ_SW: parent->m_node_sw = 0;	break;
			}
			
			// Dealloc the node:
			
			m_node_pool->Dealloc(node);
			
		// Consolidate the parent
	
		ConsolidateNode(parent);		
	}
}

//=====================================================================================================================
/// @brief		Updates an entries position in the tree. Call this when the position of the entries object has changed.
/// @param		entry - entry to update
/// @remarks	This is faster than manually using Add / Remove because the function will leave the tree 
///				alone if the entry is still within it's previous node.
/// @pre		The entry must not be null
/// @pre		The entry must belong to a node
/// @pre		The entry's object must not be null
//=====================================================================================================================

void QuadTree::UpdateEntry( QuadTreeEntry * entry )
{
	// Debug checks:

	ENSURE( entry			, "The entry must not be null"				);
	ENSURE( entry->m_parent	, "The entry must belong to a node"			);
	ENSURE( entry->m_object , "The entry's object must not be null"		);

	// Get the position of the object:

	Vec2f pos = entry->m_object->GetPosition();

	// Get the node the entry belongs to

	QuadTreeNode * node = entry->m_parent;

	// Get the positon and size of the parent node:

	Vec2f npos = node->m_center;
	Vec2f nsize = node->m_size;

	// Save if we are within bounds:

	bool in_bounds = true;

	// See if we are within the node still:

	if			( pos.x <  npos.x - nsize.x ){ in_bounds = false; }
	else if		( pos.x >= npos.x + nsize.x ){ in_bounds = false; }
	else if		( pos.y <  npos.y - nsize.y ){ in_bounds = false; }
	else if		( pos.y >= npos.y + nsize.y ){ in_bounds = false; }

	// Right: see if we are NOT within bounds. If we are still then do nothing.

	if ( in_bounds == false )
	{
		// Remove from this node: 
		
		RemoveObject(entry);
		
		// Reallocate the entry
		
		m_entry_pool->Realloc(entry);
		
		// Now insert back into the tree
		
		AddObject(entry->m_object,entry);
	}
}

//=====================================================================================================================
/// @brief		Annouces the type name for this object.
/// @returns	Type name of this object
//=====================================================================================================================

const char * QuadTree::GetTypeName() const
{
	return "QuadTree";
}

#ifdef USE_DEBUG_CONSOLE

//=====================================================================================================================
/// @brief		Renders a visualisation of the quad tree using the given primitives renderer: only used in debug
/// @param		c - Camera to view from
/// @param		p - primitives renderer to draw with
//=====================================================================================================================

void QuadTree::Render( Camera2D * c , PrimitivesRenderer * p )
{
	// Do recursive rendering, starting with the root:

	RenderRecursive(c,p,m_root);
}

//=====================================================================================================================
/// @brief		This recursive function recursively draws the quad tree.
/// @param		c - Camera to view from
/// @param		p - primitives renderer to draw with 
/// @param		node - node to start rendering from
//=====================================================================================================================

void QuadTree::RenderRecursive( Camera2D * c , PrimitivesRenderer * p , QuadTreeNode * node )
{
	// Draw this node:

	p->DrawLine
	( 
		c , 
		node->m_center + Vec2f( -node->m_size.x , +node->m_size.y ) ,
		node->m_center + Vec2f( +node->m_size.x , +node->m_size.y ) ,
		0xffff0000
	);

	p->DrawLine
	( 
		c , 
		node->m_center + Vec2f( +node->m_size.x , +node->m_size.y ) ,
		node->m_center + Vec2f( +node->m_size.x , -node->m_size.y ) ,
		0xffff0000
	);

	p->DrawLine
	( 
		c , 
		node->m_center + Vec2f( +node->m_size.x , -node->m_size.y ) ,
		node->m_center + Vec2f( -node->m_size.x , -node->m_size.y ) ,
		0xffff0000
	);

	p->DrawLine
	( 
		c , 
		node->m_center + Vec2f( -node->m_size.x , -node->m_size.y ) ,
		node->m_center + Vec2f( -node->m_size.x , +node->m_size.y ) ,
		0xffff0000
	);

	// Render child nodes:

	if ( node->m_node_nw ) RenderRecursive( c, p , node->m_node_nw );
	if ( node->m_node_sw ) RenderRecursive( c, p , node->m_node_sw );
	if ( node->m_node_ne ) RenderRecursive( c, p , node->m_node_ne );
	if ( node->m_node_se ) RenderRecursive( c, p , node->m_node_se );
}

#endif	// #ifdef USE_DEBUG_CONSOLE

#ifdef DEBUG

//=====================================================================================================================
/// @brief		Debug only function that validates the tree
//=====================================================================================================================

void QuadTree::ValidateTree()
{
	ENSURE( m_root			,	"The tree must have a root"									);
	ENSURE( m_node_pool		,	"The tree must have a node pool"							);
	ENSURE( m_entry_pool	,	"The tree must have an entry pool"							);
	ENSURE( m_max_depth	> 1 ,	"The tree must have a max depth of at least 2"				);
		
	ENSURE( m_root->m_parent		== 0	, "The root cannot have a parent"				);
	ENSURE( m_root->m_entries		== 0	, "The root cannot entries on it"				);
	ENSURE( m_root->m_size.Length() > 0		, "The root must have a valid size"				);
	ENSURE( m_root->IsAlloced()		== true	, "The root must be allocated from the pool"	);
	ENSURE( m_root->m_tree			== this	, "The root must point to this tree"			);
	
	ENSURE( m_root->m_node_nw != m_root , "The child nodes of a node must not be the node itself" );
	ENSURE( m_root->m_node_ne != m_root , "The child nodes of a node must not be the node itself" );
	ENSURE( m_root->m_node_sw != m_root , "The child nodes of a node must not be the node itself" );
	ENSURE( m_root->m_node_se != m_root , "The child nodes of a node must not be the node itself" );
	
	if ( m_root->m_node_nw ) ValidateTreeRecursive( m_root->m_node_nw );
	if ( m_root->m_node_ne ) ValidateTreeRecursive( m_root->m_node_ne );
	if ( m_root->m_node_sw ) ValidateTreeRecursive( m_root->m_node_sw );
	if ( m_root->m_node_se ) ValidateTreeRecursive( m_root->m_node_se );
	
	// Ensure all freed nodes are marked as freed:
	
	{
		Pool<QuadTreeNode>::Enumerator i = m_node_pool->FreeObjects();
		Pool<QuadTreeNode>::Enumerator e = m_node_pool->ListEnd();
		
		while ( i != e )
		{
			ENSURE( (*i)->IsDealloced() , "All freed nodes should be marked as freed" ); ++i;
		}
	}
	
	// Ensure all used nodes are marked as used:
	
	{
		Pool<QuadTreeNode>::Enumerator i = m_node_pool->UsedObjects();
		Pool<QuadTreeNode>::Enumerator e = m_node_pool->ListEnd();
		
		while ( i != e )
		{
			ENSURE( (*i)->IsAlloced() , "All freed nodes should be marked as used" ); ++i;
		}
	}	
}

//=====================================================================================================================
/// @brief		This validates the tree recursively. This is slow and is only used as a debug function
/// @param		node - node to start from. This cannot be the root.
//=====================================================================================================================

void QuadTree::ValidateTreeRecursive( QuadTreeNode * node )
{
	// The basics

	ENSURE( node->m_parent			!= 0	, "The node must have a parent"			);
	ENSURE( node->IsAlloced()		== true	, "The node must be allocated"			);
	ENSURE( node->m_size.Length()	> 0		, "The root must have a valid size"		);
	ENSURE( node->m_tree			== this	, "The root must point to this tree"	);
	
	ENSURE( node->m_node_nw != node , "The child nodes of a node must not be the node itself" );
	ENSURE( node->m_node_ne != node , "The child nodes of a node must not be the node itself" );
	ENSURE( node->m_node_sw != node , "The child nodes of a node must not be the node itself" );
	ENSURE( node->m_node_se != node , "The child nodes of a node must not be the node itself" );	
	
	// Make sure the parent points to this node
	
	ENSURE
	( 
		node->m_parent->m_node_ne == node ||
		node->m_parent->m_node_nw == node ||
		node->m_parent->m_node_se == node ||
		node->m_parent->m_node_sw == node ,
		"The parent of this node must point to it."
	)
	
	// If the node has child nodes it cannot have an entry list:
	
	if ( node->m_node_ne || node->m_node_nw || node->m_node_se || node->m_node_sw )
	{
		ENSURE( node->m_entries == 0 , "If the node is a non leaf node it cannot have an entry list" );
	}
	
	// The node can't have two entries twice:
	
	if ( node->m_node_ne )
	{
		ENSURE( node->m_node_nw != node->m_node_ne , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_sw != node->m_node_ne , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_se != node->m_node_ne , "The node cannot have two children that are the same" );
	}
	
	if ( node->m_node_nw )
	{
		ENSURE( node->m_node_ne != node->m_node_nw , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_sw != node->m_node_nw , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_se != node->m_node_nw , "The node cannot have two children that are the same" );
	}
	
	if ( node->m_node_se )
	{
		ENSURE( node->m_node_nw != node->m_node_se , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_sw != node->m_node_se , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_ne != node->m_node_se , "The node cannot have two children that are the same" );
	}

	if ( node->m_node_sw )
	{
		ENSURE( node->m_node_nw != node->m_node_sw , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_se != node->m_node_sw , "The node cannot have two children that are the same" );
		ENSURE( node->m_node_ne != node->m_node_sw , "The node cannot have two children that are the same" );
	}
	
	// Make sure positions are ok:
	
	if ( node->m_node_ne )
	{
		ENSURE( node->m_node_ne->m_center.x > node->m_center.x , "The center of the node must be correct relative to it's parent" );
		ENSURE( node->m_node_ne->m_center.y > node->m_center.y , "The center of the node must be correct relative to it's parent"  );
	}
	
	if ( node->m_node_nw )
	{
		ENSURE( node->m_node_nw->m_center.x < node->m_center.x , "The center of the node must be correct relative to it's parent"  );
		ENSURE( node->m_node_nw->m_center.y > node->m_center.y , "The center of the node must be correct relative to it's parent"  );
	}
	
	if ( node->m_node_se )
	{
		ENSURE( node->m_node_se->m_center.x > node->m_center.x , "The center of the node must be correct relative to it's parent"  );
		ENSURE( node->m_node_se->m_center.y < node->m_center.y , "The center of the node must be correct relative to it's parent"  );
	}
	
	if ( node->m_node_sw )
	{
		ENSURE( node->m_node_sw->m_center.x < node->m_center.x , "The center of the node must be correct relative to it's parent"  );
		ENSURE( node->m_node_sw->m_center.y < node->m_center.y , "The center of the node must be correct relative to it's parent"  );
	}			
	
	// Validate the entry list:
	
	if ( node->m_entries )
	{
		// The first shouldn't have a previous pointer
		
		ENSURE( node->m_entries->m_prev == 0 , "The 'prev' field for the fist item in the entry list must be null" );
		
		// Run through the list:
		
		QuadTreeEntry * e = node->m_entries;
		
		// Do it:
		
		while ( e )
		{
			// Make sure this entry points to this node:
			
			ENSURE( e->m_parent == node , "The entry must point to this node" );
			
			// Can't be dealloced
			
			ENSURE( e->IsAlloced() == true , "The entry must be allocated" );
			
			// Can't be null
			
			ENSURE( e->m_object != 0 , "The entry cannot point to a null object" );
			
			// Next entry
			
			e = e->m_next;
		}
	}
	
	// Do sub nodes
	
	if ( node->m_node_nw ) ValidateTreeRecursive( node->m_node_nw );
	if ( node->m_node_ne ) ValidateTreeRecursive( node->m_node_ne );
	if ( node->m_node_sw ) ValidateTreeRecursive( node->m_node_sw );
	if ( node->m_node_se ) ValidateTreeRecursive( node->m_node_se );	
}

#endif	// #ifdef DEBUG