#include "Quadtree.h"
#include "GameObject.h"

Quadtree::Quadtree() :
left( 0 ),
right( 0 ),
top( 0 ),
down( 0 ),
numObjectsToGrow( 4 ),
nodes( 0 ),
isLeaf( true )
{
}

Quadtree::Quadtree( double _left, double _right, double _top, double _down, unsigned int _numObjectsToGrow ) :
left( _left ),
right( _right ),
top( _top ),
down( _down ),
numObjectsToGrow( _numObjectsToGrow ),
nodes( 0 ),
isLeaf( true )
{
}

Quadtree::~Quadtree()
{
	if ( !isLeaf )
		delete [] nodes;
}

void Quadtree::AddObject( GameObject *object )
{
	if ( isLeaf ) {
		objects.push_back( object );
		bool reachedMaxObjects = ( objects.size() == numObjectsToGrow );
		if ( reachedMaxObjects ) {
			createLeaves();
			moveObjectsToLeaves();
			isLeaf = false;
		}
		return;
	}

	for ( int n = 0; n < NodeCount; ++n ) {
		if ( nodes[n].contains( object ) ) {
			nodes[n].AddObject( object );
			return;
		}
	}

	objects.push_back( object );
}

void Quadtree::Clear()
{
	objects.clear();

	if ( !isLeaf ) {
		for ( int n = 0; n < NodeCount; ++n ) {
			nodes[n].Clear();
		}
	}
}

vector<GameObject*> Quadtree::GetObjectsAt( double x, double y )
{
	if ( isLeaf ) {
		return objects;
	}

	vector<GameObject*> returnedObjects;
	vector<GameObject*> childObjects;

	if ( !objects.empty() )
		returnedObjects.insert( returnedObjects.end(), objects.begin(), objects.end() );

	for ( int n = 0; n < NodeCount; ++n ) {
		if ( nodes[n].contains( x, y ) ) {
			childObjects = nodes[n].GetObjectsAt( x, y );
			returnedObjects.insert( returnedObjects.end(), childObjects.begin(), childObjects.end() );
			break;
		}
	}
	
	return returnedObjects;
}

bool Quadtree::contains( GameObject *object )
{
	return 	object->GetX() > left &&
		object->GetX() < right &&
		object->GetY() > top &&
		object->GetY() < down;
}

bool Quadtree::contains( double x, double y )
{
	return 	( x >= left && x <= right ) &&
		( y >= top && y <= down );
}

void Quadtree::createLeaves()
{
	nodes = new Quadtree[4];
	nodes[NW] = Quadtree( left, (left+right)/2, top, (top+down)/2, numObjectsToGrow );
	nodes[NE] = Quadtree( (left+right)/2, right, top, (top+down)/2, numObjectsToGrow );
	nodes[SW] = Quadtree( left, (left+right)/2, (top+down)/2, down, numObjectsToGrow );
	nodes[SE] = Quadtree( (left+right)/2, right, (top+down)/2, down, numObjectsToGrow );
	
		
}

void Quadtree::moveObjectsToLeaves()
{
	for ( int n = 0; n < NodeCount; ++n ) {
		for ( unsigned int m = 0; m < objects.size(); ++m ) {
			if ( nodes[n].contains( objects[m] ) ) {
				nodes[n].AddObject( objects[m] );
				objects.erase( objects.begin() + m );
				--m;
			}
		}
	}
}

