src/services/Planner.java
BeforeProposed
+35−1
66
77public final class Planner {
88 public record Plan(List<String> versions, List<String> upgrades, int minutes, int downtime) {}
9 private record State(Version current, List<Version> versions, List<String> upgrades, int minutes, int downtime) {}
10 private static final Comparator<State> ORDER = Comparator.comparingInt(State::minutes)
11 .thenComparingInt(State::downtime).thenComparing(state -> String.join("/", state.upgrades));
912 public static Plan plan(Catalogue catalogue, Version from, Version to, String platform, Set<String> required, int budget) {
10 // Implement the documented maintenance-window search here.
13 catalogue.get(from);
14 catalogue.get(to);
15 if (!catalogue.get(from).supports(platform, required) || !catalogue.get(to).supports(platform, required)) return null;
16 PriorityQueue<State> queue = new PriorityQueue<>(ORDER);
17 queue.add(new State(from, List.of(from), List.of(), 0, 0));
18 Map<Version, List<State>> frontier = new HashMap<>();
19 while (!queue.isEmpty()) {
20 State current = queue.remove();
21 List<State> known = frontier.computeIfAbsent(current.current, ignored -> new ArrayList<>());
22 // One cheapest route per version is insufficient: downtime is a separate budget.
23 if (known.stream().anyMatch(previous -> dominates(previous, current))) continue;
24 known.removeIf(previous -> dominates(current, previous));
25 known.add(current);
26 if (current.current.equals(to)) {
27 return new Plan(current.versions.stream().map(Version::toString).toList(), current.upgrades, current.minutes, current.downtime);
28 }
29 for (Upgrade edge : catalogue.next(current.current)) {
30 if (!Eligibility.permits(catalogue.get(edge.to()), platform, required)) continue;
31 if (current.downtime + edge.downtime() > budget) continue;
32 if (current.versions.contains(edge.to())) continue;
33 List<Version> versions = new ArrayList<>(current.versions);
34 versions.add(edge.to());
35 List<String> upgrades = new ArrayList<>(current.upgrades);
36 upgrades.add(edge.id());
37 queue.add(new State(edge.to(), List.copyOf(versions), List.copyOf(upgrades),
38 current.minutes + edge.minutes(), current.downtime + edge.downtime()));
39 }
40 }
1141 return null;
42 }
43 private static boolean dominates(State left, State right) {
44 return left.minutes <= right.minutes && left.downtime <= right.downtime
45 && (left.minutes < right.minutes || left.downtime < right.downtime || ORDER.compare(left, right) <= 0);
1246 }
1347}