Package org.apache.sis.index.tree

# Class PointTree<E>

Object
AbstractCollection<E>
AbstractSet<E>
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:

- `queryByBoundingBox(Envelope)`

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
See Also:
  - Serialized Form

Defined in the `sis-feature` module

- ## 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
  `static final int`
  `MAXIMUM_DIMENSIONS`
  The maximum number of dimensions (inclusive) that this class currently supports.

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `PointTree(Class<E> elementType, 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<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.
  `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(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 AbstractSet

  `equals, hashCode, removeAll`

  ### Methods inherited from class AbstractCollection

  `containsAll, remove, retainAll, toArray, toArray, toString`

  ### Methods inherited from class Object

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

  ### Methods inherited from interface Collection

  `removeIf, stream, toArray`

  ### Methods inherited from interface Iterable

  `forEach`

  ### Methods inherited from interface Set

  `containsAll, remove, retainAll, toArray, toArray`

- ## Field Details

  - ### 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:
      - Constant Field Values

- ## 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, 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<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()`

  - ### 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:
      - `getCoordinateReferenceSystem()`

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

  - ### 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(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 can not 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).