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: Move the KDTree/QuadTree implementation to sis-feature module and rename as PointTree (as opposed to "region QuadTree" or to RTree).
Date Wed, 15 Jan 2020 09:54:08 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 f23b1d0  Move the KDTree/QuadTree implementation to sis-feature module and rename
as PointTree (as opposed to "region QuadTree" or to RTree).
f23b1d0 is described below

commit f23b1d076ec8e7088a608c5e048be6acb05c8d65
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Wed Jan 15 10:53:00 2020 +0100

    Move the KDTree/QuadTree implementation to sis-feature module and rename as PointTree
(as opposed to "region QuadTree" or to RTree).
---
 .../org/apache/sis/index/tree/NodeIterator.java    | 22 ++++-----
 .../java/org/apache/sis/index/tree/PointTree.java  | 32 +++++++------
 .../org/apache/sis/index/tree/PointTreeNode.java   | 38 ++++++++--------
 .../org/apache/sis/index/tree/QuadTreeNode.java    |  8 ++--
 .../org/apache/sis/index/tree/package-info.java    |  2 +-
 .../apache/sis/index/tree/PointTreeNodeTest.java   |  5 +-
 .../org/apache/sis/index/tree/PointTreeTest.java   | 14 +++---
 .../apache/sis/test/suite/FeatureTestSuite.java    |  6 ++-
 .../java/org/apache/sis/index/tree/QuadTree.java   | 53 ----------------------
 .../apache/sis/test/suite/StorageTestSuite.java    |  2 -
 10 files changed, 68 insertions(+), 114 deletions(-)

diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
b/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
similarity index 96%
rename from storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
rename to core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
index 21952a0..7fc9fbd 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
@@ -24,7 +24,7 @@ import org.apache.sis.internal.util.Numerics;
 
 
 /**
- * An iterator over the elements contained in a {@link KDTreeNode}.
+ * 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
@@ -33,7 +33,7 @@ import org.apache.sis.internal.util.Numerics;
  * @author  Martin Desruisseaux (Geomatys)
  * @version 1.1
  *
- * @param  <E>  the type of elements stored in the {@link QuadTree}.
+ * @param  <E>  the type of elements stored in the {@link PointTree}.
  *
  * @since 1.1
  * @module
@@ -99,7 +99,7 @@ class NodeIterator<E> implements Spliterator<E> {
      * Creates a new iterator for the specified search region.
      */
     @SuppressWarnings("ThisEscapedInObjectConstruction")
