You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2020/01/15 11:01:31 UTC
[sis] branch geoapi-4.0 updated: Add documentation and more
argument checks.
This is an automated email from the ASF dual-hosted git repository.
desruisseaux pushed a commit to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git
The following commit(s) were added to refs/heads/geoapi-4.0 by this push:
new 2ce1448 Add documentation and more argument checks.
2ce1448 is described below
commit 2ce14485aeeb042f6623c0f0a90898a77416e6fb
Author: Martin Desruisseaux <ma...@geomatys.com>
AuthorDate: Wed Jan 15 12:01:04 2020 +0100
Add documentation and more argument checks.
---
.../org/apache/sis/index/tree/NodeIterator.java | 17 ++--
.../java/org/apache/sis/index/tree/PointTree.java | 100 +++++++++++++++------
.../org/apache/sis/index/tree/package-info.java | 4 +
.../apache/sis/index/tree/PointTreeNodeTest.java | 12 +--
4 files changed, 89 insertions(+), 44 deletions(-)
diff --git a/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
index 7fc9fbd..21657de 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
@@ -40,13 +40,6 @@ import org.apache.sis.internal.util.Numerics;
*/
class NodeIterator<E> implements Spliterator<E> {
/**
- * The maximum number of dimensions that this class can support.
- * This value is determined by the maximal capacity of {@link Cursor#quadrants}:
- * 2<sup>{@value #MAX_DIMENSION}</sup> ≤ {@value Long#SIZE}.
- */
- static final int MAX_DIMENSION = 6;
-
- /**
* Sentinel value meaning that iteration is over.
*/
private static final Object[] FINISHED = new Object[0];
@@ -54,7 +47,7 @@ class NodeIterator<E> implements Spliterator<E> {
/**
* The function computing a position for an arbitrary element of the tree.
*/
- private final Function<? super E, double[]> evaluator;
+ private final Function<? super E, double[]> locator;
/**
* A mask with a bit set for all quadrants. This is used as the initial value of
@@ -107,7 +100,7 @@ class NodeIterator<E> implements Spliterator<E> {
bounds[i] = searchRegion.getMinimum(i);
bounds[i+n] = searchRegion.getMaximum(i);
}
- evaluator = tree.evaluator;
+ locator = tree.locator;
cursor = new Cursor<>(tree.treeRegion);
cursor.node = tree.root;
cursor.findIntersections(this);
@@ -146,7 +139,7 @@ class NodeIterator<E> implements Spliterator<E> {
* <p><b>Note:</b> we take "quadrant" name from QuadTree, but this algorithm can actually be used
* with more dimensions.</p>
*
- * @see #MAX_DIMENSION
+ * @see PointTree#MAXIMUM_DIMENSIONS
*/
long quadrants;
@@ -209,7 +202,7 @@ class NodeIterator<E> implements Spliterator<E> {
* which are quadrants 1, 3, 5, <i>etc.</i>
*
* <p>The index in this array is the dimension in which the quadrant do not intersect the search region.
- * The length of this array should be equal to {@link #MAX_DIMENSION}.</p>
+ * The length of this array should be equal to {@link PointTree#MAXIMUM_DIMENSIONS}.</p>
*/
private static final long[] CLEAR_MASKS = {
0b0101010101010101010101010101010101010101010101010101010101010101L,
@@ -341,7 +334,7 @@ class NodeIterator<E> implements Spliterator<E> {
}
@SuppressWarnings("unchecked")
final E element = (E) current[nextIndex++];
- if (filter(evaluator.apply(element))) {
+ if (filter(locator.apply(element))) {
action.accept(element);
return true;
}
diff --git a/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTree.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTree.java
index 30f5d85..33e0d16 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTree.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTree.java
@@ -25,12 +25,27 @@ import org.apache.sis.util.resources.Errors;
/**
- * A <var>k</var>-dimensional tree index for points. For <var>k</var>=2, this is a <cite>point QuadTree</cite>.
- * For <var>k</var>=3, this is point <cite>Octree</cite>. Higher dimensions are also accepted.
+ * A <var>k</var>-dimensional tree index for points.
+ * For <var>k</var>=2, this is a <cite>point QuadTree</cite>.
+ * For <var>k</var>=3, this is a point <cite>Octree</cite>.
+ * Higher dimensions are also accepted up to {@value #MAXIMUM_DIMENSIONS} dimensions.
+ * Elements are stored in this {@code PointTree} as arbitrary non-null objects with their coordinates
+ * provided by a user-specified function. That function expects an element {@code E} in argument and
+ * returns its coordinates as a {@code double[]} array. Elements can be searched by the following methods:
+ *
+ * <ul>
+ * <li>{@link #queryByBoundingBox(Envelope)}</li>
+ * </ul>
+ *
+ * The performances of this {@code 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 {@linkplain #PointTree(Envelope, Function, int) constructor}.
*
* <h2>Thread-safety</h2>
* 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.
+ * after construction, then multiple read operations in concurrent threads are safe. Users can synchronize
+ * with {@link java.util.concurrent.locks.ReadWriteLock} (the read lock must be held for complete duration
+ * of iterations or stream consumptions).
*
* <h2>References:</h2>
* Insertion algorithm is based on design of QuadTree index in H. Samet,
@@ -48,6 +63,12 @@ import org.apache.sis.util.resources.Errors;
*/
public class PointTree<E> {
/**
+ * The maximum number of dimensions (inclusive) that this class currently supports.
+ * Current maximum is {@value}. This restriction come from 2⁶ = {@value Long#SIZE}.
+ */
+ public static final int MAXIMUM_DIMENSIONS = 6;
+
+ /**
* The root node of this <var>k</var>-dimensional tree.
*/
final PointTreeNode root;
@@ -57,12 +78,14 @@ public class PointTree<E> {
* 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.
*/
- private final int capacity;
+ private final int nodeCapacity;
/**
* Number of elements in this <var>k</var>-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).
*/
- private int count;
+ private long count;
/**
* The regions covered by this tree, encoded as a center and a size.
@@ -74,50 +97,71 @@ public class PointTree<E> {
* </ul>
*
* The length of this array is two times the number of dimensions of points in this tree.
+ * This array content should not be modified, until the entire tree is rebuilt.
*/
final double[] treeRegion;
/**
* The function computing a position for an arbitrary element in this tree.
+ * The length of arrays computed by this locator must be equal to {@link #getDimension()}.
*/
- final Function<? super E, double[]> evaluator;
+ final Function<? super E, double[]> locator;
/**
* Creates an initially empty <var>k</var>-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 position computed by {@code evaluator} must have the same number of dimensions.
+ * The number of dimensions of the given envelope determines the number of dimensions of points in this tree.
+ * The positions computed by {@code locator} must have the same number of dimensions than the given envelope.
+ *
+ * <p>The {@code bounds} argument specifies the expected region of points to be added in this {@code PointTree}.
+ * Those bounds do not need to be exact; {@code PointTree} will work even if some points are located outside
+ * those bounds. However performances will be better if the {@linkplain Envelope#getMedian(int) envelope center}
+ * is close to the median of the points to be inserted in the {@code PointTree}, and if the majority of points
+ * are inside those bounds.</p>
*
- * <p>The given {@code capacity} is a threshold value controlling when the content of a node should
+ * <p>The given {@code 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.</p>
*
- * @param bounds bounds of the region of data to be inserted in the <var>k</var>-dimensional tree.
- * @param evaluator function computing a position for an arbitrary element of this tree.
- * @param capacity the capacity of each node.
+ * @param bounds bounds of the region of data to be inserted in the <var>k</var>-dimensional tree.
+ * @param locator function computing a position for an arbitrary element of this tree.
+ * @param nodeCapacity the capacity of each node (not to be confused with a capacity of the tree).
*/
- public PointTree(final Envelope bounds, final Function<? super E, double[]> evaluator, final int capacity) {
+ public PointTree(final Envelope bounds, final Function<? super E, double[]> locator, final int nodeCapacity) {
+ ArgumentChecks.ensureNonNull("bounds", bounds);
+ ArgumentChecks.ensureNonNull("locator", locator);
+ ArgumentChecks.ensureStrictlyPositive("nodeCapacity", nodeCapacity);
final int n = bounds.getDimension();
if (n < 2) {
throw new IllegalArgumentException(Errors.format(Errors.Keys.MismatchedDimension_3, "bounds", 2, n));
}
- if (n > NodeIterator.MAX_DIMENSION) {
+ if (n > MAXIMUM_DIMENSIONS) {
throw new IllegalArgumentException(Errors.format(Errors.Keys.ExcessiveNumberOfDimensions_1, n));
}
treeRegion = new double[n*2];
for (int i=0; i<n; i++) {
- treeRegion[i] = bounds.getMedian(i);
- treeRegion[i+n] = bounds.getSpan(i);
+ ArgumentChecks.ensureFinite("treeRegion", treeRegion[i] = bounds.getMedian(i));
+ ArgumentChecks.ensureFinite("treeRegion", treeRegion[i+n] = bounds.getSpan(i));
}
- this.capacity = Math.max(4, capacity);
- this.evaluator = evaluator;
- this.root = (n == 2) ? new QuadTreeNode() : new PointTreeNode.Default(n);
+ this.nodeCapacity = Math.max(4, nodeCapacity); // Here, 4 is an arbitrary value.
+ this.locator = locator;
+ this.root = (n == 2) ? new QuadTreeNode() : new PointTreeNode.Default(n);
+ }
+
+ /**
+ * Returns the number of dimensions of points in this tree.
+ *
+ * @return the number of dimensions of points in this tree.
+ */
+ public final int getDimension() {
+ return treeRegion.length >>> 1;
}
/**
- * Inserts the specified data into this tree.
+ * Inserts the specified element into this tree.
*
* @param element the element to insert.
* @return always {@code true} in current implementation.
+ * @throws NullPointerException if the given element is null.
*/
public boolean add(final E element) {
ArgumentChecks.ensureNonNull("element", element);
@@ -137,7 +181,7 @@ public class PointTree<E> {
@SuppressWarnings("unchecked")
private void insert(PointTreeNode parent, double[] region, final E element) {
boolean isRegionCopied = false;
- final double[] point = evaluator.apply(element);
+ final double[] point = locator.apply(element);
for (;;) {
final int quadrant = PointTreeNode.quadrant(point, region);
final Object child = parent.getChild(quadrant);
@@ -169,7 +213,7 @@ public class PointTree<E> {
*/
final Object[] data = (Object[]) child;
final int n = data.length;
- if (n < capacity) {
+ if (n < nodeCapacity) {
final Object[] copy = new Object[n+1];
System.arraycopy(data, 0, copy, 0, n);
copy[n] = element;
@@ -198,22 +242,24 @@ public class PointTree<E> {
/**
* Returns the number of elements in this tree.
*
- * @return the number of elements in this tree.
+ * @return the number of elements in this tree, or {@link Integer#MAX_VALUE}
+ * if there is more elements than what an {@code int} can represent.
*/
public int size() {
- return count;
+ // Negative value would be `long` overflow to be returned as MAX_VALUE.
+ return (count >>> Integer.SIZE) == 0 ? (int) count : Integer.MAX_VALUE;
}
/**
- * Performs bounding box search.
+ * Returns all elements in the given bounding box.
*
* @param searchRegion envelope representing the rectangular search region.
* @return elements that are within the given radius from the point.
*/
public Stream<E> queryByBoundingBox(final Envelope searchRegion) {
ArgumentChecks.ensureNonNull("searchRegion", searchRegion);
- ArgumentChecks.ensureDimensionMatches("searchRegion", treeRegion.length >>> 1, searchRegion);
+ ArgumentChecks.ensureDimensionMatches("searchRegion", getDimension(), searchRegion);
return StreamSupport.stream(new NodeIterator<>(this, searchRegion), false);
- // TODO: make parallel after we tested most extensively.
+ // TODO: make parallel by default after we tested most extensively.
}
}
diff --git a/core/sis-feature/src/main/java/org/apache/sis/index/tree/package-info.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/package-info.java
index fa3bc8e..095bf1c 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/index/tree/package-info.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/package-info.java
@@ -18,6 +18,10 @@
/**
* A simple <var>k</var>-dimensional point tree implementation.
*
+ * <h2>Future development</h2>
+ * Current implementation stores only points. We do not yet provide "region QuadTree" or
+ * R-Tree for storing rectangles. A future Apache SIS may add such index in this package.
+ *
* @author Chris Mattmann
* @author Martin Desruisseaux (Geomatys)
* @version 1.1
diff --git a/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeNodeTest.java b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeNodeTest.java
index ca85a1e..038631a 100644
--- a/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeNodeTest.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeNodeTest.java
@@ -34,12 +34,14 @@ import static org.junit.Assert.*;
*/
public final strictfp class PointTreeNodeTest extends TestCase {
/**
- * Verifies the value of {@link NodeIterator#MAX_DIMENSION}.
- * That value is restricted by the capacity of {@code long}.
+ * Verifies the value of {@link PointTree#MAXIMUM_DIMENSIONS}.
+ * That value is restricted by the maximal capacity of {@code long} type
+ * of {@link org.apache.sis.index.tree.NodeIterator.Cursor#quadrants}:
+ * 2<sup>{@value PointTree#MAXIMUM_DIMENSIONS}</sup> ≤ {@value Long#SIZE}.
*/
@Test
public void verifyMaxDimension() {
- assertEquals(Long.SIZE, 1 << NodeIterator.MAX_DIMENSION);
+ assertEquals(Long.SIZE, 1 << PointTree.MAXIMUM_DIMENSIONS);
}
/**
@@ -96,8 +98,8 @@ public final strictfp class PointTreeNodeTest extends TestCase {
final Field f = NodeIterator.class.getDeclaredClasses()[0].getDeclaredField("CLEAR_MASKS");
f.setAccessible(true);
final long[] masks = (long[]) f.get(null);
- assertEquals(NodeIterator.MAX_DIMENSION, masks.length);
- for (int d=0; d<NodeIterator.MAX_DIMENSION; d++) {
+ assertEquals(PointTree.MAXIMUM_DIMENSIONS, masks.length);
+ for (int d=0; d<PointTree.MAXIMUM_DIMENSIONS; d++) {
long expected = 0;
final long m = 1L << d;
for (int i=0; i<Long.SIZE; i++) {