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

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

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

//-----------------------------------------------------------------------------
// quadtree Class
//-----------------------------------------------------------------------------
namespace cbk
{
	template< class Type >
	class Octree
	{
	public:
		class Node;

		class oNode
		{
		public:
			oNode(const Type& data, const Vector& location, const BoundingBox& bounding, const float& scale);

			const Type& getData(void) const;
			oNode& getData(const Type&);

			const float& getScale(void) const;
			oNode& setScale(const float& scale);

			const Vector& getSize(void) const;
			oNode& setSize(const Vector& size);

			const Vector& getLocation(void) const;
			oNode& setLocation(const Vector& location);

			void drawNode(IDirect3DDevice9* device) const;

			const bool isInTree(void) const;

			void Remove(void);

		protected:
			void Remove(Node* node);

			Type data;

			Vector size;
			Vector location;
			BoundingBox borders;
			float scale;

			std::list<Node*> nodes;

			friend class Octree;
			friend class Node;
		};

	protected:
		class Node
		{
		public:
			void drawNode(IDirect3DDevice9* device) const;
			void drawNodes(IDirect3DDevice9* device) const;

		protected:
			Node *FLT;
			Node *FLB;
			Node *FRT;
			Node *FRB;
			Node *BLT;
			Node *BLB;
			Node *BRT;
			Node *BRB;

			oNode* node;

			BoundingBox* borders;

			Octree *root;
			Node *parent;

			const BoundingBox& getBorders(void) const;

			int Search(std::vector<const oNode*>* out, const Vector& location, const float& distance = 0.0f) const;
			int Search(std::vector<const oNode*>* out, const BoundingBox& location) const;

			Node* Insert(const Type& value, const Vector& location, const BoundingBox& bounding, const float& scale, const Vector& thisLocation, unsigned int recusionLevel, bool& added);
			Node* Insert(oNode* node, const Vector& thisLocation, unsigned int recursionLevel, std::vector<const oNode*>* out);
			Node* Delete(const Vector& location, Type* value = 0);
			Node* Delete(const BoundingBox& location, Type* value = 0);
			Node* Delete(Type data);

			Node* Cleanup(void);

			Node& SetData(const Type& value);

			Node& ClearData(void);

			Node(Octree* root, Node* parent, oNode* data);
			Node(Octree* root, Node* parent, const Vector& size, const Vector& location);

			~Node();

			operator Type(void) const;

			Node* operator[](const size_t x) const;

			void print(void) const;

			friend class Octree;
		};

	private:
		Node *m_root; // First Node in the quadtree.
		Vector size;
		float overlap;

	protected:
		Octree& Delete(Node* node);

	public:
		Octree();
		Octree(const Octree& other);
		~Octree();

		Octree& operator=(const Octree& other);

		/*
		Print out the quadtree.
		Print order will be NW, NE, SW, SE (Column major).
		*/
		void Print(void);

		Octree& SetSize(const Vector& size);
		Octree& SetOverlap(const float& overlap);

		typename Octree::oNode* Insert(const Type& data, const Vector& location, const BoundingBox& bounding, const float& scale, std::vector<const oNode*>* out);
		Octree& Delete(Type data);
		Octree& Delete(const Vector& location, Type* data = 0);
		Octree& Delete(const BoundingBox& location, Type* data = 0);
		Octree& Delete(oNode* node);

		Octree& Insert(oNode* node, std::vector<const oNode*>* out);
		Octree& Remove(oNode* node);
		Octree& Cleanup(void);

		int Search(std::vector<const oNode*>* out, const Vector& location, const float& distance = 0.0f) const;
		int Search(std::vector<const oNode*>* out, const BoundingBox& location) const;
		int Search(std::vector<const oNode*>* out, const Vector& location, const BoundingBox& bounding, const float& scale = 1.0f) const;

		void drawNodes(IDirect3DDevice9* device) const;

		friend class Node;
	};
}

#include "Octree_oNode.inl"
#include "Octree_Node.inl"
#include "Octree.inl"

#endif
