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);

}

}

}