#ifndef BSP_TREE_H
#define BSP_TREE_H

#include "BoundingBox.h"
#include "Plane.h"
#include "Vector.h"
#include "Frustum.h"

#include <list>

struct IDirect3DDevice9;

//-----------------------------------------------------------------------------
// quadtree Class
//-----------------------------------------------------------------------------
namespace cbk
{
	template< class Type >
	class BSPTree
	{
	public:
		class Division
		{
		public:
			Type getData(void) const;

			void drawPlane(IDirect3DDevice9* device) const;
			void drawPlanes(IDirect3DDevice9* device) const;

		protected:
			Division(const Vector& location, const BoundingBox& bounding, const float& scale, const Type& Data, BSPTree* const root, Division* const parent);
			Division(const Vector& normal, const Vector& position, BSPTree* const root, Division* const parent);
			~Division(void);

			Plane* plane;
			Division* Greater;
			Division* Lesser;
			Type* Data;

			float scale;
			Vector location;
			BoundingBox* borders;
			bool blocksView;

			Division* getNode(const Vector& p) const;
			Type* getData(const Vector& p) const;

			int Search(std::list<const Division*>* out, const Frustum& volume, const Vector& eyePos) const;

			Division* Insert(Division* node);
			Division* Insert(const Type& value, const Vector& location, const BoundingBox& bounding, const float& scale);
			Division* Insert(const Vector& normal, const Vector& position);

			Division* Delete(const Vector& location, Type* value = 0);

			friend class BSPTree;

			Division* parent;
			BSPTree* root;
		};

		int Search(std::list<const Division*>* out, const Frustum& volume, const Vector& eyePos) const;

		Division* Insert(const Type& value, const Vector& location, const BoundingBox& bounding, const float& scale);
		Division* Insert(const Vector& normal, const Vector& position);

		void drawPlanes(IDirect3DDevice9* device) const;

		BSPTree& Delete(const Vector& location, Type* value = 0);

		BSPTree& Clear(void);

		BSPTree(void);

	protected:
		void Insert(Division* node);

	private:
		Division* root;
		int numNodes;

		friend class Division;
	};
}

#include "BSPTree.inl"

#endif //BSP_TREE_H