/*
    * 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.spherical.twod;
  
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.List;
  import java.util.stream.Stream;
  import java.util.stream.StreamSupport;
  
  import org.apache.commons.geometry.core.partitioning.Hyperplane;
  import org.apache.commons.geometry.core.partitioning.Split;
  import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
  import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
  import org.apache.commons.geometry.euclidean.threed.Vector3D;
  import org.apache.commons.numbers.core.Precision;
  import org.apache.commons.numbers.core.Sum;
  
  /** BSP tree representing regions in 2D spherical space.
   */
  public class RegionBSPTree2S extends AbstractRegionBSPTree<Point2S, RegionBSPTree2S.RegionNode2S>
      implements BoundarySource2S {
      /** Constant containing the area of the full spherical space. */
      private static final double FULL_SIZE = 4 * Math.PI;
  
      /** List of great arc path comprising the region boundary. */
      private List<GreatArcPath> boundaryPaths;
  
      /** Create a new, empty instance.
       */
      public RegionBSPTree2S() {
          this(false);
      }
  
      /** Create a new region. If {@code full} is true, then the region will
       * represent the entire 2-sphere. Otherwise, it will be empty.
       * @param full whether or not the region should contain the entire
       *      2-sphere or be empty
       */
      public RegionBSPTree2S(final boolean full) {
          super(full);
      }
  
      /** Return a deep copy of this instance.
       * @return a deep copy of this instance.
       * @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
       */
      public RegionBSPTree2S copy() {
          final RegionBSPTree2S result = RegionBSPTree2S.empty();
          result.copy(this);
  
          return result;
      }
  
      /** {@inheritDoc} */
      @Override
      public Iterable<GreatArc> boundaries() {
          return createBoundaryIterable(GreatArc.class::cast);
      }
  
      /** {@inheritDoc} */
      @Override
      public Stream<GreatArc> boundaryStream() {
          return StreamSupport.stream(boundaries().spliterator(), false);
      }
  
      /** {@inheritDoc} */
      @Override
      public List<GreatArc> getBoundaries() {
          return createBoundaryList(GreatArc.class::cast);
      }
  
      /** Get the boundary of the region as a list of connected great arc paths. The
       * arcs are oriented such that their minus (left) side lies on the interior of
       * the region.
       * @return great arc paths representing the region boundary
       */
      public List<GreatArcPath> getBoundaryPaths() {
          if (boundaryPaths == null) {
              boundaryPaths = Collections.unmodifiableList(computeBoundaryPaths());
          }
          return boundaryPaths;
      }
  
      /** Return a list of {@link ConvexArea2S}s representing the same region
      * as this instance. One convex area is returned for each interior leaf
      * node in the tree.
      * @return a list of convex areas representing the same region as this
      *      instance
      */
     public List<ConvexArea2S> toConvex() {
         final List<ConvexArea2S> result = new ArrayList<>();
 
         toConvexRecursive(getRoot(), ConvexArea2S.full(), result);
 
         return result;
     }
 
     /** Recursive method to compute the convex areas of all inside leaf nodes in the subtree rooted at the given
      * node. The computed convex areas are added to the given list.
      * @param node root of the subtree to compute the convex areas for
      * @param nodeArea the convex area for the current node; this will be split by the node's cut hyperplane to
      *      form the convex areas for any child nodes
      * @param result list containing the results of the computation
      */
     private void toConvexRecursive(final RegionNode2S node, final ConvexArea2S nodeArea,
             final List<? super ConvexArea2S> result) {
         if (node.isLeaf()) {
             // base case; only add to the result list if the node is inside
             if (node.isInside()) {
                 result.add(nodeArea);
             }
         } else {
             // recurse
             final Split<ConvexArea2S> split = nodeArea.split(node.getCutHyperplane());
 
             toConvexRecursive(node.getMinus(), split.getMinus(), result);
             toConvexRecursive(node.getPlus(), split.getPlus(), result);
         }
     }
 
     /** {@inheritDoc} */
     @Override
     public Split<RegionBSPTree2S> split(final Hyperplane<Point2S> splitter) {
         return split(splitter, empty(), empty());
     }
 
     /** {@inheritDoc} */
     @Override
     public Point2S project(final Point2S pt) {
         // use our custom projector so that we can disambiguate points that are
         // actually equidistant from the target point
         final BoundaryProjector2S projector = new BoundaryProjector2S(pt);
         accept(projector);
 
         return projector.getProjected();
     }
 
     /** Return the current instance.
      */
     @Override
     public RegionBSPTree2S toTree() {
         return this;
     }
 
     /** {@inheritDoc} */
     @Override
     protected RegionSizeProperties<Point2S> computeRegionSizeProperties() {
         // handle simple cases
         if (isFull()) {
             return new RegionSizeProperties<>(FULL_SIZE, null);
         } else if (isEmpty()) {
             return new RegionSizeProperties<>(0, null);
         }
 
         final List<ConvexArea2S> areas = toConvex();
         final Precision.DoubleEquivalence precision = ((GreatArc) getRoot().getCut()).getPrecision();
 
         final Sum sizeSum = Sum.create();
         final Vector3D.Sum centroidVectorSum = Vector3D.Sum.create();
 
         double maxCentroidVectorWeightSq = 0.0;
 
         for (final ConvexArea2S area : areas) {
             sizeSum.add(area.getSize());
 
             final Vector3D areaCentroidVector = area.getWeightedCentroidVector();
             maxCentroidVectorWeightSq = Math.max(maxCentroidVectorWeightSq, areaCentroidVector.normSq());
 
             centroidVectorSum.add(areaCentroidVector);
         }
 
         final double size = sizeSum.getAsDouble();
         final Vector3D centroidVector = centroidVectorSum.get();
 
         // Convert the weighted centroid vector to a point on the sphere surface. If the centroid vector
         // length is less than the max length of the combined convex areas and the vector itself is
         // equivalent to zero, then we know that there are opposing and approximately equal areas in the
         // region, resulting in an indeterminate centroid. This would occur, for example, if there were
         // equal areas around each pole.
         final Point2S centroid;
         if (centroidVector.normSq() < maxCentroidVectorWeightSq &&
                 centroidVector.eq(Vector3D.ZERO, precision)) {
             centroid = null;
         } else {
             centroid = Point2S.from(centroidVector);
         }
 
         return new RegionSizeProperties<>(size, centroid);
     }
 
     /** {@inheritDoc} */
     @Override
     protected RegionNode2S createNode() {
         return new RegionNode2S(this);
     }
 
     /** {@inheritDoc} */
     @Override
     protected void invalidate() {
         super.invalidate();
 
         boundaryPaths = null;
     }
 
     /** Compute the great arc paths comprising the region boundary.
      * @return the great arc paths comprising the region boundary
      */
     private List<GreatArcPath> computeBoundaryPaths() {
         final InteriorAngleGreatArcConnector connector = new InteriorAngleGreatArcConnector.Minimize();
         return connector.connectAll(boundaries());
     }
 
     /** Return a new, empty BSP tree.
      * @return a new, empty BSP tree.
      */
     public static RegionBSPTree2S empty() {
         return new RegionBSPTree2S(false);
     }
 
     /** Return a new, full BSP tree. The returned tree represents the
      * full space.
      * @return a new, full BSP tree.
      */
     public static RegionBSPTree2S full() {
         return new RegionBSPTree2S(true);
     }
 
     /** Construct a new tree from the given boundaries. If no boundaries
      * are present, the returned tree is empty.
      * @param boundaries boundaries to construct the tree from
      * @return a new tree instance constructed from the given boundaries
      * @see #from(Iterable, boolean)
      */
     public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries) {
         return from(boundaries, false);
     }
 
     /** Construct a new tree from the given boundaries. If {@code full} is true, then
      * the initial tree before boundary insertion contains the entire space. Otherwise,
      * it is empty.
      * @param boundaries boundaries to construct the tree from
      * @param full if true, the initial tree will contain the entire space
      * @return a new tree instance constructed from the given boundaries
      */
     public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries, final boolean full) {
         final RegionBSPTree2S tree = new RegionBSPTree2S(full);
         tree.insert(boundaries);
 
         return tree;
     }
 
     /** BSP tree node for two dimensional spherical space.
      */
     public static final class RegionNode2S extends AbstractRegionBSPTree.AbstractRegionNode<Point2S, RegionNode2S> {
         /** Simple constructor.
          * @param tree tree owning the instance.
          */
         private RegionNode2S(final AbstractBSPTree<Point2S, RegionNode2S> tree) {
             super(tree);
         }
 
         /** Get the region represented by this node. The returned region contains
          * the entire area contained in this node, regardless of the attributes of
          * any child nodes.
          * @return the region represented by this node
          */
         public ConvexArea2S getNodeRegion() {
             ConvexArea2S area = ConvexArea2S.full();
 
             RegionNode2S child = this;
             RegionNode2S parent;
 
             while ((parent = child.getParent()) != null) {
                 final Split<ConvexArea2S> split = area.split(parent.getCutHyperplane());
 
                 area = child.isMinus() ? split.getMinus() : split.getPlus();
 
                 child = parent;
             }
 
             return area;
         }
 
         /** {@inheritDoc} */
         @Override
         protected RegionNode2S getSelf() {
             return this;
         }
     }
 
     /** Class used to project points onto the region boundary.
      */
     private static final class BoundaryProjector2S extends BoundaryProjector<Point2S, RegionNode2S> {
         /** Simple constructor.
          * @param point the point to project onto the region's boundary
          */
         BoundaryProjector2S(final Point2S point) {
             super(point);
         }
 
         /** {@inheritDoc} */
         @Override
         protected Point2S disambiguateClosestPoint(final Point2S target, final Point2S a, final Point2S b) {
             // return the point with the smallest coordinate values
             final int cmp = Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(a, b);
             return cmp < 0 ? a : b;
         }
     }
 }