#pragma once
#ifndef __QUADTREEHPP__
#define __QUADTREEHPP__

template<typename _T>
class QuadTreeNode
{
protected:
	QuadTreeNode<_T> *m_TL,*m_TR,*m_BL,*m_BR;
	_T m_Data;
	int m_Left,m_Top,m_Right,m_Bottom;
	QuadTreeNode<_T> *m_Parent;

public:
	QuadTreeNode (QuadTreeNode *parent)
	{
		m_Parent = parent;
		m_TL = m_TR = m_BL = m_BR = NULL;
		m_Left = m_Top = m_Right = m_Bottom = 0;
	}
	~QuadTreeNode (void)
	{
		delete m_TL;
		delete m_TR;
		delete m_BL;
		delete m_BR;
		m_TL = m_TR = m_BL = m_BR = NULL;
		m_Parent = NULL;
	}
	void Subdivide (int splithorz=0,int splitvert = 0)
	{
		delete m_TL;
		delete m_TR;
		delete m_BL;
		delete m_BR;
		m_TL = m_TR = m_BL = m_BR = NULL;
		if (splithorz == 0)
			splithorz = ((m_Bottom - m_Top) / 2) + m_Top;
		if (splitvert == 0)
			splitvert = ((m_Right - m_Left) / 2) + m_Left;
		if (splitvert<= m_Left)
			return;
		if (splitvert >= m_Right)
			return;
		if (splithorz <= m_Top)
			return;
		if (splithorz >= m_Bottom)
			return;
		m_TL = new QuadTreeNode<_T> (this);
		m_TR = new QuadTreeNode<_T> (this);
		m_BL = new QuadTreeNode<_T> (this);
		m_BR = new QuadTreeNode<_T> (this);
		m_TL->SetSize (m_Left,m_Top,splitvert,splithorz);
		m_TR->SetSize (splitvert+1,m_Top,m_Right,splithorz);
		m_BL->SetSize (m_Left,splithorz+1,splitvert,m_Bottom);
		m_BR->SetSize (splitvert+1,splithorz+1,m_Right,m_Bottom);
	}

	QuadTreeNode *TL (void)
	{ return m_TL; }
	QuadTreeNode *TR (void)
	{ return m_TR; }
	QuadTreeNode *BL (void)
	{ return m_BL; }
	QuadTreeNode *BR (void)
	{ return m_BR; }
	const _T& Data (void) const
	{ return m_Data; }
	_T& Data (void)
	{ return m_Data; }
	int Left (void) const
	{ return m_Left; }
	int Right (void) const
	{ return m_Right; }
	int Top (void) const
	{ return m_Top; }
	int Bottom (void) const
	{ return m_Bottom; }
	int Width (void) const
	{ return m_Right - m_Left; }
	int Height (void) const
	{ return m_Bottom - m_Top; }

	void SetSize (int left,int top,int right,int bottom)
	{
		if (left > right)
		{
			m_Left = right;
			m_Right = left;
		}
		else
		{
			m_Left = left;
			m_Right = right;
		}
		if (top > bottom)
		{
			m_Top = bottom;
			m_Bottom = top;
		}
		else
		{
			m_Top = top;
			m_Bottom = bottom;
		}
	}
};

template<typename _T>
class QuadTree
{
public:

protected:
	QuadTreeNode<_T> *m_Root;

	bool TraverseHelper (QuadTreeNode<_T> *node,int level,DWORD param)			// true to continue traverse
	{
		if (!node)
			return true;
		if (!TraverseFunction (node,level,param))
			return false;
		if (!TraverseHelper (node->TL (),level+1,param))
			return false;
		if (!TraverseHelper (node->TR (),level+1,param))
			return false;
		if (!TraverseHelper (node->BL (),level+1,param))
			return false;
		if (!TraverseHelper (node->BR (),level+1,param))
			return false;
		return true;
	}

public:
	QuadTree (void)
	{ m_Root = NULL; }
	~QuadTree (void)
	{
		delete m_Root;
		m_Root = NULL;
	}
	void Create (int left,int top,int right,int bottom)
	{
		m_Root = new QuadTreeNode<_T> (NULL);
		m_Root->SetSize (left,top,right,bottom);
	}
	QuadTreeNode *Root (void)
	{ return m_Root; }
	bool TraverseFunction (QuadTreeNode<_T> *node,int level,DWORD param)
	{
		return true;
	}
	void Traverse (DWORD param)
	{ TraverseHelper (m_Root,1,param); }
};


#endif