/*
 * 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.lucene.geo;

import java.util.Arrays;
import java.util.Comparator;

import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.util.ArrayUtil;

import static org.apache.lucene.geo.GeoUtils.lineCrossesLine;
import static org.apache.lucene.geo.GeoUtils.lineCrossesLineWithBoundary;
import static org.apache.lucene.geo.GeoUtils.orient;

2D line/polygon geometry implementation represented as a balanced interval tree of edges.
 Construction takes O(n log n) time for sorting and tree construction. relate() are O(n), but for most practical lines and polygons are much faster than brute force. 
@lucene.internal
/**
 * 2D line/polygon geometry implementation represented as a balanced interval tree of edges.
 * <p>
 * Construction takes {@code O(n log n)} time for sorting and tree construction.
 * {@link #relate relate()} are {@code O(n)}, but for most
 * practical lines and polygons are much faster than brute force.
 * @lucene.internal
 */
public abstract class EdgeTree {
  
minimum latitude of this geometry's bounding box area /** minimum latitude of this geometry's bounding box area */
  public final double minLat;
  
maximum latitude of this geometry's bounding box area /** maximum latitude of this geometry's bounding box area */
  public final double maxLat;
  
minimum longitude of this geometry's bounding box area /** minimum longitude of this geometry's bounding box area */
  public final double minLon;
  
maximum longitude of this geometry's bounding box area /** maximum longitude of this geometry's bounding box area */
  public final double maxLon;

  // each component is a node in an augmented 2d kd-tree: we alternate splitting between latitude/longitude,
  // and pull up max values for both dimensions to each parent node (regardless of split).

  
maximum latitude of this component or any of its children /** maximum latitude of this component or any of its children */
  protected double maxY;
  
maximum longitude of this component or any of its children /** maximum longitude of this component or any of its children */
  protected double maxX;
  
which dimension was this node split on /** which dimension was this node split on */
  // TODO: its implicit based on level, but boolean keeps code simple
  protected boolean splitX;

  // child components, or null
  protected EdgeTree left;
  protected EdgeTree right;

  
root node of edge tree /** root node of edge tree */
  protected final Edge tree;

  protected EdgeTree(final double minLat, final double maxLat, final double minLon, final double maxLon, double[] lats, double[] lons) {
    this.minLat = minLat;
    this.maxLat = maxLat;
    this.minLon = minLon;
    this.maxLon = maxLon;
    this.maxY = maxLat;
    this.maxX = maxLon;

    // create interval tree of edges
    this.tree = createTree(lats, lons);
  }

  
Returns relation to the provided triangle /** Returns relation to the provided triangle */
  public Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
    // compute bounding box of triangle
    double triMinLat = StrictMath.min(StrictMath.min(ay, by), cy);
    double triMinLon = StrictMath.min(StrictMath.min(ax, bx), cx);
    if (triMinLat <= maxY && triMinLon <= maxX) {
      Relation relation = internalComponentRelateTriangle(ax, ay, bx, by, cx, cy);
      if (relation != Relation.CELL_OUTSIDE_QUERY) {
        return relation;
      }
      if (left != null) {
        relation = left.relateTriangle(ax, ay, bx, by, cx, cy);
        if (relation != Relation.CELL_OUTSIDE_QUERY) {
          return relation;
        }
      }
      double triMaxLat = StrictMath.max(StrictMath.max(ay, by), cy);
      double triMaxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
      if (right != null && ((splitX == false && triMaxLat >= this.minLat) || (splitX && triMaxLon >= this.minLon))) {
        relation = right.relateTriangle(ax, ay, bx, by, cx, cy);
        if (relation != Relation.CELL_OUTSIDE_QUERY) {
          return relation;
        }
      }
    }
    return Relation.CELL_OUTSIDE_QUERY;
  }

  
Returns relation to the provided rectangle /** Returns relation to the provided rectangle */
  public Relation relate(double minLat, double maxLat, double minLon, double maxLon) {
    if (minLat <= maxY && minLon <= maxX) {
      Relation relation = internalComponentRelate(minLat, maxLat, minLon, maxLon);
      if (relation != Relation.CELL_OUTSIDE_QUERY) {
        return relation;
      }
      if (left != null) {
        relation = left.relate(minLat, maxLat, minLon, maxLon);
        if (relation != Relation.CELL_OUTSIDE_QUERY) {
          return relation;
        }
      }
      if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
        relation = right.relate(minLat, maxLat, minLon, maxLon);
        if (relation != Relation.CELL_OUTSIDE_QUERY) {
          return relation;
        }
      }
    }
    return Relation.CELL_OUTSIDE_QUERY;
  }

  
