Package org.apache.sis.index.tree

Class PointTree<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
org.apache.sis.index.tree.PointTree<E>
Type Parameters:
E - the type of elements stored in this tree.
All Implemented Interfaces:
Serializable, Iterable<E>, Collection<E>, Set<E>, CheckedContainer<E>
public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, Serializable
A k-dimensional tree index for points. For k=2, this is a point QuadTree. For k=3, this is a point Octree. Higher dimensions are also accepted up to 6 dimensions. Elements are stored in this PointTree as arbitrary non-null objects with their coordinates computed by a user-specified locator function. That function expects an element E in argument and returns its coordinates as a double[] array. The coordinates of each elements must be stable, i.e. applying the locator function twice on the same element must return the same coordinates. Searches based on element coordinates can be done with the following methods: The performances of this PointTree depends on two parameters: an estimated bounding box of the points to be added in this tree and a maximal capacity of leaf nodes (not to be confused with a capacity of the tree). More details are given in the constructor.

Thread-safety

This class is not thread-safe when the tree content is modified. But if the tree is kept unmodified after construction, then multiple read operations in concurrent threads are safe. Users can synchronize with ReadWriteLock (the read lock must be held for complete duration of iterations or stream consumptions).

Serialization

This tree is serializable if the locator function and all elements in the tree are also serializable. However, the serialization details is implementation specific and may change in any future Apache SIS version.

Limitations

Current implementation does not yet support removal of elements.

References