-    NodeIterator(final KDTree<E> tree, final Envelope searchRegion) {
+    NodeIterator(final PointTree<E> tree, final Envelope searchRegion) {
         final int n = searchRegion.getDimension();
         bitmask = Numerics.bitmask(1 << n) - 1;
         bounds  = new double[n*2];
@@ -115,8 +115,8 @@ class NodeIterator<E> implements Spliterator<E> {
     }
 
     /**
-     * A provider for arrays of elements of child nodes contained in a {@link KDTreeNode}.
-     * The starting point is {@link KDTree#root}. A new {@link Cursor} instance is created
+     * 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
      * (if there is only one child node, then this implementation takes a shortcut).
      */
@@ -136,15 +136,15 @@ 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.
          */
-        KDTreeNode node;
+        PointTreeNode node;
 
         /**
          * Bitmask of quadrants/octants on which to iterate. Quadrants/octants are iterated
from rightmost
          * bit to leftmost bit. Bits are cleared when the corresponding quadrant/octant become
the current
          * one. A value of 0 means that there is no more quadrant to iterate for the {@linkplain
#node}.
          *
-         * <p><b>Note:</b> we take "quadrant" name from {@link QuadTree},
but this algorithm can actually
-         * be used with more dimensions.</p>
+         * <p><b>Note:</b> we take "quadrant" name from QuadTree, but this
algorithm can actually be used
+         * with more dimensions.</p>
          *
          * @see #MAX_DIMENSION
          */
@@ -241,7 +241,7 @@ class NodeIterator<E> implements Spliterator<E> {
                 it.recycle = c.parent;
                 System.arraycopy(region, 0, c.region, 0, region.length);
             }
-            KDTreeNode.enterQuadrant(c.region, q);
+            PointTreeNode.enterQuadrant(c.region, q);
             c.parent = this;
             return c;
         }
@@ -257,7 +257,7 @@ class NodeIterator<E> implements Spliterator<E> {
          * @param  q  the quadrant/octant in which to iterate.
          */
         final void moveDown(final int q) {
-            KDTreeNode.enterQuadrant(region, q);
+            PointTreeNode.enterQuadrant(region, q);
         }
 
         /**
@@ -310,7 +310,7 @@ class NodeIterator<E> implements Spliterator<E> {
                          */
                         cursor.moveDown(q);
                     }
-                    cursor.node = (QuadTreeNode) child;
+                    cursor.node = (PointTreeNode) child;
                     cursor.findIntersections(this);
                 }
             }
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTree.java
similarity index 88%
rename from storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
rename to core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTree.java
index 61cb721..30f5d85 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTree.java
@@ -25,13 +25,19 @@ import org.apache.sis.util.resources.Errors;
 
 
 /**
- * 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.
+ * A <var>k</var>-dimensional tree index for points. For <var>k</var>=2,
this is a <cite>point QuadTree</cite>.
+ * For <var>k</var>=3, this is point <cite>Octree</cite>. 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
  * after construction, then multiple read operations in concurrent threads are safe.
  *
+ * <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>.
+ * Massachusetts: Addison Wesley Publishing Company, 1989.
+ *
+ * @author  Chris Mattmann
  * @author  Martin Desruisseaux (Geomatys)
  * @version 1.1
  *
@@ -40,11 +46,11 @@ import org.apache.sis.util.resources.Errors;
  * @since 1.1
  * @module
  */