Returns relation to the provided rectangle for this component /** Returns relation to the provided rectangle for this component */
  protected abstract Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon);

  
Returns relation to the provided triangle for this component /** Returns relation to the provided triangle for this component */
  protected abstract Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy);


  private Relation internalComponentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
    // compute bounding box of triangle
    double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
    double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
    double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
    double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
    if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
      return Relation.CELL_OUTSIDE_QUERY;
    } else if (bx == cx && by == cy) {
      return componentRelateTriangle(bx, by, ax, ay, cx, cy);
    } else if (ax == bx && ay == by) {
      return componentRelateTriangle(bx, by, cx, cy, ax, ay);
    }
    return componentRelateTriangle(ax, ay, bx, by, cx, cy);
  }


  
Returns relation to the provided rectangle for this component /** Returns relation to the provided rectangle for this component */
  protected Relation internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon) {
    // if the bounding boxes are disjoint then the shape does not cross
    if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
      return Relation.CELL_OUTSIDE_QUERY;
    }
    // if the rectangle fully encloses us, we cross.
    if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
      return Relation.CELL_CROSSES_QUERY;
    }
    return componentRelate(minLat, maxLat, minLon, maxLon);
  }

  
Creates tree from sorted components (with range low and high inclusive) /** Creates tree from sorted components (with range low and high inclusive) */
  protected static EdgeTree createTree(EdgeTree components[], int low, int high, boolean splitX) {
    if (low > high) {
      return null;
    }
    final int mid = (low + high) >>> 1;
    if (low < high) {
      Comparator<EdgeTree> comparator;
      if (splitX) {
        comparator = (left, right) -> {
          int ret = Double.compare(left.minLon, right.minLon);
          if (ret == 0) {
            ret = Double.compare(left.maxX, right.maxX);
          }
          return ret;
        };
      } else {
        comparator = (left, right) -> {
          int ret = Double.compare(left.minLat, right.minLat);
          if (ret == 0) {
            ret = Double.compare(left.maxY, right.maxY);
          }
          return ret;
        };
      }
      ArrayUtil.select(components, low, high + 1, mid, comparator);
    }
    // add midpoint
    EdgeTree newNode = components[mid];
    newNode.splitX = splitX;
    // add children
    newNode.left = createTree(components, low, mid - 1, !splitX);
    newNode.right = createTree(components, mid + 1, high, !splitX);
    // pull up max values to this node
    if (newNode.left != null) {
      newNode.maxX = Math.max(newNode.maxX, newNode.left.maxX);
      newNode.maxY = Math.max(newNode.maxY, newNode.left.maxY);
    }
    if (newNode.right != null) {
      newNode.maxX = Math.max(newNode.maxX, newNode.right.maxX);
      newNode.maxY = Math.max(newNode.maxY, newNode.right.maxY);
    }
    return newNode;
  }

  
