Part 4 of 6 · 4 min read
The code
Add stop, step, and cost.
The car:
class Elevator {
final int id; private int floor; private Dir dir = Dir.IDLE; private Door door = Door.CLOSED;
private final TreeSet<Integer> stops = new TreeSet<>();
private final int minFloor, maxFloor;
void addStop(int f) {
if (f < minFloor || f > maxFloor) throw new IllegalArgumentException("no such floor " + f);
if (f == floor && dir == Dir.IDLE) { door = Door.OPEN; return; }
stops.add(f);
if (dir == Dir.IDLE) dir = f > floor ? Dir.UP : Dir.DOWN;
}
void step() {
door = Door.CLOSED;
if (dir == Dir.IDLE) return;
floor += dir == Dir.UP ? 1 : -1;
if (stops.remove(floor)) door = Door.OPEN;
if (stops.isEmpty()) { dir = Dir.IDLE; return; }
if (dir == Dir.UP && stops.higher(floor) == null) dir = Dir.DOWN;
else if (dir == Dir.DOWN && stops.lower(floor) == null) dir = Dir.UP;
}
}
step moves one floor, opens the door if the new floor is a stop, and then decides the direction. The car turns only when no stop is left ahead. That is the sweep rule.
The cost of a hall call is how many floors the car must travel before it can serve the call.
boolean willPass(int f, Dir want) {
if (dir == Dir.IDLE) return true;
if (dir == Dir.UP) return want == Dir.UP && f >= floor && f <= stops.last();
return want == Dir.DOWN && f <= floor && f >= stops.first();
}
int cost(int f, Dir want) {
if (dir == Dir.IDLE) return Math.abs(f - floor);
if (willPass(f, want)) return Math.abs(f - floor);
int far = dir == Dir.UP ? stops.last() : stops.first();
return Math.abs(far - floor) + Math.abs(far - f); // go to the far end, then come back
}
A car that will pass the call on its current sweep pays only the distance. A car that has already passed the call, or is going the other way, pays for the trip to its far stop and back. The dispatcher picks the lowest:
class NearestDispatcher implements Dispatcher {
public Elevator pick(List<Elevator> es, int floor, Dir want) {
Elevator best = null; int bc = Integer.MAX_VALUE;
for (Elevator e : es) { int c = e.cost(floor, want); if (c < bc) { bc = c; best = e; } }
return best;
}
}
Runs:
| Setup | Result |
|---|---|
| One car at floor 0, stops 5, 2 and 8 added in that order, 14 ticks | Floors seen: 1, 2 (door open), 3, 4, 5 (open), 6, 7, 8 (open), then 8 for the rest. The car ends idle at 8 with no stops |
| Two cars, car 0 is told to go to 6 and ticks 3 times | Car 0 is at floor 3 going up with stop 6. Car 1 is idle at 0 |
| Hall call at floor 4 going up | Car 0 takes it. Its stops become 4 and 6. Cost 1 against 4 for car 1 |
| Hall call at floor 1 going up | Car 1 takes it. Car 0 is already past floor 1, so its cost is 3 + 5 = 8 against 1 |
| Press floor 12 in a 10-floor building | Refused: "no such floor 12" |
| Car idle at floor 0, press 0 | The door opens and nothing else happens |
The order in the first row shows the sweep. The presses came as 5, 2, 8, yet the car served 2, 5, 8, because the sorted set orders them by floor and the car sweeps up.
Check yourself: 1. Why does the car in the first run serve 2 before 5? 2. What is the cost for a car that has passed the call? 3. What happens when an idle car is asked for its own floor?