Скачиваний:
16
Добавлен:
01.05.2014
Размер:
3.39 Кб
Скачать
#include "StdAfx.h"

#include "Trees.h"



template<class NodeType>
BinaryTree<NodeType>::BinaryTree(NodeType node, BinaryTree<NodeType>* left,
					   BinaryTree<NodeType>* right) : 
						Left(left), Right(right), NodeValue(node)
{
	
}


/*KLPIterator<NodeType>& KLPIterator<NodeType>::operator++()
{

	return this;
}*/

RegionTree::RegionTree(const std::vector<Point>& points) : Ys(points), Xs(points), NodeCount(0)
{
	std::sort(Ys.begin(), Ys.end(), OrderByY());
	std::sort(Xs.begin(), Xs.end(), OrderByX());

	SearchTree = ConsRegionTree(1, points.size()+1, std::list<Point>(Ys.begin(), Ys.end()));

}

BinaryTree<RegionTreeNode>* RegionTree::ConsRegionTree(int l, int r, std::list<Point> allp)
{
	BinaryTree<RegionTreeNode>* result;

	if(r-l==1) result=new BinaryTree<RegionTreeNode>(RegionTreeNode(l,r,allp));
	else
	{
		int c = (l+r)/2;
		ASSERT((c-l)>0);
		ASSERT((r-c)>0);
		std::list<Point> left;
		std::list<Point> right;
		ASSERT((c-1)>=0 && (c-1)<Xs.size());
		int central = Xs[c-1].first;

		std::list<Point>::iterator i=allp.begin();
		while(i!=allp.end())
		{
			if(i->first<central) 
				left.push_back(*i);
			else
				right.push_back(*i);
			i++;
		}
		result=new BinaryTree<RegionTreeNode>(RegionTreeNode(l,r,allp), 
												ConsRegionTree(l,c,left),
												ConsRegionTree(c,r,right));

	}
	NodeCount++;
	return result;
}

std::list<Point> RegionTree::Search(int x0, int y0, int x1, int y1)
{
	this->x0=1;
	this->x1=1;
	int i=0;
	while(Xs[i].first<x0) 
	{
		this->x0++;
		i++;
		if(i==Xs.size()) break;
	}

	i=0;
	while(Xs[i].first<x1)
	{
		this->x1++;
		i++;
		if(i==Xs.size()) break;
	}

	this->y0=y0;
	this->y1=y1;

	Result.clear();
	ClearFlags(SearchTree);
	SearchSteps.clear();
	if(this->x0<this->x1) Search(SearchTree);
	return Result;
}

void RegionTree::Search(BinaryTree<RegionTreeNode>* t)
{
	t->GetNodeValue().SetOnWay(true);
	

	int b=t->GetNodeValue().GetB();
	int e=t->GetNodeValue().GetE();
	int c=(b+e)/2;
	if(x0<=b && e<=x1) 
	{
		//это узел отнесения
		t->GetNodeValue().SetFlag(true);
	
		SearchSteps.push_back(SearchStep(t, SearchStep::NodeFound));

		Point p1(0,y0);
		std::vector<Point>::const_iterator i1=std::lower_bound(t->GetNodeValue().GetPoints().begin(),
					t->GetNodeValue().GetPoints().end(), p1, OrderByY());
		std::vector<Point>::const_iterator i2 = i1;

		while(i2!=t->GetNodeValue().GetPoints().end())
			if(y1>=i2->second) i2++; else break;

		t->GetNodeValue().SetFirstAndLastPoint(i1, i2);

		int d = std::distance(i1,i2);
		if(d>0)
		{
			SearchSteps.push_back(SearchStep(t, SearchStep::BinarySearch1));
			if(d>1)
			{
				SearchSteps.push_back(SearchStep(t, SearchStep::BinarySearch2));
				if(d>2)
					SearchSteps.push_back(SearchStep(t, SearchStep::SelectPoints));
			}
		}
		

		std::copy(i1, i2, std::back_inserter(Result));
	}
	else
	{
		SearchSteps.push_back(SearchStep(t, SearchStep::SearchNode));

		if(x0<c && t->GetLeftSubTree()) Search(t->GetLeftSubTree());
		if(c<x1 && t->GetRightSubTree()) Search(t->GetRightSubTree());
	}
}

void RegionTree::ClearFlags(BinaryTree<RegionTreeNode>* t)
{
	if(t) 
	{
		t->GetNodeValue().SetFlag(false);
		t->GetNodeValue().SetOnWay(false);
		ClearFlags(t->GetLeftSubTree());
		ClearFlags(t->GetRightSubTree());
	}
}
Соседние файлы в папке Source