#ifndef BSPTREE_INL
#define BSPTREE_INL

#include "BSPTree.h"
#include "Line.h"

namespace cbk
{
	template< class Type >
	BSPTree<Type>::Division::Division(const Vector& location, const BoundingBox& bounding, const float& scale, const Type& Data, BSPTree* const root, Division* const parent)
	{
		this->Data = new Type(Data);

		this->location = location;
		this->scale = scale;

		Greater = 0;
		Lesser = 0;
		this->parent = parent;
		this->root = root;

		blocksView = false;

		borders = new BoundingBox(bounding);

		plane = 0;
	}

	template< class Type >
	BSPTree<Type>::Division::Division(const Vector& normal, const Vector& position, BSPTree* const root, Division* const parent)
	{
		this->Data = 0;

		Greater = 0;
		Lesser = 0;
		this->parent = parent;
		this->root = root;

		blocksView = true;

		borders = 0;

		plane = new Plane(normal, position);
	}

	template< class Type >
	BSPTree<Type>::Division::~Division(void)
	{
		if (Greater != 0)
		{
			root->numNodes--;
			delete Greater;
		}

		if (Lesser != 0)
		{
			root->numNodes--;
			delete Lesser;
		}

		if (plane != 0)
			delete plane;

		if (Data != 0)
			delete Data;

		if (borders != 0)
			delete borders;
	}

	template< class Type >
	void BSPTree<Type>::Division::drawPlane(IDirect3DDevice9* device) const
	{
		if (plane != 0)
			plane->draw(device);
	}

	template< class Type >
	void BSPTree<Type>::Division::drawPlanes(IDirect3DDevice9* device) const
	{
		if (Greater != 0)
			Greater->drawPlanes(device);

		if (Lesser != 0)
			Lesser->drawPlanes(device);

		drawPlane(device);
	}

	template< class Type >
	Type BSPTree<Type>::Division::getData(void) const
	{
		return *Data;
	}

	template< class Type >
	typename BSPTree<Type>::Division* BSPTree<Type>::Division::getNode(const Vector& p) const
	{
		Plane::Direction dir = plane.pointInFront(p);

		if (dir == DIR_Front)
			return Greater;
		else if (dir == DIR_Behind)
			return Lesser;
		else
			return this;
	}

	template< class Type >
	Type* BSPTree<Type>::Division::getData(const Vector& p) const
	{
		Plane::Direction dir = plane.pointInFront(p);

		if (dir == DIR_Front)
		{
			if (Greater != 0)
				return Greater->getData(p);
			else
				return 0;
		}
		else if (dir == DIR_Behind)
		{
			if (Lesser != 0)
				return Lesser->getData(p);
			else
				return 0;
		}
		else
			return &Data;
	}

	/*
	Recursively searches though the BSP tree and lists all contained objects within the specified volume.
	Returns the number of objects found.
	If out is not null, out will be a full list of all found objects.
	volume is the volume in which all found objects must occur.
	eyePos is the position of the camera, used for occluders.
	*/
	template< class Type >
	int BSPTree<Type>::Division::Search(std::list<const Division*>* out, const Frustum& volume, const Vector& eyePos) const
	{
		//Is this a division or a content?
		if (plane != 0)
		{
			bool checkGreater, checkLesser;
			int found = 0;

			//Does this block the view (occluder)
			if (!blocksView)
			{
				//Determine the relationship between the volume and this plane
				Frustum::Direction t = volume.isInside(*plane);

				//The plane divides the volume, check both
				if (t == Frustum::DIR_Inside)
				{
					checkGreater = true;
					checkLesser = true;
				}
				//The plane is on one side of the volume...check only that side
				else if (t == Frustum::DIR_Behind)
				{
					checkGreater = false;
					checkLesser = true;
				}
				else if (t == Frustum::DIR_Front)
				{
					checkGreater = true;
					checkLesser = false;
				}
			}
			else
			{
				//Determine the relationship between the plane and this camera position
				Plane::Direction t = plane->pointInFront(eyePos);

				//The eye is on the plane
				if (t == Plane::DIR_Equal)
				{
					checkGreater = true;
					checkLesser = true;
				}

				//The eye is on one side of the volume...check only that side
				else if (t == Plane::DIR_Behind)
				{
					checkGreater = false;
					checkLesser = true;
				}
				else if (t == Plane::DIR_Front)
				{
					checkGreater = true;
					checkLesser = false;
				}
			}

			//Recursively check the greater side
			if (checkGreater)
				if (Greater != 0)
					found += Greater->Search(out, volume, eyePos);

			//Recursively check the lesser side
			if (checkLesser)
				if (Lesser != 0)
					found += Lesser->Search(out, volume, eyePos);

			return found;
		}
		//This division contains a single object
		else if (borders != 0)
		{
			//Check to see if the object is at least partially inside the volume
			if (volume.isInside(*borders, location, scale))
			{
				//The object
				out->push_back(this);
				return 1;
			}
		}

		//This division is empty or the contained object is not inside the volume
		return 0;
	}

