/////////////////////////////////////////////
// QTree.cpp
//Description: This class is a general component that can make quadtree support for other components
////////////////////////////////////////////
//The contents of this file are subject to the Mozilla Public License Version 1.1 (the "License"); 
//you may not use this file except in compliance with the License. You may obtain a copy of the License at 
//http://www.mozilla.org/MPL/ 
//Software distributed under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF 
//ANY KIND, either express or implied. See the License for the specific language governing rights and 
//limitations under the License. 
//
// The original Author is Neio(neio.zhou@gmail.com) and released as public domain in July 2009 to be a part of MapWinGIS.
// The contributors should list themselves and their modifications here.
//////////////////////////////////////////////////////////
#include "StdAfx.h"
#include "QTree.h"

QTree::QTree(QTreeExtent extent)
	:extent(extent)
{
	LT = nullptr;
	RT = nullptr;
	LB = nullptr;
	RB = nullptr;
	isFull = false;
	regenerating = false;
}

QTree::~QTree(void)
{
	for (const auto& node : nodes)
	{
		delete node;
	}
	nodes.clear();

	//clear four corners
	delete LT;
	delete RT;
	delete LB;
	delete RB;
}

void QTree::Regenerate()
{
	const unsigned int nodeNumber = nodes.size();
	const double middleX = (this->extent.left + this->extent.right) / 2;
	const double middleY = (this->extent.top + this->extent.bottom) / 2;

	///vector<QTreeNode*> nodesCross(MAX_LEAF_NODES);//Crossed Shapes

	for (int i = nodeNumber - 1; i >= 0; i--)
	{
		//not exist in any two areas
		if (!(nodes[i]->Extent.left <= middleX
			&& nodes[i]->Extent.right > middleX
			||
			nodes[i]->Extent.top > middleY
			&& nodes[i]->Extent.bottom <= middleY))
		{
			//nodesCross.push_back(new QTreeNode(Node));
			const QTreeNode* node = nodes[i];
			nodes.erase(nodes.begin() + i);
			this->AddNode(*node);
			//just move away one element
			break;
		}
	}
}

void QTree::AddNode(const QTreeNode& node)
{
	//if the Node overflow the extent of QuadTree
	if (!this->extent.Contain(node.Extent))
	{
		//if the old qtree is empty
		if (this->extent.left == 0 &&
			this->extent.right == 0 &&
			this->extent.top == 0 &&
			this->extent.bottom == 0)
		{
			this->extent = node.Extent;
		}
		else
		{
			const auto oldQtree = new QTree(QTreeExtent(this->extent.left, this->extent.right, this->extent.top, this->extent.bottom));
			oldQtree->LT = this->LT;
			oldQtree->RT = this->RT;
			oldQtree->LB = this->LB;
			oldQtree->RB = this->RB;
			oldQtree->nodes = this->nodes;
			oldQtree->isFull = this->isFull;
			oldQtree->regenerating = this->regenerating;

			this->LT = nullptr;
			this->RT = nullptr;
			this->LB = nullptr;
			this->RB = nullptr;

			if (node.Extent.left < this->extent.left)
			{
				this->extent.left -= (this->extent.right - this->extent.left);
				if (node.Extent.top > this->extent.top)
				{
					//put this qtre as new qtree's RB
					this->RB = oldQtree;
					this->extent.top += (this->extent.top - this->extent.bottom);
				}
				else
				{
					//put this qtree as new qtree's RT
					this->RT = oldQtree;
					this->extent.bottom -= (this->extent.top - this->extent.bottom);
				}
			}
			else if (node.Extent.right > this->extent.right || node.Extent.top > this->extent.top || node.Extent.bottom < this->extent.bottom)
			{

				this->extent.right += (this->extent.right - this->extent.left);
				if (node.Extent.top > this->extent.top)
				{
					this->LB = oldQtree;

					this->extent.top += (this->extent.top - this->extent.bottom);
				}
				else
				{
					this->LT = oldQtree;

					this->extent.bottom -= (this->extent.top - this->extent.bottom);
				}
			}

			this->nodes.clear();
			this->isFull = false;
			this->regenerating = false;
			AddNode(node);
			return;
		}
	}

	//Count the nodes of this leaf

	if (nodes.size() < MAX_LEAF_NODES && isFull == false)
	{

		//add node into this leaf
		nodes.push_back(new QTreeNode(node));

	}
	else if (nodes.size() == MAX_LEAF_NODES && isFull == false)
	{
		//need to regenerate

		isFull = true;//set the flag
		this->Regenerate();//call for re-generate

		//after regenerated the tree
		//continue to add node
		this->AddNode(node);
	}
	else
	{
		const double middleX = (this->extent.left + this->extent.right) / 2;
		const double middleY = (this->extent.top + this->extent.bottom) / 2;

		//Exist in any two areas
		if (node.Extent.left <= middleX && node.Extent.right > middleX
			||
			node.Extent.top > middleY && node.Extent.bottom <= middleY)
		{
			nodes.push_back(new QTreeNode(node));
		}
		else if (node.Extent.right <= middleX && node.Extent.bottom > middleY)
		{
			//LT
			if (LT == nullptr)
			{
				LT = new QTree(QTreeExtent(this->extent.left
					, middleX, this->extent.top, middleY));

			}
			LT->AddNode(node);
		}
		else if (node.Extent.left > middleX && node.Extent.bottom > middleY)
		{
			//RT
			if (RT == nullptr)
			{
				RT = new QTree(QTreeExtent(middleX, this->extent.right,
					this->extent.top, middleY));

			}
			RT->AddNode(node);
		}
		else if (node.Extent.right <= middleX && node.Extent.top < middleY)
		{
			//LB
			if (LB == nullptr)
			{
				LB = new QTree(QTreeExtent(this->extent.left, middleX,
					middleY, this->extent.bottom));

			}
			LB->AddNode(node);
		}
		else //if(Node.Extent.left > middleY && Node.Extent.top < middleY)
		{
			//RB
			if (RB == nullptr)
			{
				RB = new QTree(QTreeExtent(middleX, this->extent.right,
					middleY, this->extent.bottom));

			}
			RB->AddNode(node);
		}
	}

}

