#pragma once

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

//##########################################################################
//#######################    BoundingBoxListNode    ########################
//##########################################################################

class BoundingBoxList;
class BoxedSolidList;
class BoundingBoxTree;

class BoundingBoxListNode SIGNATURED
{
	friend class BoundingBoxList;
  friend class BoxedSolidList;

//##########################################################################
// 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:
	BoundingBox
		*boundingBox;
	BoundingBoxListNode
		*previousNode;

	BoundingBoxListNode(
		BoundingBox *volume,
		const ExtentBox &slice
	):
		boundingBox(volume),
		solidSlice(slice),
		previousNode(NULL)
			{Check_Pointer(this); Check(volume);}
	~BoundingBoxListNode()
		{Check(this);}

public:
	ExtentBox
		solidSlice;
	BoundingBox*
		GetBoundingBox()
			{Check(this); return boundingBox;}
	BoundingBoxListNode*
		GetNextNode()
			{Check(this); return previousNode;}

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

//##########################################################################
//########################    BoundingBoxList    ###########################
//##########################################################################

class BoundingBoxList SIGNATURED
{

//##########################################################################
// Construction and Destruction
//
protected:
	BoundingBoxListNode
		*root;
	int
		nodeCount;
	int*
		scoreBoard;
	BoundingBox
		**boundingBoxIndex;
	Logical
		isXMajorAxis;

public:
	BoundingBoxList();
	~BoundingBoxList();

	void
		Add(
			BoundingBox* volume,
			const ExtentBox &slice
		);
	void
		Remove(BoundingBox* volume);
	void
		EraseList();

	BoundingBoxListNode*
		GetRoot()
			{Check(this); return root;}

//##########################################################################
// Tree Traversal Functions
//
public:
	BoundingBox*
		FindBoundingBoxContaining(const Point3D &point);

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

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

	BoundingBox*
		FindBoundingBoxHitBy(Line *line);

	void
		Reduce();
	void
		SortForTree();

protected:
	void
		Sort(
			BoundingBoxList &active_solids,
			ExtentBox &clipping_box,
			BoundingBoxTree &tree_so_far
		);

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