bintree.cpp

在Linux下做的QuadTree的程序

/**********************************************************************
 * $Id: Bintree.cpp 1820 2006-09-06 16:54:23Z mloskot $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2006 Refractions Research Inc.
 * 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.
 *
 **********************************************************************/

#include <geos/index/bintree/Bintree.h>
#include <geos/index/bintree/Root.h>
#include <geos/index/bintree/Interval.h>
#include <vector>

namespace geos {
namespace index { // geos.index
namespace bintree { // geos.index.bintree

using namespace std;

/**
* Ensure that the Interval for the inserted item has non-zero extents.
* Use the current minExtent to pad it, if necessary
*/
Interval*
Bintree::ensureExtent(Interval *itemInterval, double minExtent)
{
	double min=itemInterval->getMin();
	double max=itemInterval->getMax();
	// has a non-zero extent
	if (min!=max) return new Interval(itemInterval);
	// pad extent
	if (min==max) {
		min=min-minExtent/2.0;
		max=min+minExtent/2.0;
	}
//	delete itemInterval;
	return new Interval(min, max);
}



Bintree::Bintree()
{
	minExtent=1.0;
	root=new Root();
}

Bintree::~Bintree()
{
	for (unsigned int i=0; i<newIntervals.size(); i++)
		delete newIntervals[i];
	delete root;
}

int
Bintree::depth()
{
	if (root!=NULL) return root->depth();
	return 0;
}

int
Bintree::size()
{
	if (root!=NULL) return root->size();
	return 0;
}

/**
 * Compute the total number of nodes in the tree
 *
 * @return the number of nodes in the tree
 */
int
Bintree::nodeSize()
{
	if (root!=NULL) return root->nodeSize();
	return 0;
}

void
Bintree::insert(Interval *itemInterval,void* item)
{
	collectStats(itemInterval);
	Interval *insertInterval=ensureExtent(itemInterval,minExtent);
	if ( insertInterval != itemInterval )
		newIntervals.push_back(insertInterval);
	//int oldSize=size();
	root->insert(insertInterval,item);

	/* GEOS_DEBUG
	int newSize=size();
	System.out.println("BinTree: size="+newSize+"   node size="+nodeSize());
	if (newSize <= oldSize) {
	System.out.println("Lost item!");
	root.insert(insertInterval, item);
	System.out.println("reinsertion size="+size());
	}
	*/
}

vector<void*>* Bintree::iterator() {
	vector<void*>* foundItems=new vector<void*>();
	root->addAllItems(foundItems);
	return foundItems;
}

vector<void*>* Bintree::query(double x) {
	return query(new Interval(x, x));
}

/**
* min and max may be the same value
*/
vector<void*>* Bintree::query(Interval *interval) {
	/**
	* the items that are matched are all items in intervals
	* which overlap the query interval
	*/
	vector<void*>* foundItems=new vector<void*>();
	query(interval,foundItems);
	return foundItems;
}

void
Bintree::query(Interval *interval,vector<void*> *foundItems)
{
	root->addAllItemsFromOverlapping(interval,foundItems);
}

void
Bintree::collectStats(Interval *interval)
{
	double del=interval->getWidth();
	if (del<minExtent && del>0.0)
		minExtent=del;
}

} // namespace geos.index.bintree
} // namespace geos.index
} // namespace geos

/**********************************************************************
 * $Log$
 * Revision 1.13  2006/03/22 16:01:33  strk
 * indexBintree.h header split, classes renamed to match JTS
 *
 **********************************************************************/