indexbintree.h

一个很好的vc代码

/**********************************************************************
 * $Id: indexBintree.h,v 1.3 2004/10/26 17:46:18 strk Exp $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation. 
 * See the COPYING file for more information.
 *
 **********************************************************************
 * $Log: indexBintree.h,v $
 * Revision 1.3  2004/10/26 17:46:18  strk
 * Removed slash-stars in comments to remove annoying compiler warnings.
 *
 * Revision 1.2  2004/07/19 13:19:31  strk
 * Documentation fixes
 *
 * Revision 1.1  2004/07/02 13:20:42  strk
 * Header files moved under geos/ dir.
 *
 * Revision 1.6  2004/05/06 16:30:58  strk
 * Kept track of newly allocated objects by ensureExtent for Bintree and Quadtree,
 * deleted at destruction time. doc/example.cpp runs with no leaks.
 *
 * Revision 1.5  2004/03/25 02:23:55  ybychkov
 * All "index/" packages upgraded to JTS 1.4
 *
 * Revision 1.4  2003/11/07 01:23:42  pramsey
 * Add standard CVS headers licence notices and copyrights to all cpp and h
 * files.
 *
 *
 **********************************************************************/


#ifndef GEOS_INDEXBINTREE_H
#define GEOS_INDEXBINTREE_H

#include <memory>
#include <vector>
#include <geos/platform.h>
#include <geos/geom.h>

using namespace std;

namespace geos {

/*
 * \class BinTreeInterval indexBintree.h geos/indexBintree.h
 * \brief
 * Represents an (1-dimensional) closed interval on the Real number line.
 */
class BinTreeInterval {
public:
	double min, max;
	BinTreeInterval();
	virtual ~BinTreeInterval();
	BinTreeInterval(double nmin, double nmax);
	BinTreeInterval(BinTreeInterval *interval);
	void init(double nmin, double nmax);
	double getMin();
	double getMax();
	double getWidth();
	void expandToInclude(BinTreeInterval *interval);
	bool overlaps(BinTreeInterval *interval);
	bool overlaps(double nmin, double nmax);
	bool contains(BinTreeInterval *interval);
	bool contains(double nmin, double nmax);
	bool contains(double p);
};

/*
 * \class Key indexBintree.h geos/indexBintree.h
 * \brief
 * A Key is a unique identifier for a node in a tree.
 *
 * It contains a lower-left point and a level number.
 * The level number is the power of two for the size of the node envelope
 */
class Key {
public:
	static int computeLevel(BinTreeInterval *newInterval);
	Key(BinTreeInterval *newInterval);
	virtual ~Key();
	double getPoint();
	int getLevel();
	BinTreeInterval* getInterval();
	void computeKey(BinTreeInterval *itemInterval);
private:
	// the fields which make up the key
	double pt;
	int level;
	// auxiliary data which is derived from the key for use in computation
	BinTreeInterval *interval;
	void computeInterval(int level,BinTreeInterval *itemInterval);
};

class BinTreeNode;

/*
 * \class NodeBase indexBintree.h geos/indexBintree.h
 * \brief The base class for nodes in a Bintree.
 */
class NodeBase {
public:
	static int getSubnodeIndex(BinTreeInterval *interval, double centre);
	NodeBase();
	virtual ~NodeBase();
	virtual vector<void*> *getItems();
	virtual void add(void* item);
	virtual vector<void*>* addAllItems(vector<void*> *newItems);
	virtual vector<void*>* addAllItemsFromOverlapping(BinTreeInterval *interval,vector<void*> *resultItems);
	virtual int depth();
	virtual int size();
	virtual int nodeSize();
protected:	
	vector<void*>* items;
	/**
	* subnodes are numbered as follows:
	*
	*  0 | 1
	*/
	BinTreeNode* subnode[2];
	virtual bool isSearchMatch(BinTreeInterval *interval)=0;
};

/*
 * \class BinTreeNode indexBintree.h geos/indexBintree.h
 * \brief A node of a Bintree.
 */
class BinTreeNode: public NodeBase {
public:
	static BinTreeNode* createNode(BinTreeInterval *itemInterval);
	static BinTreeNode* createExpanded(BinTreeNode *node,BinTreeInterval *addInterval);
	BinTreeNode(BinTreeInterval *newInterval,int newLevel);
	virtual ~BinTreeNode();
	BinTreeInterval* getInterval();
	BinTreeNode* getNode(BinTreeInterval *searchInterval);
	NodeBase* find(BinTreeInterval *searchInterval);
	void insert(BinTreeNode *node);
private:
	BinTreeInterval *interval;
	double centre;
	int level;
	BinTreeNode* getSubnode(int index);
	BinTreeNode* createSubnode(int index);
protected:
	bool isSearchMatch(BinTreeInterval *itemInterval);
};

/*
 * \class Root indexBintree.h geos/indexBintree.h
 * \brief The root node of a single Bintree.
 *
 * It is centred at the origin,
 * and does not have a defined extent.
 */
class Root: public NodeBase {
private:
	// the singleton root node is centred at the origin.
	static double origin;
	void insertContained(BinTreeNode *tree,BinTreeInterval *itemInterval,void* item);
public:
	Root();
	virtual ~Root();
	void insert(BinTreeInterval *itemInterval,void* item);
protected:
	bool isSearchMatch(BinTreeInterval *interval);
};

/*
 * \class Bintree indexBintree.h geos/indexBintree.h
 *
 * \brief An BinTree (or "Binary BinTreeInterval Tree")
 * is a 1-dimensional version of a quadtree.
 *
 * It indexes 1-dimensional intervals (which of course may
 * be the projection of 2-D objects on an axis).
 * It supports range searching
 * (where the range may be a single point).
 *
 * This implementation does not require specifying the extent of the inserted
 * items beforehand.  It will automatically expand to accomodate any extent
 * of dataset.
 * 
 * This index is different to the BinTreeInterval Tree of Edelsbrunner
 * or the Segment Tree of Bentley.
 */
class Bintree {
public:
	static BinTreeInterval* ensureExtent(BinTreeInterval *itemInterval, double minExtent);
	Bintree();
	virtual ~Bintree();
	int depth();
	int size();
	int nodeSize();
	void insert(BinTreeInterval *itemInterval,void* item);
	vector<void*>* iterator();
	vector<void*>* query(double x);
	vector<void*>* query(BinTreeInterval *interval);
	void query(BinTreeInterval *interval,vector<void*> *foundItems);
private:
	vector<BinTreeInterval *>newIntervals;
	Root *root;
	/**
	*  Statistics
	*
	* minExtent is the minimum extent of all items
	* inserted into the tree so far. It is used as a heuristic value
	* to construct non-zero extents for features with zero extent.
	* Start with a non-zero extent, in case the first feature inserted has
	* a zero extent in both directions.  This value may be non-optimal, but
	* only one feature will be inserted with this value.
	**/
	double minExtent;
	void collectStats(BinTreeInterval *interval);
};
}
#endif