-class KDTree<E> {
+public class PointTree<E> {
     /**
      * The root node of this <var>k</var>-dimensional tree.
      */
-    final KDTreeNode root;
+    final PointTreeNode root;
 
     /**
      * The maximal capacity of each node in this tree. It should be a relatively small number.
@@ -89,7 +95,7 @@ class KDTree<E> {
      * @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) {
+    public PointTree(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));
@@ -104,7 +110,7 @@ class KDTree<E> {
         }
         this.capacity  = Math.max(4, capacity);
         this.evaluator = evaluator;
-        this.root      = (n == 2) ? new QuadTreeNode() : new KDTreeNode.Default(n);
+        this.root      = (n == 2) ? new QuadTreeNode() : new PointTreeNode.Default(n);
     }
 
     /**
@@ -129,11 +135,11 @@ class KDTree<E> {
      * @param  element  the element to insert.
      */
     @SuppressWarnings("unchecked")
-    private void insert(KDTreeNode parent, double[] region, final E element) {
+    private void insert(PointTreeNode parent, double[] region, final E element) {
         boolean isRegionCopied = false;
         final double[] point = evaluator.apply(element);
         for (;;) {
-            final int quadrant = KDTreeNode.quadrant(point, region);
+            final int quadrant = PointTreeNode.quadrant(point, region);
             final Object child = parent.getChild(quadrant);
             /*
              * If the element will be stored in a new quadrant never used before,
@@ -148,13 +154,13 @@ class KDTree<E> {
              * 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 (child instanceof PointTreeNode) {
                 if (!isRegionCopied) {
                     isRegionCopied = true;
                     region = region.clone();
                 }
-                KDTreeNode.enterQuadrant(region, quadrant);
-                parent = (KDTreeNode) child;
+                PointTreeNode.enterQuadrant(region, quadrant);
+                parent = (PointTreeNode) child;
                 continue;
             }
             /*
@@ -179,8 +185,8 @@ class KDTree<E> {
                 isRegionCopied = true;
                 region = region.clone();
             }
-            KDTreeNode.enterQuadrant(region, quadrant);
-            final KDTreeNode branch = parent.newInstance();
+            PointTreeNode.enterQuadrant(region, quadrant);
+            final PointTreeNode branch = parent.newInstance();
             for (final Object e : data) {
                 insert(branch, region, (E) e);
             }
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTreeNode.java
similarity index 84%
rename from storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
rename to core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTreeNode.java
index 3edc329..5902623 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/PointTreeNode.java
@@ -18,16 +18,16 @@ package org.apache.sis.index.tree;
 
 
 /**
- * A node in a {@link KDTree} which is the parent of other nodes. The number of child nodes
depends on
- * the number of dimensions of the tree: 4 children with two-dimensional {@link QuadTree},
8 children
- * with three-dimensional {@code Octree}, <i>etc</i>. The child node can be another
{@link KDTreeNode}
- * if that node is itself the parent of more nodes. Otherwise (i.e. if the child node is
leaf) the child
- * is an instance of {@code Object[]}.
+ * A node in a {@link PointTree} which is the parent of other nodes. The number of child
nodes depends
+ * on the number of dimensions of the tree: 4 children with two-dimensional <cite>QuadTree</cite>,
+ * 8 children with three-dimensional <cite>Octree</cite>, <i>etc</i>.
+ * The child node can be another {@link PointTreeNode} if that node is itself the parent
of more nodes.
+ * Otherwise (i.e. if the child node is leaf) the child is an instance of {@code Object[]}.
  *
  * <p>Features of arbitrary types are stored in {@code Object[]} arrays. Those arrays
should be small:
- * if the number of elements in a leaf exceeds a maximal capacity specified by the {@link
KDTree},
- * then the leaf is replaced by a new {@link KDTreeNode} and the {@code Object[]} content
is distributed
- * between the new child nodes.</p>
+ * if the number of elements in a leaf exceeds a maximal capacity specified by the {@link
PointTree},
+ * then the leaf is replaced by a new {@link PointTreeNode} and the {@code Object[]} content
+ * is distributed between the new child nodes.</p>
  *
  * <p>Addition of new features in {@code Object[]} arrays uses a <cite>copy-on-write</cite>
strategy
  * in order to keep memory usage minimal (a tree may have thousands of small arrays) and
for making
@@ -45,11 +45,11 @@ package org.apache.sis.index.tree;
  * @since   1.1
  * @module
  */
-abstract class KDTreeNode {
+abstract class PointTreeNode {
     /**
-     * Constructs an initially empty {@link KDTree} node.
+     * Constructs an initially empty {@link PointTree} node.
      */
-    KDTreeNode() {
+    PointTreeNode() {
     }
 
     /**
@@ -114,9 +114,9 @@ abstract class KDTreeNode {
      * 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>Another {@link PointTreeNode} 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>
+     *       We do not wrap the leaf in another {@link PointTreeNode} for reducing the number
of objects created.</li>
      * </ul>
      *
      * Any other kind of object is an error.
@@ -140,25 +140,25 @@ abstract class KDTreeNode {
     /**
      * Creates a new instance of the same class than this node.
      */
-    abstract KDTreeNode newInstance();
+    abstract PointTreeNode newInstance();
 
     /**
-     * Default implementation of {@link KDTreeNode} when no specialized class is available.
+     * 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.
      * 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.
      */
-    static final class Default extends KDTreeNode {
+    static final class Default extends PointTreeNode {
         /**
          * The nodes or element values in each quadrant/octant of this node.
          * Each array element can be null or an instance of one of the classes
-         * documented in {@link KDTreeNode#getChild(int)}.
+         * documented in {@link PointTreeNode#getChild(int)}.
          */
         private final Object[] children;
 
         /**
-         * Constructs an initially empty {@link KDTree} node.
+         * Constructs an initially empty {@link PointTree} node.
          *
          * @param  n  must be 2<sup>k</sup> where <var>k</var> is
the number of dimensions.
          */
@@ -170,7 +170,7 @@ abstract class KDTreeNode {
          * Creates a new instance of the same class than this node.
          */
         @Override
-        final KDTreeNode newInstance() {
+        final PointTreeNode newInstance() {
             return new Default(children.length);
         }
 
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
b/core/sis-feature/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
similarity index 92%
rename from storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
rename to core/sis-feature/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
index 036db7a..5c817f7 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
@@ -18,8 +18,8 @@ package org.apache.sis.index.tree;
 
 
 /**
- * A node in a {@link QuadTree} which is the parent of other nodes.
- * This class is a specialization of {@link KDTree} for the two-dimensional case.
+ * A node in a two-dimensional {@link PointTree} which is the parent of other nodes.
+ * This class is a specialization of {@link PointTreeNode} for the two-dimensional case.
  * This specialization is provided for reducing the number of objects to create,
  * by storing the 4 quadrants as fields instead than in an array.
  *
@@ -29,7 +29,7 @@ package org.apache.sis.index.tree;
  * @since   0.1
  * @module
  */
-final class QuadTreeNode extends KDTreeNode {
+final class QuadTreeNode extends PointTreeNode {
     /**
      * The 4 quadrants of a {@link QuadTreeNode}: North-West (NW), North-East (NE),
      * South-West (SW) and South-East (SE). Numerical values follow this bit pattern:
@@ -60,7 +60,7 @@ final class QuadTreeNode extends KDTreeNode {
      * Creates a new instance of the same class than this node.
      */
     @Override
-    final KDTreeNode newInstance() {
+    final PointTreeNode newInstance() {
         return new QuadTreeNode();
     }
 
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/package-info.java
b/core/sis-feature/src/main/java/org/apache/sis/index/tree/package-info.java
similarity index 93%
rename from storage/sis-storage/src/main/java/org/apache/sis/index/tree/package-info.java
rename to core/sis-feature/src/main/java/org/apache/sis/index/tree/package-info.java
index 3425d92..fa3bc8e 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/package-info.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/package-info.java
@@ -16,7 +16,7 @@
  */
 
 /**
- * A simple QuadTree implementation.
+ * A simple <var>k</var>-dimensional point tree implementation.
  *
  * @author  Chris Mattmann
  * @author  Martin Desruisseaux (Geomatys)
diff --git a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeNodeTest.java
similarity index 95%
rename from storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
rename to core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeNodeTest.java
index 1fe0e31..ca85a1e 100644
--- a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeNodeTest.java
@@ -24,8 +24,7 @@ import static org.junit.Assert.*;
 
 
 /**
- * Tests {@link NodeIterator}. Also contains opportunistic tests of {@link QuadTreeNode}
- * methods that are needed by the iterator.
+ * Tests {@link PointTreeNode}. Also contains a few opportunistic tests of {@link NodeIterator}.
  *
  * @author  Chris Mattmann
  * @author  Martin Desruisseaux (Geomatys)
@@ -33,7 +32,7 @@ import static org.junit.Assert.*;
  * @since   0.1
  * @module
  */
-public final strictfp class NodeIteratorTest extends TestCase {
+public final strictfp class PointTreeNodeTest extends TestCase {
     /**
      * Verifies the value of {@link NodeIterator#MAX_DIMENSION}.
      * That value is restricted by the capacity of {@code long}.
diff --git a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeTest.java
similarity index 93%
rename from storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
rename to core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeTest.java
index f9ebecc..9768fcf 100644
--- a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/index/tree/PointTreeTest.java
@@ -33,15 +33,15 @@ import static org.junit.Assert.*;
 
 
 /**
- * Tests {@link QuadTree}.
+ * Tests {@link PointTree}.
  *
  * @author  Martin Desruisseaux (Geomatys)
  * @version 1.1
  * @since   1.1
  * @module
  */
-@DependsOn(NodeIteratorTest.class)
-public final strictfp class QuadTreeTest extends TestCase {
+@DependsOn(PointTreeNode.class)
+public final strictfp class PointTreeTest extends TestCase {
     /**
      * Bounds of the region where to create points. Intentionally use asymmetric bounds
      * for increasing the chances to detect bugs in node region computations.
@@ -56,7 +56,7 @@ public final strictfp class QuadTreeTest extends TestCase {
     /**
      * The tree to test.
      */
-    private QuadTree<Element> tree;
+    private PointTree<Element> tree;
 
     /**
      * All data added to the {@link #tree}, for comparison purpose.
@@ -64,7 +64,7 @@ public final strictfp class QuadTreeTest extends TestCase {
     private List<Element> data;
 
     /**
-     * The elements to be added in the {@link QuadTree} to test.
+     * The elements to be added in the {@link PointTree} to test.
      * 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.
      */
@@ -100,7 +100,7 @@ public final strictfp class QuadTreeTest extends TestCase {
         region.width  = XMAX - XMIN;
         region.height = YMAX - YMIN;
         random = TestUtilities.createRandomNumberGenerator();
-        tree = new QuadTree<>(region, Element::getCoordinate, 5);
+        tree = new PointTree<>(region, Element::getCoordinate, 5);
         int count = random.nextInt(100) + 200;
         data = new ArrayList<>(count);
         while (--count >= 0) {
@@ -111,7 +111,7 @@ public final strictfp class QuadTreeTest extends TestCase {
     }
 
     /**
-     * Tests {@link QuadTree#queryByBoundingBox(Envelope)} with random coordinates.
+     * Tests {@link PointTree#queryByBoundingBox(Envelope)} with random coordinates.
      * This method performs some searches in random regions and compare the results
      * against searches performed by raw force.
      */
diff --git a/core/sis-feature/src/test/java/org/apache/sis/test/suite/FeatureTestSuite.java
b/core/sis-feature/src/test/java/org/apache/sis/test/suite/FeatureTestSuite.java
index 3990ea2..c7bbef6 100644
--- a/core/sis-feature/src/test/java/org/apache/sis/test/suite/FeatureTestSuite.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/test/suite/FeatureTestSuite.java
@@ -92,7 +92,11 @@ import org.junit.runners.Suite;
     org.apache.sis.coverage.grid.ReshapedImageTest.class,
     org.apache.sis.coverage.grid.GridCoverage2DTest.class,
     org.apache.sis.internal.coverage.j2d.BandedSampleConverterTest.class,
-    org.apache.sis.internal.coverage.j2d.BufferedGridCoverageTest.class
+    org.apache.sis.internal.coverage.j2d.BufferedGridCoverageTest.class,
+
+    // Index
+    org.apache.sis.index.tree.PointTreeNodeTest.class,
+    org.apache.sis.index.tree.PointTreeTest.class
 })
 public final strictfp class FeatureTestSuite extends TestSuite {
     /**
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
deleted file mode 100644
index 34db1c2..0000000
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
+++ /dev/null
@@ -1,53 +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 java.util.function.Function;
-import org.opengis.geometry.Envelope;
-
-
-/**
- * Implementation of a point QuadTree Index.
- * See {@link KDTree} for a note about thread-safety.
- *
- * <p><b>References:</b></p>
- * Insertion algorithm implemented based on design of QuadTree index
- * in H. Samet, The Design and Analysis of Spatial Data Structures.
- * Massachusetts: Addison Wesley Publishing Company, 1989.
- *
- * @author  Chris Mattmann
- * @author  Martin Desruisseaux (Geomatys)
- * @version 1.1
- *
- * @param  <E>  the type of elements stored in this tree.
- *
- * @since 0.1
- * @module
- */
-public final class QuadTree<E> extends KDTree<E> {
-    /**
-     * Creates an initially empty QuadTree with the given capacity for each node.
-     * 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 Envelope bounds, final Function<? super E, double[]> evaluator,
final int capacity) {
-        super(bounds, evaluator, capacity);
-    }
-}
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 eadc171..bbabdf6 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,8 +30,6 @@ import org.junit.BeforeClass;
  * @module
  */
 @Suite.SuiteClasses({
-    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,
     org.apache.sis.internal.storage.io.ChannelDataInputTest.class,


Mime
View raw message