Package org.locationtech.jts.index.strtree

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

    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.

    • 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

    • Field Detail

      • built

        private boolean built

      • itemBoundables

        private java.util.ArrayList itemBoundables
        Set to null when index is built, to avoid retaining memory.

      • nodeCapacity

        private int nodeCapacity

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

      • createHigherLevels

        private AbstractNode createHigherLevels​(java.util.List boundablesOfALevel,
                                        int level)
        Creates the levels higher than the given level
        Parameters:
        boundablesOfALevel - the level to build on
        level - 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

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

      • depth

        protected int depth()

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

      • queryInternal

        private void queryInternal​(java.lang.Object searchBounds,
                           AbstractNode node,
                           java.util.List matches)

      • queryInternal

        private void queryInternal​(java.lang.Object searchBounds,
                           AbstractNode node,
                           ItemVisitor visitor)

      • 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

      • itemsTree

        private java.util.List itemsTree​(AbstractNode node)

      • remove

        protected boolean remove​(java.lang.Object searchBounds,
                         java.lang.Object item)
        Removes an item from the tree. (Builds the tree, if necessary.)

      • removeItem

        private boolean removeItem​(AbstractNode node,
                           java.lang.Object item)

      • remove

        private boolean remove​(java.lang.Object searchBounds,
                       AbstractNode node,
                       java.lang.Object item)

      • boundablesAtLevel

        protected java.util.List boundablesAtLevel​(int level)

      • boundablesAtLevel

        private void boundablesAtLevel​(int level,
                               AbstractNode top,
                               java.util.Collection boundables)
        Parameters:
        level - -1 to get items

      • getComparator

        protected abstract java.util.Comparator getComparator()