void Quadtree::draw()
{
	for(int nn = 0; nn < NodeCount; nn++)
	{		
		al_draw_line(nodes[nn].left, nodes[nn].top, nodes[nn].left, nodes[nn].down, al_map_rgb(255,255,255), 2);
		al_draw_line(nodes[nn].left, nodes[nn].down, nodes[nn].right, nodes[nn].down, al_map_rgb(255,255,255), 2);
		al_draw_line(nodes[nn].right, nodes[nn].down, nodes[nn].right, nodes[nn].top, al_map_rgb(255,255,255), 2);
		al_draw_line(nodes[nn].right, nodes[nn].top, nodes[nn].left, nodes[nn].top, al_map_rgb(255,255,255), 2);
		
		if(!nodes[nn].isLeaf)
		{
			for ( int n = 0; n < NodeCount; ++n )
			{				
				al_draw_line(nodes[nn].nodes[n].left, nodes[nn].nodes[n].top, nodes[nn].nodes[n].left, nodes[nn].nodes[n].down, al_map_rgb(255,255,255), 2);
				al_draw_line(nodes[nn].nodes[n].left, nodes[nn].nodes[n].down, nodes[nn].nodes[n].right, nodes[nn].nodes[n].down, al_map_rgb(255,255,255), 2);
				al_draw_line(nodes[nn].nodes[n].right, nodes[nn].nodes[n].down, nodes[nn].nodes[n].right, nodes[nn].nodes[n].top, al_map_rgb(255,255,255), 2);
				al_draw_line(nodes[nn].nodes[n].right, nodes[nn].nodes[n].top, nodes[nn].nodes[n].left, nodes[nn].nodes[n].top, al_map_rgb(255,255,255), 2);
				
				if(!nodes[nn].nodes[n].isLeaf)
				{
					for ( int u = 0; u < NodeCount; ++u )
					{
						al_draw_line(nodes[nn].nodes[n].nodes[u].left, nodes[nn].nodes[n].nodes[u].top, nodes[nn].nodes[n].nodes[u].left, nodes[nn].nodes[n].nodes[u].down, al_map_rgb(255,255,255), 2);
						al_draw_line(nodes[nn].nodes[n].nodes[u].left, nodes[nn].nodes[n].nodes[u].down, nodes[nn].nodes[n].nodes[u].right, nodes[nn].nodes[n].nodes[u].down, al_map_rgb(255,255,255), 2);
						al_draw_line(nodes[nn].nodes[n].nodes[u].right, nodes[nn].nodes[n].nodes[u].down, nodes[nn].nodes[n].nodes[u].right, nodes[nn].nodes[n].nodes[u].top, al_map_rgb(255,255,255), 2);
						al_draw_line(nodes[nn].nodes[n].nodes[u].right, nodes[nn].nodes[n].nodes[u].top, nodes[nn].nodes[n].nodes[u].left, nodes[nn].nodes[n].nodes[u].top, al_map_rgb(255,255,255), 2);
					
						if(!nodes[nn].nodes[n].nodes[u].isLeaf)
						{
							for ( int f = 0; f < NodeCount; ++f )
							{
								al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].left, nodes[nn].nodes[n].nodes[u].nodes[f].top, nodes[nn].nodes[n].nodes[u].nodes[f].left, nodes[nn].nodes[n].nodes[u].nodes[f].down, al_map_rgb(255,255,255), 2);
								al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].left, nodes[nn].nodes[n].nodes[u].nodes[f].down, nodes[nn].nodes[n].nodes[u].nodes[f].right, nodes[nn].nodes[n].nodes[u].nodes[f].down, al_map_rgb(255,255,255), 2);
								al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].right, nodes[nn].nodes[n].nodes[u].nodes[f].down, nodes[nn].nodes[n].nodes[u].nodes[f].right, nodes[nn].nodes[n].nodes[u].nodes[f].top, al_map_rgb(255,255,255), 2);
								al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].right, nodes[nn].nodes[n].nodes[u].nodes[f].top, nodes[nn].nodes[n].nodes[u].nodes[f].left, nodes[nn].nodes[n].nodes[u].nodes[f].top, al_map_rgb(255,255,255), 2);
							
								if(!nodes[nn].nodes[n].nodes[u].nodes[f].isLeaf)
								{
									for ( int g = 0; g < NodeCount; ++g )
									{
										al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].left, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].top, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].left, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].down, al_map_rgb(255,255,255), 2);
										al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].left, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].down, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].right, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].down, al_map_rgb(255,255,255), 2);
										al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].right, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].down, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].right, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].top, al_map_rgb(255,255,255), 2);
										al_draw_line(nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].right, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].top, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].left, nodes[nn].nodes[n].nodes[u].nodes[f].nodes[g].top, al_map_rgb(255,255,255), 2);
									}
						}
							
							}
						}
					}
				}
			}

		}
	}
	
};

double Quadtree::returnRect(int i)
{
	switch (i)
	{
	case 0:
		return left;
		break;
	case 1:
		return top;
		break;
	case 2:
		return right;
		break;
	case 3:
		return down;
		break;
	default:
		break;
	}
	return 0;
};