bool QTree::RemoveNode(int index)
{
	for (int i = nodes.size() - 1; i >= 0; i--)
	{
		if (nodes[i]->index == index)
		{
			//found in this leaf
			delete nodes[i];
			nodes.erase(nodes.begin() + i);
			return true;
		}

	}
	if (LT != nullptr && LT->RemoveNode(index))
	{
		return true;
	}
	if (RT != nullptr && RT->RemoveNode(index))
	{
		return true;
	}
	if (LB != nullptr && LB->RemoveNode(index))
	{
		return true;
	}
	if (RB != nullptr && RB->RemoveNode(index))
	{
		return true;
	}
	return false;
}

vector<int> QTree::GetNodes(QTreeExtent queryExtent)
{
	vector<int> result;
	if (!this->extent.IntersectIn(queryExtent))
		/*if(QueryExtent.right <= this->extent.left
			|| QueryExtent.left >= this->extent.right
			|| QueryExtent.top <= this->extent.bottom
			|| QueryExtent.bottom >= this->extent.top)*/
	{
		return result;
	}

	//unsigned int nodeNumber = nodes.size();
	//double middleX = (this->extent.left + this->extent.right) / 2;
	//double middleY = (this->extent.top + this->extent.bottom) / 2;

	if (LT != nullptr)
	{
		const vector<int> lt = LT->GetNodes(queryExtent);
		if (!lt.empty())
		{
			for (int i : lt)
				result.push_back(i);
		}
	}
	if (RT != nullptr)
	{
		const vector<int> rt = RT->GetNodes(queryExtent);
		if (!rt.empty())
		{
			for (int i : rt)
				result.push_back(i);
		}
	}
	if (LB != nullptr)
	{
		const vector<int> lb = LB->GetNodes(queryExtent);
		if (!lb.empty())
		{
			for (int i : lb)
				result.push_back(i);
		}
	}

	if (RB != nullptr)
	{
		const vector<int> rb = RB->GetNodes(queryExtent);
		if (!rb.empty())
		{
			for (int i : rb)
			{
				result.push_back(i);
			}
		}
	}
	for (int i = nodes.size() - 1; i >= 0; i--)
	{
		if (nodes[i]->Extent.IntersectIn(queryExtent))
			result.push_back(nodes[i]->index);
	}
	return result;
}