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: Replace the half-backed mechanism in SpecializableTransform by something closer to an R-Tree. This is not yet a "professional" R-Tree; it requires that nodes for widest areas are added first and even in those condition the tree may not be well equilibrated. But it will hopefully do the work for the foreseeing time until we implement a real R-Tree.
Date Sun, 16 Feb 2020 20:49:52 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 cd87c70  Replace the half-backed mechanism in SpecializableTransform by something closer to an R-Tree. This is not yet a "professional" R-Tree; it requires that nodes for widest areas are added first and even in those condition the tree may not be well equilibrated. But it will hopefully do the work for the foreseeing time until we implement a real R-Tree.
cd87c70 is described below

commit cd87c70f79dc3d1bfddee085edeb612593bb15c1
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Sun Feb 16 21:15:31 2020 +0100

    Replace the half-backed mechanism in SpecializableTransform by something closer to an R-Tree.
    This is not yet a "professional" R-Tree; it requires that nodes for widest areas are added first
    and even in those condition the tree may not be well equilibrated. But it will hopefully do the
    work for the foreseeing time until we implement a real R-Tree.
---
 .../apache/sis/internal/referencing/RTreeNode.java | 357 +++++++++++++++++++++
 .../referencing/provider/DatumShiftGridFile.java   |   2 +-
 .../referencing/provider/DatumShiftGridGroup.java  |  21 +-
 .../operation/transform/MathTransforms.java        |   7 +-
 .../transform/SpecializableTransform.java          | 299 ++++++-----------
 5 files changed, 482 insertions(+), 204 deletions(-)

