com.vividsolutions.jts.index.strtree
Class AbstractSTRtree

java.lang.Object
  extended bycom.vividsolutions.jts.index.strtree.AbstractSTRtree
Direct Known Subclasses:
SIRtree, STRtree

public abstract class AbstractSTRtree
extends java.lang.Object

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.

Version:
1.7
See Also:
STRtree, SIRtree

Nested Class Summary
protected static interface AbstractSTRtree.IntersectsOp
          A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
 
Field Summary
protected  AbstractNode root
           
 
Constructor Summary
AbstractSTRtree(int nodeCapacity)
          Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have
 
Method Summary
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  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
protected  AbstractNode getRoot()
           
protected  void insert(java.lang.Object bounds, java.lang.Object item)
           
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(int nodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have

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 int compareDoubles(double a,
                             double b)

getRoot

protected AbstractNode getRoot()

getNodeCapacity

public int getNodeCapacity()
Returns the maximum number of child nodes that a node may have


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

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()