/**************************************************
 *
 VGP463 Computer Graphics Programming: Modeling
 Instructor: Laurie Brown Torelli
 Quadtree Class
 *
 **************************************************/
#ifndef OCT_TREE_NODE_H
#define OCT_TREE_NODE_H

#include <stack>
#include <list>
#include <vector>
#include <assert.h>

#include "BoundingBox.h"
#include "Vector.h"

namespace cbk
{
	const unsigned int maxRecursion = 7;

//-----------------------------------------------------------------------------
// quadtree Class
//-----------------------------------------------------------------------------
	template< class Type>
	typename Octree<Type>::Node* Octree<Type>::Node::Delete(const Vector& location, Type* value)
	{
		if (hasData)
		{
			if (borders.collides(location))
			{
				if (value != 0)
					(*value) = data;
				return this;
			}
		}
		else
		{
			Node* t;

			const Vector halfSize = Vector(size.X * 0.5f, size.Y * 0.5f, size.Z * 0.5f);

			const Vector FLTLoc = this->location + (halfSize * Vector( 0.5f,  0.5f,  0.5f));
			const Vector FLBLoc = this->location + (halfSize * Vector( 0.5f,  0.5f, -0.5f));
			const Vector FRTLoc = this->location + (halfSize * Vector( 0.5f, -0.5f,  0.5f));
			const Vector FRBLoc = this->location + (halfSize * Vector( 0.5f, -0.5f, -0.5f));
			const Vector BLTLoc = this->location + (halfSize * Vector(-0.5f,  0.5f,  0.5f));
			const Vector BLBLoc = this->location + (halfSize * Vector(-0.5f,  0.5f, -0.5f));
			const Vector BRTLoc = this->location + (halfSize * Vector(-0.5f, -0.5f,  0.5f));
			const Vector BRBLoc = this->location + (halfSize * Vector(-0.5f, -0.5f, -0.5f));

			if (FLT != 0)
			{
				if (FLT->borders.collides(location))
				{
					t = FLT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FLT = 0;
					}
				}
			}
			if (FLB != 0)
			{
				if (FLB->borders.collides(location))
				{
					t = FLB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FLB = 0;
					}
				}
			}
			if (FRT != 0)
			{
				if (FRT->borders.collides(location))
				{
					t = FRT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FRT = 0;
					}
				}
			}
			if (FRB != 0)
			{
				if (FRB->borders.collides(location))
				{
					t = FRB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FRB = 0;
					}
				}
			}
			if (BLT != 0)
			{
				if (BLT->borders.collides(location))
				{
					t = BLT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BLT = 0;
					}
				}
			}
			if (BLB != 0)
			{
				if (BLB->borders.collides(location))
				{
					t = BLB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BLB = 0;
					}
				}
			}
			if (BRT != 0)
			{
				if (BRT->borders.collides(location))
				{
					t = BRT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BRT = 0;
					}
				}
			}
			if (BRB != 0)
			{
				if (BRB->borders.collides(location))
				{
					t = BRB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BRB = 0;
					}
				}
			}
		}

		return 0;
	}

	template< class Type>
	typename Octree<Type>::Node* Octree<Type>::Node::Delete(Type data)
	{
		if (hasData)
			return this;
		else
		{
			Node* t;
			t = FLT->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				FLT = 0;
			}

			t = FLB->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				FLB = 0;
			}

			t = FRT->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				FRT = 0;
			}

			t = FRB->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				FRB = 0;
			}

			t = BLT->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				BLT = 0;
			}

			t = BLB->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				BLB = 0;
			}

			t = BRT->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				BRT = 0;
			}

			t = BRB->Delete(data);
			if (t != 0)
			{
				root->numNodes--;
				delete t;
				BRB = 0;
			}

			return 0;
		}
	}

	template< class Type>
	typename Octree<Type>::Node* Octree<Type>::Node::Delete(const BoundingBox& location, Type* value)
	{
		if (hasData)
		{
			if (borders.collides(location))
			{
				if (value != 0)
					(*value) = data;
				return this;
			}
		}
		else
		{
			Node* t;

			const Vector halfSize = Vector(size.X * 0.5f, size.Y * 0.5f, size.Z * 0.5f);

			const Vector FLTLoc = this->location + (halfSize * Vector( 0.5f,  0.5f,  0.5f));
			const Vector FLBLoc = this->location + (halfSize * Vector( 0.5f,  0.5f, -0.5f));
			const Vector FRTLoc = this->location + (halfSize * Vector( 0.5f, -0.5f,  0.5f));
			const Vector FRBLoc = this->location + (halfSize * Vector( 0.5f, -0.5f, -0.5f));
			const Vector BLTLoc = this->location + (halfSize * Vector(-0.5f,  0.5f,  0.5f));
			const Vector BLBLoc = this->location + (halfSize * Vector(-0.5f,  0.5f, -0.5f));
			const Vector BRTLoc = this->location + (halfSize * Vector(-0.5f, -0.5f,  0.5f));
			const Vector BRBLoc = this->location + (halfSize * Vector(-0.5f, -0.5f, -0.5f));

			if (FLT != 0)
			{
				if (FLT->borders.collides(location))
				{
					t = FLT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FLT = 0;
					}
				}
			}
			if (FLB != 0)
			{
				if (FLB->borders.collides(location))
				{
					t = FLB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FLB = 0;
					}
				}
			}
			if (FRT != 0)
			{
				if (FRT->borders.collides(location))
				{
					t = FRT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FRT = 0;
					}
				}
			}
			if (FRB != 0)
			{
				if (FRB->borders.collides(location))
				{
					t = FRB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						FRB = 0;
					}
				}
			}
			if (BLT != 0)
			{
				if (BLT->borders.collides(location))
				{
					t = BLT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BLT = 0;
					}
				}
			}
			if (BLB != 0)
			{
				if (BLB->borders.collides(location))
				{
					t = BLB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BLB = 0;
					}
				}
			}
			if (BRT != 0)
			{
				if (BRT->borders.collides(location))
				{
					t = BRT->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BRT = 0;
					}
				}
			}
			if (BRB != 0)
			{
				if (BRB->borders.collides(location))
				{
					t = BRB->Delete(location, value);
					if (t != 0)
					{
						root->numNodes--;
						delete t;
						BRB = 0;
					}
				}
			}
		}

		return 0;
	}

	template< class Type >
	typename Octree<Type>::Node* Octree<Type>::Node::Insert(oNode* node, const Vector& thisLocation, unsigned int recursionLevel, std::vector<const oNode*>* out)
	{
		if (recursionLevel > maxRecursion)
		{
			if (this->node != 0)
				out->push_back(this->node);
			return 0;
		}
			
		if (this->node != 0)
		{
			if (this->node == node)
				return 0;

			Node* t;

			if (parent == 0)
			{
				root->m_root = new Node(root, parent, root->size, Vector());
				t = root->m_root->Insert(this->node, thisLocation, recursionLevel + 1, out);
				if (t != 0)
					delete t;

				t = root->m_root->Insert(node, thisLocation, recursionLevel + 1, out);
				if (t != 0)
					delete t;
			}
			else
			{
				const BoundingBox& pBB = parent->getBorders();
				const Vector& pCenter = pBB.getCenter();
				const Vector& pSize = pBB.getGreater() - pCenter;
				const Vector& sSize = pSize * 0.5f;
				const Vector& sHSize = sSize;

				if (parent->FLT == this)
				{
					parent->FLT = new Node(root, parent, sSize, pCenter + Vector( sHSize.X,  sHSize.Y,  sHSize.Z));

					t = parent->FLT->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->FLT->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
				if (parent->FLB == this)
				{
					parent->FLB = new Node(root, parent, sSize, pCenter + Vector( sHSize.X,  sHSize.Y, -sHSize.Z));

					t = parent->FLB->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->FLB->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
				if (parent->FRT == this)
				{
					parent->FRT = new Node(root, parent, sSize, pCenter + Vector( sHSize.X, -sHSize.Y,  sHSize.Z));

					t = parent->FRT->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->FRT->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
				if (parent->FRB == this)
				{
					parent->FRB = new Node(root, parent, sSize, pCenter + Vector( sHSize.X, -sHSize.Y, -sHSize.Z));

					t = parent->FRB->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->FRB->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
				if (parent->BLT == this)
				{
					parent->BLT = new Node(root, parent, sSize, pCenter + Vector(-sHSize.X,  sHSize.Y,  sHSize.Z));

					t = parent->BLT->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->BLT->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
				if (parent->BLB == this)
				{
					parent->BLB = new Node(root, parent, sSize, pCenter + Vector(-sHSize.X,  sHSize.Y, -sHSize.Z));

					t = parent->BLB->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->BLB->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
				if (parent->BRT == this)
				{
					parent->BRT = new Node(root, parent, sSize, pCenter + Vector(-sHSize.X, -sHSize.Y,  sHSize.Z));

					t = parent->BRT->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->BRT->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
				if (parent->BRB == this)
				{
					parent->BRB = new Node(root, parent, sSize, pCenter + Vector(-sHSize.X, -sHSize.Y, -sHSize.Z));

					t = parent->BRB->Insert(this->node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;

					t = parent->BRB->Insert(node, thisLocation, recursionLevel + 1, out);
					if (t != 0)
						delete t;
				}
			}

			return this;
		}
		else
		{
			const BoundingBox& tBB = getBorders();
			const Vector& tCenter = tBB.getCenter();
			const Vector& tSize = tBB.getGreater() - tCenter;

			const Vector halfSize = tSize * 0.5f;

			const Vector FLTLoc = tCenter + (halfSize * Vector( 0.5f,  0.5f,  0.5f));
			const Vector FLBLoc = tCenter + (halfSize * Vector( 0.5f,  0.5f, -0.5f));
			const Vector FRTLoc = tCenter + (halfSize * Vector( 0.5f, -0.5f,  0.5f));
			const Vector FRBLoc = tCenter + (halfSize * Vector( 0.5f, -0.5f, -0.5f));
			const Vector BLTLoc = tCenter + (halfSize * Vector(-0.5f,  0.5f,  0.5f));
			const Vector BLBLoc = tCenter + (halfSize * Vector(-0.5f,  0.5f, -0.5f));
			const Vector BRTLoc = tCenter + (halfSize * Vector(-0.5f, -0.5f,  0.5f));
			const Vector BRBLoc = tCenter + (halfSize * Vector(-0.5f, -0.5f, -0.5f));

			const Vector& bbMin = node->borders.getLesser();
			const Vector& bbMax = node->borders.getGreater();

			const bool front = bbMax.X > (tCenter.X - root->overlap);
			const bool back = bbMin.X < (tCenter.X + root->overlap);

			const bool left = bbMax.Y > (tCenter.Y - root->overlap);
			const bool right = bbMin.Y < (tCenter.Y + root->overlap);

			const bool top = bbMax.Z > (tCenter.Z - root->overlap);
			const bool bottom = bbMin.Z < (tCenter.Z + root->overlap);

			if (front && left && top)
			{
				if (FLT == 0)
					FLT = new Node(root, this, node);
				else
					FLT->Insert(node, FLTLoc, recursionLevel + 1, out);
			}
			if (front && left && bottom)
			{
				if (FLB == 0)
					FLB = new Node(root, this, node);
				else
					FLB->Insert(node, FLBLoc, recursionLevel + 1, out);
			}
			if (front && right && top)
			{
				if (FRT == 0)
					FRT = new Node(root, this, node);
				else
					FRT->Insert(node, FRTLoc, recursionLevel + 1, out);
			}
			if (front && right && bottom)
			{
				if (FRB == 0)
					FRB = new Node(root, this, node);
				else
					FRB->Insert(node, FRBLoc, recursionLevel + 1, out);
			}
			if (back && left && top)
			{
				if (BLT == 0)
					BLT = new Node(root, this, node);
				else
					BLT->Insert(node, BLTLoc, recursionLevel + 1, out);
			}
			if (back && left && bottom)
			{
				if (BLB == 0)
					BLB = new Node(root, this, node);
				else
					BLB->Insert(node, BLBLoc, recursionLevel + 1, out);
			}
			if (back && right && top)
			{
				if (BRT == 0)
					BRT = new Node(root, this, node);
				else
					BRT->Insert(node, BRTLoc, recursionLevel + 1, out);
			}
			if (back && right && bottom)
			{
				if (BRB == 0)
					BRB = new Node(root, this, node);
				else
					BRB->Insert(node, BRBLoc, recursionLevel + 1, out);
			}

			return 0;
		}
	}
/*
	template< class Type >
	typename Octree<Type>::Node* Octree<Type>::Node::Insert(const Type& value, const Vector& location, const BoundingBox& bounding, const float& scale, const Vector& thisLocation)
	{
		if (hasData)
		{
			Node* tNode = new Node(0, overlap, thisLocation, BoundingBox(-this->size, this->size), 1.0f, this->size * 1.0f, root, parent);
			if (parent == 0)
				root->m_root = tNode;
			else
			{
				if (parent->FLT == this)
					parent->FLT = tNode;
				if (parent->FLB == this)
					parent->FLB = tNode;
				if (parent->FRT == this)
					parent->FRT = tNode;
				if (parent->FRB == this)
					parent->FRB = tNode;
				if (parent->BLT == this)
					parent->BLT = tNode;
				if (parent->BLB == this)
					parent->BLB = tNode;
				if (parent->BRT == this)
					parent->BRT = tNode;
				if (parent->BRB == this)
					parent->BRB = tNode;
			}

			tNode->Insert(this, thisLocation);
		}

		const Vector halfSize = Vector(size.X * 0.5f, size.Y * 0.5f, size.Z * 0.5f);
		const float& midX = this->location.X;
		const float& midY = this->location.Y;
		const float& midZ = this->location.Z;

		const Vector FLTLoc = this->location + (halfSize * Vector( 0.5f,  0.5f,  0.5f));
		const Vector FLBLoc = this->location + (halfSize * Vector( 0.5f,  0.5f, -0.5f));
		const Vector FRTLoc = this->location + (halfSize * Vector( 0.5f, -0.5f,  0.5f));
		const Vector FRBLoc = this->location + (halfSize * Vector( 0.5f, -0.5f, -0.5f));
		const Vector BLTLoc = this->location + (halfSize * Vector(-0.5f,  0.5f,  0.5f));
		const Vector BLBLoc = this->location + (halfSize * Vector(-0.5f,  0.5f, -0.5f));
		const Vector BRTLoc = this->location + (halfSize * Vector(-0.5f, -0.5f,  0.5f));
		const Vector BRBLoc = this->location + (halfSize * Vector(-0.5f, -0.5f, -0.5f));

		const Vector& bbMin = bounding.getLesser();
		const Vector& bbMax = bounding.getGreater();

		const bool front = bbMax.X > (midX - overlap);
		const bool back = bbMin.X < (midX + overlap);

		const bool left = bbMax.Y > (midY - overlap);
		const bool right = bbMin.Y < (midY + overlap);

		const bool top = bbMax.Z > (midZ - overlap);
		const bool bottom = bbMin.Z < (midZ + overlap);

		if (front && left && top)
		{
			if (FLT == 0)
				return FLT = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return FLT->Insert(value, location, bounding, scale, FLTLoc);
		}
		if (front && left && bottom)
		{
			if (FLB == 0)
				return FLB = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return FLB->Insert(value, location, bounding, scale, FLBLoc);
		}
		if (front && right && top)
		{
			if (FRT == 0)
				return FRT = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return FRT->Insert(value, location, bounding, scale, FRTLoc);
		}
		if (front && right && bottom)
		{
			if (FRB == 0)
				return FRB = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return FRB->Insert(value, location, bounding, scale, FRBLoc);
		}
		if (back && left && top)
		{
			if (BLT == 0)
				return BLT = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return BLT->Insert(value, location, bounding, scale, BLTLoc);
		}
		if (back && left && bottom)
		{
			if (BLB == 0)
				return BLB = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return BLB->Insert(value, location, bounding, scale, BLBLoc);
		}
		if (back && right && top)
		{
			if (BRT == 0)
				return BRT = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return BRT->Insert(value, location, bounding, scale, BRTLoc);
		}
		if (back && right && bottom)
		{
			if (BRB == 0)
				return BRB = new Node(&value, overlap, location, bounding, scale, halfSize, root, this);
			else
				return BRB->Insert(value, location, bounding, scale, BRBLoc);
		}

		return 0;
	}
*/
	template< class Type >
	typename Octree<Type>::Node& Octree<Type>::Node::SetData(const Type& value)
	{
		hasData = true;
		data = value;
		return *this;
	}

	template< class Type >
	typename Octree<Type>::Node& Octree<Type>::Node::ClearData(void)
	{
		hasData = false;
		return *this;
	}

	template< class Type >
	Octree<Type>::Node::Node(Octree* root, Node* parent, const Vector& size, const Vector& location)
	{
		node = 0;

		FLT = FLB = FRT = FRB = BLT = BLB = BRT = BRB = NULL;
		this->root = root;
		this->parent = parent;

		borders = new BoundingBox(location - size, location + size);
	}

	template< class Type >
	Octree<Type>::Node::Node(Octree* root, Node* parent, oNode* data)
	{
		assert(data != 0);

		node = data;
		data->nodes.push_back(this);

		FLT = FLB = FRT = FRB = BLT = BLB = BRT = BRB = NULL;
		this->root = root;
		this->parent = parent;
		borders = 0;
	}

	template< class Type >
	Octree<Type>::Node::~Node()
	{
		if (FLT != 0)
			delete FLT;

		if (FLB != 0)
			delete FLB;

		if (FRT != 0)
			delete FRT;

		if (FRB != 0)
			delete FRB;

		if (BLT != 0)
			delete BLT;

		if (BLB != 0)
			delete BLB;

		if (BRT != 0)
			delete BRT;

		if (BRB != 0)
			delete BRB;

		if (borders != 0)
			delete borders;

		if (node != 0)
			node->Remove(this);
	}

	template< class Type >
	Octree<Type>::Node::operator Type(void) const
	{
		return data;
	}

	template< class Type >
	typename Octree<Type>::Node* Octree<Type>::Node::operator[](const size_t x) const
	{
		switch (x)
		{
		case 0:
			return FNW;
		case 1:
			return FNE;
		case 2:
			return FSW;
		case 3:
			return FSE;
		case 4:
			return BNW;
		case 5:
			return BNE;
		case 6:
			return BSW;
		case 7:
			return BSE;
		default:
			assert(false);
		}
	}

	template< class Type >
	void Octree<Type>::Node::print(void) const
	{
		std::cout << data << " @ (" << location.X << ", " << location.Y << ", " << location.Z << ")\n";
	}

	template< class Type >
	void Octree<Type>::Node::drawNode(IDirect3DDevice9* device) const
	{
		if (node != 0)
			node->drawNode(device);
		else
			borders->draw(device);
	}

	template< class Type >
	void Octree<Type>::Node::drawNodes(IDirect3DDevice9* device) const
	{
		if (FLT != 0)
			FLT->drawNodes(device);
		if (FLB != 0)
			FLB->drawNodes(device);
		if (FRT != 0)
			FRT->drawNodes(device);
		if (FRB != 0)
			FRB->drawNodes(device);
		if (BLT != 0)
			BLT->drawNodes(device);
		if (BLB != 0)
			BLB->drawNodes(device);
		if (BRT != 0)
			BRT->drawNodes(device);
		if (BRB != 0)
			BRB->drawNodes(device);

		drawNode(device);
	}

	template< class Type >
	int Octree<Type>::Node::Search(std::vector<const oNode*>* out, const Vector& location, const float& distance) const
	{
		int found = 0;

		if (hasData)
		{
			if (location.distance(this->location) <= distance)
			{
				found++;
				if (out != 0)
					out->push_back(this);
			}
		}
		else
		{
			const Vector halfSize = Vector(size.X * 0.5f, size.Y * 0.5f, size.Z * 0.5f);
			const float& midX = this->location.X;
			const float& midY = this->location.Y;
			const float& midZ = this->location.Z;

			const Vector FLTLoc = this->location + (halfSize * Vector( 0.5f,  0.5f,  0.5f));
			const Vector FLBLoc = this->location + (halfSize * Vector( 0.5f,  0.5f, -0.5f));
			const Vector FRTLoc = this->location + (halfSize * Vector( 0.5f, -0.5f,  0.5f));
			const Vector FRBLoc = this->location + (halfSize * Vector( 0.5f, -0.5f, -0.5f));
			const Vector BLTLoc = this->location + (halfSize * Vector(-0.5f,  0.5f,  0.5f));
			const Vector BLBLoc = this->location + (halfSize * Vector(-0.5f,  0.5f, -0.5f));
			const Vector BRTLoc = this->location + (halfSize * Vector(-0.5f, -0.5f,  0.5f));
			const Vector BRBLoc = this->location + (halfSize * Vector(-0.5f, -0.5f, -0.5f));

			const bool front = (location.X + distance) > (midX - overlap);
			const bool back = (location.X - distance) < (midX + overlap);

			const bool left = (location.Y + distance) > (midY - overlap);
			const bool right = (location.Y - distance) < (midY + overlap);

			const bool top = (location.Z + distance) > (midZ - overlap);
			const bool bottom = (location.Z - distance) < (midZ + overlap);

			if (front && left && top)
			{
				if (FLT != 0)
					found += FLT->Search(out, location, distance);
			}
			if (front && left && bottom)
			{
				if (FLB != 0)
					found += FLB->Search(out, location, distance);
			}
			if (front && right && top)
			{
				if (FRT != 0)
					found += FRT->Search(out, location, distance);
			}
			if (front && right && bottom)
			{
				if (FRB != 0)
					found += FRB->Search(out, location, distance);
			}
			if (back && left && top)
			{
				if (BLT != 0)
					found += BLT->Search(out, location, distance);
			}
			if (back && left && bottom)
			{
				if (BLB != 0)
					found += BLB->Search(out, location, distance);
			}
			if (back && right && top)
			{
				if (BRT != 0)
					found += BRT->Search(out, location, distance);
			}
			if (back && right && bottom)
			{
				if (BRB != 0)
					found += BRB->Search(out, location, distance);
			}
		}

		return found;
	}

	template< class Type >
	const BoundingBox& Octree<Type>::Node::getBorders(void) const
	{
		if (node != 0)
			return node->borders;
		else
		{
			return (*borders);
		}
	}

	template< class Type >
	int Octree<Type>::Node::Search(std::vector<const oNode*>* out, const BoundingBox& location) const
	{
		int found = 0;

		if (node != 0)
		{
			if (node->borders.collides(location))
			{
				found++;
				if (out != 0)
					out->push_back(node);
			}
		}
		else
		{
			const BoundingBox& bb = getBorders();
			const Vector center = bb.getCenter();
			const Vector size = bb.getGreater() - center;
			const Vector halfSize = Vector(size.X * 0.5f, size.Y * 0.5f, size.Z * 0.5f);

			const Vector FLTLoc = center + (halfSize * Vector( 0.5f,  0.5f,  0.5f));
			const Vector FLBLoc = center + (halfSize * Vector( 0.5f,  0.5f, -0.5f));
			const Vector FRTLoc = center + (halfSize * Vector( 0.5f, -0.5f,  0.5f));
			const Vector FRBLoc = center + (halfSize * Vector( 0.5f, -0.5f, -0.5f));
			const Vector BLTLoc = center + (halfSize * Vector(-0.5f,  0.5f,  0.5f));
			const Vector BLBLoc = center + (halfSize * Vector(-0.5f,  0.5f, -0.5f));
			const Vector BRTLoc = center + (halfSize * Vector(-0.5f, -0.5f,  0.5f));
			const Vector BRBLoc = center + (halfSize * Vector(-0.5f, -0.5f, -0.5f));

			if (FLT != 0)
				if (FLT->getBorders().collides(location))
					found += FLT->Search(out, location);
			if (FLB != 0)
				if (FLB->getBorders().collides(location))
					found += FLB->Search(out, location);
			if (FRT != 0)
				if (FRT->getBorders().collides(location))
					found += FRT->Search(out, location);
			if (FRB != 0)
				if (FRB->getBorders().collides(location))
					found += FRB->Search(out, location);
			if (BLT != 0)
				if (BLT->getBorders().collides(location))
					found += BLT->Search(out, location);
			if (BLB != 0)
				if (BLB->getBorders().collides(location))
					found += BLB->Search(out, location);
			if (BRT != 0)
				if (BRT->getBorders().collides(location))
					found += BRT->Search(out, location);
			if (BRB != 0)
				if (BRB->getBorders().collides(location))
					found += BRB->Search(out, location);
		}

		return found;
	}

	template< class Type>
	typename Octree<Type>::Node* Octree<Type>::Node::Cleanup(void)
	{
		if (node != 0)
			return 0;
		else
		{
			unsigned int children = 0;
			unsigned int child = ~0;
			Node* del;
			if (FLT != 0)
			{
				del = FLT->Cleanup();
				if (del != 0)
				{
					delete del;
					if (FLT != 0)
					{
						children++;
						child = 0;
					}
				}
				else
				{
					children++;
					child = 0;
				}
			}
			if (FLB != 0)
			{
				del = FLB->Cleanup();
				if (del != 0)
				{
					delete del;
					if (FLB != 0)
					{
						children++;
						child = 1;
					}
				}
				else
				{
					children++;
					child = 1;
				}
			}
			if (FRT != 0)
			{
				del = FRT->Cleanup();
				if (del != 0)
				{
					delete del;
					if (FRT != 0)
					{
						children++;
						child = 2;
					}
				}
				else
				{
					children++;
					child = 2;
				}
			}
			if (FRB != 0)
			{
				del = FRB->Cleanup();
				if (del != 0)
				{
					delete del;
					if (FRB != 0)
					{
						children++;
						child = 3;
					}
				}
				else
				{
					children++;
					child = 3;
				}
			}
			if (BLT != 0)
			{
				del = BLT->Cleanup();
				if (del != 0)
				{
					delete del;
					if (BLT != 0)
					{
						children++;
						child = 4;
					}
				}
				else
				{
					children++;
					child = 4;
				}
			}
			if (BLB != 0)
			{
				del = BLB->Cleanup();
				if (del != 0)
				{
					delete del;
					if (BLB != 0)
					{
						children++;
						child = 5;
					}
				}
				else
				{
					children++;
					child = 5;
				}
			}
			if (BRT != 0)
			{
				del = BRT->Cleanup();
				if (del != 0)
				{
					delete del;
					if (BRT != 0)
					{
						children++;
						child = 6;
					}
				}
				else
				{
					children++;
					child = 6;
				}
			}
			if (BRB != 0)
			{
				del = BRB->Cleanup();
				if (del != 0)
				{
					delete del;
					if (BRB != 0)
					{
						children++;
						child = 7;
					}
				}
				else
				{
					children++;
					child = 7;
				}
			}

			if (children == 0)
			{
				if (parent != 0)
				{
					if (parent->FLT == this)
						parent->FLT = 0;
					else if (parent->FLB == this)
						parent->FLB = 0;
					else if (parent->FRT == this)
						parent->FRT = 0;
					else if (parent->FRB == this)
						parent->FRB = 0;
					else if (parent->BLT == this)
						parent->BLT = 0;
					else if (parent->BLB == this)
						parent->BLB = 0;
					else if (parent->BRT == this)
						parent->BRT = 0;
					else if (parent->BRB == this)
						parent->BRB = 0;
				}
				else
					root->m_root = 0;

				return this;
			}
			else if (children == 1)
			{
				Node* n;
				switch (child)
				{
				case 0:
					n = FLT;
					FLT = 0;
					break;
				case 1:
					n = FLB;
					FLB = 0;
					break;
				case 2:
					n = FRT;
					FRT = 0;
					break;
				case 3:
					n = FRB;
					FRB = 0;
					break;
				case 4:
					n = BLT;
					BLT = 0;
					break;
				case 5:
					n = BLB;
					BLB = 0;
					break;
				case 6:
					n = BRT;
					BRT = 0;
					break;
				case 7:
					n = BRB;
					BRB = 0;
					break;
				default:
					assert(child <= 7);
				}

				if (parent != 0)
				{
					n->parent = parent;
					if (parent->FLT == this)
						parent->FLT = n;
					else if (parent->FLB == this)
						parent->FLB = n;
					else if (parent->FRT == this)
						parent->FRT = n;
					else if (parent->FRB == this)
						parent->FRB = n;
					else if (parent->BLT == this)
						parent->BLT = n;
					else if (parent->BLB == this)
						parent->BLB = n;
					else if (parent->BRT == this)
						parent->BRT = n;
					else if (parent->BRB == this)
						parent->BRB = n;
				}
				else
				{
					root->m_root = n;
					n->parent = 0;
				}

				return this;
			}
			else
				return 0;
		}
	}
}

#endif //OCT_TREE_NODE_H
