Package org.meteoinfo.jts.index.strtree

Class AbstractSTRtree

java.lang.Object

org.meteoinfo.jts.index.strtree.AbstractSTRtree

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

SIRtree, STRtree

public abstract class AbstractSTRtree
extends java.lang.Object
implements java.io.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 Boundables rather than AbstractNodes, 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.

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 have

Method Summary

Modifier and Type	Method	Description
protected java.util.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 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.
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.
protected boolean	remove(java.lang.Object searchBounds, java.lang.Object item)	Removes an item from the tree.
protected int	size()
protected int	size(AbstractNode node)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

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

lastNode

protected AbstractNode lastNode(java.util.List nodes)

compareDoubles

protected static int compareDoubles(double a,
                                    double b)

getRoot

public AbstractNode 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

protected int size(AbstractNode node)

depth

protected int depth()

depth

protected int depth(AbstractNode node)

insert

protected void insert(java.lang.Object bounds,
                      java.lang.Object item)

query

protected java.util.List query(java.lang.Object searchBounds)

Also builds the tree, if necessary.

query

protected void query(java.lang.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 java.util.List 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.

Returns:

a List of items and/or Lists

remove

protected boolean remove(java.lang.Object searchBounds,
                         java.lang.Object item)

Removes an item from the tree. (Builds the tree, if necessary.)

boundablesAtLevel

protected java.util.List boundablesAtLevel(int level)

getComparator

protected abstract java.util.Comparator getComparator()