Class AbstractSTRtree
- java.lang.Object
-
- org.locationtech.jts.index.strtree.AbstractSTRtree
-
- All Implemented Interfaces:
Serializable
public abstract class AbstractSTRtree extends Object implements Serializable
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
Boundable
s rather thanAbstractNode
s, because the STR algorithm operates on both nodes and data, both of which are treated as Boundables.This class is thread-safe. Building the tree is synchronized, and querying is stateless.
- Version:
- 1.7
- See Also:
STRtree
,SIRtree
, Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected static interface
AbstractSTRtree.IntersectsOp
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
-
Field Summary
Fields Modifier and Type Field Description protected AbstractNode
root
-
Constructor Summary
Constructors Constructor Description AbstractSTRtree()
Constructs an AbstractSTRtree with the default node capacity.AbstractSTRtree(int nodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may haveAbstractSTRtree(int nodeCapacity, ArrayList itemBoundables)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and all leaf nodes in the treeAbstractSTRtree(int nodeCapacity, AbstractNode root)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and the root node
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected List
boundablesAtLevel(int level)
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.protected static int
compareDoubles(double a, double b)
protected abstract AbstractNode
createNode(int level)
protected List
createParentBoundables(List childBoundables, int newLevel)
Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.protected int
depth()
protected int
depth(AbstractNode node)
protected abstract Comparator
getComparator()
protected abstract AbstractSTRtree.IntersectsOp
getIntersectsOp()
int
getNodeCapacity()
Returns the maximum number of child nodes that a node may have.AbstractNode
getRoot()
Gets the root node of the tree.protected void
insert(Object bounds, Object item)
boolean
isEmpty()
Tests whether the index contains any items.List
itemsTree()
Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree.protected AbstractNode
lastNode(List nodes)
protected List
query(Object searchBounds)
Also builds the tree, if necessary.protected void
query(Object searchBounds, ItemVisitor visitor)
Also builds the tree, if necessary.protected boolean
remove(Object searchBounds, Object item)
Removes an item from the tree.protected int
size()
protected int
size(AbstractNode node)
-
-
-
Field Detail
-
root
protected AbstractNode root
-
-
Constructor Detail
-
AbstractSTRtree
public AbstractSTRtree()
Constructs an AbstractSTRtree with the default node capacity.
-
AbstractSTRtree
public AbstractSTRtree(int nodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have- Parameters:
nodeCapacity
- the maximum number of child nodes in a node
-
AbstractSTRtree
public AbstractSTRtree(int nodeCapacity, AbstractNode root)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and the root node- Parameters:
nodeCapacity
- the maximum number of child nodes in a noderoot
- the root node that links to all other nodes in the tree
-
AbstractSTRtree
public AbstractSTRtree(int nodeCapacity, ArrayList itemBoundables)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and all leaf nodes in the tree- Parameters:
nodeCapacity
- the maximum number of child nodes in a nodeitemBoundables
- the list of leaf nodes in the tree
-
-
Method Detail
-
build
public 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. Can only be called once, and thus can be called only after all of the data has been inserted into the tree.
-
createNode
protected abstract AbstractNode createNode(int level)
-
createParentBoundables
protected List createParentBoundables(List childBoundables, int newLevel)
Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.
-
lastNode
protected AbstractNode lastNode(List nodes)
-
compareDoubles
protected static int compareDoubles(double a, double b)
-
getRoot
public AbstractNode getRoot()
Gets the root node of the tree.- Returns:
- the root node
-
getNodeCapacity
public int getNodeCapacity()
Returns the maximum number of child nodes that a node may have.- Returns:
- the node capacity
-
isEmpty
public boolean isEmpty()
Tests whether the index contains any items. This method does not build the index, so items can still be inserted after it has been called.- Returns:
- true if the index does not contain any items
-
size
protected int size()
-
size
protected int size(AbstractNode node)
-
depth
protected int depth()
-
depth
protected int depth(AbstractNode node)
-
query
protected void query(Object searchBounds, ItemVisitor visitor)
Also builds the tree, if necessary.
-
getIntersectsOp
protected abstract AbstractSTRtree.IntersectsOp getIntersectsOp()
- Returns:
- a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
- See Also:
AbstractSTRtree.IntersectsOp
-
itemsTree
public List itemsTree()
Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree.The returned
List
s contain eitherObject
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.
- Returns:
- a List of items and/or Lists
-
remove
protected boolean remove(Object searchBounds, Object item)
Removes an item from the tree. (Builds the tree, if necessary.)
-
boundablesAtLevel
protected List boundablesAtLevel(int level)
-
getComparator
protected abstract Comparator getComparator()
-
-