#include "Quadtree.h"
#include "GameObject.h"
#include "DarkGDK.h"
#include <list>
#include <algorithm>



//const int QuadTree::tilesize;
QTNode::QTNode( QTNODE_TYPE type, Rect boundary, QTNode* parent )
{
	for( int i = 0; i<4; ++i )
		this->child[i] = NULL;

	this->boundary = boundary;
	this->type = type;
	this->parent = parent;
}	// end Konstructor



QTNode::~QTNode()
{
	objects.clear();
}	// end Destructor



void QTNode::AddChild(QTNode *child)
{
	for( int i = 0; i<4; i++ )
		if( this->child[i] == NULL )
		{
			this->child[i] = child;
			break;
		}
}	// end AddChild



void QTNode::AddObject(GameObject* obj)
{
	objects.push_back( obj );
}	// end AddObject



void QTNode::RemoveObject(GameObject* obj)
{
	for( std::vector<GameObject*>::iterator it = objects.begin(); it != objects.end(); ++it )
	{
		if( (*it) == obj )
		{
			objects.erase(it);
			break;
		}
	}
}	// end RemoveObject



bool QTNode::ObjectExist(GameObject* obj)
{
	for( std::vector<GameObject*>::iterator it = objects.begin(); it != objects.end(); ++it )
	{
		if( (*it) == obj )
			return true;
	}
	return false;
}	// end ObjectExist



// checks if a gameobject collides with the node
bool QTNode::ObjectCollision(GameObject* obj)
{
	if( obj )
		return boundary.IntersectsWithRect( obj->GetBoundary() );
	return false;
}	// end UnitCollision





// ###############################################################
// ################# QUAD TREE METHODS GO BELOW ##################
// ###############################################################

QTNode* QuadTree::CreateNode( Rect boundary, QTNode* parent )
{
	if( boundary.botright_x - boundary.topleft_x > tilesize )
		return new QTNode( QTNODE_TYPE_PARENT, boundary, parent );
	return new QTNode( QTNODE_TYPE_LEAF, boundary, parent );
}	// end CreateNode




QuadTree::QuadTree(int sizex, int sizey)
{
	//				tlx,	tly,	brx,			bry
	Rect boundary(	0,		0,		sizex*tilesize,	sizey*tilesize );
	std::list<QTNode*> nodes;

	root = CreateNode( boundary, NULL );
	nodes.push_back(root);
	for( std::list<QTNode*>::iterator it = nodes.begin(); it != nodes.end(); ++it )
	{
		// there are still nodes left which need to be split
		QTNode* n = (*it);
		Rect r = n->boundary;
		Rect boundary1( r.topleft_x,					r.topleft_y,					(r.topleft_x+r.botright_x)/2,	(r.topleft_y+r.botright_y)/2 );
		Rect boundary2( (r.topleft_x+r.botright_x)/2,	r.topleft_y,					r.botright_x,					(r.topleft_y+r.botright_y)/2 );
		Rect boundary3( r.topleft_x,					(r.topleft_y+r.botright_y)/2,	(r.topleft_x+r.botright_x)/2,	r.botright_y   );
		Rect boundary4( (r.topleft_x+r.botright_x)/2,	(r.topleft_y+r.botright_y)/2,	r.botright_x,					r.botright_y   );

		n->AddChild( CreateNode( boundary1, n ) );
		n->AddChild( CreateNode( boundary2, n ) );
		n->AddChild( CreateNode( boundary3, n ) );
		n->AddChild( CreateNode( boundary4, n ) );
		for( int i = 0; i<4; ++i )
		{
			// if child isn't leaf, add it to the nodes vector
			// to split it as well
			QTNode* child = n->child[i];
			if( child && child->type == QTNODE_TYPE_PARENT )
				nodes.push_back( child );
			else
				break;
		}
	}
	//nodes.clear();
}	// end Konstructor



QuadTree::~QuadTree()
{
	std::list<QTNode*> nodes;
	nodes.push_back(root);
	for( std::list<QTNode*>::iterator it = nodes.begin(); it != nodes.end(); it = nodes.erase( it ) )
	{
		QTNode* n = (*it);
		for( int i = 0; i<4; ++i )
		{
			if( n->child[i] != NULL )
				nodes.push_back( n->child[i] );
		}

		delete n;
	}
	//nodes.clear();
}	// end Destructor