Insertion algorithm is based on design of QuadTree index in H. Samet, The Design and Analysis of Spatial Data Structures. Massachusetts: Addison Wesley Publishing Company, 1989.
Since:
1.1
Version:
1.1
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static interface 
    PointTree.Locator<E>
    Provides the coordinates of any element stored in PointTree.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private long
    count
    Number of elements in this k-dimensional tree.
    private final org.opengis.referencing.crs.CoordinateReferenceSystem
    crs
    The coordinate reference system, or null if none.
    private final Class<E>
    elementType
    The type of elements in this set.
    (package private) final PointTree.Locator<? super E>
    locator
    Function computing the position of any element in this tree.
    static final int
    MAXIMUM_DIMENSIONS
    The maximum number of dimensions (inclusive) that this class currently supports.
    private final int
    nodeCapacity
    The maximal capacity of each node in this tree.
    private final boolean
    parallel
    Whether the stream can be parallel by default.
    (package private) final PointTreeNode
    root
    The root node of this k-dimensional tree.
    private static final long
    serialVersionUID
    For cross-version compatibility.
    (package private) final double[]
    treeRegion
    The regions covered by this tree, encoded as a center and a size.

  • Constructor Summary

    Constructors
    Constructor
    Description
    PointTree(Class<E> elementType, org.opengis.geometry.Envelope bounds, PointTree.Locator<? super E> locator, int nodeCapacity, boolean parallel)
    Creates an initially empty k-dimensional tree with the given capacity for each node.
    PointTree(PointTree<E> other)
    Creates a new tree initialized to a copy of the given tree.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(E element)
    Inserts the specified element into this tree if it is not already present.
    boolean
    addAll(Collection<? extends E> elements)
    Inserts all elements from the specified collection into this tree if they are not already present.
    void
    clear()
    Removes all elements from this tree.
    boolean
    contains(Object element)
    Returns true if this set contains the specified element.
    final Optional<org.opengis.referencing.crs.CoordinateReferenceSystem>
    getCoordinateReferenceSystem()
    Returns the coordinate reference system (CRS) of all points in this tree.
    final int
    getDimension()
    Returns the number of dimensions of points in this tree.
    final Class<E>
    getElementType()
    Returns the base type of all elements in this tree.
    private boolean
    insert(PointTreeNode parent, double[] region, E element, double[] point)
    Inserts the specified data into the given node.
    boolean
    isEmpty()
    Returns true if this set contains no elements.
    Iterator<E>
    iterator()
    Creates an iterator over all elements in this set.
    Stream<E>
    parallelStream()
    Returns a possibly parallel stream with this tree as its source.
    Stream<E>
    queryByBoundingBox(org.opengis.geometry.Envelope searchRegion)
    Returns all elements in the given bounding box.
    int
    size()
    Returns the number of elements in this tree.
    Spliterator<E>
    spliterator()
    Creates an iterator over all elements in this set.

    Methods inherited from class java.util.AbstractSet

    equals, hashCode, removeAll

    Methods inherited from class java.util.AbstractCollection

    containsAll, remove, retainAll, toArray, toArray, toString

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.util.Collection

    removeIf, stream

    Methods inherited from interface java.lang.Iterable

    forEach

    Methods inherited from interface java.util.Set

    containsAll, remove, retainAll, toArray, toArray

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      For cross-version compatibility.
      See Also:

    • MAXIMUM_DIMENSIONS

      public static final int MAXIMUM_DIMENSIONS
      The maximum number of dimensions (inclusive) that this class currently supports. Current maximum is 6. This restriction come from 2⁶ = 64.
      See Also:

    • elementType

      private final Class<E> elementType
      The type of elements in this set.
      See Also:

    • crs

      private final org.opengis.referencing.crs.CoordinateReferenceSystem crs
      The coordinate reference system, or null if none.
      See Also:

    • root

      final PointTreeNode root
      The root node of this k-dimensional tree.

    • nodeCapacity

      private final int nodeCapacity
      The maximal capacity of each node in this tree. It should be a relatively small number. If the number of elements in a leaf node exceeds this capacity, then the node will be transformed into a parent node with children nodes.

    • count

      private long count
      Number of elements in this k-dimensional tree. This is used as an unsigned integer (we do not expect to have as many elements, but in this case it is easy to get the extra bit provided by unsigned integer).
      See Also:

    • treeRegion

      final double[] treeRegion
      The regions covered by this tree, encoded as a center and a size. This array contains two parts:
      • The first half contains coordinates of the point in the center of the region covered by this tree.
      • The second half contains the size of the region along each dimension.
      The length of this array is two times the number of dimensions of points in this tree. This array content should not be modified, unless the entire tree is rebuilt (keep in mind that this array may be shared by PointTree copies).

    • locator

      final PointTree.Locator<? super E> locator
      Function computing the position of any element in this tree. The length of arrays computed by this locator must be equal to getDimension().

    • parallel

      private final boolean parallel
      Whether the stream can be parallel by default. Should be false if the locator is not thread-safe.

  • Constructor Details

    • PointTree

      public PointTree(PointTree<E> other)
      Creates a new tree initialized to a copy of the given tree. This copy constructor shares some data structure from the other tree for reducing memory usage, but the two trees are nevertheless independent (changes in a tree does not affect the other tree).
      Parameters:
      other - the other tree to copy.

    • PointTree

      public PointTree(Class<E> elementType, org.opengis.geometry.Envelope bounds, PointTree.Locator<? super E> locator, int nodeCapacity, boolean parallel)
      Creates an initially empty k-dimensional tree with the given capacity for each node. The number of dimensions of the given envelope determines the number of dimensions of points in this tree. The positions computed by locator must have the same number of dimensions than the given envelope.

      The bounds argument specifies the expected region of points to be added in this PointTree. Those bounds do not need to be exact; PointTree will work even if some points are located outside those bounds. However, performances will be better if the envelope center is close to the median of the points to be inserted in the PointTree, and if the majority of points are inside those bounds.

      The given nodeCapacity is a threshold value controlling when the content of a node should be splited into smaller children nodes. That capacity should be a relatively small number, for example 10. Determining the most efficient value may require benchmarking.

      Parameters:
      elementType - the base type of all elements in this tree.
      bounds - bounds of the region of data to be inserted in the k-dimensional tree.
      locator - function computing the position of any element in this tree.
      nodeCapacity - the capacity of each node (not to be confused with a capacity of the tree).
      parallel - whether the stream can be parallel by default. Should be false if the given locator is not thread-safe.

  • Method Details

    • getCoordinateReferenceSystem

      public final Optional<org.opengis.referencing.crs.CoordinateReferenceSystem> getCoordinateReferenceSystem()
      Returns the coordinate reference system (CRS) of all points in this tree. The CRS is taken from the envelope given in argument to the constructor.
      Returns:
      the CRS of all points in this tree, if presents.
      See Also:

    • getDimension

      public final int getDimension()
      Returns the number of dimensions of points in this tree.
      Returns:
      the number of dimensions of points in this tree.
      See Also:

    • getElementType

      public final Class<E> getElementType()
      Returns the base type of all elements in this tree.
      Specified by:
      getElementType in interface CheckedContainer<E>
      Returns:
      the element type.

    • clear

      public void clear()
      Removes all elements from this tree.
      Specified by:
      clear in interface Collection<E>
      Specified by:
      clear in interface Set<E>
      Overrides:
      clear in class AbstractCollection<E>

    • isEmpty

      public boolean isEmpty()
      Returns true if this set contains no elements.
      Specified by:
      isEmpty in interface Collection<E>
      Specified by:
      isEmpty in interface Set<E>
      Overrides:
      isEmpty in class AbstractCollection<E>
      Returns:
      whether this set is empty.

    • size

      public int size()
      Returns the number of elements in this tree.
      Specified by:
      size in interface Collection<E>
      Specified by:
      size in interface Set<E>
      Specified by:
      size in class AbstractCollection<E>
      Returns:
      the number of elements in this tree, or Integer.MAX_VALUE if there is more elements than what an int can represent.

    • add

      public boolean add(E element)
      Inserts the specified element into this tree if it is not already present.
      Specified by:
      add in interface Collection<E>
      Specified by:
      add in interface Set<E>
      Overrides:
      add in class AbstractCollection<E>
      Parameters:
      element - the element to insert.
      Returns:
      true if the element has been added, or false if it was already present.
      Throws:
      NullPointerException - if the given element is null.

    • addAll

      public boolean addAll(Collection<? extends E> elements)
      Inserts all elements from the specified collection into this tree if they are not already present.
      Specified by:
      addAll in interface Collection<E>
      Specified by:
      addAll in interface Set<E>
      Overrides:
      addAll in class AbstractCollection<E>
      Parameters:
      elements - the elements to insert.
      Returns:
      true if at least one element has been added.
      Throws:
      NullPointerException - if an element is null.

    • insert

      private boolean insert(PointTreeNode parent, double[] region, E element, double[] point)
      Inserts the specified data into the given node. This method will iterate through node children until a suitable node is found. This method may invoke itself recursively.
      Parameters:
      parent - the parent where to add the given data.
      region - region of current node, as the center in first half and size in second half.
      element - the element to insert.
      point - a pre-allocated array where to store the coordinates. This method will write in this array.
      Returns:
      true if the element has been added, or false if it was already present.

    • contains

      public boolean contains(Object element)
      Returns true if this set contains the specified element.
      Specified by:
      contains in interface Collection<E>
      Specified by:
      contains in interface Set<E>
      Overrides:
      contains in class AbstractCollection<E>
      Parameters:
      element - the object to search.
      Returns:
      whether this set contains the specified element.

    • iterator

      public Iterator<E> iterator()
      Creates an iterator over all elements in this set. In current implementation, the iterator does not support element removal.
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface Set<E>
      Specified by:
      iterator in class AbstractCollection<E>

    • spliterator

      public Spliterator<E> spliterator()
      Creates an iterator over all elements in this set. The iterator characteristics are sized, distinct and non-null.
      Specified by:
      spliterator in interface Collection<E>
      Specified by:
      spliterator in interface Iterable<E>
      Specified by:
      spliterator in interface Set<E>

    • parallelStream

      public Stream<E> parallelStream()
      Returns a possibly parallel stream with this tree as its source. It is allowable for this method to return a sequential stream.
      Specified by:
      parallelStream in interface Collection<E>
      Returns:
      a possibly parallel stream over the elements in this tree.

    • queryByBoundingBox

      public Stream<E> queryByBoundingBox(org.opengis.geometry.Envelope searchRegion)
      Returns all elements in the given bounding box. The given envelope shall be in the same CRS than the points in this tree (this is currently not verified). The returned stream may be parallel by default, depending on the argument given to the constructor. If the action to be applied on the stream cannot be parallel, then user should invoke BaseStream.sequential() explicitly.
      Parameters:
      searchRegion - envelope representing the rectangular search region.
      Returns:
      elements that are in the given search region (bounds inclusive).