#ifndef OCTREE_INL
#define OCTREE_INL

#include "Octree.h"

namespace cbk
{
	template< class Type>
	Octree<Type>& Octree<Type>::Delete(Node* node)
	{
		assert(node != 0);

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

		delete node;

		return *this;
	}

	template< class Type>
	Octree<Type>& Octree<Type>::Cleanup(void)
	{
		if (m_root != 0)
			if (m_root->Cleanup() != 0)
			{
				delete m_root;
				m_root = 0;
			}

		return *this;
	}

	template< class Type >
	Octree<Type>::Octree()
	{
		overlap = 0.0f;
		size = Vector();
		m_root = NULL;
	}

	template< class Type >
	Octree<Type>::Octree(const Octree& other)
	{
		m_root = NULL;
		overlap = 0.0f;
		size = Vector();
		*this = other;
	}

	template< class Type >
	Octree<Type>::~Octree()
	{
		delete m_root;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::operator=(const Octree& other)
	{
		if (m_root != 0)
			delete m_root;

		if (other.m_root != 0)
			m_root = new Node(*other.m_root);
		else
			m_root = 0;

		return *this;
	}

	/*
	Print out the quadtree.
	Print order will be NW, NE, SW, SE (Column major).
	*/
	template< class Type >
	void Octree<Type>::Print(void)
	{
		if (m_root == 0)
		{
			cout << "No data" << endl;
			return;
		}

		Node ***m_iterate = new Node**;
		std::stack<Node**> nodeStack;

		// what next?
		*m_iterate = 0;
		nodeStack.push(*m_iterate);
		*m_iterate = &m_root;
		do
		{
			if ((**m_iterate)->FLT != 0)
				nodeStack.push(&(**m_iterate)->FLT);
			if ((**m_iterate)->FLB != 0)
				nodeStack.push(&(**m_iterate)->FLB);
			if ((**m_iterate)->FRT != 0)
				nodeStack.push(&(**m_iterate)->FRT);
			if ((**m_iterate)->FRB != 0)
				nodeStack.push(&(**m_iterate)->FRB);
			if ((**m_iterate)->BLT != 0)
				nodeStack.push(&(**m_iterate)->BLT);
			if ((**m_iterate)->BLB != 0)
				nodeStack.push(&(**m_iterate)->BLB);
			if ((**m_iterate)->BRT != 0)
				nodeStack.push(&(**m_iterate)->BRT);
			if ((**m_iterate)->BRB != 0)
				nodeStack.push(&(**m_iterate)->BRB);

			if ((**m_iterate)->hasData)
				(**m_iterate)->print();

			*m_iterate = nodeStack.top();
			nodeStack.pop();
		} while (*m_iterate != 0);
		cout << endl;
		delete m_iterate;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::SetSize(const Vector& size)
	{
		assert(m_root == 0);
		this->size = size;
		return *this;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::SetOverlap(const float& overlap)
	{
		assert(m_root == 0);
		this->overlap = overlap;
		return *this;
	}

	template< class Type >
	typename Octree<Type>::oNode* Octree<Type>::Insert(const Type& data, const Vector& location, const BoundingBox& bounding, const float& scale, std::vector<const oNode*>* out)
	{
		assert(size != Vector());
		assert(overlap != 0);
		assert(out != 0);

		oNode* mNode = new oNode(data, location, bounding, scale);

		if (m_root == 0)
			m_root = new Node(this, 0, mNode);
		else
			m_root->Insert(mNode, Vector(), 0, out);

		return mNode;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::Insert(oNode* node, std::vector<const oNode*>* out)
	{
		assert(size != Vector());
		assert(overlap != 0);
		assert(out != 0);

		if (m_root == 0)
			m_root = new Node(this, 0, node);
		else
			m_root->Insert(node, Vector(), 0, out);

		return *this;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::Delete(const Vector& location, Type* data)
	{
		if (m_root != 0)
		{
			Node* t = m_root->Delete(location, data);
			if (t != 0)
			{
				delete t;
				m_root = 0;
			}
		}

		return *this;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::Delete(oNode* node)
	{
		if (node != 0)
		{
			node->Remove();
			delete node;
		}

		return *this;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::Remove(oNode* node)
	{
		if (m_root != 0)
			if (node != 0)
				node->Remove();

		return *this;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::Delete(Type data)
	{
		if (m_root != 0)
		{
			Node* t = m_root->Delete(data);
			if (t != 0)
			{
				delete t;
				m_root = 0;
			}
		}

		return *this;
	}

	template< class Type >
	Octree<Type>& Octree<Type>::Delete(const BoundingBox& location, Type* data)
	{
		if (m_root != 0)
		{
			Node* t = m_root->Delete(location, data);
			if (t != 0)
			{
				delete t;
				m_root = 0;
			}
		}

		return *this;
	}

	template< class Type >
	int Octree<Type>::Search(std::vector<const oNode*>* out, const Vector& location, const float& distance = 0.0f) const
	{
		float mDistance = distance;
		if (mDistance <= overlap)
			mDistance = overlap;

		if (m_root == 0)
			return 0;
		else
			return m_root->Search(out, location, mDistance);
	}

	template< class Type >
	int Octree<Type>::Search(std::vector<const oNode*>* out, const BoundingBox& location) const
	{
		if (m_root == 0)
			return 0;
		else
			return m_root->Search(out, location);
	}

	template< class Type >
	int Octree<Type>::Search(std::vector<const oNode*>* out, const Vector& location, const BoundingBox& bounding, const float& scale = 1.0f) const
	{
		if (m_root == 0)
			return 0;
		else
		{
			BoundingBox vol = (bounding * scale) + location;
			return m_root->Search(out, vol);
		}
	}

	template< class Type >
	void Octree<Type>::drawNodes(IDirect3DDevice9* device) const
	{
		D3DXMATRIX i;
		
		device->SetTransform(D3DTS_WORLD, D3DXMatrixIdentity(&i));
		if (m_root != 0)
			m_root->drawNodes(device);
	}
}

#endif //OCTREE_INL