#pragma once

#include "bndgbox.h"
#include "memblock.h"

//##########################################################################
//#######################    BoundingBoxTreeNode    ########################
//##########################################################################

class BoundingBoxTree;
	
class BoundingBoxTreeNode SIGNATURED
{
	friend class BoundingBoxTree;
	
//##########################################################################
// Memory Allocation
//
private:
	static MemoryBlock* GetAllocatedMemory();
	void* operator new(size_t)			{ return GetAllocatedMemory()->New(); }
	void operator delete(void *where)	{ GetAllocatedMemory()->Delete(where); }

//##########################################################################
// Construction and Destruction
//
protected:
	ExtentBox
		nodeExtents;
	BoundingBox
		*staticContents;
	BoundingBoxTreeNode
		*nodeBranches[6],
		*innerNode;

	BoundingBoxTreeNode(
		BoundingBox *volume,
		const ExtentBox &extents
	);
	~BoundingBoxTreeNode();

	void
		Add(
			BoundingBox *BoundingBox,
			const ExtentBox &extents
		);
	void
		Remove(
			BoundingBox *BoundingBox,
			const ExtentBox &extents
		);

//##########################################################################
// Tree Traversal Functions
//
protected:
	static int
		TraversalOrder[6];

	static void
		SetTraversalOrder(
			int first,
			int second,
			int third
		);

public:
	BoundingBoxTreeNode*
		FindSmallestNodeContaining(
			const ExtentBox &extents,
			BoundingBoxTreeNode *parent
		);

	BoundingBoxTreeNode*
		FindSmallestNodeContainingColumn(const ExtentBox &extents);

	BoundingBox*
		FindBoundingBoxContaining(
			const Point3D &point,
			BoundingBox *parent
		);

	void
		FindBoundingBoxesContaining(
			BoundingBox *volume,
			const ExtentBox &slice,
			BoundingBoxCollisionList &list
		);

	BoundingBox*
		FindBoundingBoxUnder(
			const Point3D &point,
        Scalar *height
		);

	BoundingBox*
		FindBoundingBoxHitBy(Line *line);

//##########################################################################
// Test Support
//
public:
	Logical
		TestInstance() const;
};

//##########################################################################
//########################    BoundingBoxTree    ###########################
//##########################################################################

class BoundingBoxTree SIGNATURED
{
	
//##########################################################################
// Construction and Destruction
//
protected:
	BoundingBoxTreeNode *root;

public:
	BoundingBoxTree()
		{Check_Pointer(this); root = NULL;}
	~BoundingBoxTree()
		{Check(this); EraseTree();}

	static void
		SetTraversalOrder(
			int first,
			int second,
			int third
		)
			{BoundingBoxTreeNode::SetTraversalOrder(first, second, third);}

	void
		Add(
			BoundingBox* volume,
			const ExtentBox &extents
		);
	void
		Remove(BoundingBox* volume)
			{
				Check(this); Check(volume); Check(root);
				root->Remove(volume, *volume);
			}
	void
		EraseTree();

//##########################################################################
// Tree Traversal Functions
//
public:
	BoundingBox*
		FindBoundingBoxContaining(const Point3D &point)
			{
				Check(this); Check(&point); Check(root);
				return root->FindBoundingBoxContaining(point, NULL);
			}

	BoundingBoxTreeNode*
		FindSmallestNodeContaining(const ExtentBox &extents)
			{
				Check(this); Check(&extents); Check(root);
				return root->FindSmallestNodeContaining(extents, NULL);
			}

	void
		FindBoundingBoxesContaining(
			BoundingBox *volume,
			BoundingBoxCollisionList &list
		)
			{
				Check(this); Check(volume); Check(&list); Check(root);
				root->FindBoundingBoxesContaining(
					volume,
					*volume,
					list
				);
			}

	BoundingBoxTreeNode*
		FindSmallestNodeContainingColumn(const ExtentBox &extents)
			{
				Check(this); Check(&extents); Check(root);
				Verify((BoundingBoxTreeNode::TraversalOrder[4]>>1) == Y_Axis);
				return root->FindSmallestNodeContainingColumn(extents);
			}

	BoundingBox*
		FindBoundingBoxUnder(
			const Point3D &point,
			Scalar *height
		)
			{
				Check(this); Check(&point); Check(root); Check_Pointer(height);
				Verify((BoundingBoxTreeNode::TraversalOrder[4]>>1) == Y_Axis);
				return root->FindBoundingBoxUnder(point, height);
			}

	BoundingBox*
		FindBoundingBoxHitBy(Line *line);

//##########################################################################
// Test Support
//
public:
	Logical
		TestInstance() const;
};