sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] branch geoapi-4.0 updated: Add documentation and more argument checks.
Date Wed, 15 Jan 2020 11:01:31 GMT
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 <martin.desruisseaux@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++) {


Mime
View raw message