diff --git a/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/RTreeNode.java b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/RTreeNode.java
new file mode 100644
index 0000000..5e470bb
--- /dev/null
+++ b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/RTreeNode.java
@@ -0,0 +1,357 @@
+/*
+ * 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.internal.referencing;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.function.Consumer;
+import org.opengis.geometry.DirectPosition;
+import org.opengis.geometry.Envelope;
+import org.opengis.geometry.MismatchedReferenceSystemException;
+import org.opengis.referencing.crs.CoordinateReferenceSystem;
+import org.apache.sis.geometry.GeneralEnvelope;
+import org.apache.sis.io.wkt.Formatter;
+import org.apache.sis.util.Utilities;
+import org.apache.sis.util.resources.Errors;
+import org.apache.sis.util.collection.TreeTable;
+import org.apache.sis.util.collection.TableColumn;
+import org.apache.sis.util.collection.DefaultTreeTable;
+
+
+/**
+ * Placeholder for a RTree. This simple implementation is not designed for scalability or performance.
+ * This class is there for minimal service, to be replaced in some future Apache SIS version by a more
+ * sophisticated tree. Current version of this class is okay for small trees where big nodes are added
+ * before small nodes.
+ *
+ * <p>A {@code RTreeNode} instance is used as the root of the tree. Children nodes are stored as a linked list
+ * (the list is implemented by the {@link #sibling} field, which reference the next element in the list).</p>
+ *
+ * <div class="note"><b>Possible evolution:</b>
+ * a future version could avoid extending {@link GeneralEnvelope}. Instead we could provide abstract
+ * {@code contains(…)} methods and let subclasses define them, with possibly more efficient implementations.
+ * We would still need an implementation that delegate to {@link GeneralEnvelope} since that class has the
+ * advantage of handling envelopes crossing the anti-meridian.</div>
+ *
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since   1.1
+ * @module
+ */
+public class RTreeNode extends GeneralEnvelope {
+    /**
+     * For cross-version compatibility.
+     */
+    private static final long serialVersionUID = -6544217991652682694L;
+
+    /**
+     * The parent, or {@code null} if none.
+     *
+     * @see #getParent()
+     */
+    private RTreeNode parent;
+
+    /**
+     * The first node fully included in this code, or {@code null} if none. If non-null, that node and all
+     * its {@linkplain #sibling}s shall be fully included in this {@code RTreeNode}. The child may contain
+     * other children, thus forming a tree from this wider node to smaller nodes.
+     *
+     * @see #getChildren()
+     */
+    private RTreeNode firstChild;
+
+    /**
+     * The next node having the same parent than this node. This is used for creating a linked list of nodes
+     * that are the children of the {@linkplain #parent}.
+     *
+     * <div class="note"><b>Design note:</b>
+     * an {@code RTreeNode children} array instead of {@link #firstChild} + {@link #sibling} would be more intuitive.
+     * But the use of linked list avoid one level of indirection and is one less object to create for each node.
+     * The gain may be negligible with a few hundreds nodes, but a future version of this class may target much
+     * more numerous nodes.</div>
+     */
+    private RTreeNode sibling;
+
+    /**
+     * Creates a new node for the given envelope.
+     *
+     * @param  area  the region covered by this node.
+     */
+    public RTreeNode(final Envelope area) {
+        super(area);
+    }
+
+    /**
+     * Returns the parent of this node, or {@code null} if none.
+     *
+     * @return the parent of this node, or {@code null} if none.
+     */
+    public final RTreeNode getParent() {
+        return parent;
+    }
+
+    /**
+     * Returns the immediate children of this node, or an empty list if none.
+     *
+     * @return the immediate children of this node.
+     */
+    public final List<RTreeNode> getChildren() {
+        final List<RTreeNode> children = new ArrayList<>();
+        for (RTreeNode child = firstChild; child != null; child = child.sibling) {
+            assert child.parent == this : child;
+            children.add(child);
+        }
+        return children;
+    }
+
+    /**
+     * Executes the given action on the given node, all its children and all its siblings.
+     *
+     * @param node    the node on which to execute the action, or {@code null} if none.
+     * @param action  the action to execute.
+     */
+    public static void walk(RTreeNode node, final Consumer<? super RTreeNode> action) {
+        while (node != null) {
+            action.accept(node);
+            walk(node.firstChild, action);
+            node = node.sibling;
+        }
+    }
+
+    /**
+     * Adds the given node to the tree having this node as the root. This method assumes that this
+     * node or its siblings are likely to contain the nodes given to this method. This method will
+     * work even if this assumption does not hold, but the tree will be inefficient in such case.
+     *
+     * <p>A "professional" R-Tree would make a better effort for creating a balanced tree here.
+     * Current version of this class uses a simple algorithm, okay for small trees where big nodes
+     * are added before small nodes. This is not a good general purpose R-Tree.</p>
+     *
+     * @param  node  the node to add to this tree. If this node has sibling, they will be added too.
+     *
+     * @see #finish()
+     */
+    public final void addNode(RTreeNode node) {
+detach: for (RTreeNode next; node != null; node = next) {
+            next = node.sibling;
+            node.sibling = null;                    // Detach the siblings for adding each node individually.
+            RTreeNode tail, receiver = this;
+            do {
+                tail = receiver;
+                if (receiver.tryAddChild(node)) {
+                    continue detach;                // Node accepted by a child, process the next node if any.
+                }
+                receiver = receiver.sibling;
+            } while (receiver != null);
+            tail.sibling = node;                    // Not a child of this node, but assume common parent.
+            node.parent = parent;
+        }
+    }
+
+    /**
+     * Tries to add a child. This method checks if the given candidate is fully included in this {@code RTreeNode}.
+     * The given node may have children but shall not have any {@linkplain #sibling}, because this method does not
+     * check if the siblings would also be included in this node.
+     *
+     * @param  candidate  the single node (without sibling) to add as a child if possible.
+     * @return whether the given node has been added.
+     */
+    private boolean tryAddChild(final RTreeNode candidate) {
+        assert candidate.sibling == null : candidate;
+        if (contains(candidate)) {
+            RTreeNode child = firstChild;
+            if (child == null) {
+                firstChild = candidate;                     // This node had no children before this method call.
+            } else {
+                RTreeNode lastChild;
+                do {
+                    lastChild = child;
+                    if (child.tryAddChild(candidate)) {
+                        return true;                        // Given node added to a child instead than to this node.
+                    }
+                    child = child.sibling;
+                } while (child != null);
+                lastChild.sibling = candidate;              // Add last in the linked list of this node children.
+            }
+            candidate.parent = this;
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * Finishes the construction of the tree. This methods sets the CRS of all nodes to a common value.
+     * An exception is thrown if incompatible CRS are found. This method does not verify the number of
+     * dimensions; this check should have been done by the caller.
+     *
+     * <p>This method should be invoked only on the instance on which {@link #addNode(RTreeNode)} has been
+     * invoked.</p>
+     *
+     * @return the root of the tree (may be {@code this}).
+     */
+    public final RTreeNode finish() {
+        final Uniformizer action = new Uniformizer();
+        walk(this, action);
+        action.set = true;
+        walk(this, action);
+        RTreeNode next = sibling;
+        if (next == null) {
+            return this;
+        }
+        /*
+         * If there is more than one node, create a synthetic parent containing them all.
+         * We do not need to traverse all node for this task; only the immediate children
+         * of the new parent.
+         */
+        parent = new RTreeNode(this);
+        parent.firstChild = this;
+        do {
+            parent.add(next);           // Compute union of envelopes (not an addition of node).
+            next.parent = parent;
+            next = next.sibling;
+        } while (next != null);
+        return parent;
+    }
+
+    /**
+     * The action for getting a common CRS for all nodes, then for setting the CRS of all nodes.
+     * This action will be executed on the whole tree, with recursive traversal of children.
+     */
+    private static final class Uniformizer implements Consumer<RTreeNode> {
+        /** The CRS common to all nodes. */
+        private CoordinateReferenceSystem common;
+
+        /** {@code false} for collecting information, or {@code true} for setting all node CRS. */
+        boolean set;
+
+        /** Invoked for each node of the tree. */
+        @Override public void accept(final RTreeNode node) {
+            if (set) {
+                node.setCoordinateReferenceSystem(common);
+            } else {
+                final CoordinateReferenceSystem crs = node.getCoordinateReferenceSystem();
+                if (common == null) {
+                    common = crs;
+                } else if (crs != null && !Utilities.equalsIgnoreMetadata(common, crs)) {
+                    throw new MismatchedReferenceSystemException(Errors.format(Errors.Keys.MismatchedCRS));
+                }
+            }
+        }
+    }
+
+    /**
+     * Returns the node that contains the given position, or {@code null} if none.
+     * The given node does not need to be the root of the tree; it can be any node.
+     * This method will check that node first. If it does not contain the position,
+     * then this method goes up in the parent nodes.
+     *
+     * <p>If consecutive positions are close to each other, then a good strategy is
+     * to give to this method the most recently used node.</p>
+     *
+     * @param  node  any node in the tree. Should be node most likely to contain the position.
+     * @param  pos   the position of the node to locate.
+     * @return the smallest node containing the given position.
+     */
+    public static RTreeNode locate(RTreeNode node, final DirectPosition pos) {
+        RTreeNode skip = null;      // For avoiding to invoke `contains(pos)` twice on the same mode.
+        do {
+            if (node.contains(pos)) {
+                /*
+                 * Before to return the node we just found, check if a child contains the point.
+                 * If we find a child containing the point, then `node` is updated to that child.
+                 */
+                RTreeNode candidate = node.firstChild;
+                while (candidate != null) {
+                    if (candidate != skip && candidate.contains(pos)) {
+                        node = candidate;
+                        candidate = node.firstChild;        // Continue checking children of the child.
+                    } else {
+                        candidate = candidate.sibling;      // Check other children of the parent node.
+                    }
+                }
+                return node;
+            }
+            skip = node;
+            node = node.parent;
+        } while (node != null);
+        return null;
+    }
+
+    /**
+     * Returns a hash code value based on the this node and its children,
+     * ignoring the parent and the siblings.
+     *
+     * @return a hash code value for this node and its children.
+     */
+    @Override
+    public int hashCode() {
+        return super.hashCode() + 37 * getChildren().hashCode();
+    }
+
+    /**
+     * Compares this node with the given object for equality, ignoring the parent and the siblings.
+     *
+     * @param  obj  the object to compare with this node.
+     * @return whether the two objects are of the same class, have equal envelope and equal children list.
+     */
+    @Override
+    public boolean equals(final Object obj) {
+        return super.equals(obj) && getChildren().equals(((RTreeNode) obj).getChildren());
+    }
+
+    /**
+     * Formats this envelope as a "{@code DOMAIN}" element (non-standard).
+     */
+    @Override
+    protected String formatTo(final Formatter formatter) {
+        super.formatTo(formatter);
+        return "Domain";
+    }
+
+    /**
+     * Returns a string representation of this node and its children as a tree.
+     * This method is for debugging purposes.
+     *
+     * @return a string representation of this node and all its children.
+     */
+    @Override
+    public String toString() {
+        return toTree().toString();
+    }
+
+    /**
+     * Returns a representation of this node and its children as a tree.
+     * This is mostly for debugging purposes.
+     *
+     * @return a tree representation of this node and all its children.
+     */
+    public final TreeTable toTree() {
+        final DefaultTreeTable tree = new DefaultTreeTable(TableColumn.VALUE);
+        toTree(tree.getRoot());
+        return tree;
+    }
+
+    /**
+     * Adds this node and its children to the given node. This method invokes itself recursively.
+     */
+    private void toTree(final TreeTable.Node addTo) {
+        addTo.setValue(TableColumn.VALUE, super.toString());
+        for (final RTreeNode child : getChildren()) {
+            child.toTree(addTo.newChild());
+        }
+    }
+}
diff --git a/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridFile.java b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridFile.java
index fe3e139..d216397 100644
--- a/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridFile.java
+++ b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridFile.java
@@ -418,7 +418,7 @@ abstract class DatumShiftGridFile<C extends Quantity<C>, T extends Quantity<T>>
         final Map<Envelope,MathTransform> specializations = new LinkedHashMap<>(Containers.hashMapCapacity(subgrids.length));
         for (final DatumShiftGridFile<Angle,Angle> sg : subgrids) try {
             final Envelope domain = sg.getDomainOfValidity(Units.DEGREE);
-            final MathTransform st = InterpolatedTransform.createGeodeticTransformation(factory, sg);
+            final MathTransform st = createGeodeticTransformation(provider, factory, sg);
             if (specializations.putIfAbsent(domain, st) != null) {
                 DatumShiftGridLoader.log(provider, Errors.getResources((Locale) null)
                         .getLogRecord(Level.FINE, Errors.Keys.DuplicatedElement_1, domain));
diff --git a/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridGroup.java b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridGroup.java
index a009a92..c43b225 100644
--- a/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridGroup.java
+++ b/core/sis-referencing/src/main/java/org/apache/sis/internal/referencing/provider/DatumShiftGridGroup.java
@@ -34,6 +34,7 @@ import org.apache.sis.internal.referencing.j2d.TileOrganizer;
 import org.apache.sis.internal.referencing.j2d.Tile;
 import org.apache.sis.internal.referencing.Resources;
 import org.apache.sis.internal.util.CollectionsExt;
+import org.apache.sis.util.collection.Containers;
 
 
 /**
@@ -62,10 +63,16 @@ import org.apache.sis.internal.util.CollectionsExt;
  */
 final class DatumShiftGridGroup<C extends Quantity<C>, T extends Quantity<T>> extends DatumShiftGridFile<C,T> {
     /**
+     * For cross-version compatibility.
+     */
+    private static final long serialVersionUID = -1602724619897451422L;
+
+    /**
      * The bounds of a sub-grid, together with the subsampling level compared to the grid having the finest resolution.
      * All values in this class are integers, but nevertheless stored as {@code double} for avoiding to cast them every
      * time {@link DatumShiftGridGroup#interpolateInCell(double, double, double[])} is executed.
      */
+    @SuppressWarnings("CloneableImplementsClone")
     private static final class Region extends IntervalRectangle {
         /** Subsampling compared to the grid having finest resolution. */
         private final double sx, sy;
@@ -150,7 +157,7 @@ final class DatumShiftGridGroup<C extends Quantity<C>, T extends Quantity<T>> ex
             throws IOException, FactoryException, NoninvertibleTransformException
     {
         final TileOrganizer mosaic = new TileOrganizer(null);
-        final Map<Tile,DatumShiftGridFile<C,T>> grids = new LinkedHashMap<>();
+        final Map<Tile,DatumShiftGridFile<C,T>> grids = new LinkedHashMap<>(Containers.hashMapCapacity(subgrids.size()));
         for (final DatumShiftGridFile<C,T> grid : subgrids) {
             final int[] size = grid.getGridSize();
             final Tile  tile = new Tile(new Rectangle(size[0], size[1]),
@@ -263,11 +270,12 @@ final class DatumShiftGridGroup<C extends Quantity<C>, T extends Quantity<T>> ex
 
     /**
      * Interpolates the translation to apply for the given two-dimensional grid indices.
-     * This method is a fallback used when {@code SpecializableTransform} has not been able to use directly
-     * one of the child transforms — it should happen only in a minority of cases, so performance is not the
-     * priority here. The given point is assumed outside all sub-grids (otherwise {@code SpecializableTransform}
-     * would not be invoking this fallback). Consequently searching a sub-grid containing the given point is not
-     * sufficient; we have to search for the nearest grid even if the point is outside.
+     * During forward coordinate transformations, this method is invoked only if {@code SpecializableTransform}
+     * has been unable to use directly one of the child transforms — so performance is not the priority in that
+     * situation. During inverse transformations, this method is invoked for estimating an initial position before
+     * iterative refinements. The given point may be outside all sub-grids (otherwise {@code SpecializableTransform}
+     * would have done the work itself at least in the forward transformation case). Consequently searching a sub-grid
+     * containing the given point is not sufficient; we need to search for the nearest grid even if the point is outside.
      *
      * @param  gridX   first grid coordinate of the point for which to get the translation.
      * @param  gridY   second grid coordinate of the point for which to get the translation.
@@ -285,6 +293,7 @@ final class DatumShiftGridGroup<C extends Quantity<C>, T extends Quantity<T>> ex
                 distance = d;
                 nearest  = r;
                 ni       = i;
+                if (d == 0) break;
             }
         }
         subgrids[ni].interpolateInCell(nearest.x(gridX), nearest.y(gridY), vector);
diff --git a/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/MathTransforms.java b/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/MathTransforms.java
index eb81518..23dfc19 100644
--- a/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/MathTransforms.java
+++ b/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/MathTransforms.java
@@ -313,13 +313,16 @@ public final class MathTransforms extends Static {
     public static MathTransform specialize(final MathTransform global, final Map<Envelope,MathTransform> specializations) {
         ArgumentChecks.ensureNonNull("generic", global);
         ArgumentChecks.ensureNonNull("specializations", specializations);
+        final SpecializableTransform tr;
         if (specializations.isEmpty()) {
             return global;
         } else if (global.getSourceDimensions() == 2 && global.getTargetDimensions() == 2) {
-            return new SpecializableTransform2D(global, specializations);
+            tr = new SpecializableTransform2D(global, specializations);
         } else {
-            return new SpecializableTransform(global, specializations);
+            tr = new SpecializableTransform(global, specializations);
         }
+        final MathTransform substitute = tr.getSubstitute();
+        return (substitute != null) ? substitute : tr;
     }
 
     /**
diff --git a/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/SpecializableTransform.java b/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/SpecializableTransform.java
index d22a9a4..1d9e306 100644
--- a/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/SpecializableTransform.java
+++ b/core/sis-referencing/src/main/java/org/apache/sis/referencing/operation/transform/SpecializableTransform.java
@@ -18,24 +18,22 @@ package org.apache.sis.referencing.operation.transform;
 
 import java.util.Map;
 import java.util.List;
-import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Objects;
+import java.util.Collections;
 import java.io.Serializable;
 import org.opengis.geometry.Envelope;
 import org.opengis.geometry.DirectPosition;
 import org.opengis.geometry.MismatchedDimensionException;
-import org.opengis.geometry.MismatchedReferenceSystemException;
 import org.opengis.referencing.operation.Matrix;
 import org.opengis.referencing.operation.MathTransform;
 import org.opengis.referencing.operation.TransformException;
-import org.opengis.referencing.crs.CoordinateReferenceSystem;
 import org.opengis.referencing.operation.NoninvertibleTransformException;
 import org.apache.sis.internal.referencing.DirectPositionView;
 import org.apache.sis.internal.referencing.Resources;
-import org.apache.sis.geometry.GeneralEnvelope;
+import org.apache.sis.internal.referencing.RTreeNode;
 import org.apache.sis.io.wkt.Formatter;
-import org.apache.sis.util.resources.Errors;
+import org.apache.sis.util.ArgumentChecks;
 import org.apache.sis.util.ComparisonMode;
 import org.apache.sis.util.Utilities;
 
@@ -46,7 +44,7 @@ import org.apache.sis.util.Utilities;
  * The lower and upper values of given envelopes are inclusive.
  *
  * @author  Martin Desruisseaux (Geomatys)
- * @version 1.0
+ * @version 1.1
  *
  * @see MathTransforms#specialize(MathTransform, Map)
  *
@@ -70,11 +68,11 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
      * Shall be unmodified after {@link SpecializableTransform} construction.
      */
     @SuppressWarnings("CloneableImplementsClone")                               // We will not use clone().
-    private static final class SubArea extends GeneralEnvelope {
+    private static final class SubArea extends RTreeNode {
         /**
          * For cross-version compatibility.
          */
-        private static final long serialVersionUID = 4197316795428796526L;
+        private static final long serialVersionUID = -7668993675003269862L;
 
         /**
          * The transform to apply in this area.
@@ -85,22 +83,11 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
          * The inverse of the transform, computed when first needed.
          * Synchronization for multi-threading is done (indirectly) in {@link SpecializableTransform#inverse()}.
          *
-         * @see #createInverse(SubArea)
+         * @see #createInverseTransform()
          */
         MathTransform inverse;
 
         /**
-         * Specialization, or {@code null} if none. If non-null, that sub-area shall be fully included
-         * in this {@code SubArea}. The specialization may itself contain another specialization. This
-         * form a chain from this wider area to smallest area, where each step is a smaller area.
-         *
-         * <p>Note that this is note a substitute for an R-Tree. This is an optimization for the common
-         * case where coordinates are close to each other (e.g. when iterating in a geometry), in which
-         * case we can check immediately for inclusion in smaller areas before to check the wider area.</p>
-         */
-        private SubArea specialization;
-
-        /**
          * Creates a new area where a transform is valid.
          */
         SubArea(final Envelope area, final MathTransform transform) {
@@ -109,97 +96,23 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
         }
 
         /**
-         * Tries to add a nested sub-area (a specialization of a specialization).
-         *
-         * @return whether the given area has been added.
-         */
-        boolean addSpecialization(final SubArea candidate) {
-            if (specialization == null) {
-                if (!contains(candidate)) {
-                    return false;
-                }
-            } else if (!candidate.addSpecialization(specialization)) {
-                return specialization.addSpecialization(candidate);
-            }
-            specialization = candidate;
-            return true;
-        }
-
-        /**
-         * Sets the CRS of all given ares to a common value. An exception is thrown if incompatible CRS are found.
-         * This method does not verify the number of dimensions; this check should have been done by the caller.
-         */
-        static void uniformize(final SubArea[] domains) {
-            CoordinateReferenceSystem common = null;
-            for (SubArea area : domains) {
-                do {
-                    final CoordinateReferenceSystem crs = area.getCoordinateReferenceSystem();
-                    if (common == null) {
-                        common = crs;
-                    } else if (crs != null && !Utilities.equalsIgnoreMetadata(common, crs)) {
-                        throw new MismatchedReferenceSystemException(Errors.format(Errors.Keys.MismatchedCRS));
-                    }
-                } while ((area = area.specialization) != null);
-            }
-            for (SubArea area : domains) {
-                do area.setCoordinateReferenceSystem(common);
-                while ((area = area.specialization) != null);
-            }
-        }
-
-        /**
          * Creates the inverse transforms. This method should be invoked only once when first needed
          * in a block synchronized (indirectly) by {@link SpecializableTransform#inverse()}.
          */
-        static void createInverse(SubArea area) throws NoninvertibleTransformException {
-            do {
-                area.inverse = area.transform.inverse();
-                area = area.specialization;
-            } while (area != null);
-        }
-
-        /**
-         * Returns the area that contains the given position, or {@code null} if none.
-         * This method may be replaced by an R-Tree in a future Apache SIS version.
-         */
-        static SubArea find(final SubArea[] domains, final DirectPosition pos) {
-            for (SubArea area : domains) {
-                if (area.contains(pos)) {
-                    SubArea next = area.specialization;
-                    while (next != null && next.contains(pos)) {
-                        area = next;
-                        next = next.specialization;
-                    }
-                    return area;
-                }
-            }
-            return null;
-        }
-
-        /**
-         * Returns the area that contains the given position, looking only in the given area or its specializations.
-         * Returns {@code null} if no area has been found.
-         */
-        static SubArea find(SubArea area, final DirectPosition pos) {
-            SubArea found = null;
-            while (area.contains(pos)) {
-                found = area;
-                area = area.specialization;
-                if (area == null) break;
+        final void createInverseTransform() throws NoninvertibleTransformException {
+            inverse = transform.inverse();
+            for (final RTreeNode node : getChildren()) {
+                ((SubArea) node).createInverseTransform();
             }
-            return found;
         }
 
         /**
-         * Formats the given area and its transform as a pseudo-WKT.
+         * Formats this area and its transform as a pseudo-WKT.
          * For {@link SpecializableTransform#formatTo(Formatter)} implementation only.
          */
-        static void format(SubArea area, final Formatter formatter) {
-            while (area != null) {
-                formatter.newLine(); formatter.append(area);
-                formatter.newLine(); formatter.append(area.transform);
-                area = area.specialization;
-            }
+        final void format(final Formatter formatter) {
+            formatter.newLine(); formatter.append(this);
+            formatter.newLine(); formatter.append(transform);
         }
 
         /**
@@ -207,11 +120,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
          */
         @Override
         public int hashCode() {
-            int code = super.hashCode() ^ transform.hashCode();
-            if (specialization != null) {
-                code += 37 * specialization.hashCode();
-            }
-            return code;
+            return super.hashCode() ^ transform.hashCode();
         }
 
         /**
@@ -219,34 +128,18 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
          */
         @Override
         public boolean equals(final Object obj) {
-            if (super.equals(obj)) {
-                final SubArea other = (SubArea) obj;
-                return transform.equals(other.transform) && Objects.equals(specialization, other.specialization);
-            }
-            return false;
-        }
-
-        /**
-         * Formats this envelope as a "{@code DOMAIN}" element (non-standard).
-         * This is used by {@link SpecializableTransform#formatTo(Formatter)}.
-         */
-        @Override
-        protected String formatTo(final Formatter formatter) {
-            super.formatTo(formatter);
-            return "Domain";
+            return super.equals(obj) && transform.equals(((SubArea) obj).transform);
         }
     }
 
     /**
-     * Domains where specialized transforms are valid. The array should be very small.
-     * In current implementation, elements in this array shall not overlap.
-     * This array may be replaced by an R-Tree in a future Apache SIS version.
+     * Domains where specialized transforms are valid. This is the root of an R-Tree.
      */
-    private final SubArea[] domains;
+    private final RTreeNode domains;
 
     /**
      * The inverse of this transform, computed when first needed.
-     * Part of serialization for avoiding rounding error issues.
+     * This object is included in serialization for avoiding rounding error issues.
      *
      * @see #inverse()
      */
@@ -260,36 +153,42 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
      */
     SpecializableTransform(final MathTransform global, final Map<Envelope,MathTransform> specializations) {
         this.global = global;
+        SubArea root = null;
         final int sourceDim = global.getSourceDimensions();
         final int targetDim = global.getTargetDimensions();
-        final List<SubArea> areas = new ArrayList<>(specializations.size());
         for (final Map.Entry<Envelope,MathTransform> entry : specializations.entrySet()) {
             MathTransform tr = entry.getValue();
             ensureDimensionMatches(0, sourceDim, tr.getSourceDimensions());
             ensureDimensionMatches(1, targetDim, tr.getTargetDimensions());
-            SubArea[] inherited = null;
+            /*
+             * If the given MathTransform is another SpecializableTransform, then instead of storing nested
+             * SpecializableTransforms we will store directly the specializations that it contains. It will
+             * reduce the amountof steps when transforming coordinates.
+             */
+            List<SubArea> inherited = Collections.emptyList();
             if (tr instanceof SpecializableTransform) {
-                inherited = ((SpecializableTransform) tr).domains;
-                tr = ((SpecializableTransform) tr).global;
+                inherited = ((SpecializableTransform) tr).roots();
+                tr        = ((SpecializableTransform) tr).global;
             }
             final SubArea area = new SubArea(entry.getKey(), tr);
-            addSpecialization(area, areas, sourceDim);
-            /*
-             * At this point we are usually done for the current SubArea. But if the given MathTransform
-             * is another SpecializableTransform, then instead of storing nested SpecializableTransforms
-             * we will store directly the specializations that it contains.  This will reduce the amount
-             * of steps when transforming coordinates.
-             */
-            if (inherited != null) {
+            ArgumentChecks.ensureDimensionMatches("envelope", sourceDim, area);
+            if (!area.isEmpty()) {
+                if (root == null) root = area;
+                else root.addNode(area);
+                /*
+                 * If the transform was another SpecializableTransform, copies the nested RTreeNode.
+                 * A copy is necessary: we shall not modify the nodes of the given transform.
+                 */
                 for (final SubArea other : inherited) {
                     final SubArea e = new SubArea(other, other.transform);
                     e.intersect(area);
-                    addSpecialization(e, areas, sourceDim);
+                    if (!e.isEmpty()) {
+                        root.addNode(e);
+                    }
                 }
             }
         }
-        domains = areas.toArray(new SubArea[areas.size()]);
-        SubArea.uniformize(domains);
+        domains = (root != null) ? root.finish() : null;
     }
 
     /**
@@ -305,35 +204,35 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
     }
 
     /**
-     * Verifies if the given {@code area} has the expected number of dimensions,
-     * then adds it to {@code domains} list (eventually as a child of an existing node).
-     *
-     * @param  area     the new sub-area to add.
-     * @param  domains  where to add the sub-area (not necessarily directly; maybe as a child of an existing node).
-     * @param  dim      expected number of dimensions, for verification purpose.
+     * Returns the {@link SubArea} instances at the root of this class. This is the {@link #domains} node,
+     * unless that node is a synthetic node created by {@link RTreeNode} when it needs to contain more than
+     * one children.
      */
-    private static void addSpecialization(final SubArea area, final List<SubArea> domains, final int dim) {
-        if (!area.isEmpty()) {
-            if (area.getDimension() != dim) {
-                throw new MismatchedDimensionException(Errors.format(Errors.Keys.MismatchedDimension_3,
-                            "envelope", dim, area.getDimension()));
-            }
-            for (final SubArea previous : domains) {
-                if (previous.addSpecialization(area)) {
-                    return;
-                }
-            }
-            for (final SubArea previous : domains) {
-                if (area.intersects(previous)) {
-                    // Pending implementation of R-Tree in Apache SIS.
-                    throw new IllegalArgumentException("Current implementation does not accept overlapping envelopes.");
-                }
-            }
-            domains.add(area);
+    @SuppressWarnings("unchecked")
+    private List<SubArea> roots() {
+        if (domains == null) {
+            return Collections.emptyList();
+        } else if (domains instanceof SubArea) {
+            return Collections.singletonList((SubArea) domains);
+        } else {
+            /*
+             * We are cheating here since we have a `List<RTreeNode>`. But this `SpecializableTransform`
+             * class adds only `SubArea` instance in this list, so a ClassCastException in the code that
+             * use this list would be a bug in our conditions of `RTreeNode` use.
+             */
+            return (List) domains.getChildren();
         }
     }
 
     /**
+     * If this transform has no children, then returns the transform that we should use instead.
+     * Otherwise returns {@code null}.
+     */
+    final MathTransform getSubstitute() {
+        return (domains == null) ? global : null;
+    }
+
+    /**
      * Gets the dimension of input points.
      */
     @Override
@@ -350,10 +249,20 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
     }
 
     /**
-     * Returns the transform to use for the given domain.
+     * Returns the node that contains the given position, or {@code null} if none.
+     * This method searches from the root of the tree. It should be invoked only when
+     * we do not know what was the last search result.
      */
-    private MathTransform forDomain(final SubArea domain) {
-        return (domain != null) ? domain.transform : global;
+    private SubArea locate(final DirectPosition pos) {
+        return (SubArea) RTreeNode.locate(domains, pos);
+    }
+
+    /**
+     * Returns the transform to use for the given position, or {@link #global} if none.
+     */
+    private MathTransform forDomain(final DirectPosition pos) {
+        final RTreeNode domain = RTreeNode.locate(domains, pos);
+        return (domain != null) ? ((SubArea) domain).transform : global;
     }
 
     /**
@@ -362,7 +271,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
      */
     @Override
     public final DirectPosition transform(final DirectPosition ptSrc, DirectPosition ptDst) throws TransformException {
-        return forDomain(SubArea.find(domains, ptSrc)).transform(ptSrc, ptDst);
+        return forDomain(ptSrc).transform(ptSrc, ptDst);
     }
 
     /**
@@ -371,7 +280,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
      */
     @Override
     public final Matrix derivative(final DirectPosition point) throws TransformException {
-        return forDomain(SubArea.find(domains, point)).derivative(point);
+        return forDomain(point).derivative(point);
     }
 
     /**
@@ -384,7 +293,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
                                   boolean derivate) throws TransformException
     {
         final DirectPositionView pos = new DirectPositionView.Double(srcPts, srcOff, global.getSourceDimensions());
-        final MathTransform tr = forDomain(SubArea.find(domains, pos));
+        final MathTransform tr = forDomain(pos);
         if (tr instanceof AbstractMathTransform) {
             return ((AbstractMathTransform) tr).transform(srcPts, srcOff, dstPts, dstOff, derivate);
         } else {
@@ -422,7 +331,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
             int dstOff, int srcInc, int dstInc, int numPts) throws TransformException
     {
         final boolean downard = (srcInc < 0);
-        SubArea domain = SubArea.find(domains, src);
+        SubArea domain = locate(src);
         while (numPts > 0) {
             int srcOff = src.offset;
             final MathTransform tr;
@@ -431,19 +340,17 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
                 do {                                        // Count how many points will use that transform.
                     src.offset += srcInc;
                     if (--numPts <= 0) break;
-                    domain = SubArea.find(domains, src);    // More expansive check than the case where domain is non-null.
+                    domain = locate(src);                   // More expansive check than the case where domain is non-null.
                 } while (domain == null);
             } else {
-                final SubArea previous = domain;
+                RTreeNode next = domain;
                 tr = domain.transform;                      // The specialized transform to apply.
                 do {                                        // Count how many points will use that transform.
                     src.offset += srcInc;
                     if (--numPts <= 0) break;
-                    domain = SubArea.find(domain, src);     // Cheaper check compared to the case where domain is null.
-                } while (domain == previous);
-                if (domain == null) {
-                    domain = SubArea.find(domains, src);    // Need to update with the more expansive check.
-                }
+                    next = SubArea.locate(domain, src);     // Cheaper check compared to the case where domain is null.
+                } while (next == domain);
+                domain = (SubArea) next;
             }
             final int num = (src.offset - srcOff) / srcInc;
             int dstLow = dstOff;
@@ -560,7 +467,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
      */
     @Override
     protected final int computeHashCode() {
-        return super.computeHashCode() + 7*global.hashCode() ^ Arrays.hashCode(domains);
+        return super.computeHashCode() + 7*global.hashCode() ^ domains.hashCode();
     }
 
     /**
@@ -571,7 +478,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
         if (super.equals(object, mode)) {
             final SpecializableTransform other = (SpecializableTransform) object;
             return Utilities.deepEquals(global, other.global, mode) &&
-                   Utilities.deepEquals(domains, other.domains, mode);
+                   Objects.equals(domains, other.domains);
         }
         return false;
     }
@@ -589,9 +496,11 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
     protected final String formatTo(final Formatter formatter) {
         formatter.newLine();
         formatter.append(global);
-        for (SubArea domain : domains) {
-            SubArea.format(domain, formatter);
-        }
+        RTreeNode.walk(domains, (node) -> {
+            if (node instanceof SubArea) {
+                ((SubArea) node).format(formatter);
+            }
+        });
         formatter.setInvalidWKT(SpecializableTransform.class, null);
         return "Specializable_MT";
     }
@@ -640,8 +549,8 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
         Inverse(final SpecializableTransform forward) throws NoninvertibleTransformException {
             this.forward = forward;
             this.global = forward.global.inverse();
-            for (final SubArea domain : forward.domains) {
-                SubArea.createInverse(domain);
+            for (final SubArea domain : forward.roots()) {
+                domain.createInverseTransform();
             }
         }
 
@@ -660,7 +569,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
         public final DirectPosition transform(final DirectPosition ptSrc, DirectPosition ptDst) throws TransformException {
             final double[] source = ptSrc.getCoordinate();      // Needs to be first in case ptDst overwrites ptSrc.
             ptDst = global.transform(ptSrc, ptDst);
-            final SubArea domain = SubArea.find(forward.domains, ptDst);
+            final SubArea domain = forward.locate(ptDst);
             if (domain != null) {
                 ptDst = domain.inverse.transform(new DirectPositionView.Double(source), ptDst);
             }
@@ -709,7 +618,7 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
                     derivative = derivate ? tr.derivative(new DirectPositionView.Double(srcPts, srcOff, srcInc)) : null;
                 }
                 if (secondTry) break;
-                final SubArea domain = SubArea.find(forward.domains, new DirectPositionView.Double(dstPts, dstOff, dstInc));
+                final SubArea domain = forward.locate(new DirectPositionView.Double(dstPts, dstOff, dstInc));
                 if (domain != null) {
                     tr = domain.inverse;
                     secondTry = true;
@@ -726,18 +635,17 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
         private void transform(final TransformCall transform, final double[] dstPts,
                 int srcOff, int dstOff, int srcInc, int dstInc, int numPts) throws TransformException
         {
-            final SubArea[] domains = forward.domains;
             transform.apply(global, srcOff, dstOff, numPts);
             final DirectPositionView dst = new DirectPositionView.Double(dstPts, dstOff, dstInc);
             while (numPts > 0) {
-                SubArea domain = SubArea.find(domains, dst);
+                SubArea domain = forward.locate(dst);
                 if (domain == null) {
                     dst.offset += dstInc;
                     numPts--;
                     continue;
                 }
                 do {
-                    final SubArea specialized = domain;             // Contains the specialized transform to use.
+                    RTreeNode next = domain;                        // Contains the specialized transform to use.
                     int num = (dst.offset - dstOff) / dstInc;       // Number of points that are not retransformeD.
                     srcOff += num * srcInc;                         // Skip the source coordinates that are not retransformed.
                     dstOff = dst.offset;                            // Destination index of the first coordinate to retransform.
@@ -747,10 +655,11 @@ class SpecializableTransform extends AbstractMathTransform implements Serializab
                             domain = null;
                             break;
                         }
-                        domain = SubArea.find(domain, dst);
-                    } while (domain == specialized);
+                        next = RTreeNode.locate(domain, dst);
+                    } while (next == domain);
                     num = (dst.offset - dstOff) / dstInc;           // Number of points to retransform.
-                    transform.apply(specialized.inverse, srcOff, dstOff, num);
+                    transform.apply(domain.inverse, srcOff, dstOff, num);
+                    domain = (SubArea) next;
                     srcOff += srcInc * num;
                     dstOff = dst.offset;
                 } while (domain != null);


Mime
View raw message