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
commit f7b4b91831b4c1f202427a93412de0418382ffa4 Author: Martin Desruisseaux <[email protected]> AuthorDate: Fri Jan 17 00:04:31 2020 +0100 Use a pre-allocated buffer for storing the coordinate values during traversal of elements in a PointTree. --- .../org/apache/sis/index/tree/NodeIterator.java | 56 ++++++++++------ .../java/org/apache/sis/index/tree/PointTree.java | 75 +++++++++++++++++----- .../org/apache/sis/index/tree/PointTreeTest.java | 8 ++- 3 files changed, 101 insertions(+), 38 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 3bd0a29..c3aeb40 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 @@ -19,7 +19,6 @@ package org.apache.sis.index.tree; import java.util.Arrays; import java.util.Spliterator; import java.util.function.Consumer; -import java.util.function.Function; import org.opengis.geometry.Envelope; import org.apache.sis.internal.util.Numerics; @@ -28,8 +27,8 @@ import org.apache.sis.internal.util.Numerics; * An iterator over the elements contained in a {@link PointTreeNode}. * The iterator applies a first filtering of elements by traversing only the nodes that <em>may</em> * intersect the Area Of Interest (AOI). But after a node has been retained, an additional check for - * inclusion may be necessary. That additional check is performed by {@link #filter(double[])} and - * can be overridden by subclasses. + * inclusion may be necessary. That additional check is performed by {@link #filter(Object)} and can + * be overridden by subclasses. * * @author Martin Desruisseaux (Geomatys) * @version 1.1 @@ -39,7 +38,7 @@ import org.apache.sis.internal.util.Numerics; * @since 1.1 * @module */ -class NodeIterator<E> implements Spliterator<E> { +class NodeIterator<E> implements Spliterator<E>, Cloneable { /** * Sentinel value meaning that iteration is over. */ @@ -48,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[]> locator; + private final PointTree.Locator<? super E> locator; /** * A mask with a bit set for all quadrants. This is used as the initial value of @@ -63,6 +62,11 @@ class NodeIterator<E> implements Spliterator<E> { private final double[] bounds; /** + * A pre-allocated buffer where to store point coordinates, or {@code null} if not needed. + */ + private double[] point; + + /** * The object to use for updating the {@link #current} field, or {@code null} if none. * This {@code NodeIterator} starts by returning elements in the {@link #current} array. * When iteration over {@link #current} array is finished, {@code NodeIterator} uses the @@ -99,6 +103,7 @@ class NodeIterator<E> implements Spliterator<E> { bitmask = Numerics.bitmask(1 << n) - 1; bounds = new double[n*2]; if (searchRegion != null) { + point = new double[n]; for (int i = n; --i >= 0;) { bounds[i] = searchRegion.getMinimum(i); bounds[i+n] = searchRegion.getMaximum(i); @@ -108,28 +113,33 @@ class NodeIterator<E> implements Spliterator<E> { Arrays.fill(bounds, n, n*2, Double.POSITIVE_INFINITY); } locator = tree.locator; - cursor = new Cursor<>(tree.treeRegion); + cursor = new Cursor<>(tree.treeRegion); cursor.node = tree.root; cursor.findIntersections(this); current = next(); } /** - * Creates a new iterator initialized to a copy of the given iterator. + * Invoked after {@link #clone()} for copying the fields that can not be shared between two + * {@link NodeIterator} instances. This is used for {@link #trySplit()} implementation. * * @param quadrants the value to assign to {@link Cursor#quadrants}. * That bitmask shall not intersect the bitmask of {@code other.cursor}. + * @return whether this iterator has to data to iterate. */ - private NodeIterator(final NodeIterator<E> other, final long quadrants) { - final Cursor<E> c = other.cursor; - locator = other.locator; - bitmask = other.bitmask; - bounds = other.bounds; + private boolean postClone(final long quadrants) { + final Cursor<E> c = cursor; + if (point != null) { + point = new double[point.length]; + } cursor = new Cursor<>(c.region); cursor.parent = c.parent; cursor.node = c.node; cursor.quadrants = quadrants; + recycle = null; + nextIndex = 0; current = next(); + return (current != null); } /** @@ -359,7 +369,7 @@ class NodeIterator<E> implements Spliterator<E> { } @SuppressWarnings("unchecked") final E element = (E) current[nextIndex++]; - if (filter(locator.apply(element))) { + if (filter(element)) { action.accept(element); return true; } @@ -367,17 +377,18 @@ class NodeIterator<E> implements Spliterator<E> { } /** - * Returns whether the given position is included in the search region. + * Returns whether the given element is included in the search region. * The default implementation verifies if the point is included in the bounding box. * Subclasses may override, for example for restricting the points to a radius around a central location. * - * @param position the position to check for inclusion. - * @return whether the position is in the search region. + * @param element the element to check for inclusion. + * @return whether the element is in the search region. */ - protected boolean filter(final double[] position) { + protected boolean filter(final E element) { + locator.getPositionOf(element, point); final int n = bounds.length >>> 1; for (int i = n; --i >= 0;) { - final double p = position[i]; + final double p = point[i]; if (!(p >= bounds[i] && p <= bounds[i+n])) { // Use '!' for catching NaN. return false; } @@ -399,9 +410,12 @@ class NodeIterator<E> implements Spliterator<E> { c.quadrants &= ~q; half |= q; } - if (half != 0) { - return new NodeIterator<>(this, half); - // TODO: check if new.current != null. + if (half != 0) try { + @SuppressWarnings("unchecked") + final NodeIterator<E> second = (NodeIterator<E>) clone(); + if (second.postClone(half)) return second; + } catch (CloneNotSupportedException e) { + throw new AssertionError(e); } // TODO: go down in the tree and explore other nodes. } 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 74688e9..4e607dd 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 @@ -19,12 +19,12 @@ package org.apache.sis.index.tree; import java.io.Serializable; import java.util.Optional; import java.util.AbstractSet; +import java.util.Collection; 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; import org.opengis.geometry.Envelope; import org.opengis.referencing.crs.CoordinateReferenceSystem; import org.apache.sis.util.ArgumentChecks; @@ -50,7 +50,7 @@ import org.apache.sis.util.collection.CheckedContainer; * * 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(Class, Envelope, Function, int, boolean) constructor}. + * More details are given in the {@linkplain #PointTree(Class, Envelope, Locator, int, boolean) constructor}. * * <h2>Thread-safety</h2> * This class is not thread-safe when the tree content is modified. But if the tree is kept unmodified @@ -81,6 +81,23 @@ import org.apache.sis.util.collection.CheckedContainer; */ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, Serializable { /** + * Provides the coordinates of any element stored in {@link PointTree}. + * + * @param <E> the type of elements stored in this tree. + */ + @FunctionalInterface + public interface Locator<E> { + /** + * Provides the coordinates of the given element. The coordinate shall be written in the supplied array. + * The array length will be {@link PointTree#getDimension()} and this method shall overwrite all array values. + * + * @param element the element for which to get the coordinates. + * @param dest a pre-allocated array where to store the coordinate values. + */ + void getPositionOf(E element, double[] dest); + } + + /** * For cross-version compatibility. */ private static final long serialVersionUID = 488727778652772913L; @@ -142,10 +159,10 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, final double[] treeRegion; /** - * The function computing a position for an arbitrary element in this tree. + * Function computing the position of any element in this tree. * The length of arrays computed by this locator must be equal to {@link #getDimension()}. */ - final Function<? super E, double[]> locator; + final Locator<? super E> locator; /** * Whether the stream can be parallel by default. @@ -188,13 +205,13 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, * * @param elementType the base type of all elements in this tree. * @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 locator function computing the position of any element in this tree. * @param nodeCapacity the capacity of each node (not to be confused with a capacity of the tree). * @param parallel whether the stream can be parallel by default. * Should be {@code false} if the given {@code locator} is not thread-safe. */ public PointTree(final Class<E> elementType, final Envelope bounds, - final Function<? super E, double[]> locator, final int nodeCapacity, final boolean parallel) + final Locator<? super E> locator, final int nodeCapacity, final boolean parallel) { ArgumentChecks.ensureNonNull ("elementType", elementType); ArgumentChecks.ensureNonNull ("bounds", bounds); @@ -300,9 +317,32 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, @Override public boolean add(final E element) { ArgumentChecks.ensureNonNull("element", element); - final boolean p = insert(root, treeRegion, element); - if (p) count++; - return p; + final boolean modified = insert(root, treeRegion, element, new double[getDimension()]); + if (modified) count++; + return modified; + } + + /** + * Inserts all elements from the specified collection into this tree if they are not already present. + * + * @param elements the elements to insert. + * @return {@code true} if at least one element has been added. + * @throws NullPointerException if an element is null. + */ + @Override + public boolean addAll(final Collection<? extends E> elements) { + ArgumentChecks.ensureNonNull("elements", elements); + final double[] buffer = new double[getDimension()]; + boolean modified = false; + int i = 0; + for (final E element : elements) { + ArgumentChecks.ensureNonNullElement("element", i++, element); + if (insert(root, treeRegion, element, buffer)) { + modified = true; + count++; + } + } + return modified; } /** @@ -312,12 +352,13 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<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. + * @param point a pre-allocated array where to store the coordinates. This method will write in this array. * @return {@code true} if the element has been added, or {@code false} if it was already present. */ @SuppressWarnings("unchecked") - private boolean insert(PointTreeNode parent, double[] region, final E element) { + private boolean insert(PointTreeNode parent, double[] region, final E element, final double[] point) { boolean isRegionCopied = false; - final double[] point = locator.apply(element); + locator.getPositionOf(element, point); for (;;) { final int quadrant = PointTreeNode.quadrant(point, region); final Object child = parent.getChild(quadrant); @@ -372,8 +413,9 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, } PointTreeNode.enterQuadrant(region, quadrant); final PointTreeNode branch = parent.newInstance(); + final double[] buffer = new double[point.length]; for (final Object e : data) { - insert(branch, region, (E) e); + insert(branch, region, (E) e, buffer); } parent.setChild(quadrant, branch); parent = branch; @@ -394,7 +436,8 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, } PointTreeNode parent = root; final double[] region = treeRegion.clone(); - final double[] point = locator.apply((E) element); + final double[] point = new double[getDimension()]; + locator.getPositionOf((E) element, point); for (;;) { final int quadrant = PointTreeNode.quadrant(point, region); final Object child = parent.getChild(quadrant); @@ -431,9 +474,9 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>, @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;} + @Override public long estimateSize() {return count;} + @Override public int characteristics() {return SIZED | DISTINCT | NONNULL;} + @Override protected boolean filter(E e) {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 081b5c0..460bc53 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 @@ -79,6 +79,12 @@ public final strictfp class PointTreeTest extends TestCase { y = random.nextInt(YMAX - YMIN) + YMIN; } + /** Stores the coordinates of this element in the given array. */ + void getPosition(final double[] dest) { + dest[1] = y; + dest[0] = x; + } + @Override public double getX() {return x;} @Override public double getY() {return y;} @Override public String toString() {return "P(" + x + ", " + y + ')';} @@ -103,7 +109,7 @@ public final strictfp class PointTreeTest extends TestCase { region.width = XMAX - XMIN; region.height = YMAX - YMIN; random = TestUtilities.createRandomNumberGenerator(); - tree = new PointTree<>(Element.class, region, Element::getCoordinate, 5, false); + tree = new PointTree<>(Element.class, region, Element::getPosition, 5, false); int count = random.nextInt(100) + 200; data = new HashSet<>(Containers.hashMapCapacity(count)); while (--count >= 0) {
