//Copyright (C) 2007 SiegeLord
//See ReadMe.txt and License.txt for copying information

#include "quadtree.h"

//we can set this somewhere and then use it in files that can't get to where it is created
SQuadNode* g_qnRootNode = 0;

unsigned int g_nQuadTreeObsPerNode = 3;

//recursively subdivides a node into many nodes, only does so if there are more than a certain number of objects
//in the node already
//note, it removes the objects from the passed list as it goes... make sure it isn't the main list! :-P
//naturally, you can't use this to subdivide the node's own objects...
//first pointer is restricted
void SubdivideQuadNode(SQuadNode* restrict node, list<SCollidableObject*> *objects)
{
	//if we have objects we first just loop through the objects and see if we can add them to this node
	if(objects)
	{
		list<SCollidableObject*>::iterator it = objects->begin();
		while(it != objects->end())
		{
			if(node->extents.InsideTest((*it)->global_bbox))
			{
				(*it)->quad_node = node;
				node->objects.push_back(*it);

				it = objects->erase(it);
			}
			else
				it++;
		}
	}

	//now we check if this node is overpopulated or not
	//if it is, we subdivide it into smaller nodes
	if(node->objects.size() > g_nQuadTreeObsPerNode)
	{
		//create the children if we don't have them
		if(!node->children)
		{
			//first we make 4 new nodes
			node->children = new SQuadNode[4];

			node->children[0].parent = node;
			node->children[1].parent = node;
			node->children[2].parent = node;
			node->children[3].parent = node;

			const float mid_x = (node->extents.Max.x + node->extents.Min.x) / 2.0f;
			const float mid_y = (node->extents.Max.y + node->extents.Min.y) / 2.0f;

			// +---+---+
			// | 0 | 1 |
			// +---+---+
			// | 2 | 3 |
			// +---+---+

			node->children[0].extents.Min.x = node->extents.Min.x;
			node->children[0].extents.Min.y = node->extents.Min.y;
			node->children[0].extents.Max.x = mid_x;
			node->children[0].extents.Max.y = mid_y;

			node->children[1].extents.Min.x = mid_x;
			node->children[1].extents.Min.y = node->extents.Min.y;
			node->children[1].extents.Max.x = node->extents.Max.x;
			node->children[1].extents.Max.y = mid_y;

			node->children[2].extents.Min.x = node->extents.Min.x;
			node->children[2].extents.Min.y = mid_y;
			node->children[2].extents.Max.x = mid_x;
			node->children[2].extents.Max.y = node->extents.Max.y;

			node->children[3].extents.Min.x = mid_x;
			node->children[3].extents.Min.y = mid_y;
			node->children[3].extents.Max.x = node->extents.Max.x;
			node->children[3].extents.Max.y = node->extents.Max.y;
		}
	}
	if(node->children)
	{
		//now, subdivide the objects already in this node amongst the children
		SubdivideQuadNode(&node->children[0], &node->objects);
		SubdivideQuadNode(&node->children[1], &node->objects);
		SubdivideQuadNode(&node->children[2], &node->objects);
		SubdivideQuadNode(&node->children[3], &node->objects);
	}
}

void DestroyQuadNode(SQuadNode* node)
{
	if(node->children)
	{
		DestroyQuadNode(&node->children[0]);
		DestroyQuadNode(&node->children[1]);
		DestroyQuadNode(&node->children[2]);
		DestroyQuadNode(&node->children[3]);
	}
	//delete node;
}

bool PruneNode(SQuadNode* node)
{
	bool empty = true;
	if(node->children)
	{
		empty &= PruneNode(&node->children[0]);
		empty &= PruneNode(&node->children[1]);
		empty &= PruneNode(&node->children[2]);
		empty &= PruneNode(&node->children[3]);
		if(empty)//delete its children
		{
			DestroyQuadNode(&node->children[0]);
			DestroyQuadNode(&node->children[1]);
			DestroyQuadNode(&node->children[2]);
			DestroyQuadNode(&node->children[3]);
			delete[] node->children;
			node->children = 0;
		}
	}
	//now, we may have some objects of our own... we report that in in case we are a child ourselves
	empty &= node->objects.size() == 0;
	return empty;
}

