Base class for STRtree and SIRtree. More...

#include <AbstractSTRtree.h>

Inheritance diagram for geos::index::strtree::AbstractSTRtree:

Classes
class	IntersectsOp
	A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds. More...

Public Member Functions
	AbstractSTRtree (std::size_t newNodeCapacity)
	Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have.

virtual void	build ()
	Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been inserted into the tree.

virtual std::size_t	getNodeCapacity ()
	Returns the maximum number of child nodes that a node may have.

virtual void	query (const void searchBounds, const AbstractNode node, std::vector< void * > *matches)

void	iterate (ItemVisitor &visitor)

virtual void	boundablesAtLevel (int level, AbstractNode top, BoundableList boundables)

ItemsList *	itemsTree ()
	Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree.

Protected Member Functions
virtual AbstractNode *	createNode (int level)=0

virtual std::unique_ptr< BoundableList >	createParentBoundables (BoundableList *childBoundables, int newLevel)
	Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.

virtual AbstractNode *	lastNode (BoundableList *nodeList)

virtual AbstractNode *	getRoot ()

virtual void	insert (const void bounds, void item)
	Also builds the tree, if necessary.

void	query (const void searchBounds, std::vector< void > &foundItems)
	Also builds the tree, if necessary.

void	query (const void *searchBounds, ItemVisitor &visitor)
	Also builds the tree, if necessary.

void	query (const void *searchBounds, const AbstractNode &node, ItemVisitor &visitor)

bool	remove (const void itemEnv, void item)
	Also builds the tree, if necessary.

std::unique_ptr< BoundableList >	boundablesAtLevel (int level)

virtual IntersectsOp *	getIntersectsOp ()=0

Protected Attributes
AbstractNode *	root

std::vector< AbstractNode * > *	nodes

std::size_t	nodeCapacity

Detailed Description

Base class for STRtree and SIRtree.

STR-packed R-trees are described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.

This implementation is based on Boundables rather than just AbstractNodes, because the STR algorithm operates on both nodes and data, both of which are treated here as Boundables.

Member Function Documentation

◆ boundablesAtLevel()

virtual void geos::index::strtree::AbstractSTRtree::boundablesAtLevel	(	int	level,
		AbstractNode *	top,
		BoundableList *	boundables
	)

virtual

Parameters

level	-1 to get items
top	an AbstractNode
boundables	a BoundableList

◆ build()

virtual void geos::index::strtree::AbstractSTRtree::build ( )

virtual

Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been inserted into the tree.

Can only be called once, and thus can be called only after all of the data has been inserted into the tree.

◆ createParentBoundables()

virtual std::unique_ptr< BoundableList > geos::index::strtree::AbstractSTRtree::createParentBoundables	(	BoundableList *	childBoundables,
		int	newLevel
	)

protectedvirtual

Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.

Reimplemented in geos::index::strtree::SIRtree.

◆ getIntersectsOp()

virtual IntersectsOp * geos::index::strtree::AbstractSTRtree::getIntersectsOp ( )

protectedpure virtual

Returns: a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.

See also: IntersectsOp

Implemented in geos::index::strtree::SIRtree, and geos::index::strtree::STRtree.

◆ itemsTree()

ItemsList * geos::index::strtree::AbstractSTRtree::itemsTree ( )

Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree.

The returned Lists contain either Object items, or Lists which correspond to subtrees of the tree Subtrees which do not contain any items are not included.

Builds the tree if necessary.

Note: The caller is responsible for releasing the list

Returns: a List of items and/or Lists

◆ iterate()

void geos::index::strtree::AbstractSTRtree::iterate ( ItemVisitor & visitor )

Iterate over all items added thus far. Explicitly does not build the tree.

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

AbstractSTRtree.h

Classes

Public Member Functions

Protected Member Functions

Protected Attributes