// updates the GameObject information inside the tree
// !!the root is never used for any information!!
// checks with which nodes the GameObject collides and stores it in the node's objects vector
// if it has pathing enabled
void QuadTree::UpdateObjectInformation(GameObject* obj)
{
	std::list<QTNode*> nodes;
	nodes.push_back(root);
	for( std::list<QTNode*>::iterator it = nodes.begin(); it != nodes.end(); ++it )
	{
		for( int i=0; i<4; ++i )
		{
			QTNode* child = (*it)->child[i];
			if( child->ObjectCollision( obj ) )
			{
				if( !child->ObjectExist( obj ) )
					child->AddObject( obj );
				
				if( child->type == QTNODE_TYPE_PARENT )
					nodes.push_back( child );
				//else
				//	dbBox( child->boundary.topleft_x, child->boundary.topleft_y, child->boundary.botright_x, child->boundary.botright_y );
			}
			else if( child->ObjectExist( obj ) )
			{
				child->RemoveObject( obj );

				if( child->type == QTNODE_TYPE_PARENT )
					nodes.push_back( child );
			}
		}
	}
	//nodes.clear();
}	// end UpdateUnitInformation



// returns all leaf-nodes in which the unit is stored
/*const std::vector<QTNode*>& QuadTree::GetQTNode(int unitid)
{
	std::list<QTNode*> nodes;
	nodes.push_back(root);
	std::list<QTNode*>::iterator it = nodes.begin();
	std::vector<QTNode*> result;

	while( it != nodes.end() )
	{
		QTNode* n = (*it);

		for( int i=0; i<4; ++i )
		{
			if( n->child[i]->UnitExist(unitid) )
			{
				if( n->child[i]->type == QTNODE_TYPE_PARENT )
					nodes.push_back( n->child[i] );
				else
					result.push_back( n->child[i] );
			}
		}

		it++;
	}
	nodes.clear();
	return result;
}	// end GetQTNode*/



// returns all objects within the radius of the given position
std::vector<GameObject*> QuadTree::GetObjects(float coordx, float coordy, float radius )
{
	std::list<QTNode*> nodes;
	nodes.push_back(root);
	std::vector<GameObject*> result;
	radius *= radius;
	for( std::list<QTNode*>::iterator it = nodes.begin(); it != nodes.end(); ++it )
	{
		for( int i=0; i<4; ++i )
		{
			QTNode* child = (*it)->child[i];
			Rect r = child->boundary;
			bool collides = false;
			if( r.IsPointInside( coordx, coordy ) )
			{
				collides = true;
			}
			else
			{
				const float dx = coordx - r.GetCenterX();
				const float dy = coordy - r.GetCenterY();
				if( dx*dx+dy*dy <= radius )
					collides = true;
			}

			if( collides )
			{
				if( child->type == QTNODE_TYPE_PARENT )
					nodes.push_back( child );
				else
				{
					std::vector<GameObject*> v = child->GetObjects();
					if( !v.empty() )
					{
						for( std::vector<GameObject*>::iterator it = v.begin(); it != v.end(); ++it )
						{
							// add object to the result vector if it isn't in the result vector yet
							if( std::find( result.begin(), result.end(), (*it) ) == result.end() )
								result.push_back( (*it) );
						}
					}
				}
			}
		}
	}
	//nodes.clear();
	return result;
}	// end GetObjects



// removes object completely from the tree
void QuadTree::RemoveObject( GameObject* obj )
{
	std::list<QTNode*> nodes;
	nodes.push_back(root);
	for( std::list<QTNode*>::iterator it = nodes.begin(); it != nodes.end(); ++it )
	{
		for( int i=0; i<4; ++i )
		{
			QTNode* child = (*it)->child[i];
			if( child->ObjectExist( obj ) )
			{
				child->RemoveObject( obj );
				if( child->type == QTNODE_TYPE_PARENT )
					nodes.push_back( child );
			}
		}
	}
	//nodes.clear();
}	// end RemoveObject