-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWorldBuildingUtil.java
More file actions
68 lines (58 loc) · 2.38 KB
/
WorldBuildingUtil.java
File metadata and controls
68 lines (58 loc) · 2.38 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
package BackendManagers;
import BackendManagers.Interfaces.WorldBuildingUtilInterface;
import CommonUtils.MST;
import CommonUtils.UsefulContainers.iPair;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;
/**
* Contains helpful functions for dealing with our world building. Will not be integrated with
* production classes, as it is a tool for helping us with content creation.
*
* <bold>251 students: you may use any of the data structures you have previously created, but may not use
* any Java util library except List/ArrayList and java.util.stream.* .</bold>
*/
public class WorldBuildingUtil implements WorldBuildingUtilInterface {
private static double euclideanDistance(iPair p, iPair q) {
return Math.sqrt(Math.pow(p.a - q.a, 2) + Math.pow(p.b - q.b, 2));
}
/**
* Selects roads per the specifications (minimum cost to connect all cities).
*
* @param filename file to read input from
* @return list of roads, per the specifications
*/
@Override
public List<CityEdge> getMinimumConnectingRoads(String filename) {
try {
BufferedReader bf = new BufferedReader(new FileReader(filename));
int C = Integer.parseInt(bf.readLine());
double[][] weights = new double[C][C];
iPair[] coords = new iPair[C];
// Read in city coordinates
for (int i = 0; i < C; i++) {
String[] in = bf.readLine().split(" ");
int a = Integer.parseInt(in[0]);
int b = Integer.parseInt(in[1]);
iPair coord = new iPair(a, b);
coords[i] = coord;
// Update distances to all previous cities
for (int j = 0; j < i; j++) {
double dist = euclideanDistance(coords[i], coords[j]);
weights[i][j] = dist;
weights[j][i] = dist;
}
}
return MST.denseMST(weights)
.stream()
.map(p -> new CityEdge(coords[p.a], coords[p.b]))
.toList();
} catch (IOException e) {
//This should never happen... uh oh o.o
System.err.println("ATTENTION TAs: Couldn't find test file: \"" + filename + "\":: " + e.getMessage());
System.exit(1);
}
return null;
}
}