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 c2a2897 Move QuadTree implementation into KDTree after generalization
to the n-dimensional case. Tested in two-dimensional case but not yet with
higher dimensions. For now the maximal number of dimensions is 6.
c2a2897 is described below
commit c2a2897095a96cdbc6b233aee1731a818e18e57a
Author: Martin Desruisseaux <[email protected]>
AuthorDate: Tue Jan 14 20:12:18 2020 +0100
Move QuadTree implementation into KDTree after generalization to the
n-dimensional case.
Tested in two-dimensional case but not yet with higher dimensions.
For now the maximal number of dimensions is 6.
---
.../java/org/apache/sis/index/tree/KDTree.java | 181 ++++++++++++++++++++-
.../java/org/apache/sis/index/tree/KDTreeNode.java | 131 ++++++++++++++-
.../org/apache/sis/index/tree/NodeIterator.java | 165 ++++++++++++-------
.../java/org/apache/sis/index/tree/QuadTree.java | 140 +---------------
.../org/apache/sis/index/tree/QuadTreeNode.java | 81 +++------
.../apache/sis/index/tree/NodeIteratorTest.java | 112 +++++++++++++
.../apache/sis/index/tree/QuadTreeNodeTest.java | 56 -------
.../org/apache/sis/index/tree/QuadTreeTest.java | 32 ++--
.../apache/sis/test/suite/StorageTestSuite.java | 2 +-
9 files changed, 562 insertions(+), 338 deletions(-)
diff --git
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
index c3bfef5..61cb721 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
@@ -16,10 +16,17 @@
*/
package org.apache.sis.index.tree;
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+import java.util.function.Function;
+import org.opengis.geometry.Envelope;
+import org.apache.sis.util.ArgumentChecks;
+import org.apache.sis.util.resources.Errors;
+
/**
- * Base class of <var>k</var>-dimensional tree index. For <var>k</var>=2, this
is a {@link QuadTree}.
- * For <var>k</var>=3, this is an {@code Octree}. Higher dimensions are also
accepted.
+ * A <var>k</var>-dimensional tree index for points. For <var>k</var>=2, this
is a point {@link QuadTree}.
+ * For <var>k</var>=3, this is an point {@code Octree}. Higher dimensions are
also accepted.
*
* <h2>Thread-safety</h2>
* This class is not thread-safe when the tree content is modified. But if the
tree is kept unmodified
@@ -33,10 +40,174 @@ package org.apache.sis.index.tree;
* @since 1.1
* @module
*/
-abstract class KDTree<E> {
+class KDTree<E> {
+ /**
+ * The root node of this <var>k</var>-dimensional tree.
+ */
+ final KDTreeNode root;
+
+ /**
+ * The maximal capacity of each node in this tree. It should be a
relatively small number.
+ * 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;
+
+ /**
+ * Number of elements in this <var>k</var>-dimensional tree.
+ */
+ private int count;
+
+ /**
+ * The regions covered by this tree, encoded as a center and a size.
+ * This array contains two parts:
+ *
+ * <ul>
+ * <li>The first half contains coordinates of the point in the center of
the region covered by this tree.</li>
+ * <li>The second half contains the size of the region along each
dimension.</li>
+ * </ul>
+ *
+ * The length of this array is two times the number of dimensions of
points in this tree.
+ */
+ final double[] treeRegion;
+
+ /**
+ * The function computing a position for an arbitrary element in this tree.
+ */
+ final Function<? super E, double[]> evaluator;
+
+ /**
+ * 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.
+ *
+ * <p>The given {@code capacity} 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.
+ */
+ KDTree(final Envelope bounds, final Function<? super E, double[]>
evaluator, final int capacity) {
+ 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) {
+ 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);
+ }
+ this.capacity = Math.max(4, capacity);
+ this.evaluator = evaluator;
+ this.root = (n == 2) ? new QuadTreeNode() : new
KDTreeNode.Default(n);
+ }
+
+ /**
+ * Inserts the specified data into this tree.
+ *
+ * @param element the element to insert.
+ * @return always {@code true} in current implementation.
+ */
+ public boolean add(final E element) {
+ ArgumentChecks.ensureNonNull("element", element);
+ insert(root, treeRegion, element);
+ count++;
+ return true;
+ }
+
+ /**
+ * Inserts the specified data into the given node. This method will
iterate through node children
+ * until a suitable node is found. This method may invoke itself
recursively.
+ *
+ * @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.
+ */
+ @SuppressWarnings("unchecked")
+ private void insert(KDTreeNode parent, double[] region, final E element) {
+ boolean isRegionCopied = false;
+ final double[] point = evaluator.apply(element);
+ for (;;) {
+ final int quadrant = KDTreeNode.quadrant(point, region);
+ final Object child = parent.getChild(quadrant);
+ /*
+ * If the element will be stored in a new quadrant never used
before,
+ * create a leaf node for that new quadrant. This is the easiest
case.
+ */
+ if (child == null) {
+ parent.setChild(quadrant, new Object[] {element});
+ return;
+ }
+ /*
+ * If the quadrant where to store the element is a parent
containing other nodes,
+ * enter in that quadrant and repeat all above checks with that
node as the new parent.
+ * We continue down the tree until a leaf node is found.
+ */
+ if (child instanceof KDTreeNode) {
+ if (!isRegionCopied) {
+ isRegionCopied = true;
+ region = region.clone();
+ }
+ KDTreeNode.enterQuadrant(region, quadrant);
+ parent = (KDTreeNode) child;
+ continue;
+ }
+ /*
+ * At this point we reached a leaf of the tree. Store the element
in that leaf
+ * if there is enough room.
+ */
+ final Object[] data = (Object[]) child;
+ final int n = data.length;
+ if (n < capacity) {
+ 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.
+ }
+ /*
+ * Leaf can not add the given element because the leaf has reached
its maximal capacity.
+ * Replace the leaf node by a parent node and add all previous
elements into it. After
+ * data has been copied, continue attempts to insert the element
given to this method.
+ */
+ if (!isRegionCopied) {
+ isRegionCopied = true;
+ region = region.clone();
+ }
+ KDTreeNode.enterQuadrant(region, quadrant);
+ final KDTreeNode branch = parent.newInstance();
+ for (final Object e : data) {
+ insert(branch, region, (E) e);
+ }
+ parent.setChild(quadrant, branch);
+ parent = branch;
+ }
+ }
+
+ /**
+ * Returns the number of elements in this tree.
+ *
+ * @return the number of elements in this tree.
+ */
+ public int size() {
+ return count;
+ }
+
/**
- * Creates an initially empty tree.
+ * Performs bounding box search.
+ *
+ * @param searchRegion envelope representing the rectangular search
region.
+ * @return elements that are within the given radius from the point.
*/
- KDTree() {
+ public Stream<E> queryByBoundingBox(final Envelope searchRegion) {
+ ArgumentChecks.ensureNonNull("searchRegion", searchRegion);
+ ArgumentChecks.ensureDimensionMatches("searchRegion",
treeRegion.length >>> 1, searchRegion);
+ return StreamSupport.stream(new NodeIterator<>(this, searchRegion),
false);
+ // TODO: make parallel after we tested most extensively.
}
}
diff --git
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
index 1692c35..3edc329 100644
---
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
+++
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
@@ -53,22 +53,107 @@ abstract class KDTreeNode {
}
/**
+ * Returns the quadrant/octant relative to the given point.
+ * Each bit specifies the relative position for a dimension.
+ * For (<var>x</var>, <var>y</var>, <var>z</var>, <var>t</var>)
coordinates, the pattern is:
+ *
+ * <ul>
+ * <li>Bit 0 is the relative position of <var>x</var> coordinate: 0 for
East and 1 for West.</li>
+ * <li>Bit 1 is the relative position of <var>y</var> coordinate: 0 for
North and 1 for South.</li>
+ * <li>Bit 2 is the relative position of <var>z</var> coordinate: 0 for
up and 1 for down.</li>
+ * <li>Bit 3 is the relative position of <var>t</var> coordinate: 0 for
future and 1 for past.</li>
+ * <li><i>etc.</i> for any additional dimensions.</li>
+ * </ul>
+ *
+ * @param point data (<var>x</var>, <var>y</var>, …) coordinate.
+ * @param region region of current node, as the center in first half and
size in second half.
+ * @return an identification of the quadrant where the given point is
located.
+ */
+ static int quadrant(final double[] point, final double[] region) {
+ int q = 0;
+ for (int i = region.length >>> 1; --i >= 0;) { // Iterate
only over center coordinates.
+ if (point[i] < region[i]) {
+ q |= (1 << i);
+ }
+ }
+ return q;
+ }
+
+ /**
+ * Modifies in place the specified for describing the coordinates of the
specified quadrant.
+ *
+ * @param region region of current node, as the center in first half
and size in second half.
+ * @param quadrant the quadrant as computed by {@link
#quadrant(double[], double[])}.
+ */
+ static void enterQuadrant(final double[] region, final int quadrant) {
+ final int n = region.length >>> 1;
+ for (int i = n; --i >= 0;) {
+ region[i] += factor(quadrant, i) * (region[i+n] *= 0.5); //
TODO: use Math.fma with JDK9.
+ }
+ }
+
+ /**
+ * Returns 0.5 if the given quadrant is in the East/North/Up/Future side,
+ * or -0.5 if in the West/South/Down/Past side.
+ *
+ * @param quadrant the quadrant as computed by {@link
#quadrant(double[], double[])}.
+ * @param dimension the dimension index: 0 for <var>x</var>, 1 for
<var>y</var>, <i>etc.</i>
+ */
+ static double factor(final int quadrant, final int dimension) {
+ /*
+ * The 3FE0000000000000 long value is the bit pattern of 0.5. The
leftmost bit at (Long.SIZE - 1)
+ * is the sign, which we set to the sign encoded in the quadrant
value. This approach allow us to
+ * get the value efficiently, without jump instructions.
+ */
+ return Double.longBitsToDouble(0x3FE0000000000000L |
+ (((long) (quadrant & (1 << dimension))) << (Long.SIZE - 1 -
dimension)));
+ }
+
+ /**
+ * Returns the child of this node that resides in the specified
quadrant/octant.
+ * The return value can be null or an instance of one of those two classes:
+ *
+ * <ul>
+ * <li>Another {@link KDTreeNode} if the node in a quadrant/octant is
itself a parent of other children.</li>
+ * <li>{@code Object[]} if the node in a quadrant/octant is a leaf. In
such case, the array contains elements.
+ * We do not wrap the leaf in another {@link KDTreeNode} for
reducing the number of objects created.</li>
+ * </ul>
+ *
+ * Any other kind of object is an error.
+ *
+ * @param quadrant quadrant/octant of child to get.
+ * @return child in the specified quadrant/octant.
+ * @throws IndexOutOfBoundsException if the specified quadrant/octant is
out of bounds.
+ */
+ abstract Object getChild(int quadrant);
+
+ /**
+ * Sets the node's quadrant/octant to the specified child.
+ * The {@code child} value must be one of the types documented in {@link
#getChild(int)}.
+ *
+ * @param quadrant quadrant/octant where the child resides.
+ * @param child child of this node in the specified quadrant/octant.
+ * @throws IndexOutOfBoundsException if the specified quadrant/octant is
out of bounds.
+ */
+ abstract void setChild(int quadrant, Object child);
+
+ /**
+ * Creates a new instance of the same class than this node.
+ */
+ abstract KDTreeNode newInstance();
+
+ /**
* Default implementation of {@link KDTreeNode} 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.
* Since this class should be used only for relatively large numbers of
dimensions,
* the cost of arrays creation should be less significant compared to
array length.
*/
- private static final class Default extends KDTreeNode {
+ static final class Default extends KDTreeNode {
/**
* The nodes or element values in each quadrant/octant of this node.
- * Each array element can be null or an instance of one of those two
classes:
- *
- * <ul>
- * <li>Another {@link KDTreeNode} if the node in a quadrant/octant
is itself a parent of other children.</li>
- * <li>{@code Object[]} if the node in a quadrant/octant is a leaf.
In such case, the array contains elements.
- * We do not wrap the leaf in another {@link KDTreeNode} for
reducing the number of objects created.</li>
- * </ul>
+ * Each array element can be null or an instance of one of the classes
+ * documented in {@link KDTreeNode#getChild(int)}.
*/
private final Object[] children;
@@ -80,5 +165,35 @@ abstract class KDTreeNode {
Default(final int n) {
children = new Object[n];
}
+
+ /**
+ * Creates a new instance of the same class than this node.
+ */
+ @Override
+ final KDTreeNode newInstance() {
+ return new Default(children.length);
+ }
+
+ /**
+ * Returns the child of this node that resides in the specified
quadrant/octant.
+ *
+ * @param quadrant quadrant/octant of child to get.
+ * @return child in the specified quadrant/octant.
+ */
+ @Override
+ final Object getChild(final int quadrant) {
+ return children[quadrant];
+ }
+
+ /**
+ * Sets the node's quadrant/octant to the specified child.
+ *
+ * @param quadrant quadrant/octant where the child resides.
+ * @param child child of this node in the specified
quadrant/octant.
+ */
+ @Override
+ final void setChild(final int quadrant, final Object child) {
+ children[quadrant] = child;
+ }
}
}
diff --git
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
index 322e724..21952a0 100644
---
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
+++
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
@@ -18,17 +18,17 @@ package org.apache.sis.index.tree;
import java.util.Spliterator;
import java.util.function.Consumer;
-import java.awt.geom.Point2D;
-import java.awt.geom.Rectangle2D;
import java.util.function.Function;
+import org.opengis.geometry.Envelope;
+import org.apache.sis.internal.util.Numerics;
/**
* An iterator over the elements contained in a {@link KDTreeNode}.
* 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(Point2D)}
- * and can be overridden by subclasses.
+ * inclusion may be necessary. That additional check is performed by {@link
#filter(double[])} and
+ * can be overridden by subclasses.
*
* @author Martin Desruisseaux (Geomatys)
* @version 1.1
@@ -40,26 +40,40 @@ import java.util.function.Function;
*/
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];
/**
- * The function computing a position for an arbitrary element of this tree.
+ * The function computing a position for an arbitrary element of the tree.
*/
- private final Function<? super E, ? extends Point2D> evaluator;
+ private final Function<? super E, double[]> evaluator;
/**
- * The region on which to iterate.
+ * A mask with a bit set for all quadrants. This is used as the initial
value of
+ * {@link Cursor#quadrants} before to clear to bits of quadrants to not
search.
*/
- private final double xmin, ymin, xmax, ymax;
+ private final long bitmask;
+
+ /**
+ * The region on which to iterate. The first half are minimal coordinates
+ * and the second half are maximal coordinates.
+ */
+ private final double[] bounds;
/**
* 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
* {@link Cursor} for changing the array reference to the next array. The
iteration then
- * continues until all leaf nodes intersecting the area of interest (AOI)
have been traversed.
+ * continues until all leaf nodes intersecting the search region have been
traversed.
*/
private Cursor<E> cursor;
@@ -82,23 +96,27 @@ class NodeIterator<E> implements Spliterator<E> {
private Cursor<E> recycle;
/**
- * Creates a new iterator for the specified bounding box.
+ * Creates a new iterator for the specified search region.
*/
@SuppressWarnings("ThisEscapedInObjectConstruction")
- NodeIterator(final QuadTree<E> tree, final Rectangle2D region) {
+ NodeIterator(final KDTree<E> tree, final Envelope searchRegion) {
+ final int n = searchRegion.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);
+ }
evaluator = tree.evaluator;
- xmin = region.getMinX();
- ymin = region.getMinY();
- xmax = region.getMaxX();
- ymax = region.getMaxY();
- cursor = new Cursor<>(tree);
+ cursor = new Cursor<>(tree.treeRegion);
+ cursor.node = tree.root;
cursor.findIntersections(this);
current = next();
}
/**
* A provider for arrays of elements of child nodes contained in a {@link
KDTreeNode}.
- * The starting point is {@link QuadTree#root}. A new {@link Cursor}
instance is created
+ * The starting point is {@link KDTree#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
* (if there is only one child node, then this implementation takes a
shortcut).
*/
@@ -118,7 +136,7 @@ class NodeIterator<E> implements Spliterator<E> {
* The node for which to iterate over elements. Only the
quadrants/octants identified
* by the {@link #quadrants} bitmask will be traversed.
*/
- QuadTreeNode node;
+ KDTreeNode node;
/**
* Bitmask of quadrants/octants on which to iterate. Quadrants/octants
are iterated from rightmost
@@ -127,36 +145,28 @@ class NodeIterator<E> implements Spliterator<E> {
*
* <p><b>Note:</b> we take "quadrant" name from {@link QuadTree}, but
this algorithm can actually
* be used with more dimensions.</p>
+ *
+ * @see #MAX_DIMENSION
*/
- int quadrants;
-
- /**
- * (<var>x</var>,<var>y</var>) coordinate in the center of {@link
#node} node,
- * and (<var>Δx</var>,<var>Δy</var>) size of the {@link #node} node.
- */
- private double cx, cy, dx, dy;
+ long quadrants;
/**
- * Creates a new cursor with all values initialized to zero.
- * It is caller responsibility to initialize all fields.
+ * (<var>x</var>,<var>y</var>,…) coordinates in the center of {@link
#node} node,
+ * followed by (<var>Δx</var>,<var>Δy</var>,…) sizes of the {@link
#node} node.
*/
- private Cursor() {
- }
+ private final double[] region;
/**
- * Creates a new cursor initialized to the root node of the given tree.
+ * Creates a new cursor. It is caller responsibility to initialize the
{@link #node} field, the
+ * {@link #parent} field if a parent exists, and to invoke {@link
#findIntersections(NodeIterator)}.
*/
- Cursor(final QuadTree<E> tree) {
- node = tree.root;
- cx = tree.centerX;
- cy = tree.centerY;
- dx = tree.width;
- dy = tree.height;
+ Cursor(final double[] region) {
+ this.region = region.clone(); // Must be cloned because this
class may modify those values.
}
/**
* Computes a bitmask of all quadrants/octants that intersect the
search area. This method
- * must be invoked after {@link #cx}, {@link #cy}, {@link #dx}, {@link
#dy} fields changed.
+ * must be invoked after {@link #region} values changed.
*
* @todo the computation performed in this method is not necessary
when the caller knows that
* the node is fully included in the AOI. We should carry a flag
for this common case.
@@ -164,14 +174,53 @@ class NodeIterator<E> implements Spliterator<E> {
* @param it the iterator which defines the area of interest.
*/
final void findIntersections(final NodeIterator<E> it) {
- quadrants = (1 << 4) - 1;
// Bits initially set for all quadrants.
- if (!(it.xmin <= cx)) quadrants &= ~((1 << QuadTreeNode.NW) | (1
<< QuadTreeNode.SW)); // Clear bits of all quadrant on West side.
- if (!(it.xmax >= cx)) quadrants &= ~((1 << QuadTreeNode.NE) | (1
<< QuadTreeNode.SE)); // Clear bits of all quadrant on East side.
- if (!(it.ymin <= cy)) quadrants &= ~((1 << QuadTreeNode.SE) | (1
<< QuadTreeNode.SW)); // Clear bits of all quadrant on South side.
- if (!(it.ymax >= cy)) quadrants &= ~((1 << QuadTreeNode.NE) | (1
<< QuadTreeNode.NW)); // Clear bits of all quadrant on North side.
+ final double[] bounds = it.bounds;
+ quadrants = it.bitmask; // Bits
initially set for all quadrants.
+ final int n = bounds.length >>> 1;
+ for (int i = n; --i >= 0;) {
+ final double c = region[i];
+ /*
+ * Example: given xmin and xmax the bounds of the search
region in dimension of x,
+ * and cx the x coordinate of the center of current node, then:
+ *
+ * if !(xmin <= cx) then we want to clear the bits of all
quadrants on West side.
+ * if !(xmax >= cx) then we want to clear the bits of all
quadrants on East side.
+ *
+ * Quadrants on the East side are all quadrants with a number
where bit 0 is unset.
+ * Those quadrants are 0, 2, 4, 6, etc. Conversely quadrants
on the West side have
+ * bit 0 set. They are 1, 3, 5, 7, etc.
+ *
+ * Applying the same rational on y:
+ *
+ * if !(ymin <= cy) then we want to clear bits of all
quadrants on South side.
+ * if !(ymax >= cy) then we want to clear bits of all
quadrants on North side.
+ *
+ * Quadrants on the North side have bit 1 unset:
+ */
+ if (!(bounds[i] <= c)) quadrants &= CLEAR_MASKS[i]; //
Use '!' for catching NaN.
+ if (!(bounds[i+n] >= c)) quadrants &= ~CLEAR_MASKS[i];
+ }
}
/**
+ * Masks for clearing the bits of all quadrants that do not intersect
the search region on the left side.
+ * For example for <var>x</var> dimension, this is the mask to apply
if the {@code xmin <= cx} condition
+ * is false. In this example {@code CLEAR_MASKS[0]} clears the bits of
all quadrants on the West side,
+ * 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>
+ */
+ private static final long[] CLEAR_MASKS = {
+
0b0101010101010101010101010101010101010101010101010101010101010101L,
+
0b0011001100110011001100110011001100110011001100110011001100110011L,
+
0b0000111100001111000011110000111100001111000011110000111100001111L,
+
0b0000000011111111000000001111111100000000111111110000000011111111L,
+
0b0000000000000000111111111111111100000000000000001111111111111111L,
+ 0b0000000000000000000000000000000011111111111111111111111111111111L
+ };
+
+ /**
* Creates a new {@code Cursor} for getting element arrays in the
{@linkplain #node} quadrant/octant,
* without changing the state of this {@code Cursor}. This method is
invoked when there is a need to
* iterate in two more more children, in which case we can not yet
discard the information contained
@@ -187,13 +236,13 @@ class NodeIterator<E> implements Spliterator<E> {
final Cursor<E> push(final NodeIterator<E> it, final int q) {
Cursor<E> c = it.recycle;
if (c == null) {
- c = new Cursor<>();
+ c = new Cursor<>(region);
} else {
it.recycle = c.parent;
+ System.arraycopy(region, 0, c.region, 0, region.length);
}
+ KDTreeNode.enterQuadrant(c.region, q);
c.parent = this;
- c.cx = cx + QuadTreeNode.factorX(q) * (c.dx = dx * 0.5); //
TODO: use Math.fma with JDK9.
- c.cy = cy + QuadTreeNode.factorY(q) * (c.dy = dy * 0.5);
return c;
}
@@ -208,8 +257,7 @@ class NodeIterator<E> implements Spliterator<E> {
* @param q the quadrant/octant in which to iterate.
*/
final void moveDown(final int q) {
- cx += QuadTreeNode.factorX(q) * (dx *= 0.5); // Center and
size of the child node.
- cy += QuadTreeNode.factorY(q) * (dy *= 0.5);
+ KDTreeNode.enterQuadrant(region, q);
}
/**
@@ -227,18 +275,19 @@ class NodeIterator<E> implements Spliterator<E> {
}
/**
- * Returns an array of elements that <em>may</em> intersect the area of
interest,
+ * Returns an array of elements that <em>may</em> intersect the search
region,
* or {@link #FINISHED} if the iteration is finished. This method does not
verify
- * if the points are really in the AOI; callers may need to filter the
returned array.
+ * if the points are really in the search region; callers may need to
filter the
+ * returned array.
*
- * @return array of elements that may be in the area of interest (AOI),
+ * @return array of elements that may be in the search region,
* or {@link #FINISHED} if the iteration is finished.
*/
@SuppressWarnings("ReturnOfCollectionOrArrayField")
private Object[] next() {
while (cursor != null) {
while (cursor.quadrants != 0) {
- final int q = Integer.numberOfTrailingZeros(cursor.quadrants);
+ final int q = Long.numberOfTrailingZeros(cursor.quadrants);
cursor.quadrants &= ~(1 << q);
final Object child = cursor.node.getChild(q);
if (child != null) {
@@ -307,13 +356,15 @@ class NodeIterator<E> implements Spliterator<E> {
* @param position the position to check for inclusion.
* @return whether the position is in the search region.
*/
- protected boolean filter(final Point2D position) {
- final double x = position.getX();
- if (x >= xmin && x <= xmax) {
- final double y = position.getY();
- return (y >= ymin && y <= ymax);
+ protected boolean filter(final double[] position) {
+ final int n = bounds.length >>> 1;
+ for (int i = n; --i >= 0;) {
+ final double p = position[i];
+ if (!(p >= bounds[i] && p <= bounds[i+n])) { // Use '!'
for catching NaN.
+ return false;
+ }
}
- return false;
+ return true;
}
/**
diff --git
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
index 22c4475..34db1c2 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
@@ -16,16 +16,12 @@
*/
package org.apache.sis.index.tree;
-import java.util.stream.Stream;
import java.util.function.Function;
-import java.awt.geom.Point2D;
-import java.awt.geom.Rectangle2D;
-import java.util.stream.StreamSupport;
-import org.apache.sis.util.ArgumentChecks;
+import org.opengis.geometry.Envelope;
/**
- * Implementation of QuadTree Index.
+ * Implementation of a point QuadTree Index.
* See {@link KDTree} for a note about thread-safety.
*
* <p><b>References:</b></p>
@@ -44,140 +40,14 @@ import org.apache.sis.util.ArgumentChecks;
*/
public final class QuadTree<E> extends KDTree<E> {
/**
- * The root node of this QuadTree.
- */
- final QuadTreeNode root;
-
- /**
- * The maximal capacity of each node in this tree. Should be a relatively
small number.
- * If the number of elements in a leaf node exceeds this capacity, then
the node will be
- * transformed into a parent node with 4 children.
- */
- private final int capacity;
-
- /**
- * Number of elements in this QuadTree.
- */
- private int count;
-
- /**
- * Coordinates of the point in the center of the area of interest.
- */
- final double centerX, centerY;
-
- /**
- * Size of the area of interest.
- */
- final double width, height;
-
- /**
- * The function computing a position for an arbitrary element of this tree.
- */
- final Function<? super E, ? extends Point2D> evaluator;
-
- /**
* Creates an initially empty QuadTree with the given capacity for each
node.
- * The capacity should be a relatively small number. If the number of
elements
- * in a leaf node exceeds this capacity, then the node will be transformed
into
- * a parent node with 4 children.
+ * The given envelope must be two-dimensional.
*
* @param bounds bounds of the region of data to be inserted in the
QuadTree.
* @param evaluator function computing a position for an arbitrary
element of this tree.
* @param capacity the capacity of each node.
*/
- public QuadTree(final Rectangle2D bounds, final Function<? super E, ?
extends Point2D> evaluator, final int capacity) {
- this.centerX = bounds.getCenterX();
- this.centerY = bounds.getCenterY();
- this.width = bounds.getWidth();
- this.height = bounds.getHeight();
- this.capacity = Math.max(4, capacity);
- this.evaluator = evaluator;
- this.root = new QuadTreeNode();
- }
-
- /**
- * Inserts the specified data into this QuadTree.
- *
- * @param element the element to insert.
- * @return always {@code true} in current implementation.
- */
- public boolean add(final E element) {
- ArgumentChecks.ensureNonNull("element", element);
- insert(root, centerX, centerY, width, height, element);
- count++;
- return true;
- }
-
- /**
- * Inserts the specified data into the given node. This method will
iterate through node children
- * until a suitable node is found. This method may invoke itself
recursively.
- *
- * @param parent the parent where to add the given data.
- * @param cx <var>x</var> coordinate in the center of {@code
parent} node.
- * @param cy <var>y</var> coordinate in the center of {@code
parent} node.
- * @param dx size of the {@code parent} node along the <var>x</var>
axis.
- * @param dy size of the {@code parent} node along the <var>y</var>
axis.
- * @param element the element to insert.
- */
- @SuppressWarnings("unchecked")
- private void insert(QuadTreeNode parent, double cx, double cy, double dx,
double dy, final E element) {
- final Point2D position = evaluator.apply(element);
- final double x = position.getX();
- final double y = position.getY();
- for (;;) {
- final int q = QuadTreeNode.quadrant(x, y, cx, cy);
- final Object child = parent.getChild(q);
- if (child == null) {
- // New quadrant created in an existing parent (easy case).
- parent.setChild(q, new Object[] {element});
- break;
- }
- cx += QuadTreeNode.factorX(q) * (dx *= 0.5); // Center and
size of the child node.
- cy += QuadTreeNode.factorY(q) * (dy *= 0.5); // TODO: use
Math.fma with JDK9.
- if (child instanceof QuadTreeNode) {
- parent = (QuadTreeNode) child; // Continue
until leaf node is found.
- } else {
- final Object[] data = (Object[]) child;
- final int n = data.length;
- if (n < capacity) {
- final Object[] copy = new Object[n+1];
- System.arraycopy(data, 0, copy, 0, n);
- copy[n] = element;
- parent.setChild(q, copy);
- break; // Leaf node
can take the data — done.
- }
- /*
- * Leaf can not add the given element because the leaf has
reached its maximal capacity.
- * Replace the leaf node by a parent node and add all previous
elements into it. After
- * data has been copied, continue attempts to insert the
element given to this method.
- */
- final QuadTreeNode branch = new QuadTreeNode();
- for (final Object e : data) {
- insert(branch, cx, cy, dx, dy, (E) e);
- }
- parent.setChild(q, branch);
- parent = branch;
- }
- }
- }
-
- /**
- * Returns the number of elements in this tree.
- *
- * @return the number of elements in this tree.
- */
- public int size() {
- return count;
- }
-
- /**
- * Performs bounding box search.
- *
- * @param searchRegion envelope representing the rectangular search
region.
- * @return elements that are within the given radius from the point.
- */
- public Stream<E> queryByBoundingBox(final Rectangle2D searchRegion) {
- return StreamSupport.stream(new NodeIterator<>(this, searchRegion),
false);
- // TODO: make parallel after we tested most extensively.
+ public QuadTree(final Envelope bounds, final Function<? super E, double[]>
evaluator, final int capacity) {
+ super(bounds, evaluator, capacity);
}
}
diff --git
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
index 1024768..036db7a 100644
---
a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
+++
b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
@@ -40,62 +40,11 @@ final class QuadTreeNode extends KDTreeNode {
* </ul>
*
* This pattern is generalizable to <var>n</var> dimensions (by contrast,
the use of a {@code Quadrant}
- * enumeration is not generalizable). Current implementation uses only 2
dimensions, but a future version
- * may generalize.
+ * enumeration is not generalizable).
*/
static final int NE = 0, NW = 1, SE = 2, SW = 3;
/**
- * The mask to apply on quadrant values for getting the sign of
<var>x</var> and <var>y</var>
- * values relative to the center of a node.
- *
- * Also used as bit position + 1 (this is possible only for mask values 1
and 2).
- * If we generalize to 3 or more dimensions, we will need to differentiate
those
- * "bit positions" from "mask values".
- */
- private static final int X_MASK = 1, Y_MASK = 2;
-
- /**
- * Returns the quadrant relative to the given point.
- *
- * @param x data <var>x</var> coordinate.
- * @param y data <var>y</var> coordinate.
- * @param cx center of current node along <var>x</var> axis.
- * @param cy center of current node along <var>y</var> axis.
- * @return one of {@link #NE}, {@link #NW}, {@link #SE} or {@link #SW}
constants.
- */
- static int quadrant(final double x, final double y, final double cx, final
double cy) {
- int q = 0;
- if (x < cx) q = X_MASK;
- if (y < cy) q |= Y_MASK;
- // Same for z and all other dimensions.
- return q;
- }
-
- /**
- * Returns 0.5 if the given quadrant is in the East side, or -0.5 if in
the West side.
- */
- static double factorX(final int quadrant) {
- /*
- * The 3FE0000000000000 long value is the bit pattern of 0.5. The
leftmost bit at (Long.SIZE - 1)
- * is the sign, which we set to the sign encoded in the quadrant
value. This approach allow us to
- * get the value efficiently, without jump instructions.
- */
- return Double.longBitsToDouble(0x3FE0000000000000L | (((long)
quadrant) << (Long.SIZE - X_MASK)));
- }
-
- /**
- * Returns 0.5 if the given quadrant is in the North side, or -0.5 if in
the South side.
- */
- static double factorY(final int quadrant) {
- /*
- * Same approach than for factorY, except that we need to clear the
bits on the right side of
- * the Y mask (it was not necessary for X because they were no bit on
the right side of X mask).
- */
- return Double.longBitsToDouble(0x3FE0000000000000L | (((long)
(quadrant & Y_MASK)) << (Long.SIZE - Y_MASK)));
- }
-
- /**
* The child nodes in 4 quadrants of equal size.
* Quadrants are North-West, North-East, South-East and South-West.
*/
@@ -108,19 +57,28 @@ final class QuadTreeNode extends KDTreeNode {
}
/**
+ * Creates a new instance of the same class than this node.
+ */
+ @Override
+ final KDTreeNode newInstance() {
+ return new QuadTreeNode();
+ }
+
+ /**
* Returns the child of this node that resides in the specified quadrant.
*
- * @param q quadrant of child to get.
+ * @param quadrant quadrant of child to get.
* @return child in the specified quadrant.
*/
- final Object getChild(final int q) {
+ @Override
+ final Object getChild(final int quadrant) {
final Object child;
- switch (q) {
+ switch (quadrant) {
case NW: child = nw; break;
case NE: child = ne; break;
case SW: child = sw; break;
case SE: child = se; break;
- default: throw new AssertionError(q);
+ default: throw new IndexOutOfBoundsException(/*quadrant*/); //
TODO: uncomment with JDK9.
}
return child;
}
@@ -128,16 +86,17 @@ final class QuadTreeNode extends KDTreeNode {
/**
* Sets the node's quadrant to the specified child.
*
- * @param q quadrant where the child resides.
- * @param child child of this node in the specified quadrant.
+ * @param quadrant quadrant where the child resides.
+ * @param child child of this node in the specified quadrant.
*/
- final void setChild(final int q, final Object child) {
- switch (q) {
+ @Override
+ final void setChild(final int quadrant, final Object child) {
+ switch (quadrant) {
case NW: nw = child; break;
case NE: ne = child; break;
case SW: sw = child; break;
case SE: se = child; break;
- default: throw new AssertionError(q);
+ default: throw new IndexOutOfBoundsException(/*quadrant*/); //
TODO: uncomment with JDK9.
}
}
}
diff --git
a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
new file mode 100644
index 0000000..1fe0e31
--- /dev/null
+++
b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
@@ -0,0 +1,112 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sis.index.tree;
+
+import java.lang.reflect.Field;
+import org.apache.sis.test.TestCase;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+
+/**
+ * Tests {@link NodeIterator}. Also contains opportunistic tests of {@link
QuadTreeNode}
+ * methods that are needed by the iterator.
+ *
+ * @author Chris Mattmann
+ * @author Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since 0.1
+ * @module
+ */
+public final strictfp class NodeIteratorTest extends TestCase {
+ /**
+ * Verifies the value of {@link NodeIterator#MAX_DIMENSION}.
+ * That value is restricted by the capacity of {@code long}.
+ */
+ @Test
+ public void verifyMaxDimension() {
+ assertEquals(Long.SIZE, 1 << NodeIterator.MAX_DIMENSION);
+ }
+
+ /**
+ * Tests {@link QuadTreeNode#factor(int,int)} for dimension 0 (X).
+ */
+ @Test
+ public void testFactorX() {
+ assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.NE, 0), STRICT);
+ assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.NW, 0), STRICT);
+ assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.SE, 0), STRICT);
+ assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.SW, 0), STRICT);
+ }
+
+ /**
+ * Tests {@link QuadTreeNode#factor(int,int)} for dimension 1 (Y).
+ */
+ @Test
+ public void testFactorY() {
+ assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.NE, 1), STRICT);
+ assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.NW, 1), STRICT);
+ assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.SE, 1), STRICT);
+ assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.SW, 1), STRICT);
+ }
+
+ /**
+ * Tests {@link QuadTreeNode#quadrant(double[], double[])}.
+ */
+ @Test
+ public void testQuadrant() {
+ final double[] region = new double[] {200, 300, Double.NaN,
Double.NaN};
+ assertEquals(QuadTreeNode.SW, QuadTreeNode.quadrant(new double[] {195,
285}, region));
+ assertEquals(QuadTreeNode.NW, QuadTreeNode.quadrant(new double[] {195,
305}, region));
+ assertEquals(QuadTreeNode.SE, QuadTreeNode.quadrant(new double[] {210,
280}, region));
+ assertEquals(QuadTreeNode.NE, QuadTreeNode.quadrant(new double[] {215,
305}, region));
+ }
+
+ /**
+ * Tests {@link QuadTreeNode#enterQuadrant(double[], int)}.
+ */
+ @Test
+ public void testEnterQuadrant() {
+ final double[] region = new double[] {200, 300, 100, 60};
+ QuadTreeNode.enterQuadrant(region, QuadTreeNode.SE);
+ assertArrayEquals(new double[] {225, 285, 50, 30}, region, STRICT);
+ }
+
+ /**
+ * Verifies {@link
org.apache.sis.index.tree.NodeIterator.Cursor#CLEAR_MASKS}.
+ *
+ * @throws ReflectiveOperationException if this test can not access to
private field that we want to verify.
+ */
+ @Test
+ public void verifyClearMasks() throws ReflectiveOperationException {
+ 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++) {
+ long expected = 0;
+ final long m = 1L << d;
+ for (int i=0; i<Long.SIZE; i++) {
+ if ((i & m) == 0) {
+ expected |= (1L << i);
+ }
+ }
+ assertEquals(expected, masks[d]);
+ }
+ }
+}
diff --git
a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeNodeTest.java
b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeNodeTest.java
deleted file mode 100644
index 86b4b93..0000000
---
a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeNodeTest.java
+++ /dev/null
@@ -1,56 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.sis.index.tree;
-
-import org.apache.sis.test.TestCase;
-import org.junit.Test;
-
-import static org.junit.Assert.*;
-
-
-/**
- * Tests {@link QuadTreeNode}.
- *
- * @author Chris Mattmann
- * @author Martin Desruisseaux (Geomatys)
- * @version 1.1
- * @since 0.1
- * @module
- */
-public final strictfp class QuadTreeNodeTest extends TestCase {
- /**
- * Tests {@link QuadTreeNode#factorX(int)}.
- */
- @Test
- public void testFactorX() {
- assertEquals(+0.5, QuadTreeNode.factorX(QuadTreeNode.NE), STRICT);
- assertEquals(-0.5, QuadTreeNode.factorX(QuadTreeNode.NW), STRICT);
- assertEquals(+0.5, QuadTreeNode.factorX(QuadTreeNode.SE), STRICT);
- assertEquals(-0.5, QuadTreeNode.factorX(QuadTreeNode.SW), STRICT);
- }
-
- /**
- * Tests {@link QuadTreeNode#factorY(int)}.
- */
- @Test
- public void testFactorY() {
- assertEquals(+0.5, QuadTreeNode.factorY(QuadTreeNode.NE), STRICT);
- assertEquals(+0.5, QuadTreeNode.factorY(QuadTreeNode.NW), STRICT);
- assertEquals(-0.5, QuadTreeNode.factorY(QuadTreeNode.SE), STRICT);
- assertEquals(-0.5, QuadTreeNode.factorY(QuadTreeNode.SW), STRICT);
- }
-}
diff --git
a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
index 016a7cf..f9ebecc 100644
---
a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
+++
b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
@@ -21,10 +21,9 @@ import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Random;
-import java.util.function.Function;
-import java.awt.Rectangle;
-import java.awt.geom.Point2D;
-import java.awt.geom.Rectangle2D;
+import org.opengis.geometry.Envelope;
+import org.apache.sis.geometry.DirectPosition2D;
+import org.apache.sis.geometry.Envelope2D;
import org.apache.sis.test.DependsOn;
import org.apache.sis.test.TestCase;
import org.apache.sis.test.TestUtilities;
@@ -41,7 +40,7 @@ import static org.junit.Assert.*;
* @since 1.1
* @module
*/
-@DependsOn(QuadTreeNodeTest.class)
+@DependsOn(NodeIteratorTest.class)
public final strictfp class QuadTreeTest extends TestCase {
/**
* Bounds of the region where to create points. Intentionally use
asymmetric bounds
@@ -66,13 +65,11 @@ public final strictfp class QuadTreeTest extends TestCase {
/**
* The elements to be added in the {@link QuadTree} to test.
- * This element extends {@link Point2D} for convenience, but this is not a
requirement.
+ * This element extends {@link DirectPosition2D} for convenience, but this
is not a requirement.
* The point is unmodifiable; attempt to modify a coordinate will cause
the test to fail.
*/
- private static final class Element extends Point2D {
- /** The coordinate values. */
- private final int x, y;
-
+ @SuppressWarnings("serial")
+ private static final class Element extends DirectPosition2D {
/** Creates a new element with random coordinates. */
Element(final Random random) {
x = random.nextInt(XMAX - XMIN) + XMIN;
@@ -84,10 +81,10 @@ public final strictfp class QuadTreeTest extends TestCase {
@Override public String toString() {return "P(" + x + ", " + y + ')';}
@Override public void setLocation(double x, double y) {
- fail("Location shoulf not be modified.");
+ fail("Location should not be modified.");
}
- @Override public Object clone() {
+ @Override public DirectPosition2D clone() {
fail("Location should not be cloned.");
return super.clone();
}
@@ -97,8 +94,13 @@ public final strictfp class QuadTreeTest extends TestCase {
* Creates a tree filled with random values.
*/
private void createTree() {
+ final Envelope2D region = new Envelope2D();
+ region.x = XMIN;
+ region.y = YMIN;
+ region.width = XMAX - XMIN;
+ region.height = YMAX - YMIN;
random = TestUtilities.createRandomNumberGenerator();
- tree = new QuadTree<>(new Rectangle(XMIN, YMIN, XMAX - XMIN, YMAX -
YMIN), Function.identity(), 5);
+ tree = new QuadTree<>(region, Element::getCoordinate, 5);
int count = random.nextInt(100) + 200;
data = new ArrayList<>(count);
while (--count >= 0) {
@@ -109,7 +111,7 @@ public final strictfp class QuadTreeTest extends TestCase {
}
/**
- * Tests {@link QuadTree#queryByBoundingBox(Rectangle2D)} with random
coordinates.
+ * Tests {@link QuadTree#queryByBoundingBox(Envelope)} with random
coordinates.
* This method performs some searches in random regions and compare the
results
* against searches performed by raw force.
*/
@@ -117,7 +119,7 @@ public final strictfp class QuadTreeTest extends TestCase {
public void testQueryByBoundingBox() {
createTree();
final Set<Element> expected = new HashSet<>();
- final Rectangle2D.Double region = new Rectangle2D.Double();
+ final Envelope2D region = new Envelope2D();
for (int i=0; i<20; i++) {
final int xmin = random.nextInt(XMAX - XMIN) + XMIN;
final int ymin = random.nextInt(YMAX - YMIN) + YMIN;
diff --git
a/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java
b/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java
index cc09ca9..eadc171 100644
---
a/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java
+++
b/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java
@@ -30,7 +30,7 @@ import org.junit.BeforeClass;
* @module
*/
@Suite.SuiteClasses({
- org.apache.sis.index.tree.QuadTreeNodeTest.class,
+ org.apache.sis.index.tree.NodeIteratorTest.class,
org.apache.sis.index.tree.QuadTreeTest.class,
org.apache.sis.internal.storage.CodeTypeTest.class,
org.apache.sis.internal.storage.io.IOUtilitiesTest.class,
