AbstractBSPTree.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.commons.geometry.core.partitioning.bsp;

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SplitLocation;

/** Abstract class for Binary Space Partitioning (BSP) tree implementations. This
 * class contains basic structures and algorithms that should be common
 * to all BSP tree implementations, regardless of the end use cases for the tree
 * (eg, whether the tree is intended to represent polytopes, hold attributes like
 * a map, etc).
 *
 * <h2>Implementation Notes</h2>
 * <ul>
 *      <li>The {@link AbstractBSPTree} class is designed to work closely with its nested node type,
 *      {@link AbstractNode}. The tree class handles all tree manipulation operations while the node type
 *      is primarily a simple data type and delegates tree operations to internal methods within its
 *      parent tree. This allows for easier overriding of tree behavior in subclasses.</li>
 *      <li>Each time the structure of the tree is modified, a {@link #getVersion() version number} is
 *      incremented in the tree. This allows certain tree properties to be computed lazily and then
 *      cached. The tree version number is incremented with the {@link #invalidate() invalidate} method. Properties
 *      can be cached directly on nodes using the {@link AbstractBSPTree.AbstractNode#checkValid() checkValid}
 *      and {@link AbstractBSPTree.AbstractNode#nodeInvalidated() nodeInvalidated} methods.</li>
 *      <li>Since the methods used to construct and modify trees can vary by use case, no public API is provided
 *      for manipulating the tree. Subclasses are expected to use the protected methods of this class to
 *      create their own. For tree construction, subclasses are expected to pass their own {@link SubtreeInitializer}
 *      instances to {@link #insert(HyperplaneConvexSubset, SubtreeInitializer) insert} and
 *      {@link #cutNode(AbstractNode, Hyperplane, SubtreeInitializer) cutNode} in order to set the correct properties on
 *      tree nodes. To support tree copying, subclasses must also override
 *      {@link #copyNodeProperties(AbstractNode, AbstractNode) copyNodeProperties}.</li>
 *      <li>This class is not thread safe.</li>
 * </ul>
 *
 * @param <P> Point implementation type
 * @param <N> BSP tree node implementation type
 * @see BSPTree
 */