	template< class Type >
	typename BSPTree<Type>::Division* BSPTree<Type>::Division::Delete(const Vector& location, Type* value = 0)
	{
		const Vector& center = (borders.getCenter() * scale) + location;

		if (plane != 0)
		{
			const Plane::Direction dir = plane.pointInFront(center);

			if (dir == Plane::DIR_Front)
			{
				if (Greater != 0)
				{
					Division* del = Greater->Delete(location, value);
					if (del != 0)
					{
						delete del;
						root->numNodes--;
					}
				}
			}
			else if (dir == Plane::DIR_Behind)
			{
				if (Lesser != 0)
				{
					Division* del = Lesser->Delete(location, value);
					if (del != 0)
					{
						delete del;
						root->numNodes--;
					}
				}
			}
		}
		else if (borders.collides(location - this->location, scale))
		{
			if (value != 0)
				*value = Data;

			if (parent != 0)
			{
				if (parent->Greater == this)
					parent->Greater = 0;
				else if (parent->Lesser == this)
					parent->Lesser = 0;

				if (Greater != 0)
				{
					parent->Insert(Greater);
					Greater = 0;
				}
				if (Lesser != 0)
				{
					parent->Insert(Lesser);
					Lesser = 0;
				}
			}
			else
			{
				root->root = 0;

				if (Greater != 0)
				{
					root->Insert(Greater);
					Greater = 0;
				}
				if (Lesser != 0)
				{
					root->Insert(Lesser);
					Lesser = 0;
				}
			}

			return this;
		}

		return 0;
	}

	template< class Type >
	typename BSPTree<Type>::Division* BSPTree<Type>::Division::Insert(Division* node)
	{
		const Vector& center = (borders->getCenter() * scale) + location;
		const Plane::Direction dir = plane->pointInFront(center);

		if (dir == Plane::DIR_Front)
		{
			if (Greater == 0)
			{
				node->parent = this;
				return (Greater = node);
			}
			else
				return Greater->Insert(node);
		}
		else if (dir == Plane::DIR_Behind)
		{
			if (Lesser == 0)
			{
				node->parent = this;
				return (Lesser = node);
			}
			else
				return Lesser->Insert(node);
		}

		return 0;
	}

