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>
A kdimensional 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 nonnull objects with their coordinates
computed by a userspecified 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.
Threadsafety
This class is not threadsafe 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 withReadWriteLock
(the read lock must be held for complete duration
of iterations or stream consumptions).
Serialization
This tree is serializable if thelocator
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:
Defined in the sisfeature
module

Nested Class Summary
Modifier and TypeClassDescriptionstatic interface
Provides the coordinates of any element stored inPointTree
. 
Field Summary
Modifier and TypeFieldDescriptionstatic final int
The maximum number of dimensions (inclusive) that this class currently supports. 
Constructor Summary
ConstructorDescriptionPointTree
(Class<E> elementType, Envelope bounds, PointTree.Locator<? super E> locator, int nodeCapacity, boolean parallel) Creates an initially empty kdimensional 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 TypeMethodDescriptionboolean
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
Returnstrue
if this set contains the specified element.Returns the coordinate reference system (CRS) of all points in this tree.final int
Returns the number of dimensions of points in this tree.Returns the base type of all elements in this tree.boolean
isEmpty()
Returns true if this set contains no elements.iterator()
Creates an iterator over all elements in this set.Returns a possibly parallel stream with this tree as its source.queryByBoundingBox
(Envelope searchRegion) Returns all elements in the given bounding box.int
size()
Returns the number of elements in this tree.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 Set
containsAll, remove, retainAll, toArray, toArray

Field Details

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


Constructor Details

PointTree
Creates a new tree initialized to a copy of the given tree. This copy constructor shares some data structure from theother
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 kdimensional 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 bylocator
must have the same number of dimensions than the given envelope.The
bounds
argument specifies the expected region of points to be added in thisPointTree
. 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 thePointTree
, 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 kdimensional 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 befalse
if the givenlocator
is not threadsafe.


Method Details

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
Returns the base type of all elements in this tree. Specified by:
getElementType
in interfaceCheckedContainer<E>
 Returns:
 the element type.

clear
public void clear()Removes all elements from this tree. Specified by:
clear
in interfaceCollection<E>
 Specified by:
clear
in interfaceSet<E>
 Overrides:
clear
in classAbstractCollection<E>

isEmpty
public boolean isEmpty()Returns true if this set contains no elements. Specified by:
isEmpty
in interfaceCollection<E>
 Specified by:
isEmpty
in interfaceSet<E>
 Overrides:
isEmpty
in classAbstractCollection<E>
 Returns:
 whether this set is empty.

size
public int size()Returns the number of elements in this tree. Specified by:
size
in interfaceCollection<E>
 Specified by:
size
in interfaceSet<E>
 Specified by:
size
in classAbstractCollection<E>
 Returns:
 the number of elements in this tree, or
Integer.MAX_VALUE
if there is more elements than what anint
can represent.

add
Inserts the specified element into this tree if it is not already present. Specified by:
add
in interfaceCollection<E>
 Specified by:
add
in interfaceSet<E>
 Overrides:
add
in classAbstractCollection<E>
 Parameters:
element
 the element to insert. Returns:
true
if the element has been added, orfalse
if it was already present. Throws:
NullPointerException
 if the given element is null.

addAll
Inserts all elements from the specified collection into this tree if they are not already present. Specified by:
addAll
in interfaceCollection<E>
 Specified by:
addAll
in interfaceSet<E>
 Overrides:
addAll
in classAbstractCollection<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
Returnstrue
if this set contains the specified element. Specified by:
contains
in interfaceCollection<E>
 Specified by:
contains
in interfaceSet<E>
 Overrides:
contains
in classAbstractCollection<E>
 Parameters:
element
 the object to search. Returns:
 whether this set contains the specified element.

iterator
Creates an iterator over all elements in this set. In current implementation, the iterator does not support element removal. 
spliterator
Creates an iterator over all elements in this set. The iterator characteristics are sized, distinct andnonnull
. Specified by:
spliterator
in interfaceCollection<E>
 Specified by:
spliterator
in interfaceIterable<E>
 Specified by:
spliterator
in interfaceSet<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 interfaceCollection<E>
 Returns:
 a possibly parallel stream over the elements in this tree.

queryByBoundingBox
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 invokeBaseStream.sequential()
explicitly. Parameters:
searchRegion
 envelope representing the rectangular search region. Returns:
 elements that are in the given search region (bounds inclusive).
