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/16 23:05:21 UTC
[sis] branch geoapi-4.0 updated (6fee246 -> f7b4b91)
This is an automated email from the ASF dual-hosted git repository.
desruisseaux pushed a change to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git.
from 6fee246 Review of the methods added in Geometries internal class: - Be more specific about whether we unwrap GeometryWrapper or not. - Keep classical loops in this case. Actually since those loops are very small, applying lambda in Geometries require about twice more lines of code than loops. - Revert to package-private access some methods that, when public, encouraged the writing of code specific to a single geometry library. - Change some implementation to have a consisten [...]
new a3ddd65 Add a copy constructor to PointTree. This constructor share the data structures than can safely be shared, in order to reduce memory usage.
new f7b4b91 Use a pre-allocated buffer for storing the coordinate values during traversal of elements in a PointTree.
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../org/apache/sis/index/tree/NodeIterator.java | 56 ++++++++-----
.../java/org/apache/sis/index/tree/PointTree.java | 96 ++++++++++++++++++----
.../org/apache/sis/index/tree/PointTreeNode.java | 43 +++++++++-
.../org/apache/sis/index/tree/QuadTreeNode.java | 16 ++++
.../org/apache/sis/index/tree/PointTreeTest.java | 8 +-
5 files changed, 179 insertions(+), 40 deletions(-)
[sis] 02/02: Use a pre-allocated buffer for storing the coordinate
values during traversal of elements in a PointTree.
Posted by de...@apache.org.
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 <ma...@geomatys.com>
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) {
[sis] 01/02: Add a copy constructor to PointTree. This constructor
share the data structures than can safely be shared,
in order to reduce memory usage.
Posted by de...@apache.org.
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 a3ddd65ea0f8d69b3de1c02b2b99e830b259fad1
Author: Martin Desruisseaux <ma...@geomatys.com>
AuthorDate: Thu Jan 16 23:03:13 2020 +0100
Add a copy constructor to PointTree. This constructor share the data structures than can safely be shared, in order to reduce memory usage.
---
.../java/org/apache/sis/index/tree/PointTree.java | 21 ++++++++++-
.../org/apache/sis/index/tree/PointTreeNode.java | 43 +++++++++++++++++++++-
.../org/apache/sis/index/tree/QuadTreeNode.java | 16 ++++++++
3 files changed, 78 insertions(+), 2 deletions(-)
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 b1e0e29..74688e9 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
@@ -136,7 +136,8 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<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.
+ * This array content should not be modified, unless the entire tree is rebuilt (keep in
+ * mind that this array may be shared by {@link PointTree} copies).
*/
final double[] treeRegion;
@@ -153,6 +154,24 @@ public class PointTree<E> extends AbstractSet<E> implements CheckedContainer<E>,
private final boolean parallel;
/**
+ * Creates a new tree initialized to a copy of the given tree.
+ * This copy constructor shares some data structure from the {@code other} tree for reducing memory usage,
+ * but the two trees are nevertheless independent (changes in a tree does not affect the other tree).
+ *
+ * @param other the other tree to copy.
+ */
+ public PointTree(final PointTree<E> other) {
+ root = (PointTreeNode) other.root.clone();
+ elementType = other.elementType;
+ crs = other.crs;
+ nodeCapacity = other.nodeCapacity;
+ count = other.count;
+ treeRegion = other.treeRegion;
+ locator = other.locator;
+ parallel = other.parallel;
+ }
+
+ /**
* 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 positions computed by {@code locator} must have the same number of dimensions than the given envelope.
diff --git a/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTreeNode.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTreeNode.java
index a424550..87b544b 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTreeNode.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTreeNode.java
@@ -48,7 +48,7 @@ import java.io.Serializable;
* @since 1.1
* @module
*/
-abstract class PointTreeNode implements Serializable {
+abstract class PointTreeNode implements Cloneable, Serializable {
/**
* For cross-version compatibility.
*/
@@ -158,6 +158,22 @@ abstract class PointTreeNode implements Serializable {
abstract PointTreeNode newInstance();
/**
+ * Returns a clone of this node. This is invoked when creating a copy of {@link PointTree}.
+ * The clone is a semi-deep clone: all children that are instances of {@link PointTreeNode}
+ * shall be cloned recursively, but instances of {@code Object[]} (the leaf nodes) are not
+ * cloned. It is safe to not clone the {@code Object[]} arrays because {@link PointTree}
+ * uses a copy-on-write strategy when data need to be modified.
+ */
+ @Override
+ protected Object clone() {
+ try {
+ return super.clone();
+ } catch (CloneNotSupportedException e) {
+ throw new AssertionError(e);
+ }
+ }
+
+ /**
* Default implementation of {@link PointTreeNode} when no specialized class is available.
* This default implementation stores children in an array. The usage of arrays allows
* arbitrary lengths, but implies one more object to be created for each node instance.
@@ -187,6 +203,22 @@ abstract class PointTreeNode implements Serializable {
}
/**
+ * Creates a new node initialized to a copy of the given node.
+ *
+ * @see #clone()
+ */
+ private Default(final Default other) {
+ children = other.children.clone();
+ for (int i=0; i<children.length; i++) {
+ final Object value = children[i];
+ if (value instanceof PointTreeNode) {
+ children[i] = ((PointTreeNode) value).clone();
+ }
+ // Do not clone arrays because we use them as copy-on-write data structures.
+ }
+ }
+
+ /**
* Creates a new instance of the same class than this node.
*/
@Override
@@ -223,5 +255,14 @@ abstract class PointTreeNode implements Serializable {
final void setChild(final int quadrant, final Object child) {
children[quadrant] = child;
}
+
+ /**
+ * Returns a clone of this node. This is invoked when creating a copy of {@link PointTree}.
+ */
+ @Override
+ @SuppressWarnings("CloneDoesntCallSuperClone")
+ protected Object clone() {
+ return new Default(this);
+ }
}
}
diff --git a/core/sis-feature/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
index 1b4e676..c33af7d 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
@@ -112,4 +112,20 @@ final class QuadTreeNode extends PointTreeNode {
default: throw new IndexOutOfBoundsException(/*quadrant*/); // TODO: uncomment with JDK9.
}
}
+
+ /**
+ * Returns a clone of this node. This is invoked when creating a copy of {@link PointTree}.
+ */
+ @Override
+ protected Object clone() {
+ final QuadTreeNode c = (QuadTreeNode) super.clone();
+ for (int i=0; i<4; i++) {
+ final Object value = c.getChild(i);
+ if (value instanceof PointTreeNode) {
+ c.setChild(i, ((PointTreeNode) value).clone());
+ }
+ // Do not clone arrays because we use them as copy-on-write data structures.
+ }
+ return c;
+ }
}