Class AbstractSTRtree
java.lang.Object
org.locationtech.jts.index.strtree.AbstractSTRtree
- All Implemented Interfaces:
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 than AbstractNode
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected static interface
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
private static final int
private ArrayList
Set to null when index is built, to avoid retaining memory.private int
protected AbstractNode
private static final long
-
Constructor Summary
ConstructorsConstructorDescriptionConstructs 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 have -
Method Summary
Modifier and TypeMethodDescriptionprotected List
boundablesAtLevel
(int level) private void
boundablesAtLevel
(int level, AbstractNode top, Collection boundables) 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) private AbstractNode
createHigherLevels
(List boundablesOfALevel, int level) Creates the levels higher than the given levelprotected 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
protected abstract AbstractSTRtree.IntersectsOp
int
Returns the maximum number of child nodes that a node may havegetRoot()
protected void
boolean
isEmpty()
Tests whether the index contains any items.Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree.private List
itemsTree
(AbstractNode node) protected AbstractNode
protected List
Also builds the tree, if necessary.protected void
query
(Object searchBounds, ItemVisitor visitor) Also builds the tree, if necessary.private void
queryInternal
(Object searchBounds, AbstractNode node, List matches) private void
queryInternal
(Object searchBounds, AbstractNode node, ItemVisitor visitor) protected boolean
Removes an item from the tree.private boolean
remove
(Object searchBounds, AbstractNode node, Object item) private boolean
removeItem
(AbstractNode node, Object item) protected int
size()
protected int
size
(AbstractNode node)
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
root
-
built
private boolean built -
itemBoundables
Set to null when index is built, to avoid retaining memory. -
nodeCapacity
private int nodeCapacity -
DEFAULT_NODE_CAPACITY
private static final int DEFAULT_NODE_CAPACITY- See Also:
-
-
Constructor Details
-
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
-
-
Method Details
-
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
-
createParentBoundables
Sorts the childBoundables then divides them into groups of size M, where M is the node capacity. -
lastNode
-
compareDoubles
protected static int compareDoubles(double a, double b) -
createHigherLevels
Creates the levels higher than the given level- Parameters:
boundablesOfALevel
- the level to build onlevel
- the level of the Boundables, or -1 if the boundables are item boundables (that is, below level 0)- Returns:
- the root, which may be a ParentNode or a LeafNode
-
getRoot
-
getNodeCapacity
public int getNodeCapacity()Returns the maximum number of child nodes that a node may have -
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
-
depth
protected int depth() -
depth
-
insert
-
query
Also builds the tree, if necessary. -
query
Also builds the tree, if necessary. -
getIntersectsOp
- Returns:
- a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
- See Also:
-
queryInternal
-
queryInternal
-
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
-
itemsTree
-
remove
Removes an item from the tree. (Builds the tree, if necessary.) -
removeItem
-
remove
-
boundablesAtLevel
-
boundablesAtLevel
- Parameters:
level
- -1 to get items
-
getComparator
-