// Author : Chris Tolley
// Date   : 7/13/2004
// QuadTree.h contains the class declaration for a quad tree class to 
// use to keep track of objects in a 3d space

#if !defined(AFX_QUADTREE_H__E9D11DB6_EFE7_4952_8171_6B0D72A55D12__INCLUDED_)
#define AFX_QUADTREE_H__E9D11DB6_EFE7_4952_8171_6B0D72A55D12__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <vector>
using std::vector;

#include "SmartPointer.h"

// Forward class declarations
class QuadNode;
class Object;
class LeafQuadNode;

class QuadTree
{
public:
	// Constructor.  Size must be a power of 2
	QuadTree( unsigned short size );

	// Destructor
	virtual ~QuadTree();

	// Initializes the quad tree
	void Initialize( unsigned short maxX, unsigned short minX,
					 unsigned short maxZ, unsigned short minZ,
					 unsigned short arrayPos = 0 );

	// Inserts an object into the quadtree and returns the node it is in
	void Insert( SmartPointer& obj );

	// Removes an object from the quadtree
	void Remove( SmartPointer& obj );

	// Removes all objects in this quadtree
	void RemoveAll();

	// Stores any objects in a circle within radius around x,z
	void GetObjects( vector< SmartPointer >& objects, float radius, 
					 float x, float z )							const;

	// Returns the index value of x's upper left child
	inline unsigned short ULChild( unsigned short x ) const
	{ return ( x * 4 ) + 4; };

	// Returns the index value of x's upper right child
	inline unsigned short URChild( unsigned short x ) const
	{ return ( x * 4 ) + 1; };

	// Returns the index value of x's lower left child
	inline unsigned short LLChild( unsigned short x ) const
	{ return ( x * 4 ) + 3; };

	// Returns the index value of x's lower right child
	inline unsigned short LRChild( unsigned short x ) const
	{ return ( x * 4 ) + 2; };

	// Returns true if x is the index to the root of the tree
	inline bool isRoot( unsigned short x ) const
	{ return x == 0; };

	// Returns true if x is the index to an upper left child
	inline bool isULChild( unsigned short x ) const
	{ return ( x % 4 ) == 0; };

	// Returns true if x is the index to an upper right child
	inline bool isURChild( unsigned short x ) const
	{ return ( x % 4 ) == 1; };

	// Returns true if x is the index to a lower left child
	inline bool isLLChild( unsigned short x ) const
	{ return ( x % 4 ) == 3; };

	// Returns true if x is the index to a lower right child
	inline bool isLRChild( unsigned short x ) const
	{ return ( x % 4 ) == 2; };

	// Returns the parent index of x
	inline unsigned short getParent( unsigned short x ) const
	{ return ( x / 4 ) - ( ( x % 4 ) - 1 ); };

	// Need to figure out a way to rewrite this function better
	// Returns true if x is the index to a leaf
	inline bool isLeaf( unsigned short x ) const
	{ return x >= m_iNumInterior; };

	// Returns the size of the array
	inline int size() { return m_usSize; };
private:
	// Holds the quad nodes for this tree
	vector< QuadNode* > m_vNodes;

	// The size of the quad tree.  Must be a power of two
	unsigned short m_usSize;

	// Keeps track of the number of interior nodes
	int m_iNumInterior;
};

#endif // !defined(AFX_QUADTREE_H__E9D11DB6_EFE7_4952_8171_6B0D72A55D12__INCLUDED_)
