Problem 4.5 — Elevator

SCAN sweeps in one direction and serves everything on the way — FCFS zig-zags and wastes floors.

SCAN dispatch with a shared, lock-protected request set.

public class Elevator {
  public enum Dir { IDLE, UP, DOWN }

  private int floor = 0;
  private Dir dir = Dir.IDLE;
  private final TreeSet<Integer> stops = new TreeSet<>(); // sorted → SCAN

  public synchronized void push(int target) {
    stops.add(target);
    if (dir == Dir.IDLE) dir = target > floor ? Dir.UP : Dir.DOWN;
  }

  // called by a single controller loop tick
  public synchronized void tick() {
    if (stopAt(floor)) {
      stops.remove(floor);
      System.out.println("~ floor " + floor + " (door open)");
    }
    Integer next = nextStop();
    if (next == null) { dir = Dir.IDLE; return; }
    floor += dir == Dir.UP ? 1 : -1;        // move one floor per tick
    if (!hasRequestsAhead()) dir = dir == Dir.UP ? Dir.DOWN : Dir.UP; // reverse at end
  }

  private boolean hasRequestsAhead() {
    return dir == Dir.UP ? stops.ceiling(floor + 1) != null
                         : stops.floor(floor - 1) != null;
  }
  private Integer nextStop() {
    return dir == Dir.UP ? stops.ceiling(floor) : stops.floor(floor);
  }
  private boolean stopAt(int f) { return stops.contains(f); }
}

// External calls: controller picks the best elevator (e.g. nearest & same/IDLE direction).
public class ElevatorController {
  private final List<Elevator> cars;
  public ElevatorController(int n) {
    cars = new ArrayList<>();
    for (int i = 0; i < n; i++) cars.add(new Elevator());
  }
  public void call(int fromFloor, boolean up) {
    Elevator best = null;
    int bestDist = Integer.MAX_VALUE;
    for (Elevator e : cars) {                 // naive nearest-first
      int d = Math.abs(e.floor() - fromFloor);
      if (d < bestDist) { best = e; bestDist = d; }
    }
    best.push(fromFloor);
  }
}