JavaAlgorithms/divideconquer/SkylineAlgorithm.java

package divideconquer;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author dimgrichr
 *     <p>Space complexity: O(n) Time complexity: O(nlogn), because it is a divide and conquer
 *     algorithm
 */
public class SkylineAlgorithm {
  private ArrayList<Point> points;

  /**
   * Main constructor of the application. ArrayList points gets created, which represents the sum of
   * all edges.
   */
  public SkylineAlgorithm() {
    points = new ArrayList<>();
  }

  /** @return points, the ArrayList that includes all points. */
  public ArrayList<Point> getPoints() {
    return points;
  }

  /**
   * The main divide and conquer, and also recursive algorithm. It gets an ArrayList full of points
   * as an argument. If the size of that ArrayList is 1 or 2, the ArrayList is returned as it is, or
   * with one less point (if the initial size is 2 and one of it's points, is dominated by the other
   * one). On the other hand, if the ArrayList's size is bigger than 2, the function is called
   * again, twice, with arguments the corresponding half of the initial ArrayList each time. Once
   * the flashback has ended, the function produceFinalSkyLine gets called, in order to produce the
   * final skyline, and return it.
   *
   * @param list, the initial list of points
   * @return leftSkyLine, the combination of first half's and second half's skyline
   * @see Point
   */
  public ArrayList<Point> produceSubSkyLines(ArrayList<Point> list) {

    // part where function exits flashback
    int size = list.size();
    if (size == 1) {
      return list;
    } else if (size == 2) {
      if (list.get(0).dominates(list.get(1))) {
        list.remove(1);
      } else {
        if (list.get(1).dominates(list.get(0))) {
          list.remove(0);
        }
      }
      return list;
    }

    // recursive part of the function
    ArrayList<Point> leftHalf = new ArrayList<>();
    ArrayList<Point> rightHalf = new ArrayList<>();
    for (int i = 0; i < list.size(); i++) {
      if (i < list.size() / 2) {
        leftHalf.add(list.get(i));
      } else {
        rightHalf.add(list.get(i));
      }
    }
    ArrayList<Point> leftSubSkyLine = produceSubSkyLines(leftHalf);
    ArrayList<Point> rightSubSkyLine = produceSubSkyLines(rightHalf);

    // skyline is produced
    return produceFinalSkyLine(leftSubSkyLine, rightSubSkyLine);
  }

  /**
   * The first half's skyline gets cleared from some points that are not part of the final skyline
   * (Points with same x-value and different y=values. The point with the smallest y-value is kept).
   * Then, the minimum y-value of the points of first half's skyline is found. That helps us to
   * clear the second half's skyline, because, the points of second half's skyline that have greater
   * y-value of the minimum y-value that we found before, are dominated, so they are not part of the
   * final skyline. Finally, the "cleaned" first half's and second half's skylines, are combined,
   * producing the final skyline, which is returned.
   *
   * @param left the skyline of the left part of points
   * @param right the skyline of the right part of points
   * @return left the final skyline
   */
  public ArrayList<Point> produceFinalSkyLine(ArrayList<Point> left, ArrayList<Point> right) {

    // dominated points of ArrayList left are removed
    for (int i = 0; i < left.size() - 1; i++) {
      if (left.get(i).x == left.get(i + 1).x && left.get(i).y > left.get(i + 1).y) {
        left.remove(i);
        i--;
      }
    }

    // minimum y-value is found
    int min = left.get(0).y;
    for (int i = 1; i < left.size(); i++) {
      if (min > left.get(i).y) {
        min = left.get(i).y;
        if (min == 1) {
          i = left.size();
        }
      }
    }

    // dominated points of ArrayList right are removed
    for (int i = 0; i < right.size(); i++) {
      if (right.get(i).y >= min) {
        right.remove(i);
        i--;
      }
    }

    // final skyline found and returned
    left.addAll(right);
    return left;
  }

  public static class Point {
    private int x;
    private int y;

    /**
     * The main constructor of Point Class, used to represent the 2 Dimension points.
     *
     * @param x the point's x-value.
     * @param y the point's y-value.
     */
    public Point(int x, int y) {
      this.x = x;
      this.y = y;
    }

    /** @return x, the x-value */
    public int getX() {
      return x;
    }

    /** @return y, the y-value */
    public int getY() {
      return y;
    }

    /**
     * Based on the skyline theory, it checks if the point that calls the function dominates the
     * argument point.
     *
     * @param p1 the point that is compared
     * @return true if the point wich calls the function dominates p1 false otherwise.
     */
    public boolean dominates(Point p1) {
      // checks if p1 is dominated
      return (this.x < p1.x && this.y <= p1.y) || (this.x <= p1.x && this.y < p1.y);
    }
  }

  /**
   * It is used to compare the 2 Dimension points, based on their x-values, in order get sorted
   * later.
   */
  class XComparator implements Comparator<Point> {
    @Override
    public int compare(Point a, Point b) {
      return Integer.compare(a.x, b.x);
    }
  }
}