[sis] branch geoapi-4.0 updated: Initial implementation of Spliterator.trySplit() for parallelism during PointTree traversal. Implementation is incomplete since it splits only the first node; we should go down in other nodes too.

[desruisseaux]

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 29ac56d  Initial implementation of Spliterator.trySplit() for 
parallelism during PointTree traversal. Implementation is incomplete since it 
splits only the first node; we should go down in other nodes too.
29ac56d is described below

commit 29ac56de59ea5e9404671992a186ebad41e0c245
Author: Martin Desruisseaux <martin.desruisse...@geomatys.com>
AuthorDate: Wed Jan 15 15:22:34 2020 +0100

    Initial implementation of Spliterator.trySplit() for parallelism during 
PointTree traversal.
    Implementation is incomplete since it splits only the first node; we should 
go down in other nodes too.
---
 .../org/apache/sis/index/tree/NodeIterator.java    | 40 +++++++++++++++++++---
 1 file changed, 35 insertions(+), 5 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 ebf786a..3cf27cc 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
@@ -57,8 +57,8 @@ class NodeIterator<E> implements Spliterator<E> {
     private final long bitmask;
 
     /**
-     * The region on which to iterate. The first half are minimal coordinates
-     * and the second half are maximal coordinates.
+     * The region on which to iterate. The first half are minimal coordinates 
and the second
+     * half are maximal coordinates. The content of this array should not be 
modified.
      */
     private final double[] bounds;
 
@@ -115,6 +115,24 @@ class NodeIterator<E> implements Spliterator<E> {
     }
 
     /**
+     * Creates a new iterator initialized to a copy of the given iterator.
+     *
+     * @param  quadrants  the value to assign to {@link Cursor#quadrants}.
+     *         That bitmask shall not intersect the bitmask of {@code 
other.cursor}.
+     */
+    private NodeIterator(final NodeIterator<E> other, final long quadrants) {
+        final Cursor<E> c = other.cursor;
+        locator           = other.locator;
+        bitmask           = other.bitmask;
+        bounds            = other.bounds;
+        cursor            = new Cursor<>(c.region);
+        cursor.parent     = c.parent;
+        cursor.node       = c.node;
+        cursor.quadrants  = quadrants;
+        current           = next();
+    }
+
+    /**
      * A provider for arrays of elements of child nodes contained in a {@link 
PointTreeNode}.
      * The starting point is {@link PointTree#root}. A new {@link Cursor} 
instance is created
      * for each level when the node at next level is itself a parent of at 
least two nodes
@@ -368,12 +386,24 @@ class NodeIterator<E> implements Spliterator<E> {
     }
 
     /**
-     * If this iterator can be partitioned, returns an iterator covering a 
strict prefix of the elements.
-     *
-     * @todo Checks {@link Cursor#quadrants} and take half of the bits.
+     * If this iterator can be partitioned, returns an iterator covering about 
half of the elements.
+     * Otherwise returns {@code null}.
      */
     @Override
     public final Spliterator<E> trySplit() {
+        final Cursor<E> c = cursor;
+        if (c != null) {
+            long half = 0;
+            for (int n = Long.bitCount(c.quadrants) / 2; n >= 0; --n) {
+                final long q = Long.lowestOneBit(c.quadrants);
+                c.quadrants &= ~q;
+                half |= q;
+            }
+            if (half != 0) {
+                return new NodeIterator<>(this, half);
+            }
+            // TODO: go down in the tree and explore other quadrants.
+        }
         return null;
     }