public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPTree.AbstractNode<P, N>>
    implements BSPTree<P, N> {

    /** Interface used to initialize newly created BSP subtrees, consisting of a single parent
     * node and two child nodes.
     * @param <N> BSP tree node implementation type
     */
    @FunctionalInterface
    public interface SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?, ?>> {

        /** Initialize the given newly-created subtree. The subtree consists of a single root node and two
         * child nodes.
         * @param root the root node of the new subtree
         */
        void initSubtree(N root);
    }

    /** The default number of levels to print when creating a string representation of the tree. */
    private static final int DEFAULT_TREE_STRING_MAX_DEPTH = 8;

    /** Integer value set on various node fields when a value is unknown. */
    private static final int UNKNOWN_VALUE = -1;

    /** The root node for the tree. */
    private N root;

    /** The current modification version for the tree structure. This is incremented each time
     * a structural change occurs in the tree and is used to determine when cached values
     * must be recomputed.
     */
    private int version;

    /** {@inheritDoc} */
    @Override
    public N getRoot() {
        if (root == null) {
            setRoot(createNode());
        }
        return root;
    }

    /** Set the root node for the tree. Cached tree properties are invalidated
     * with {@link #invalidate()}.
     * @param root new root node for the tree
     */
    protected void setRoot(final N root) {
        this.root = root;

        this.root.makeRoot();

        invalidate();
    }

    /** {@inheritDoc} */
    @Override
    public int count() {
        return getRoot().count();
    }

    /** {@inheritDoc} */
    @Override
    public int height() {
        return getRoot().height();
    }

    /** {@inheritDoc} */
    @Override
    public void accept(final BSPTreeVisitor<P, N> visitor) {
        accept(getRoot(), visitor);
    }

    /** {@inheritDoc} */
    @Override
    public N findNode(final P pt, final FindNodeCutRule cutBehavior) {
        return findNode(getRoot(), pt, cutBehavior);
    }

    /** {@inheritDoc} */
    @Override
    public Iterable<N> nodes() {
        return () -> new NodeIterator<>(getRoot());
    }

    /** {@inheritDoc} */
    @Override
    public void copy(final BSPTree<P, N> src) {
        copySubtree(src.getRoot(), getRoot());
    }

    /** {@inheritDoc} */
    @Override
    public void extract(final N node) {
        // copy downward
        final N extracted = importSubtree(node);

        // extract upward
        final N newRoot = extractParentPath(node, extracted);

        // set the root of this tree
        setRoot(newRoot);
    }

    /** {@inheritDoc} */
    @Override
    public void transform(final Transform<P> transform) {
        final boolean swapChildren = swapsInsideOutside(transform);
        transformRecursive(getRoot(), transform, swapChildren);

        invalidate();
    }

    /** Get a simple string representation of the tree structure. The returned string contains
     * the tree structure down to the default max depth of {@value #DEFAULT_TREE_STRING_MAX_DEPTH}.
     * @return a string representation of the tree
     */
    public String treeString() {
        return treeString(DEFAULT_TREE_STRING_MAX_DEPTH);
    }

    /** Get a simple string representation of the tree structure. The returned string contains
     * the tree structure down to {@code maxDepth}.
     * @param maxDepth the maximum depth in the tree to print; nodes below this depth are skipped
     * @return a string representation of the tree
     */
    public String treeString(final int maxDepth) {
        final BSPTreePrinter<P, N> printer = new BSPTreePrinter<>(maxDepth);
        accept(printer);

        return printer.toString();
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        return new StringBuilder()
                .append(getClass().getSimpleName())
                .append("[count= ")
                .append(count())
                .append(", height= ")
                .append(height())
                .append(']')
                .toString();
    }

    /** Create a new node for this tree.
     * @return a new node for this tree
     */
    protected abstract N createNode();

    /** Copy non-structural node properties from {@code src} to {@code dst}.
     * Non-structural properties are those properties not directly related
     * to the structure of the BSP tree, i.e. properties other than parent/child
     * connections and cuts. Subclasses should override this method to copy additional
     * properties stored on nodes.
     * @param src source node
     * @param dst destination node
     */
    protected abstract void copyNodeProperties(N src, N dst);

    /** Create a non-structural copy of the given node. Properties such as parent/child
     * connections and cuts are <em>not</em> copied.
     * @param src the node to copy; does not need to belong to the current tree
     * @return the copied node
     * @see AbstractBSPTree#copyNodeProperties(AbstractNode, AbstractNode)
     */
    protected N copyNode(final N src) {
        final N copy = createNode();
        copyNodeProperties(src, copy);

        return copy;
    }

    /** Recursively copy a subtree. The returned node is not attached to the current tree.
     * Structural <em>and</em> non-structural properties are copied from the source subtree
     * to the destination subtree. This method does nothing if {@code src} and {@code dst}
     * reference the same node.
     * @param src the node representing the source subtree; does not need to belong to the
     *      current tree
     * @param dst the node representing the destination subtree
     * @return the copied node, ie {@code dst}
     */
    protected N copySubtree(final N src, final N dst) {
        // only copy if we're actually switching nodes
        if (src != dst) {
            // copy non-structural properties
            copyNodeProperties(src, dst);

            // copy the subtree structure
            HyperplaneConvexSubset<P> cut = null;
            N minus = null;
            N plus = null;

            if (!src.isLeaf()) {
                final AbstractBSPTree<P, N> dstTree = dst.getTree();

                cut = src.getCut();
                minus = copySubtree(src.getMinus(), dstTree.createNode());
                plus = copySubtree(src.getPlus(), dstTree.createNode());
            }

            dst.setSubtree(cut, minus, plus);
        }

        return dst;
    }

    /** Import the subtree represented by the given node into this tree. If the given node
     * already belongs to this tree, then the node is returned directly without modification.
     * If the node does <em>not</em> belong to this tree, a new node is created and the src node
     * subtree is copied into it.
     *
     * <p>This method does not modify the current structure of the tree.</p>
     * @param src node to import
     * @return the given node if it belongs to this tree, otherwise a new node containing
     *      a copy of the given node's subtree
     * @see #copySubtree(AbstractNode, AbstractNode)
     */
    protected N importSubtree(final N src) {
        // create a copy of the node if it's not already in this tree
        if (src.getTree() != this) {
            return copySubtree(src, createNode());
        }

        return src;
    }

    /** Extract the path from {@code src} to the root of its tree and
     * set it as the parent path of {@code dst}. Leaf nodes created during
     * the extraction are given the same node properties as their counterparts
     * in the source tree but without the cuts and child nodes. The properties
     * of {@code dst} are not modified, with the exception of its parent node
     * reference.
     * @param src the source node to copy the parent path from
     * @param dst the destination node to place under the extracted path
     * @return the root node of the extracted path
     */
    protected N extractParentPath(final N src, final N dst) {
        N dstParent = dst;
        N dstChild;

        N srcChild = src;
        N srcParent = srcChild.getParent();

        while (srcParent != null) {
            dstChild = dstParent;
            dstParent = copyNode(srcParent);

            if (srcChild.isMinus()) {
                dstParent.setSubtree(
                        srcParent.getCut(),
                        dstChild,
                        copyNode(srcParent.getPlus()));
            } else {
                dstParent.setSubtree(
                        srcParent.getCut(),
                        copyNode(srcParent.getMinus()),
                        dstChild);
            }

            srcChild = srcParent;
            srcParent = srcChild.getParent();
        }

        return dstParent;
    }

    /** Find the smallest node in the tree containing the point, starting
     * at the given node.
     * @param start the node to begin the search with
     * @param pt the point to check
     * @param cutRule value determining the search behavior when the test point
     *      lies directly on the cut of an internal node
     * @return the smallest node in the tree containing the point
     */
    protected N findNode(final N start, final P pt, final FindNodeCutRule cutRule) {
        final Hyperplane<P> cutHyper = start.getCutHyperplane();
        if (cutHyper != null) {
            final HyperplaneLocation cutLoc = cutHyper.classify(pt);

            final boolean onPlusSide = cutLoc == HyperplaneLocation.PLUS;
            final boolean onMinusSide = cutLoc == HyperplaneLocation.MINUS;
            final boolean onCut = !onPlusSide && !onMinusSide;

            if (onMinusSide || (onCut && cutRule == FindNodeCutRule.MINUS)) {
                return findNode(start.getMinus(), pt, cutRule);
            } else if (onPlusSide || cutRule == FindNodeCutRule.PLUS) {
                return findNode(start.getPlus(), pt, cutRule);
            }
        }
        return start;
    }

    /** Visit the nodes in a subtree.
     * @param node the node to begin the visit process
     * @param visitor the visitor to pass nodes to
     */
    protected void accept(final N node, final BSPTreeVisitor<P, N> visitor) {
        acceptRecursive(node, visitor);
    }

    /** Recursively visit the nodes in the subtree rooted at the given node.
     * @param node the node located at the root of the subtree to visit
     * @param visitor the visitor to pass nodes to
     * @return true if the visit operation should continue
     */
    private boolean acceptRecursive(final N node, final BSPTreeVisitor<P, N> visitor) {
        if (node.isLeaf()) {
            return shouldContinueVisit(visitor.visit(node));
        } else {
            final BSPTreeVisitor.Order order = visitor.visitOrder(node);

            if (order != null) {

                switch (order) {
                case PLUS_MINUS_NODE:
                    return acceptRecursive(node.getPlus(), visitor) &&
                            acceptRecursive(node.getMinus(), visitor) &&
                            shouldContinueVisit(visitor.visit(node));
                case PLUS_NODE_MINUS:
                    return acceptRecursive(node.getPlus(), visitor) &&
                            shouldContinueVisit(visitor.visit(node)) &&
                            acceptRecursive(node.getMinus(), visitor);
                case MINUS_PLUS_NODE:
                    return acceptRecursive(node.getMinus(), visitor) &&
                            acceptRecursive(node.getPlus(), visitor) &&
                            shouldContinueVisit(visitor.visit(node));
                case MINUS_NODE_PLUS:
                    return acceptRecursive(node.getMinus(), visitor) &&
                            shouldContinueVisit(visitor.visit(node)) &&
                            acceptRecursive(node.getPlus(), visitor);
                case NODE_PLUS_MINUS:
                    return shouldContinueVisit(visitor.visit(node)) &&
                            acceptRecursive(node.getPlus(), visitor) &&
                            acceptRecursive(node.getMinus(), visitor);
                case  NODE_MINUS_PLUS:
                    return shouldContinueVisit(visitor.visit(node)) &&
                            acceptRecursive(node.getMinus(), visitor) &&
                            acceptRecursive(node.getPlus(), visitor);
                default: // NONE
                    break;
                }
            }

            return true;
        }
    }

    /** Return true if the given BSP tree visit result indicates that the current visit
     * operation should continue.
     * @param result visit result from BSP tree node visit operation
     * @return true if the visit operation should continue with remaining nodes in the
     *      BSP tree
     */
    private boolean shouldContinueVisit(final BSPTreeVisitor.Result result) {
        return result == BSPTreeVisitor.Result.CONTINUE;
    }

    /** Cut a node with a hyperplane. The algorithm proceeds as follows:
     * <ol>
     *      <li>The hyperplane is trimmed by splitting it with each cut hyperplane on the
     *      path from the given node to the root of the tree.</li>
     *      <li>If the remaining portion of the hyperplane is <em>not</em> empty, then
     *          <ul>
     *              <li>the remaining portion becomes the cut hyperplane subset for the node,</li>
     *              <li>two new child nodes are created and initialized with
     *              {@code subtreeInitializer}, and</li>
     *              <li>true is returned.</li>
     *          </ul>
     *      </li>
     *      <li>If the remaining portion of the hyperplane <em>is</em> empty (ie, the
     *      cutting hyperplane does not intersect the node's region), then
     *          <ul>
     *              <li>the node is converted to a leaf node (meaning that previous
     *              child nodes are lost), and</li>
     *              <li>false is returned.</li>
     *          </ul>
     *      </li>
     * </ol>
     *
     * <p>It is important to note that since this method uses the path from given node
     * to the tree root, it must only be used on nodes that are already inserted into
     * the tree.</p>
     *
     * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree
     * structure is changed.</p>
     *
     * @param node the node to cut
     * @param cutter the hyperplane to cut the node with
     * @param subtreeInitializer object used to initialize any newly-created subtrees
     * @return true if the node was cut and two new child nodes were created;
     *      otherwise false
     * @see #trimToNode(AbstractNode, HyperplaneConvexSubset)
     * @see #setNodeCut(AbstractNode, HyperplaneConvexSubset, SubtreeInitializer)
     * @see #removeNodeCut(AbstractNode)
     * @see #invalidate()
     */
    protected boolean cutNode(final N node, final Hyperplane<P> cutter,
            final SubtreeInitializer<N> subtreeInitializer) {

        // cut the hyperplane using all hyperplanes from this node up
        // to the root
        final HyperplaneConvexSubset<P> cut = trimToNode(node, cutter.span());
        if (cut == null || cut.isEmpty()) {
            // insertion failed; the node was not cut
            removeNodeCut(node);
            return false;
        }

        setNodeCut(node, cut, subtreeInitializer);
        return true;
    }

    /** Trim the given hyperplane convex subset to the region defined by the given node. This method
     * cuts the subset with the cut hyperplanes (binary partitioners) of all parent nodes up to the
     * root and returns the trimmed subset or {@code null} if the subset lies outside of the region
     * defined by the node.
     *
     * <p>If the subset is directly coincident with a binary partitioner of a parent node,
     * then the relative orientations of the associated hyperplanes are used to determine the behavior,
     * as described below.
     * <ul>
     *      <li>If the orientations are <strong>similar</strong>, then the subset is determined to
     *      lie <em>outside</em> of the node's region and {@code null} is returned.</li>
     *      <li>If the orientations are <strong>different</strong> (ie, opposite), then the subset
     *      is determined to lie <em>inside</em> of the node's region and the fit operation continues
     *      with the remaining parent nodes.</li>
     * </ul>
     * These rules are designed to allow the creation of trees with node regions that are the thickness
     * of a single hyperplane. For example, in two dimensions, a tree could be constructed with an internal
     * node containing a cut along the x-axis in the positive direction and with a child node containing a
     * cut along the x-axis in the opposite direction. If the nodes in the tree are given inside and outside
     * attributes, then this tree could be used to represent a region consisting of a single line or a region
     * consisting of the entire space except for the single line. This would not be possible if nodes were not
     * able to have cut hyperplanes that were coincident with parent cuts but in opposite directions.
     *
     * <p>
     * Another way of looking at the rules above is that inserting a hyperplane into the tree that exactly
     * matches the hyperplane of a parent node does not add any information to the tree. However, adding a
     * hyperplane to the tree that is coincident with a parent node but with the opposite orientation,
     * <em>does</em> add information to the tree.
     *
     * @param node the node representing the region to fit the hyperplane subset to
     * @param sub the hyperplane subset to trim to the node's region
     * @return the trimmed hyperplane subset or null if the given hyperplane subset does not intersect
     *      the node's region
     */
    protected HyperplaneConvexSubset<P> trimToNode(final N node, final HyperplaneConvexSubset<P> sub) {

        HyperplaneConvexSubset<P> result = sub;

        N parentNode = node.getParent();
        N currentNode = node;

        while (parentNode != null && result != null) {
            final Split<? extends HyperplaneConvexSubset<P>> split = result.split(parentNode.getCutHyperplane());

            if (split.getLocation() == SplitLocation.NEITHER) {
                // if we're directly on the splitter and have the same orientation, then
                // we say the subset does not lie in the node's region (no new information
                // is added to the tree in this case)
                if (result.getHyperplane().similarOrientation(parentNode.getCutHyperplane())) {
                    result = null;
                }
            } else {
                result = currentNode.isPlus() ? split.getPlus() : split.getMinus();
            }

            currentNode = parentNode;
            parentNode = parentNode.getParent();
        }

        return result;
    }

    /** Remove the cut from the given node. Returns true if the node had a cut before
     * the call to this method. Any previous child nodes are lost.
     *
     * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree
     * structure changed.</p>
     * @param node the node to remove the cut from
     * @return true if the node previously had a cut
     */
    protected boolean removeNodeCut(final N node) {
        if (node.getCut() != null) {
            node.setSubtree(null, null, null);

            invalidate();

            return true;
        }

        return false;
    }

    /** Set the cut hyperplane subset for the given node. Two new child nodes are created for the
     * node and the new subtree is initialized with {@code subtreeInitializer}.
     *
     * <p>This method performs absolutely <em>no</em> validation on the given cut
     * hyperplane subset. It is the responsibility of the caller to ensure that the
     * hyperplane subset fits the region represented by the node.</p>
     *
     * <p>This method always calls {@link #invalidate()} to invalidate cached tree properties.</p>
     * @param node the node to cut
     * @param cut the hyperplane convex subset to set as the node cut
     * @param subtreeInitializer object used to initialize the newly-created subtree
     */
    protected void setNodeCut(final N node, final HyperplaneConvexSubset<P> cut,
            final SubtreeInitializer<N> subtreeInitializer) {

        node.setSubtree(cut, createNode(), createNode());

        subtreeInitializer.initSubtree(node);

        invalidate();
    }

    /** Insert the given hyperplane convex subset into the tree, starting at the root node. Any subtrees
     * created are initialized with {@code subtreeInit}.
     * @param convexSub hyperplane convex subset to insert into the tree
     * @param subtreeInit object used to initialize newly created subtrees
     */
    protected void insert(final HyperplaneConvexSubset<P> convexSub, final SubtreeInitializer<N> subtreeInit) {
        insertRecursive(getRoot(), convexSub,
                convexSub.getHyperplane().span(), subtreeInit);
    }

    /** Recursively insert a hyperplane convex subset into the tree at the given node.
     * @param node the node to begin insertion with
     * @param insert the hyperplane subset to insert
     * @param trimmed hyperplane subset containing the result of splitting the entire
     *      space with each hyperplane from this node to the root
     * @param subtreeInit object used to initialize newly created subtrees
     */
    private void insertRecursive(final N node, final HyperplaneConvexSubset<P> insert,
            final HyperplaneConvexSubset<P> trimmed, final SubtreeInitializer<N> subtreeInit) {
        if (node.isLeaf()) {
            setNodeCut(node, trimmed, subtreeInit);
        } else {
            final Split<? extends HyperplaneConvexSubset<P>> insertSplit = insert.split(node.getCutHyperplane());

            final HyperplaneConvexSubset<P> minus = insertSplit.getMinus();
            final HyperplaneConvexSubset<P> plus = insertSplit.getPlus();

            if (minus != null || plus != null) {
                final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit = trimmed.split(node.getCutHyperplane());

                if (minus != null) {
                    insertRecursive(node.getMinus(), minus, trimmedSplit.getMinus(), subtreeInit);
                }
                if (plus != null) {
                    insertRecursive(node.getPlus(), plus, trimmedSplit.getPlus(), subtreeInit);
                }
            }
        }
    }

    /** Return true if the given transform swaps the inside and outside of
     * the region.
     *
     * <p>The default behavior of this method is to return true if the transform
     * does not preserve spatial orientation (ie, {@link Transform#preservesOrientation()}
     * is false). Subclasses may need to override this method to implement the correct
     * behavior for their space and dimension.</p>
     * @param transform transform to check
     * @return true if the given transform swaps the interior and exterior of
     *      the region
     */
    protected boolean swapsInsideOutside(final Transform<P> transform) {
        return !transform.preservesOrientation();
    }

    /** Transform the subtree rooted as {@code node} recursively.
     * @param node the root node of the subtree to transform
     * @param t the transform to apply
     * @param swapChildren if true, the plus and minus child nodes of each internal node
     *      will be swapped; this should be the case when the transform is a reflection
     */
    private void transformRecursive(final N node, final Transform<P> t, final boolean swapChildren) {
        if (node.isInternal()) {
            // transform our cut
            final HyperplaneConvexSubset<P> transformedCut = node.getCut().transform(t);

            // transform our children
            transformRecursive(node.getMinus(), t, swapChildren);
            transformRecursive(node.getPlus(), t, swapChildren);

            final N transformedMinus = swapChildren ? node.getPlus() : node.getMinus();
            final N transformedPlus = swapChildren ? node.getMinus() : node.getPlus();

            // set our new state
            node.setSubtree(transformedCut, transformedMinus, transformedPlus);
        }
    }

    /** Split this tree with the given hyperplane, placing the split contents into the given
     * target trees. One of the given trees may be null, in which case that portion of the split
     * will not be exported. The current tree is not modified.
     * @param splitter splitting hyperplane
     * @param minus tree that will contain the portion of the tree on the minus side of the splitter
     * @param plus tree that will contain the portion of the tree on the plus side of the splitter
     */
    protected void splitIntoTrees(final Hyperplane<P> splitter,
            final AbstractBSPTree<P, N> minus, final AbstractBSPTree<P, N> plus) {

        final AbstractBSPTree<P, N> temp = (minus != null) ? minus : plus;

        final N splitRoot = temp.splitSubtree(this.getRoot(), splitter.span());

        if (minus != null) {
            if (plus != null) {
                plus.extract(splitRoot.getPlus());
            }
            minus.extract(splitRoot.getMinus());
        } else {
            plus.extract(splitRoot.getPlus());
        }
    }

    /** Split the subtree rooted at the given node by a partitioning convex subset defined
     * on the same region as the node. The subtree rooted at {@code node} is imported into
     * this tree, meaning that if it comes from a different tree, the other tree is not
     * modified.
     * @param node the root node of the subtree to split; may come from a different tree,
     *      in which case the other tree is not modified
     * @param partitioner partitioning convex subset
     * @return node containing the split subtree
     */
    protected N splitSubtree(final N node, final HyperplaneConvexSubset<P> partitioner) {
        if (node.isLeaf()) {
            return splitLeafNode(node, partitioner);
        }
        return splitInternalNode(node, partitioner);
    }

    /** Split the given leaf node by a partitioning convex subset defined on the
     * same region and import it into this tree.
     * @param node the leaf node to split
     * @param partitioner partitioning convex subset
     * @return node containing the split subtree
     */
    private N splitLeafNode(final N node, final HyperplaneConvexSubset<P> partitioner) {
        // in this case, we just create a new parent node with the partitioner as its
        // cut and two copies of the original node as children
        final N parent = createNode();
        parent.setSubtree(partitioner, copyNode(node), copyNode(node));

        return parent;
    }

    /** Split the given internal node by a partitioning convex subset defined on the same region
     * as the node and import it into this tree.
     * @param node the internal node to split
     * @param partitioner partitioning convex subset
     * @return node containing the split subtree
     */
    private N splitInternalNode(final N node, final HyperplaneConvexSubset<P> partitioner) {
        // split the partitioner and node cut with each other's hyperplanes to determine their relative positions
        final Split<? extends HyperplaneConvexSubset<P>> partitionerSplit = partitioner.split(node.getCutHyperplane());
        final Split<? extends HyperplaneConvexSubset<P>> nodeCutSplit =
                node.getCut().split(partitioner.getHyperplane());

        final SplitLocation partitionerSplitSide = partitionerSplit.getLocation();
        final SplitLocation nodeCutSplitSide = nodeCutSplit.getLocation();

        final N result = createNode();

        final N resultMinus;
        final N resultPlus;

        if (partitionerSplitSide == SplitLocation.PLUS) {
            if (nodeCutSplitSide == SplitLocation.PLUS) {
                // partitioner is on node cut plus side, node cut is on partitioner plus side
                final N nodePlusSplit = splitSubtree(node.getPlus(), partitioner);

                resultMinus = nodePlusSplit.getMinus();

                resultPlus = copyNode(node);
                resultPlus.setSubtree(node.getCut(), importSubtree(node.getMinus()), nodePlusSplit.getPlus());
            } else {
                // partitioner is on node cut plus side, node cut is on partitioner minus side
                final N nodePlusSplit = splitSubtree(node.getPlus(), partitioner);

                resultMinus = copyNode(node);
                resultMinus.setSubtree(node.getCut(), importSubtree(node.getMinus()), nodePlusSplit.getMinus());

                resultPlus = nodePlusSplit.getPlus();
            }
        } else if (partitionerSplitSide == SplitLocation.MINUS) {
            if (nodeCutSplitSide == SplitLocation.MINUS) {
                // partitioner is on node cut minus side, node cut is on partitioner minus side
                final N nodeMinusSplit = splitSubtree(node.getMinus(), partitioner);

                resultMinus = copyNode(node);
                resultMinus.setSubtree(node.getCut(), nodeMinusSplit.getMinus(), importSubtree(node.getPlus()));

                resultPlus = nodeMinusSplit.getPlus();
            } else {
                // partitioner is on node cut minus side, node cut is on partitioner plus side
                final N nodeMinusSplit = splitSubtree(node.getMinus(), partitioner);

                resultMinus = nodeMinusSplit.getMinus();

                resultPlus = copyNode(node);
                resultPlus.setSubtree(node.getCut(), nodeMinusSplit.getPlus(), importSubtree(node.getPlus()));
            }
        } else if (partitionerSplitSide == SplitLocation.BOTH) {
            // partitioner and node cut split each other
            final N nodeMinusSplit = splitSubtree(node.getMinus(), partitionerSplit.getMinus());
            final N nodePlusSplit = splitSubtree(node.getPlus(), partitionerSplit.getPlus());

            resultMinus = copyNode(node);
            resultMinus.setSubtree(nodeCutSplit.getMinus(), nodeMinusSplit.getMinus(), nodePlusSplit.getMinus());

            resultPlus = copyNode(node);
            resultPlus.setSubtree(nodeCutSplit.getPlus(), nodeMinusSplit.getPlus(), nodePlusSplit.getPlus());
        } else {
            // partitioner and node cut are parallel or anti-parallel
            final boolean sameOrientation = partitioner.getHyperplane().similarOrientation(node.getCutHyperplane());

            resultMinus = importSubtree(sameOrientation ? node.getMinus() : node.getPlus());
            resultPlus = importSubtree(sameOrientation ? node.getPlus() : node.getMinus());
        }

        result.setSubtree(partitioner, resultMinus, resultPlus);

        return result;
    }

    /** Invalidate any previously computed properties that rely on the internal structure of the tree.
     * This method must be called any time the tree's internal structure changes in order to force cacheable
     * tree and node properties to be recomputed the next time they are requested.
     *
     * <p>This method increments the tree's {@link #version} property.</p>
     * @see #getVersion()
     */
    protected void invalidate() {
        version = Math.max(0, version + 1); // positive values only
    }

    /** Get the current structural version of the tree. This is incremented each time the
     * tree structure is changes and can be used by nodes to allow caching of computed values.
     * @return the current version of the tree structure
     * @see #invalidate()
     */
    protected int getVersion() {
        return version;
    }

    /** Abstract implementation of {@link BSPTree.Node}. This class is intended for use with
     * {@link AbstractBSPTree} and delegates tree mutation methods back to the parent tree object.
     * @param <P> Point implementation type
     * @param <N> BSP tree node implementation type
     */
    public abstract static class AbstractNode<P extends Point<P>, N extends AbstractNode<P, N>>
        implements BSPTree.Node<P, N> {
        /** The owning tree instance. */
        private final AbstractBSPTree<P, N> tree;

        /** The parent node; this will be null for the tree root node. */
        private N parent;

        /** The hyperplane convex subset cutting the node's region; this will be null for leaf nodes. */
        private HyperplaneConvexSubset<P> cut;

        /** The node lying on the minus side of the cut hyperplane; this will be null
         * for leaf nodes.
         */
        private N minus;

        /** The node lying on the plus side of the cut hyperplane; this will be null
         * for leaf nodes.
         */
        private N plus;

        /** The current version of the node. This is set to track the tree's version
         * and is used to detect when certain values need to be recomputed due to
         * structural changes in the tree.
         */
        private int nodeVersion = -1;

        /** The depth of this node in the tree. This will be zero for the root node and
         * {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs to be computed.
         */
        private int depth = UNKNOWN_VALUE;

        /** The total number of nodes in the subtree rooted at this node. This will be
         * set to {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs
         * to be computed.
         */
        private int count = UNKNOWN_VALUE;

        /** The height of the subtree rooted at this node. This will
         * be set to {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs
         * to be computed.
         */
        private int height = UNKNOWN_VALUE;

        /** Simple constructor.
         * @param tree the tree instance that owns this node
         */
        protected AbstractNode(final AbstractBSPTree<P, N> tree) {
            this.tree = tree;
        }

        /** {@inheritDoc} */
        @Override
        public AbstractBSPTree<P, N> getTree() {
            return tree;
        }

        /** {@inheritDoc} */
        @Override
        public int depth() {
            // Calculate our depth based on our parent's depth, if possible.
            if (depth == UNKNOWN_VALUE &&
                parent != null) {
                final int parentDepth = parent.depth();
                if (parentDepth != UNKNOWN_VALUE) {
                    depth = parentDepth + 1;
                }
            }
            return depth;
        }

        /** {@inheritDoc} */
        @Override
        public int height() {
            checkValid();

            if (height == UNKNOWN_VALUE) {
                if (isLeaf()) {
                    height = 0;
                } else {
                    height = Math.max(getMinus().height(), getPlus().height()) + 1;
                }
            }

            return height;
        }

        /** {@inheritDoc} */
        @Override
        public int count() {
            checkValid();

            if (count == UNKNOWN_VALUE) {
                count = 1;

                if (!isLeaf()) {
                    count += minus.count() + plus.count();
                }
            }

            return count;
        }

        /** {@inheritDoc} */
        @Override
        public Iterable<N> nodes() {
            return () -> new NodeIterator<>(getSelf());
        }

        /** {@inheritDoc} */
        @Override
        public void accept(final BSPTreeVisitor<P, N> visitor) {
            tree.accept(getSelf(), visitor);
        }

        /** {@inheritDoc} */
        @Override
        public N getParent() {
            return parent;
        }

        /** {@inheritDoc} */
        @Override
        public boolean isLeaf() {
            return cut == null;
        }

        /** {@inheritDoc} */
        @Override
        public boolean isInternal() {
            return cut != null;
        }

        /** {@inheritDoc} */
        @Override
        public boolean isPlus() {
            return parent != null && parent.getPlus() == this;
        }

        /** {@inheritDoc} */
        @Override
        public boolean isMinus() {
            return parent != null && parent.getMinus() == this;
        }

        /** {@inheritDoc} */
        @Override
        public HyperplaneConvexSubset<P> getCut() {
            return cut;
        }

        /** {@inheritDoc} */
        @Override
        public Hyperplane<P> getCutHyperplane() {
            return (cut != null) ? cut.getHyperplane() : null;
        }

        /** {@inheritDoc} */
        @Override
        public N getPlus() {
            return plus;
        }

        /** {@inheritDoc} */
        @Override
        public N getMinus() {
            return minus;
        }

        /** {@inheritDoc} */
        @Override
        public HyperplaneConvexSubset<P> trim(final HyperplaneConvexSubset<P> sub) {
            return getTree().trimToNode(getSelf(), sub);
        }

        /** {@inheritDoc} */
        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append(this.getClass().getSimpleName())
                .append("[cut= ")
                .append(getCut())
                .append(']');

            return sb.toString();
        }

        /** Set the parameters for the subtree rooted at this node. The arguments should either be
         * all null (representing a leaf node) or all non-null (representing an internal node).
         *
         * <p>Absolutely no validation is performed on the arguments. Callers are responsible for
         * ensuring that any given hyperplane subset fits the region defined by the node and that
         * any child nodes belong to this tree and are correctly initialized.</p>
         *
         * @param newCut the new cut hyperplane subset for the node
         * @param newMinus the new minus child for the node
         * @param newPlus the new plus child for the node
         */
        protected void setSubtree(final HyperplaneConvexSubset<P> newCut, final N newMinus, final N newPlus) {
            this.cut = newCut;

            final N self = getSelf();

            // cast for access to private member
            final AbstractNode<P, N> minusNode = newMinus;
            final AbstractNode<P, N> plusNode = newPlus;

            // get the child depth now if we know it offhand, otherwise set it to the unknown value
            // and have the child pull it when needed
            final int childDepth = (depth != UNKNOWN_VALUE) ? depth + 1 : UNKNOWN_VALUE;

            if (newMinus != null) {
                minusNode.parent = self;
                minusNode.depth = childDepth;
            }
            this.minus = newMinus;

            if (newPlus != null) {
                plusNode.parent = self;
                plusNode.depth = childDepth;
            }
            this.plus = newPlus;
        }

        /**
         * Make this node a root node, detaching it from its parent and settings its depth to zero.
         * Any previous parent node will be left in an invalid state since one of its children now
         * does not have a reference back to it.
         */
        protected void makeRoot() {
            parent = null;
            depth = 0;
        }

        /** Check if cached node properties are valid, meaning that no structural updates have
         * occurred in the tree since the last call to this method. If updates have occurred, the
         * {@link #nodeInvalidated()} method is called to clear the cached properties. This method
         * should be called at the beginning of any method that fetches cacheable properties
         * to ensure that no stale values are returned.
         */
        protected void checkValid() {
            final int treeVersion = tree.getVersion();

            if (nodeVersion != treeVersion) {
                // the tree structure changed somewhere
                nodeInvalidated();

                // store the current version
                nodeVersion = treeVersion;
            }
        }

        /** Method called from {@link #checkValid()} when updates
         * are detected in the tree. This method should clear out any
         * computed properties that rely on the structure of the tree
         * and prepare them for recalculation.
         */
        protected void nodeInvalidated() {
            count = UNKNOWN_VALUE;
            height = UNKNOWN_VALUE;
        }

        /** Get a reference to the current instance, cast to type N.
         * @return a reference to the current instance, as type N.
         */
        protected abstract N getSelf();
    }

    /** Class for iterating through the nodes in a BSP subtree.
     * @param <P> Point implementation type
     * @param <N> Node implementation type
     */
    private static final class NodeIterator<P extends Point<P>, N extends AbstractNode<P, N>> implements Iterator<N> {

        /** The current node stack. */
        private final Deque<N> stack = new LinkedList<>();

        /** Create a new instance for iterating over the nodes in the given subtree.
         * @param subtreeRoot the root node of the subtree to iterate
         */
        NodeIterator(final N subtreeRoot) {
            stack.push(subtreeRoot);
        }

        /** {@inheritDoc} */
        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        /** {@inheritDoc} */
        @Override
        public N next() {
            if (stack.isEmpty()) {
                throw new NoSuchElementException();
            }

            final N result = stack.pop();

            if (result != null && !result.isLeaf()) {
                stack.push(result.getPlus());
                stack.push(result.getMinus());
            }

            return result;
        }
    }
}