GEOS  3.8.0dev
Classes | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
geos::index::strtree::AbstractSTRtree Class Referenceabstract

Base class for STRtree and SIRtree. More...

#include <AbstractSTRtree.h>

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

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. More...
 
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. More...
 

Static Public Member Functions

static bool compareDoubles (double a, double b)
 

Protected Member Functions

virtual AbstractNodecreateNode (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 AbstractNodelastNode (BoundableList *nodeList)
 
virtual AbstractNodegetRoot ()
 
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< BoundableListboundablesAtLevel (int level)
 
virtual IntersectsOpgetIntersectsOp ()=0
 

Protected Attributes

AbstractNoderoot
 
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

virtual void geos::index::strtree::AbstractSTRtree::boundablesAtLevel ( int  level,
AbstractNode top,
BoundableList boundables 
)
virtual
Parameters
level-1 to get items
topan AbstractNode
boundablesa BoundableList
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.

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::STRtree, and geos::index::strtree::SIRtree.

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
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: