Repository navigation
Expand file tree
/
Copy pathSkylineAlgorithm.java
More file actions
169 lines (150 loc) · 5.3 KB
/
Copy pathSkylineAlgorithm.java
File metadata and controls
169 lines (150 loc) · 5.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
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);
}
}
}