TheAlgorithms-Java/divideconquer/SkylineAlgorithm.java at master · windNight/TheAlgorithms-Java · GitHub

History

169 lines (150 loc) · 5.3 KB

Raw

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

}

TheAlgorithms-Java/divideconquer/SkylineAlgorithm.java at master · windNight/TheAlgorithms-Java · GitHub

Expand file tree

Breadcrumbs

SkylineAlgorithm.java

Latest commit

History

Breadcrumbs

SkylineAlgorithm.java

File metadata and controls