endorsed/src/org.apache.sis.referencing/main/org/apache/sis/referencing/internal/RTreeNode.java

/*
 * 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.referencing.internal;

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.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;

// Specific to the geoapi-4.0 branch:
import org.opengis.coordinate.MismatchedCoordinateMetadataException;


/**
 * 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>
 *
 * <h2>Possible evolution</h2>
 * 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.
 *
 * @author  Martin Desruisseaux (Geomatys)
 */
@SuppressWarnings("CloneableImplementsClone")
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 as this node. This is used for creating a linked list of nodes
     * that are the children of the {@linkplain #parent}.
     *
     * <h4>Design note</h4>
     * 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.
     */
    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 of 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 method should be invoked only on the instance
     * on which {@link #addNode(RTreeNode)} has been invoked. It performs the following tasks:
     *
     * <ol>
     *   <li>Verify that all nodes have the same CRS or null CRS. 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.</li>
     *   <li>Set the CRS of all nodes to the common value found in previous step.</li>
     *   <li>Ensure that the tree has a single root, by creating a synthetic parent if necessary.</li>
     * </ol>
     *
     * @return the root of the tree, which is {@code this} if this node has no sibling.
     */
    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 nodes for this task; only the immediate children
         * of the new parent. The purpose of the synthetic parent is to have a single root
         * (i.e. no sibling).
         */
        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 MismatchedCoordinateMetadataException(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, or {@code null} if none.
     * @return the smallest node containing the given position, or {@code null} if none.
     */
    public static RTreeNode locate(RTreeNode node, final DirectPosition pos) {
        RTreeNode skip = null;      // For avoiding to invoke `contains(pos)` twice on the same mode.
        if (node != null) 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());
        }
    }
}