Региональный поиск метод дерева регионов / Source / Trees

#ifndef __TREES_H
#define __TREES_H

class Point
{
public:
	Point(int x, int y) : first(x), second(y) {}
	Point() : first(0), second(0) {}
	int first;
	int second;
	int number;
};

class OrderByY : public std::binary_function<Point, Point, bool>
{
public:
	bool operator() (const Point& p1, const Point& p2)
	{
		return p1.second<p2.second;
	}
};

class OrderByX : public std::binary_function<Point, Point, bool>
{
public:
	bool operator() (const Point& p1, const Point& p2)
	{
		return p1.first<p2.first;
	}
};


template<class NodeType>
class BinaryTree
{
public:
	BinaryTree(NodeType node, BinaryTree<NodeType>* left=0,
				BinaryTree<NodeType>* right=0);
	~BinaryTree()
	{
		if(Left) delete Left;
		if(Right) delete Right;
	}

	NodeType& GetNodeValue() {return NodeValue;}
	//void SetNodeValue(const NodeType& val);

	BinaryTree* GetLeftSubTree() const {return Left;}
	BinaryTree* GetRightSubTree() const {return Right;}

	//KLPIterator<NodeType> GetRoot() const {return KLPIterator<NodeType>(this); }

private:
	BinaryTree<NodeType>* Left;
	BinaryTree<NodeType>* Right;
	NodeType NodeValue;
};

/*template<class NodeType>
class KLPIterator
{
public:
	KLPIterator(const BinaryTree<NodeType>* root);
	KLPIterator(const KLPIterator<NodeType>& iter);

	KLPIterator& operator= (const KLPIterator& iter);
	bool operator== (const KLPIterator& iter) const;
	bool operator!= (const KLPIterator& iter) const;

	NodeType& operator* () const;
	NodeType* operator-> () const;

	KLPIterator<NodeType>& operator++();
	KLPIterator<NodeType>& operator--();

private:
	BinaryTree<NodeType>* Root; 
};*/

typedef std::pair<int,int> Segment;


class RegionTreeNode
{
public:
	RegionTreeNode(int b, int e, const std::list<Point>& pt) : 
	  B(b), E(e), Flag(false), OnWay(false) 
	  { std::copy(pt.begin(), pt.end(), std::back_inserter(Points));}
	//RegionTreeNode(const RegionTreeNode&);

	int GetB() const { return B; }	//начало отрезка
	int GetE() const { return E; }	//конец отрезка
	const std::vector<Point>& GetPoints() const { return Points; }

	//является ли узел узлом отнесения
	void SetFlag(bool fl) { Flag = fl; }
	bool GetFlag() const { return Flag; }

	//лежит ли на пути поиска
	bool IsOnWay() const { return OnWay; } 
	void SetOnWay(bool w) { OnWay = w; }

	//точки из этого интервала
	std::vector<Point>::const_iterator GetFirstPoint() const { return FirstPoint; };
	std::vector<Point>::const_iterator GetLastPoint() const { return LastPoint; };

	void SetFirstAndLastPoint (const std::vector<Point>::const_iterator& i1,
		const std::vector<Point>::const_iterator& i2)
	{
		FirstPoint = i1;
		LastPoint = i2;
	}

private:
	const int B;
	const int E;
	std::vector<Point> Points;
	bool Flag;
	bool OnWay;

	std::vector<Point>::const_iterator FirstPoint, LastPoint;
};

class SearchStep
{
public:
	enum StepType {SearchNode, NodeFound, BinarySearch1, BinarySearch2, SelectPoints};
	SearchStep(BinaryTree<RegionTreeNode>* node, StepType tp) : Node(node), Tp(tp) { };
	bool operator == (const SearchStep& st1) const
	{ return Node == st1.GetNode() && Tp == st1.GetTp();}

	BinaryTree<RegionTreeNode>* GetNode() const { return Node; }
	StepType GetTp() const {return Tp;}
private:
	BinaryTree<RegionTreeNode>* Node;
	StepType Tp;
};

class RegionTree
{
public:
	RegionTree(const std::vector<Point>& points);
	~RegionTree() { delete SearchTree; }

	BinaryTree<RegionTreeNode>* GetRoot() const { return SearchTree; };
	std::list<Point> Search(int x0, int y0, int x1, int y1);

	int GetNodeCount() const { return NodeCount; }

	const std::list<SearchStep>& GetSearchSteps() const { return SearchSteps; }
private:
	BinaryTree<RegionTreeNode>* ConsRegionTree(int l, int r, std::list<Point>);
	void Search(BinaryTree<RegionTreeNode>* t);
	int x0, y0, x1, y1;	//образец для поиска
	std::list<Point> Result;	//результат поиска


	std::vector<Point> Ys;	//отсортированный по возрастанию y массив точек
	std::vector<Point> Xs;	//отсортированный по возрастанию x массив точек

	BinaryTree<RegionTreeNode>* SearchTree;

	int NodeCount;	//количество узлов

	std::list<SearchStep> SearchSteps;

	void ClearFlags(BinaryTree<RegionTreeNode>* t);
};

#endif