# Elevator System — decision log

The Phase 5 answer key. Every entry is a question an interviewer actually asks ("why is that a
separate class?", "what exactly does that lock protect?") and the answer that earns the mark: **what
change or failure the decision anticipates, and what it would cost without it.**

Eleven classes. The two biggest, `Lift` and `ElevatorSystem`, are ~209 and ~207 lines and rather more
than half of each is javadoc; the other nine are 20–70 lines. `ElevatorSystem` contains no routing
rule and no dispatch rule; `Lift` contains no routing rule and no knowledge of the building.

| File | One reason to change |
|---|---|
| `ElevatorSystem` | the *sequence* of dispatching, withdrawing and ticking changes |
| `Lift` | the mechanics of one car's tick or its bookkeeping change |
| `DispatchPolicy` / `NearestAlignedPolicy` | which lift should answer a call |
| `StopOrder` / `ScanOrder` | which stop a car heads for next |
| `StopOrders` | whether every shaft routes the same way |
| `FloorAccess` | which floors a shaft physically reaches |
| `LiftView` | what a dispatcher is allowed to know about a lift |
| `Call` | what we record about a request |
| `LiftStatus`, `Direction` | given by the contract, not ours to change |
| `Demo` | what we show when we run it |

---

## Concurrency first, because this problem is about concurrency

### The shared mutable state, named out loud

There are exactly **two** pieces, and telling them apart is the whole design.

1. **Each lift's own state** — `floor`, `direction`, `inService`, `load`, `stops`, `hallCalls`,
   `ridersFor`. These are one consistent thing, never several: a load of 3 with two riders recorded is
   not a valid lift. So they are guarded by one lock, `Lift`'s own monitor, and every public method on
   `Lift` is `synchronized`.

2. **The assignment of calls to lifts.** This is the one people miss, because *it is not stored
   anywhere*. Dispatching means reading every lift, choosing one, and handing it the call — three
   steps that are one decision. Two dispatchers interleaving them both pick the same idle lift; a
   dispatcher racing a withdrawal hands a call to a lift that is on its way out. `dispatchLock` in
   `ElevatorSystem` exists for this and nothing else.

**What is deliberately *not* shared mutable state.** `lifts` is built once, wrapped in `List.copyOf`
and held in a `final` field, so it is immutable and safely published. That is why there is **no
`ConcurrentHashMap` anywhere in the base reference**, and the right answer to "why not?" is not "I
forgot": a concurrent collection buys per-entry atomicity, and nothing here needs per-entry atomicity.
What needs atomicity spans several reads and a write, which no collection can provide.

### Lock granularity: one lock per car, not one per building

A lift bank's entire point is that three cars move at once. One building-wide lock would serialise
three independent cars and buy no correctness, so `carCall`, `step`, `status` and `pendingStops` take
**only** the relevant lift's monitor and never `dispatchLock`. A passenger pressing a button inside a
car does not need the dispatcher's permission, so it does not need the dispatcher's lock.

### Lock ordering, and why it cannot be got wrong here

> **`dispatchLock` is always acquired before any lift's monitor, and never after.**

The dangerous path is real and easy to write: let a withdrawal begin by locking the lift, then ask the
building to re-home its orphaned calls. That is lift-then-dispatch, the reverse order, and it
deadlocks against any concurrent `hallCall` within milliseconds. **This was built and measured**: a
variant of this reference with exactly that inversion is caught by
`tests_concurrency/ElevatorStressTest` on the first repetition, reported as `kind: "deadlock"` rather
than as a wrong answer.

The ordering is not maintained by remembering it. It is enforced structurally, in two places:

- **`Lift` holds no reference to `ElevatorSystem`.** It cannot call back, so it cannot take
  `dispatchLock` from inside its own monitor. `withdraw()` therefore *returns* the orphaned calls
  instead of re-homing them, and the caller — which already holds `dispatchLock` — re-dispatches them.
- **`StopOrder` is handed a floor, a direction and a read-only set, never a lift and never the
  building.** It is consulted while the lift's monitor is held, so anything it could reach would be
  reachable under that monitor. Handing it primitives makes the wrong thing unexpressible.

### Atomicity vs visibility: `carCall` is the check-then-act

"Read the load, decide there is room, add a passenger" is three steps. Unless they are one atomic
step, several threads see the same last place and all take it. The stress suite pushes 64 threads at a
four-person lift and admits five if this is wrong — the unsynchronised variant of this reference fails
it on the first repetition with `expected: <4> but was: <5>`.

### Snapshots, not handles

`status()` and `view()` each build an immutable record while holding the lift's monitor, so a caller
gets a view that was true at one instant rather than a mixture of two. `pendingStops()` returns
`List.copyOf`. Two threads asking at the same time may get different answers, and neither is stale —
a lift really is moving. What is *not* allowed is a single answer that was never true, and that is
what these guarantee.

**Consequence worth stating:** no invariant that spans two API calls is promised, and none is claimed.
"Out of service implies no pending stops" is true *within* one `status()`, and the stress suite is
written to assert only within-one-snapshot properties, because asserting across two calls would be
testing something the design deliberately does not offer.

---

## Seam 1 · `LiftView` — the smallest and most load-bearing decision

It does two jobs at once, which is why it is a record and not a getter on `Lift`.

**It is the interface-segregation boundary.** A `DispatchPolicy` needs to compare lifts; it has no
business moving one. Handing it a `Lift` would hand it `step()`, `withdraw()` and `acceptCarCall()` —
a policy that can drive a lift is a policy that can break one. `LiftView` exposes the five facts a
choice is made from and no verbs at all. It deliberately omits `capacity`, because no dispatch rule in
this problem depends on it.

**It is the deadlock-avoidance mechanism**, as above. The two purposes are the same purpose seen from
two angles: the narrowest thing that answers the question is also the thing that cannot take a lock.

**Cost without it.** A policy holding live `Lift` references re-reads them under lift monitors while
`dispatchLock` is held, and the first policy that wants to know something the view does not carry
reaches for the building. That is the lock cycle, arriving through the seam rather than through the
withdrawal path.

## Seam 2 · `DispatchPolicy` — which lift answers, and it is *pure*

**Anticipates:** every change to dispatch, which is the most volatile rule in any lift bank —
up-peak, down-peak, energy saving, load balancing, express shafts, VIP.

**It picks; it does not place the call.** That is the decision worth defending. The same call answers
"which lift *would* answer a call at floor 7?" without making a call, and it keeps the policy out of
the locking story entirely. `ElevatorSystem.dispatch()` applies the answer, and **checks it**: a
policy that returns a lift it was not offered gets an `IllegalStateException` naming the mistake
rather than a call quietly going missing. A seam is a stranger; validate what it hands back.

**Why a `Comparator` chain and not nested `if`s.** The requirement *is* a priority order — aligned,
then nearest, then least busy, then lowest id — and a comparator chain says so in the shape the
requirement was written in. Each `thenComparing` is exactly one tie-break, so adding or removing one
is a line. The final tie-break on `liftId` is what makes the ordering **total**: no tie survives it,
so the same building always makes the same choice and a test can assert an id. A dispatch rule with a
surviving tie is untestable, and worse, quietly non-deterministic under threads.

## Seam 3 · `StopOrder` / `StopOrders` — which stop a car heads for next

**Anticipates:** every change to routing. Two of the three curveballs land here and cost 2 lines and
10 lines respectively.

Three decisions inside it are each worth a sentence in a defence:

- **It returns `OptionalInt`, and the floor it returns need not be pending.** Empty means "nothing to
  do". That single allowance is what makes "an idle lift returns to the lobby" a decorator rather than
  two new branches inside `step()` — measured at 2 lines — and it means no phantom stop is ever
  inserted into a lift's work list, so `pendingStops` keeps meaning "what this lift owes people".
- **It is a per-lift factory (`StopOrders`), not one shared object.** "This shaft routes differently
  from that one" is a real requirement — express lifts, goods lifts, a car reserved for a VIP. With
  one shared rule, every such requirement becomes an `if (liftId == ...)` inside the rule, and the
  rule slowly turns into the building's wiring diagram.
- **It is documented as pure, quick and forbidden from calling back.** Those are not style notes; they
  are the terms on which it is safe to invoke a stranger while holding a lock.

`ScanOrder` is written entirely in `NavigableSet`'s neighbour queries — `higher` is "the next stop
above me", `lower` is "the next below" — which is why the pending stops are a `TreeSet` and not a
queue. **Arrival order is precisely the thing a lift must ignore**, so the data structure should not
be able to remember it.

## Seam 4 · `FloorAccess` — which floors a shaft reaches

The one seam that is a genuine up-front bet, so here is the honest accounting. It costs a functional
interface and a one-line default. It buys curveball 1 for 2 lines instead of ~10–14 across two files.

The defence is not "I predicted the curveball", it is that **the alternative is a duplicated
assumption**: dispatch and the car panel both need the answer, they live in different methods, and
when they disagree the failure mode is a passenger being told lift 3 and watching lift 3 sail past.
Basements only two lifts reach, service floors and sky lobbies are the norm in a tall building rather
than the exception.

## Modelling · `Call` carries the direction, on purpose

A bare floor number would have been enough for the lift's own routing, and would have been wrong.
When a lift is withdrawn its calls are **re-dispatched**, and re-dispatching needs the direction the
caller originally asked for — otherwise the replacement lift is chosen by a different rule than the
first one was. So the direction has to outlive the `hallCall` that carried it, and that is what makes
`Call` a type rather than an `int`.

`Call` is a **value**: two people pressing UP on floor 7 are asking for the same thing, so a lift
keeps at most one stop per floor. `Lift` is an **entity**: it is identified by its id and nothing ever
looks one up by its contents.

## Modelling · why `load` is not derivable from a set of destinations

`ridersFor` is a `Map<floor, count>`, not a `Set<floor>`, because two passengers can want the same
floor and both have to get out when it is served. The counted map is the difference between a load
that returns to zero and a load that drifts. It is also why `carCall` models *one passenger*: one call
is one person, one seat and one stop, so there is no second call needed to say "and I am aboard" that
somebody could forget to make.

## Invariants sit in constructors

`ElevatorSystem` refuses a building with fewer than two floors or no lifts. `Lift` refuses a
non-positive id or capacity. `Call` refuses floor 0 and refuses `Direction.IDLE`, because "a call
must ask for a direction" is a property of a call rather than a thing to re-check at each use site.
There is no `validate()` method anywhere; an invalid instance never gets far enough to need one.

## Collections never escape

Handing a caller the collection a lift actually works from is the classic failure here — it lets the
dispatcher, or a test, or a `StopOrder`, quietly rewrite a lift's work list. There are three guards:
`pendingStops()`
returns `List.copyOf`, `lifts` is a `List.copyOf` built once, and the set handed to a `StopOrder` is
`Collections.unmodifiableNavigableSet` — deliberately a *view* rather than a copy, so the order gets
`NavigableSet`'s neighbour queries on live data with no allocation on the hot path and no way to
corrupt it. That matters precisely because `StopOrder` is the part a candidate is expected to replace.

## Errors: `Optional` inside, exceptions at the edge, `false` for "no"

Three different signals, chosen rather than mixed:

- **`OptionalInt`** inside, from `StopOrder.next` — "nothing to do" is an ordinary outcome of a
  search, not an exception.
- **`false`** from `carCall` — a full lift is not an error. It is the single most common thing that
  happens in a lift, the caller can obviously act on it, and an exception for it would make the normal
  path exceptional. This is the one place the contract's return type carries a decision rather than a
  value.
- **Exceptions at the edge**, split by kind: `IllegalArgumentException` for a request that could never
  make sense (a floor that does not exist, `Direction.IDLE`, UP from the top floor), and
  `IllegalStateException` for one that makes sense but cannot be honoured *now* (no lift can reach
  that floor, the lift is out of service, the withdrawal is illegal). That split is the useful one,
  because the first tells the caller to fix its code and the second tells it to try again later.

**Why no custom exception types.** The contract fixes the classes the grader asserts, so
`NoLiftAvailableException extends IllegalStateException` would add files and buy nothing the message
does not already say. If the contract had left the choice open, the answer would be different — and
saying *that* out loud is the point, rather than either choice on its own.

## Time is `step()`, and nothing else

Nothing in the reference reads a clock, sleeps, or starts a thread. `step()` is time, so every route
is reproducible, no test needs to wait, and the concurrency suite can hammer the building without
racing a scheduler as well as itself. A real building would drive `step()` from a timer; that timer is
the caller's problem and its absence here is a scope decision, not an oversight.

## What was deliberately *not* built

Named so the scope is explicit rather than forgotten:

- **No `Floor` class.** A floor is an `int` in a fixed range. A `Floor` object with an id and nothing
  else is ceremony.
- **No `Passenger` class.** Nothing in the requirements distinguishes one passenger from another; a
  count per destination is the whole of what is needed. A `Passenger` with only a destination is a
  `Map.Entry` with a name.
- **No door state machine, no weight sensor, no emergency mode.** Stated out of scope.
- **No `Lift` subclasses for express or goods lifts.** The two things that actually differ are which
  floors it reaches and how it routes, and both are injected. `ExpressLift extends Lift` would put
  building policy inside the car and make the two overridable behaviours impossible to combine —
  which is exactly what curveballs 1, 2 and 3 do combine, since each decorates a seam and delegates.
- **No `ScheduledExecutorService`.** See above: `step()` is time.
- **No lock-free anything.** The contract asks for correctness and for the candidate to be able to
  explain the locking, not for throughput. A `compareAndSet` loop on a packed lift state would be
  faster, unreadable, and impossible to defend against "why?".
