geos::index::intervalrtree::SortedPackedIntervalRTree Class Reference

A static index on a set of 1-dimensional intervals, using an R-Tree packed based on the order of the interval midpoints. More...

#include <SortedPackedIntervalRTree.h>

Collaboration diagram for geos::index::intervalrtree::SortedPackedIntervalRTree:

Public Member Functions
	SortedPackedIntervalRTree ()
	SortedPackedIntervalRTree (std::size_t initialCapacity)
void	insert (double min, double max, void *item)
void	query (double min, double max, index::ItemVisitor *visitor)

Private Member Functions
void	init ()
void	buildLevel (IntervalRTreeNode::ConstVect &src, IntervalRTreeNode::ConstVect &dest)
const IntervalRTreeNode *	buildTree ()

Private Attributes
std::vector< IntervalRTreeLeafNode >	leaves
std::vector< IntervalRTreeBranchNode >	branches
const IntervalRTreeNode *	root = nullptr
int	level = 0

Detailed Description

A static index on a set of 1-dimensional intervals, using an R-Tree packed based on the order of the interval midpoints.

It supports range searching, where the range is an interval of the real line (which may be a single point). A common use is to index 1-dimensional intervals which are the projection of 2-D objects onto an axis of the coordinate system.

This index structure is static

• items cannot be added or removed once the first query has been made. The advantage of this characteristic is that the index performance can be optimized based on a fixed set of items.

Author

Martin Davis

Definition at line 52 of file SortedPackedIntervalRTree.h.

Constructor & Destructor Documentation

geos::index::intervalrtree::SortedPackedIntervalRTree::SortedPackedIntervalRTree ( )

inline

Definition at line 72 of file SortedPackedIntervalRTree.h.

geos::index::intervalrtree::SortedPackedIntervalRTree::SortedPackedIntervalRTree ( std::size_t  initialCapacity )

inline

Definition at line 74 of file SortedPackedIntervalRTree.h.

Member Function Documentation

void geos::index::intervalrtree::SortedPackedIntervalRTree::buildLevel ( IntervalRTreeNode::ConstVect &  src, IntervalRTreeNode::ConstVect &  dest  )

private

const IntervalRTreeNode* geos::index::intervalrtree::SortedPackedIntervalRTree::buildTree ( )

private

void geos::index::intervalrtree::SortedPackedIntervalRTree::init ( )

private

void geos::index::intervalrtree::SortedPackedIntervalRTree::insert ( double  min, double  max, void *  item  )

inline

Adds an item to the index which is associated with the given interval

Parameters

min	the lower bound of the item interval
max	the upper bound of the item interval
item	the item to insert, ownership left to caller

Exceptions

IllegalStateException

if the index has already been queried

Definition at line 88 of file SortedPackedIntervalRTree.h.

void geos::index::intervalrtree::SortedPackedIntervalRTree::query	(	double	min,
		double	max,
		index::ItemVisitor *	visitor
	)

Search for intervals in the index which intersect the given closed interval and apply the visitor to them.

Parameters

min	the lower bound of the query interval
max	the upper bound of the query interval
visitor	the visitor to pass any matched items to

Member Data Documentation

std::vector<IntervalRTreeBranchNode> geos::index::intervalrtree::SortedPackedIntervalRTree::branches

private

Definition at line 55 of file SortedPackedIntervalRTree.h.

std::vector<IntervalRTreeLeafNode> geos::index::intervalrtree::SortedPackedIntervalRTree::leaves

private

Definition at line 54 of file SortedPackedIntervalRTree.h.

int geos::index::intervalrtree::SortedPackedIntervalRTree::level = 0

private

Definition at line 64 of file SortedPackedIntervalRTree.h.

const IntervalRTreeNode* geos::index::intervalrtree::SortedPackedIntervalRTree::root = nullptr

private

If root is null that indicates that the tree has not yet been built, OR nothing has been added to the tree. In both cases, the tree is still open for insertions.

Definition at line 63 of file SortedPackedIntervalRTree.h.

---

The documentation for this class was generated from the following file:

• SortedPackedIntervalRTree.h