public abstract class AbstractSTRtree
extends java.lang.Object
implements java.io.Serializable
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.
STRtree
,
SIRtree
,
Serialized FormModifier and Type | Class and Description |
---|---|
protected static interface |
AbstractSTRtree.IntersectsOp
A test for intersection between two bounds, necessary because subclasses
of AbstractSTRtree have different implementations of bounds.
|
Modifier and Type | Field and Description |
---|---|
private boolean |
built |
private static int |
DEFAULT_NODE_CAPACITY |
private java.util.ArrayList |
itemBoundables
Set to null when index is built, to avoid retaining memory.
|
private int |
nodeCapacity |
protected AbstractNode |
root |
private static long |
serialVersionUID |
Constructor and 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 have
|
Modifier and Type | Method and Description |
---|---|
protected java.util.List |
boundablesAtLevel(int level) |
private void |
boundablesAtLevel(int level,
AbstractNode top,
java.util.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(java.util.List boundablesOfALevel,
int level)
Creates the levels higher than the given level
|
protected abstract AbstractNode |
createNode(int level) |
protected java.util.List |
createParentBoundables(java.util.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 java.util.Comparator |
getComparator() |
protected abstract AbstractSTRtree.IntersectsOp |
getIntersectsOp() |
int |
getNodeCapacity()
Returns the maximum number of child nodes that a node may have
|
AbstractNode |
getRoot() |
protected void |
insert(java.lang.Object bounds,
java.lang.Object item) |
boolean |
isEmpty()
Tests whether the index contains any items.
|
java.util.List |
itemsTree()
Gets a tree structure (as a nested list)
corresponding to the structure of the items and nodes in this tree.
|
private java.util.List |
itemsTree(AbstractNode node) |
protected AbstractNode |
lastNode(java.util.List nodes) |
protected java.util.List |
query(java.lang.Object searchBounds)
Also builds the tree, if necessary.
|
protected void |
query(java.lang.Object searchBounds,
ItemVisitor visitor)
Also builds the tree, if necessary.
|
private void |
queryInternal(java.lang.Object searchBounds,
AbstractNode node,
ItemVisitor visitor) |
private void |
queryInternal(java.lang.Object searchBounds,
AbstractNode node,
java.util.List matches) |
private boolean |
remove(java.lang.Object searchBounds,
AbstractNode node,
java.lang.Object item) |
protected boolean |
remove(java.lang.Object searchBounds,
java.lang.Object item)
Removes an item from the tree.
|
private boolean |
removeItem(AbstractNode node,
java.lang.Object item) |
protected int |
size() |
protected int |
size(AbstractNode node) |
private static final long serialVersionUID
protected AbstractNode root
private boolean built
private java.util.ArrayList itemBoundables
private int nodeCapacity
private static final int DEFAULT_NODE_CAPACITY
public AbstractSTRtree()
public AbstractSTRtree(int nodeCapacity)
nodeCapacity
- the maximum number of child nodes in a nodepublic void build()
protected abstract AbstractNode createNode(int level)
protected java.util.List createParentBoundables(java.util.List childBoundables, int newLevel)
protected AbstractNode lastNode(java.util.List nodes)
protected static int compareDoubles(double a, double b)
private AbstractNode createHigherLevels(java.util.List boundablesOfALevel, int level)
boundablesOfALevel
- the level to build onlevel
- the level of the Boundables, or -1 if the boundables are item
boundables (that is, below level 0)public AbstractNode getRoot()
public int getNodeCapacity()
public boolean isEmpty()
protected int size()
protected int size(AbstractNode node)
protected int depth()
protected int depth(AbstractNode node)
protected void insert(java.lang.Object bounds, java.lang.Object item)
protected java.util.List query(java.lang.Object searchBounds)
protected void query(java.lang.Object searchBounds, ItemVisitor visitor)
protected abstract AbstractSTRtree.IntersectsOp getIntersectsOp()
AbstractSTRtree.IntersectsOp
private void queryInternal(java.lang.Object searchBounds, AbstractNode node, java.util.List matches)
private void queryInternal(java.lang.Object searchBounds, AbstractNode node, ItemVisitor visitor)
public java.util.List itemsTree()
The returned List
s 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.
private java.util.List itemsTree(AbstractNode node)
protected boolean remove(java.lang.Object searchBounds, java.lang.Object item)
private boolean removeItem(AbstractNode node, java.lang.Object item)
private boolean remove(java.lang.Object searchBounds, AbstractNode node, java.lang.Object item)
protected java.util.List boundablesAtLevel(int level)
private void boundablesAtLevel(int level, AbstractNode top, java.util.Collection boundables)
level
- -1 to get itemsprotected abstract java.util.Comparator getComparator()