Internal tree node: represents geometry edge from lat1,lon1 to lat2,lon2. The sort value is low, which is the minimum latitude of the edge. max stores the maximum latitude of this edge or any children. /**
   * Internal tree node: represents geometry edge from lat1,lon1 to lat2,lon2.
   * The sort value is {@code low}, which is the minimum latitude of the edge.
   * {@code max} stores the maximum latitude of this edge or any children.
   */
  static class Edge {
    // lat-lon pair (in original order) of the two vertices
    final double lat1, lat2;
    final double lon1, lon2;
    //edge belongs to the dateline
    final boolean dateline;
    
min of this edge /** min of this edge */
    final double low;
    
max latitude of this edge or any children /** max latitude of this edge or any children */
    double max;

    
left child edge, or null /** left child edge, or null */
    Edge left;
    
right child edge, or null /** right child edge, or null */
    Edge right;

    Edge(double lat1, double lon1, double lat2, double lon2, double low, double max) {
      this.lat1 = lat1;
      this.lon1 = lon1;
      this.lat2 = lat2;
      this.lon2 = lon2;
      this.low = low;
      this.max = max;
      dateline = (lon1 == GeoUtils.MIN_LON_INCL && lon2 == GeoUtils.MIN_LON_INCL)
          || (lon1 == GeoUtils.MAX_LON_INCL && lon2 == GeoUtils.MAX_LON_INCL);
    }

    
Returns true if the triangle crosses any edge in this edge subtree /** Returns true if the triangle crosses any edge in this edge subtree */
    boolean crossesTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
      // compute min lat of triangle bounding box
      double triMinLat = StrictMath.min(StrictMath.min(ay, by), cy);
      if (triMinLat <= max) {
        double dy = lat1;
        double ey = lat2;
        double dx = lon1;
        double ex = lon2;

        // compute remaining bounding box of triangle
        double triMinLon = StrictMath.min(StrictMath.min(ax, bx), cx);
        double triMaxLat = StrictMath.max(StrictMath.max(ay, by), cy);
        double triMaxLon = StrictMath.max(StrictMath.max(ax, bx), cx);

        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
        // if not, don't waste our time trying more complicated stuff
        boolean outside = (dy < triMinLat && ey < triMinLat) ||
            (dy > triMaxLat && ey > triMaxLat) ||
            (dx < triMinLon && ex < triMinLon) ||
            (dx > triMaxLon && ex > triMaxLon);

        if (outside == false) {
          if (lineCrossesLine(dx, dy, ex, ey, ax, ay, bx, by) ||
              lineCrossesLine(dx, dy, ex, ey, bx, by, cx, cy) ||
              lineCrossesLine(dx, dy, ex, ey, cx, cy, ax, ay)) {
            return true;
          }
        }

        if (left != null && left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
          return true;
        }

        if (right != null && triMaxLat >= low && right.crossesTriangle(ax, ay, bx, by, cx, cy)) {
          return true;
        }
      }
      return false;
    }

    
Returns true if the box crosses any edge in this edge subtree /** Returns true if the box crosses any edge in this edge subtree */
    boolean crossesBox(double minLat, double maxLat, double minLon, double maxLon, boolean includeBoundary) {
      // we just have to cross one edge to answer the question, so we descend the tree and return when we do.
      if (minLat <= max) {
        // we compute line intersections of every polygon edge with every box line.
        // if we find one, return true.
        // for each box line (AB):
        //   for each poly line (CD):
        //     intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C) * orient(A,B,D) <= 0
        double cy = lat1;
        double dy = lat2;
        double cx = lon1;
        double dx = lon2;

        // optimization: see if either end of the line segment is contained by the rectangle
        if (Rectangle.containsPoint(cy, cx, minLat, maxLat, minLon, maxLon) ||
            Rectangle.containsPoint(dy, dx, minLat, maxLat, minLon, maxLon)) {
          return true;
        }

        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
        // if not, don't waste our time trying more complicated stuff
        boolean outside = (cy < minLat && dy < minLat) ||
            (cy > maxLat && dy > maxLat) ||
            (cx < minLon && dx < minLon) ||
            (cx > maxLon && dx > maxLon);

        if (outside == false) {
          if (includeBoundary == true &&
              lineCrossesLineWithBoundary(cx, cy, dx, dy, minLon, minLat, maxLon, minLat) ||
              lineCrossesLineWithBoundary(cx, cy, dx, dy, maxLon, minLat, maxLon, maxLat) ||
              lineCrossesLineWithBoundary(cx, cy, dx, dy, maxLon, maxLat, maxLon, minLat) ||
              lineCrossesLineWithBoundary(cx, cy, dx, dy, minLon, maxLat, minLon, minLat)) {
            // include boundaries: ensures box edges that terminate on the polygon are included
            return true;
          } else if (lineCrossesLine(cx, cy, dx, dy, minLon, minLat, maxLon, minLat) ||
              lineCrossesLine(cx, cy, dx, dy, maxLon, minLat, maxLon, maxLat) ||
              lineCrossesLine(cx, cy, dx, dy, maxLon, maxLat, maxLon, minLat) ||
              lineCrossesLine(cx, cy, dx, dy, minLon, maxLat, minLon, minLat)) {
            return true;
          }
        }

        if (left != null && left.crossesBox(minLat, maxLat, minLon, maxLon, includeBoundary)) {
          return true;
        }

        if (right != null && maxLat >= low && right.crossesBox(minLat, maxLat, minLon, maxLon, includeBoundary)) {
          return true;
        }
      }
      return false;
    }

    
