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: First version of PointTree as a java.util.Set implementation. Optimized version of `contains` and `remove` to be provided in a next commit.
Date Wed, 15 Jan 2020 12:06:36 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 5d975b2  First version of PointTree as a java.util.Set implementation. Optimized
version of `contains` and `remove` to be provided in a next commit.
5d975b2 is described below

commit 5d975b230019075b782994b4d1f3ba72838f4070
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Wed Jan 15 13:05:54 2020 +0100

    First version of PointTree as a java.util.Set implementation.
    Optimized version of `contains` and `remove` to be provided in a next commit.
---
 .../org/apache/sis/index/tree/NodeIterator.java    | 21 ++++--
 .../java/org/apache/sis/index/tree/PointTree.java  | 83 ++++++++++++++++------
 .../org/apache/sis/index/tree/PointTreeTest.java   | 11 +--
 .../src/test/java/org/apache/sis/test/Assert.java  |  1 +
 4 files changed, 84 insertions(+), 32 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 21657de..ebf786a 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
@@ -16,6 +16,7 @@
  */
 package org.apache.sis.index.tree;
 
+import java.util.Arrays;
 import java.util.Spliterator;
 import java.util.function.Consumer;
 import java.util.function.Function;
@@ -90,15 +91,21 @@ class NodeIterator<E> implements Spliterator<E> {
 
     /**
      * Creates a new iterator for the specified search region.
+     * If the given region is null, then infinite bounds are assumed.
      */
     @SuppressWarnings("ThisEscapedInObjectConstruction")
     NodeIterator(final PointTree<E> tree, final Envelope searchRegion) {
-        final int n = searchRegion.getDimension();
+        final int n = tree.getDimension();
         bitmask = Numerics.bitmask(1 << n) - 1;
         bounds  = new double[n*2];
-        for (int i = n; --i >= 0;) {
-            bounds[i]   = searchRegion.getMinimum(i);
-            bounds[i+n] = searchRegion.getMaximum(i);
+        if (searchRegion != null) {
+            for (int i = n; --i >= 0;) {
+                bounds[i]   = searchRegion.getMinimum(i);
+                bounds[i+n] = searchRegion.getMaximum(i);
+            }
+        } else {
+            Arrays.fill(bounds, 0, n,   Double.NEGATIVE_INFINITY);
+            Arrays.fill(bounds, n, n*2, Double.POSITIVE_INFINITY);
         }
         locator = tree.locator;
         cursor = new Cursor<>(tree.treeRegion);
@@ -374,7 +381,7 @@ class NodeIterator<E> implements Spliterator<E> {
      * Returns an estimate of the number of elements or {@link Long#MAX_VALUE} if too expensive
to compute.
      */
     @Override
-    public final long estimateSize() {
+    public long estimateSize() {
         return Long.MAX_VALUE;
     }
 
@@ -382,7 +389,7 @@ class NodeIterator<E> implements Spliterator<E> {
      * Returns a set of characteristics of this iterator and its elements.
      */
     @Override
-    public final int characteristics() {
-        return ORDERED | NONNULL;
+    public int characteristics() {
+        return DISTINCT | NONNULL;
     }
 }
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 33e0d16..2033d81 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
@@ -16,6 +16,11 @@
  */
 package org.apache.sis.index.tree;
 
+import java.io.Serializable;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.Spliterator;
+import java.util.Spliterators;
 import java.util.stream.Stream;
 import java.util.stream.StreamSupport;
 import java.util.function.Function;
@@ -30,8 +35,11 @@ import org.apache.sis.util.resources.Errors;
  * 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:
+ * computed by a user-specified {@code locator} function. That function expects an element
{@code E}
+ * in argument and returns its coordinates as a {@code double[]} array.
+ * The coordinates of each elements must be <em>stable</em>, i.e. applying the
{@code locator} function
+ * twice on the same element must return the same coordinates.
+ * Searches based on element coordinates can be done with the following methods:
  *
  * <ul>
  *   <li>{@link #queryByBoundingBox(Envelope)}</li>
@@ -47,6 +55,10 @@ import org.apache.sis.util.resources.Errors;
  * with {@link java.util.concurrent.locks.ReadWriteLock} (the read lock must be held for
complete duration
  * of iterations or stream consumptions).
  *
+ * <h2>Serialization</h2>
+ * This tree is serializable if all elements in the tree are also serializable. However the
serialization
+ * details is implementation specific and may change in any future Apache SIS version.
+ *
  * <h2>References:</h2>
  * Insertion algorithm is based on design of QuadTree index in H. Samet,
  * <u>The Design and Analysis of Spatial Data Structures</u>.
@@ -61,7 +73,7 @@ import org.apache.sis.util.resources.Errors;
  * @since 1.1
  * @module
  */
-public class PointTree<E> {
+public class PointTree<E> extends AbstractSet<E> implements Serializable {
     /**
      * The maximum number of dimensions (inclusive) that this class currently supports.
      * Current maximum is {@value}. This restriction come from 2⁶ = {@value Long#SIZE}.
@@ -157,17 +169,30 @@ public class PointTree<E> {
     }
 
     /**
-     * Inserts the specified element into this tree.
+     * Returns 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.
+     */
+    @Override
+    public int size() {
+        // Negative value would be `long` overflow to be returned as MAX_VALUE.
+        return (count >>> Integer.SIZE) == 0 ? (int) count : Integer.MAX_VALUE;
+    }
+
+    /**
+     * Inserts the specified element into this tree if it is not already present.
      *
      * @param  element  the element to insert.
-     * @return always {@code true} in current implementation.
+     * @return {@code true} if the element has been added, or {@code false} if it was already
present.
      * @throws NullPointerException if the given element is null.
      */
+    @Override
     public boolean add(final E element) {
         ArgumentChecks.ensureNonNull("element", element);
-        insert(root, treeRegion, element);
-        count++;
-        return true;
+        final boolean p = insert(root, treeRegion, element);
+        if (p) count++;
+        return p;
     }
 
     /**
@@ -177,9 +202,10 @@ public class PointTree<E> {
      * @param  parent   the parent where to add the given data.
      * @param  region   region of current node, as the center in first half and size in second
half.
      * @param  element  the element to insert.
+     * @return {@code true} if the element has been added, or {@code false} if it was already
present.
      */
     @SuppressWarnings("unchecked")
-    private void insert(PointTreeNode parent, double[] region, final E element) {
+    private boolean insert(PointTreeNode parent, double[] region, final E element) {
         boolean isRegionCopied = false;
         final double[] point = locator.apply(element);
         for (;;) {
@@ -191,7 +217,7 @@ public class PointTree<E> {
              */
             if (child == null) {
                 parent.setChild(quadrant, new Object[] {element});
-                return;
+                return true;
             }
             /*
              * If the quadrant where to store the element is a parent containing other nodes,
@@ -208,17 +234,22 @@ public class PointTree<E> {
                 continue;
             }
             /*
-             * At this point we reached a leaf of the tree. Store the element in that leaf
-             * if there is enough room.
+             * At this point we reached a leaf of the tree. First, verify that the element
is not
+             * already present. If not, store the element in that leaf if there is enough
room.
              */
             final Object[] data = (Object[]) child;
             final int n = data.length;
+            for (int i=0; i<n; i++) {
+                if (element.equals(data[i])) {
+                    return false;
+                }
+            }
             if (n < nodeCapacity) {
                 final Object[] copy = new Object[n+1];
                 System.arraycopy(data, 0, copy, 0, n);
                 copy[n] = element;
                 parent.setChild(quadrant, copy);
-                return;                                     // Leaf node can take the data
— done.
+                return true;                                // Leaf node can take the data
— done.
             }
             /*
              * Leaf can not add the given element because the leaf has reached its maximal
capacity.
@@ -240,14 +271,26 @@ public class PointTree<E> {
     }
 
     /**
-     * Returns 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.
+     * Creates an iterator over all elements in this set.
+     * In current implementation, the iterator does not support element removal.
      */
-    public int size() {
-        // Negative value would be `long` overflow to be returned as MAX_VALUE.
-        return (count >>> Integer.SIZE) == 0 ? (int) count : Integer.MAX_VALUE;
+    @Override
+    public Iterator<E> iterator() {
+        return Spliterators.iterator(spliterator());
+    }
+
+    /**
+     * Creates an iterator over all elements in this set. The iterator characteristics are
+     * {@linkplain Spliterator#SIZED sized}, {@linkplain Spliterator#DISTINCT distinct} and
+     * {@link Spliterator#NONNULL non-null}.
+     */
+    @Override
+    public Spliterator<E> spliterator() {
+        return new NodeIterator<E>(this, null) {
+            @Override public    long    estimateSize()     {return count;}
+            @Override public    int     characteristics()  {return SIZED | DISTINCT | NONNULL;}
+            @Override protected boolean filter(double[] p) {return true;}
+        };
     }
 
     /**
diff --git a/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeTest.java b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeTest.java
index 9768fcf..fbe80a8 100644
--- a/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeTest.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeTest.java
@@ -16,20 +16,20 @@
  */
 package org.apache.sis.index.tree;
 
-import java.util.List;
-import java.util.ArrayList;
 import java.util.Set;
 import java.util.HashSet;
 import java.util.Random;
 import org.opengis.geometry.Envelope;
-import org.apache.sis.geometry.DirectPosition2D;
 import org.apache.sis.geometry.Envelope2D;
+import org.apache.sis.geometry.DirectPosition2D;
+import org.apache.sis.util.collection.Containers;
 import org.apache.sis.test.DependsOn;
 import org.apache.sis.test.TestCase;
 import org.apache.sis.test.TestUtilities;
 import org.junit.Test;
 
 import static org.junit.Assert.*;
+import static org.apache.sis.test.Assert.assertSetEquals;
 
 
 /**
@@ -61,7 +61,7 @@ public final strictfp class PointTreeTest extends TestCase {
     /**
      * All data added to the {@link #tree}, for comparison purpose.
      */
-    private List<Element> data;
+    private Set<Element> data;
 
     /**
      * The elements to be added in the {@link PointTree} to test.
@@ -102,12 +102,13 @@ public final strictfp class PointTreeTest extends TestCase {
         random = TestUtilities.createRandomNumberGenerator();
         tree = new PointTree<>(region, Element::getCoordinate, 5);
         int count = random.nextInt(100) + 200;
-        data = new ArrayList<>(count);
+        data = new HashSet<>(Containers.hashMapCapacity(count));
         while (--count >= 0) {
             final Element e = new Element(random);
             assertEquals(data.add(e), tree.add(e));
             assertEquals(data.size(), tree.size());
         }
+        assertSetEquals(data, tree);
     }
 
     /**
diff --git a/core/sis-utility/src/test/java/org/apache/sis/test/Assert.java b/core/sis-utility/src/test/java/org/apache/sis/test/Assert.java
index 36d0edc..53c3482 100644
--- a/core/sis-utility/src/test/java/org/apache/sis/test/Assert.java
+++ b/core/sis-utility/src/test/java/org/apache/sis/test/Assert.java
@@ -262,6 +262,7 @@ public strictfp class Assert extends org.opengis.test.Assert {
         }
         if (expected instanceof Set<?> && actual instanceof Set<?>) {
             assertEquals("Set.equals(Object) failed:", expected, actual);
+            assertEquals("Unexpected hash code value.", expected.hashCode(), actual.hashCode());
         }
     }
 


Mime
View raw message