/*
 * 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.
 * <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 */
  public final double minLat;
  /** maximum latitude of this geometry's bounding box area */
  public final double maxLat;
  /** minimum longitude of this geometry's bounding box area */
  public final double minLon;
  /** 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 */
  protected double maxY;
  /** maximum longitude of this component or any of its children */
  protected double maxX;
  /** 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 */
  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 */
  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 */
  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 */
  protected abstract Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon);

  /** 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);
    }
    return componentRelateTriangle(ax, ay, bx, by, cx, cy);
  }


  /** 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) */
  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 {@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 */
    final double low;
    /** max latitude of this edge or any children */
    double max;

    /** left child edge, or null */
    Edge left;
    /** 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 */
    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 */
    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 */
    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 */
  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.
   * @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) */
  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;
  }
}