Returns true if the line crosses any edge in this edge subtree /** Returns true if the line crosses any edge in this edge subtree */
    boolean crossesLine(double a2x, double a2y, double b2x, double b2y) {
      double minY = StrictMath.min(a2y, b2y);
      double maxY = StrictMath.max(a2y, b2y);
      if (minY <= max) {
        double a1x = lon1;
        double a1y = lat1;
        double b1x = lon2;
        double b1y = lat2;

        double minX = StrictMath.min(a2x, b2x);
        double maxX = StrictMath.max(a2x, b2x);

        boolean outside = (a1y < minY && b1y < minY) ||
            (a1y > maxY && b1y > maxY) ||
            (a1x < minX && b1x < minX) ||
            (a1x > maxX && b1x > maxX);
        if (outside == false && lineCrossesLineWithBoundary(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y)) {
          return true;
        }

        if (left != null && left.crossesLine(a2x, a2y, b2x, b2y)) {
          return true;
        }
        if (right != null && maxY >= low && right.crossesLine(a2x, a2y, b2x, b2y)) {
          return true;
        }
      }
      return false;
    }
  }

  //This should be moved when LatLonShape is moved from sandbox!
  
Compute whether the given x, y point is in a triangle; uses the winding order method /**
   * Compute whether the given x, y point is in a triangle; uses the winding order method */
  protected static boolean pointInTriangle (double x, double y, double ax, double ay, double bx, double by, double cx, double cy) {
    double minX = StrictMath.min(ax, StrictMath.min(bx, cx));
    double minY = StrictMath.min(ay, StrictMath.min(by, cy));
    double maxX = StrictMath.max(ax, StrictMath.max(bx, cx));
    double maxY = StrictMath.max(ay, StrictMath.max(by, cy));
    //check the bounding box because if the triangle is degenerated, e.g points and lines, we need to filter out
    //coplanar points that are not part of the triangle.
    if (x >= minX && x <= maxX && y >= minY && y <= maxY ) {
      int a = orient(x, y, ax, ay, bx, by);
      int b = orient(x, y, bx, by, cx, cy);
      if (a == 0 || b == 0 || a < 0 == b < 0) {
        int c = orient(x, y, cx, cy, ax, ay);
        return c == 0 || (c < 0 == (b < 0 || a < 0));
      }
      return false;
    } else {
      return false;
    }
  }

  
Creates an edge interval tree from a set of geometry vertices.
Returns:
root node of the tree./**
   * Creates an edge interval tree from a set of geometry vertices.
   * @return root node of the tree.
   */
  private static Edge createTree(double[] lats, double[] lons) {
    Edge edges[] = new Edge[lats.length - 1];
    for (int i = 1; i < lats.length; i++) {
      double lat1 = lats[i-1];
      double lon1 = lons[i-1];
      double lat2 = lats[i];
      double lon2 = lons[i];
      edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2), Math.max(lat1, lat2));
    }
    // sort the edges then build a balanced tree from them
    Arrays.sort(edges, (left, right) -> {
      int ret = Double.compare(left.low, right.low);
      if (ret == 0) {
        ret = Double.compare(left.max, right.max);
      }
      return ret;
    });
    return createTree(edges, 0, edges.length - 1);
  }

  
Creates tree from sorted edges (with range low and high inclusive) /** Creates tree from sorted edges (with range low and high inclusive) */
  private static Edge createTree(Edge edges[], int low, int high) {
    if (low > high) {
      return null;
    }
    // add midpoint
    int mid = (low + high) >>> 1;
    Edge newNode = edges[mid];
    // add children
    newNode.left = createTree(edges, low, mid - 1);
    newNode.right = createTree(edges, mid + 1, high);
    // pull up max values to this node
    if (newNode.left != null) {
      newNode.max = Math.max(newNode.max, newNode.left.max);
    }
    if (newNode.right != null) {
      newNode.max = Math.max(newNode.max, newNode.right.max);
    }
    return newNode;
  }
}