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

#pragma once

#include "neonz.h"
#include "objectex.h"

struct SQuadNode;

extern SQuadNode* g_qnRootNode;

//this object can interface with the quad tree
struct SCollidableObject : SObjectEx
{
	//the node the object is supposed to be in
	SQuadNode* quad_node;
	//the bounding rectangle of the object local coords
	SRect bbox;
	//the bounding rectangle of the object in global coords
	SRect global_bbox;
	void UpdateBBox()
	{
		vector2d offset = GetGlobalPosition();
		global_bbox.Max = bbox.Max + offset;
		global_bbox.Min = bbox.Min + offset;
	}
};

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

struct SQuadNode
{
	SRect extents;
	SQuadNode* parent;
	SQuadNode* children;

	list<SCollidableObject*> objects;

	SQuadNode()
	{
		parent = 0;
		children = 0;
	}
};

//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 = 0);

//destroy the quad tree node and all of its children
void DestroyQuadNode(SQuadNode* node);

//tests if the quad node is empty and deletes it's children if it is
//recursive
bool PruneNode(SQuadNode* node);

//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
//note that we do NOT remove it from the node!
//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 = true);

//removes the object from the node that it is in
void RemoveObjectFromQuadNode(SCollidableObject* object);

//just a convenience function, adds the object to a node and sets all the appropriate things
void AddObjectToQuadNode(SQuadNode* node, SCollidableObject* object);

//Draws the quad tree network recursively
void DrawQuadNode(SQuadNode* node);

//finds any objects that intersect a point within the quadtree node
//It won't find anything if you put the point outside the node... don't do that please
//Note that it returns a maximum of one objects... use other functions if you want them all
SCollidableObject* QuadTreePointTest(SQuadNode* node, vector2d& point);

//finds any objects that intersect a point within the quadtree node
//It won't find anything if you put the point outside the node... don't do that please
bool QuadTreePointTestMulti(SQuadNode* node, vector2d& point, list<SCollidableObject*> *ret);

//finds any objects that intersect a circle within the quadtree node
//It won't find anything if you put the point outside the node... don't do that please
bool QuadTreeCircleTestMulti(SQuadNode* node, vector2d& point, float rad, list<SCollidableObject*> *ret);

//Here is how this all works
//First, at the beginning of the game all we do is add all objects to the root node
//Moreover, whenever we want to add a new object we just add it to the root node
//Now, every step we call the following in this order
//For each object, we call the UpdateQuadTree function - it shuffles arround the objects about the quad tree
//  but, it does mess up the tree by potentially overpopulating it in places
//In any event, we then call SubdivideQuadNode at the end of the step(no more object additions)
//  this will rebalance all the nodes again
//Now we also call PruneNode, this does not have to be done every step... is is mostly for memory's sake
//  it may also speed up collision testing. All it does is delete the children of a node if they have nothing in them
//Now, given all that... when can we test for collisions?
//Well... at any time really, but the most efficient time would be after we at PruneNode'd the root node