//this checks to see if the object if is in its node... if not we just add it to the parent of the node it was in...
//rince and repeat
//there is a step afterwards that makes sure that all objects are inside the node
//first - signifies that this is the original node we are checking
void UpdateQuadTree(SCollidableObject* object, bool first)
{
	if(!object->quad_node->extents.InsideTest(object->global_bbox))
	{
		//remove it from the node, if it is there
		if(first)//only the first has it
		{
			RemoveObjectFromQuadNode(object);
		}

		//add it to the parent
		object->quad_node = object->quad_node->parent;

		UpdateQuadTree(object, false);
	}
	else
	{
		//actually add the object to the node's object list
		if(!first)//we do not add it to the first since it is already there!
		{
			object->quad_node->objects.push_back(object);
		}
	}
}

void DrawQuadNode(SQuadNode* node)
{
	DrawRect(node->extents.Min.x, node->extents.Min.y, node->extents.Max.x, node->extents.Max.y, -10, 0xffffc0e1);
	if(node->children)
	{
		DrawQuadNode(&node->children[0]);
		DrawQuadNode(&node->children[1]);
		DrawQuadNode(&node->children[2]);
		DrawQuadNode(&node->children[3]);
	}
}

void AddObjectToQuadNode(SQuadNode* node, SCollidableObject* object)
{
	node->objects.push_back(object);
	object->quad_node = node;
}

SCollidableObject* QuadTreePointTest(SQuadNode* node, vector2d& point)
{
	for(list<SCollidableObject*>::iterator it = node->objects.begin(); it != node->objects.end(); it++)
	{
		if((*it)->global_bbox.PointTest(point))
		{
			return *it;
		}
	}
	if(node->children)
	{
		vector2d mid;
		mid = (node->extents.Max + node->extents.Min) / 2;
		//figure THAT out!
		int idx = (point.x > mid.x ? 1 : 0) + (point.y > mid.y ? 2 : 0);

		return QuadTreePointTest(&node->children[idx], point);
	}
	return 0;
}


bool QuadTreePointTestMulti(SQuadNode* node, vector2d& point, list<SCollidableObject*> *ret)
{
	for(list<SCollidableObject*>::iterator it = node->objects.begin(); it != node->objects.end(); it++)
	{
		if((*it)->global_bbox.PointTest(point))
		{
			ret->push_back(*it);
		}
	}
	if(node->children)
	{
		vector2d mid;
		mid = (node->extents.Max + node->extents.Min) / 2;
		//figure THAT out!
		int idx = (point.x > mid.x ? 1 : 0) + (point.y > mid.y ? 2 : 0);

		QuadTreePointTestMulti(&node->children[idx], point, ret);
	}
	return ret->size() > 0;
}

bool QuadTreeCircleTestMulti(SQuadNode* node, vector2d& point, float rad, list<SCollidableObject*> *ret)
{
	SRect rect(point.x - rad, point.y - rad, point.x + rad, point.y + rad);
	if(!node->extents.IntersectTest(rect))
		return false;

	float rad_sqr = rad * rad;

	for(list<SCollidableObject*>::iterator it = node->objects.begin(); it != node->objects.end(); it++)
	{
		if((*it)->global_bbox.IntersectTest(rect))
		{
			//now we actually test to see if it is in a circle
			if(vector2d((*it)->GetGlobalPosition(), point).GetLengthSQ() < rad_sqr)
				ret->push_back(*it);
		}
	}
	if(node->children)
	{
		if(node->children[0].extents.IntersectTest(rect))
			QuadTreeCircleTestMulti(&node->children[0], point, rad, ret);
		if(node->children[1].extents.IntersectTest(rect))
			QuadTreeCircleTestMulti(&node->children[1], point, rad, ret);
		if(node->children[2].extents.IntersectTest(rect))
			QuadTreeCircleTestMulti(&node->children[2], point, rad, ret);
		if(node->children[3].extents.IntersectTest(rect))
			QuadTreeCircleTestMulti(&node->children[3], point, rad, ret);
	}
	return ret->size() > 0;
}

void RemoveObjectFromQuadNode(SCollidableObject* object)
{
	list<SCollidableObject*>::iterator it = object->quad_node->objects.begin();
	while(it != object->quad_node->objects.end())
	{
		if(object == *it)
		{
			 object->quad_node->objects.erase(it);
			 break;
		}
		else
			it++;
	}
}