	template< class Type >
	typename BSPTree<Type>::Division* BSPTree<Type>::Division::Insert(const Vector& normal, const Vector& position)
	{
		if (plane != 0)
		{
			if (blocksView)
			{
				const Plane::Direction dir = plane->pointInFront(position);

				if (dir == Plane::DIR_Front)
				{
					if (Greater == 0)
					{
						Greater = new Division(normal, position, root, this);
						root->numNodes++;
						return Greater;
					}
					else
						return Greater->Insert(normal, position);
				}
				else if (dir == Plane::DIR_Behind)
				{
					if (Lesser == 0)
					{
						Lesser = new Division(normal, position, root, this);
						root->numNodes++;
						return Lesser;
					}
					else
						return Lesser->Insert(normal, position);
				}
			}
			else
			{
				if (parent != 0)
				{
					if (parent->Lesser == this)
						parent->Lesser = 0;
					if (parent->Greater == this)
						parent->Greater = 0;
				}
				Division* t = root->Insert(normal, position);
				t->Insert(this);
			}
		}
		else
		{
			plane = new Plane(normal, position);

			Insert(*Data, this->location, *borders, this->scale);

			delete Data;
			Data = 0;

			delete borders;
			borders = 0;

			root->numNodes--;
		}

		return 0;
	}

	template< class Type >
	typename BSPTree<Type>::Division* BSPTree<Type>::Division::Insert(const Type& value, const Vector& location, const BoundingBox& bounding, const float& scale)
	{
		const Vector& center = (bounding.getCenter() * scale) + location;

		if (plane != 0)
		{
			const Plane::Direction dir = plane->pointInFront(center);

			if (dir == Plane::DIR_Front)
			{
				if (Greater == 0)
				{
					Greater = new Division(location, bounding, scale, value, root, this);
					root->numNodes++;
					return Greater;
				}
				else
					return Greater->Insert(value, location, bounding, scale);
			}
			else if (dir == Plane::DIR_Behind)
			{
				if (Lesser == 0)
				{
					Lesser = new Division(location, bounding, scale, value, root, this);
					root->numNodes++;
					return Lesser;
				}
				else
					return Lesser->Insert(value, location, bounding, scale);
			}
		}
		else
		{
			const Vector& n = location - this->location;
			const Vector& p = (location + this->location) / 2.0f;

			plane = new Plane(n, p);

			Insert(*Data, this->location, *borders, this->scale);
			Insert(value, location, bounding, scale);

			delete Data;
			Data = 0;

			delete borders;
			borders = 0;

			root->numNodes--;
		}

		return 0;
	}

	template< class Type >
	int BSPTree<Type>::Search(std::list<const Division*>* out, const Frustum& volume, const Vector& eyePos) const
	{
		if (root != 0)
			return root->Search(out, volume, eyePos);
		else
			return 0;
	}

	template< class Type >
	typename BSPTree<Type>::Division* BSPTree<Type>::Insert(const Type& value, const Vector& location, const BoundingBox& bounding, const float& scale)
	{
		if (root != 0)
			return root->Insert(value, location, bounding, scale);
		else
		{
			root = new Division(location, bounding, scale, value, this, 0);
			numNodes = 1;
			return root;
		}
	}

	template< class Type >
	void BSPTree<Type>::Insert(Division* node)
	{
		if (root != 0)
			root->Insert(node);
		else
		{
			node->parent = 0;
			root = node;
		}
	}
	
	template< class Type >
	typename BSPTree<Type>::Division* BSPTree<Type>::Insert(const Vector& normal, const Vector& position)
	{
		if (root != 0)
			return root->Insert(normal, position);
		else
			return root = new Division(normal, position, this, 0);
	}

	template< class Type >
	BSPTree<Type>& BSPTree<Type>::Delete(const Vector& location, Type* value = 0)
	{
		if (root != 0)
		{
			Division* del = root->Delete(location, value);
			if (del != 0)
			{
				numNodes--;
				delete del;
			}
		}

		return *this;
	}

	template< class Type >
	void BSPTree<Type>::drawPlanes(IDirect3DDevice9* device) const
	{
		if (root != 0)
			root->drawPlanes(device);
	}

	template< class Type >
	BSPTree<Type>& BSPTree<Type>::Clear(void)
	{
		if (root != 0)
		{
			numNodes = 0;
			root = 0;
			delete root;
		}

		return *this;
	}

	template< class Type >
	BSPTree<Type>::BSPTree(void)
	{
		root = 0;
		numNodes = 0;
	}
}

#endif //BSPTREE_INL