Notes
Requirements
The requirements. A building has N cars and F floors. Each floor has a hall panel with up and down buttons; each car has a panel of destination floors. The system picks a good car for every hall call, cars stop at requested floors on the way, doors open on arrival, and displays show where each car is. Buttons are pressed from many places at once. Weight limits and fire mode are out of scope for the first pass.
Ask what good means. Are we minimising waiting time or energy? Waiting time. Can a call be reassigned to another car later? Not in version one. Should the code run in real time or as a simulation? A simulation with ticks, where a car moves one floor per tick, keeps it testable and deterministic. And how big is the building? A handful of cars and under a hundred floors, so simple loops over cars are fine.
- N cars, F floors
- hall panel: up or down button
- on each floor
- car panel: a destination floor
- pick a good car for each call
- stop at floors on the way
- doors open on arrival
- displays show car position
- buttons pressed concurrently
- out of scope: weight sensors
- optimise wait time or energy?
- average wait time
- can a car skip a hall call?
- only if another car takes it
- reassign calls later?
- not in version one
- a simulation or real time?
- ticks: one floor per tick
- how many cars and floors?
- 2 to 8 cars, under 100 floors
Entities
The entities. A request is either a hall call, a floor plus a direction, or a car call, a car plus a destination floor. They are different shapes, so model them as a sealed interface with two records, and the compiler knows those are the only kinds. The system owns the cars. Each car knows its floor, its direction, whether its doors are open, and the set of floors it must still visit.
Class diagram
In code: a direction enum with up, down and idle. A sealed request interface permitting exactly two records, hall call and car call. And a car class with its floor, direction, door state, and two sorted sets of stops: floors above it to visit on the way up, and floors below it for the way down. Sorted sets give the next stop in either direction in logarithmic time.
enum Direction { UP, DOWN, IDLE }
sealed interface Request
permits HallCall, CarCall {}
record HallCall(int floor, Direction d)
record CarCall(int carId, int floor)
class Car {
int floor; Direction direction;
DoorState doors;
TreeSet<Integer> upStops, downStops;
} Two decisions
Here is the key design move. There are two independent decisions. First, which car should answer a hall call: that is dispatching, it looks at all cars, and it is a policy the building owner may want to tune. Second, in what order a single car visits its stops: that is scheduling, and it only looks at one car. Keeping them in separate classes means you can change one without breaking the other.
Scheduling: LOOK
For scheduling, first come first served is a disaster: a car at floor five serving nine, two, eight, three in arrival order zigzags twenty-two floors. The LOOK algorithm, borrowed from disk scheduling, keeps moving in its current direction while there are stops ahead, then reverses. The same requests take eleven floors. It is fair, too: nobody waits more than one full sweep.
With two sorted sets, LOOK is a few lines. Adding a stop puts it in the up set if it is above the car and in the down set if below. Each tick the car checks: going up with nothing left above? Turn down if there is anything below, otherwise go idle. The same for going down. An idle car heads toward whichever stop is closer. That is the entire per-car scheduler.
- car at 5, requests: 9, 2, 8, 3
- FCFS: 5-9-2-8-3 = 4+7+6+5
- = 22 floors of travel
- LOOK: up 8, 9 then down 3, 2
- = 4 + 7 = 11 floors
- LOOK = sweep one way while
- stops remain ahead, then
- reverse; never runs to the
- top floor for nothing
up = !upStops.isEmpty() down = !downStops.isEmpty() if (dir == UP && !up) dir = down ? DOWN : IDLE else if (dir == DOWN && !down) dir = up ? UP : IDLE else if (dir == IDLE && (up || down)) dir = toward the closer stop addStop(f): f above -> upStops, below -> downStops
Strategy: dispatch
Dispatching is a Strategy with one method: choose a car for this hall call. Our default gives each car a cost. An idle car costs its distance. A car already moving toward the caller in the same direction also costs its distance, because it will pass by anyway. Any other car must finish its sweep first, so it gets a big penalty. The cheapest car wins. Zoning or energy-saving rules are just other strategies.
d = |car.floor - call.floor| idle car: cost = d moving toward the caller in the same direction: cost = d otherwise: d + 2 * topFloor (it must finish its sweep) ties: lowest car id swap in: zoning, energy saving, destination dispatch
Flow: a hall call
Follow one hall call. Someone on floor five presses up. The button handler validates the floor and drops a hall call into the request queue, then returns immediately. On the next tick, the control loop drains the queue, asks the dispatch strategy which car should go, and adds floor five to that car's stops. From then on it is just that car's LOOK scheduler. A car call skips dispatch and goes straight to its own car.
The control loop
The control loop runs one tick at a time. It drains every pending request and assigns them. Then it moves each car: if the doors are open, close them this tick. Otherwise choose a direction, and if there is a stop at the current floor open the doors, or else move one floor and open the doors if that floor was a stop. A tick model makes the simulation deterministic, so tests can step it and assert exact positions.
for (r; (r = inbox.poll()) != null;) hall call -> dispatch.choose(..) car call -> that car for (Car c : cars) move(c): doors open? close them, return chooseDirection(); idle? return stop here? open doors else floor += 1 or -1 arrived at a stop? open doors
Concurrency
Concurrency is where this design shines. Buttons are pressed from many threads, but those threads never touch a car. They only validate and put a request in a lock-free concurrent queue. Exactly one thread, the control loop, reads that queue and owns all car state. Because only one thread ever writes to the cars, the car class needs no locks at all, and there is no lock ordering to get wrong and no deadlock to debug.
- button threads: press() only
- validates and enqueues
- ConcurrentLinkedQueue:
- lock-free, many producers
- control loop: the only thread
- that reads or writes cars
- so Car needs no locks at all
- no lock ordering, no deadlocks
Observer: displays
Floor displays, the arrival chime and an audit log all want to know when a car arrives. That is the Observer pattern again: they register an elevator listener, and the system calls them when doors open. The listener list is copy-on-write, so new displays can subscribe while the loop is running. The scheduling code never needs to know how many screens are in the lobby.
Safety
Put the safety rules in the structure, not in comments. A car never moves while its doors are open, because move closes the doors and returns before anything else. Cars move exactly one floor per tick, so they never stop between floors. An invalid floor is rejected before it ever reaches the queue. An emergency stop would be a new mode that clears every stop and opens doors at the nearest floor.
- never move with doors open:
- move() closes doors first
- never stop between floors:
- one floor per tick
- invalid floor: rejected in
- press(), before queueing
- emergency stop: a new mode
- that clears all stops
Extensibility
Extending it. A full car should skip new hall calls, so dispatch checks capacity. Tall buildings use express zones, which is a zoning dispatch strategy. Destination dispatch, where riders choose their floor in the lobby, groups riders going to the same floors into one car. Re-running dispatch every tick allows reassigning calls. Fire service and maintenance become per-car modes, a natural place for the State pattern.
- capacity: skip hall calls when
- the car is full
- express zones: a zoning
- DispatchStrategy
- destination dispatch: riders
- pick a floor in the lobby
- reassign calls each tick
- fire mode / maintenance:
- per-car State objects
Testing
The full code is below. The demo presses hall calls on floors five and two, lets a few ticks pass, adds car calls to nine and seven, and presses the lobby button from a separate thread. Car one picks up at two and five on the way up and delivers to nine; car two serves the lobby and goes to seven. Everything is idle after thirteen ticks, and the program asserts nothing was left unserved.
HallCall(5, UP), HallCall(2, UP) Car1 opens at 2 Car2 opens at 0 (lobby call) Car1 opens at 5 Car1 opens at 9 (rider chose 9) Car2 opens at 7 All idle after 13 ticks: [Car1@9 IDLE, Car2@7 IDLE]
Follow-ups
Expect follow-ups. Why LOOK and not SCAN? SCAN runs to the last floor even when nobody is there; LOOK turns at the last stop. Can a rider starve? No, every stop is served within one sweep. A car breaks down? Mark it out of service and move its hall calls to other cars. Morning rush? Park idle cars at the lobby. Real time? A scheduled executor calls step every second.
- why LOOK and not SCAN?
- no trip to the end floor
- starvation? at most one sweep
- a car breaks down?
- move its stops to others
- peak hours? park idle cars
- at the lobby in the morning
- real time instead of ticks?
- a scheduler fires step()
Say it like this
The short version. Buttons enqueue sealed request records into a concurrent queue. One control loop owns all car state, so cars need no locks. A dispatch strategy picks the cheapest car for each hall call, and each car runs the LOOK algorithm over two sorted stop sets. A tick model keeps it deterministic and testable, and displays are observers.
- "Buttons enqueue sealed
- requests; one control loop owns
- all car state, so cars need no
- locks. A dispatch strategy
- picks the cheapest car; each
- car runs LOOK with two sorted
- stop sets. Ticks keep it
- testable; displays observe."