# NOTES — six files, and three field declarations that decide everything else

Compile and run from the directory holding the sources:

```
..\..\..\.toolchain\jdk-21\bin\javac.exe -d out *.java
..\..\..\.toolchain\jdk-21\bin\java.exe -cp out Main
```

`javac -Xlint:all` prints nothing and exits 0. Real output, from exactly this code:

```
== 1 - lift 1 stands on floor 4, travelling UP. Calls arrive: 9, 2, 7 ==
  ArrayDeque, arrival order   serves [9, 2, 7]  in 20 ticks
  TreeMap, direction order    serves [7, 9, 2]  in 15 ticks

== 2 - what a lift actually asks its pending stops ==
  pendingStops()                    [2, 5, 9]
  nextStopAtOrAbove(4)  ceilingKey   5
  nextStopAtOrAbove(5)  ceilingKey   5
  nextStopAtOrAbove(10) ceilingKey   null
  highestStopAtOrBelow(4) floorKey   2
  highestStopAtOrBelow(1) floorKey   null
  owedBelow(5)          headMap      1
  directionCalledFor(5) HashMap.get  DOWN
  directionCalledFor(4) HashMap.get  null
  nextStop(4, UP)                    5
  nextStop(4, DOWN)                  2
  nextStop(4, IDLE)                  5
  nextStop(10, UP) turns round       9

== 3 - pendingStops must be ascending. A HashSet of floors looks ascending ==
  10-floor building, added 9,2,7,4   [2, 4, 7, 9]
  20-floor tower,   added 19,3,12,5  [19, 3, 5, 12]
  20-floor tower,   added 3,19,20,4  [3, 19, 20, 4]
  TreeSet of 19,3,12,5               [3, 5, 12, 19]

== 4 - lift 3 is withdrawn. Its calls go on a worklist and get re-placed ==
  addLast 2,5,9  toString [2, 5, 9]  drained [2, 5, 9]
  push    2,5,9  toString [9, 5, 2]  drained [9, 5, 2]
  two callers on floor 7, UP first then DOWN:
    directionCalledFor(7)             UP
    same two calls, drained by push   DOWN
    pendingStops in both cases        [7]

== 5 - the factories that hand back something you cannot write to ==
  pendingStops().add(9)             java.lang.UnsupportedOperationException (no message)
    top frames of pendingStops().add(9):
      at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:142)
      at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:147)
      at Main.lambda$theViewsThatThrow$1(Main.java:191)
  Arrays.asList(...).add(5)         java.lang.UnsupportedOperationException (no message)
  Arrays.asList(...).set(0, 2)      no throw
  Set.of(...).add(5)                java.lang.UnsupportedOperationException (no message)
  Map.of(...).put(5, DOWN)          java.lang.UnsupportedOperationException (no message)
  Map.of(7, UP, 7, DOWN)            java.lang.IllegalArgumentException: duplicate key: 7
  Map.of(7, null)                   java.lang.NullPointerException (no message)
  List.of(2, null, 9)               java.lang.NullPointerException (no message)
  Set.of(2,5,7,9,10) iterates       [7, 9, 10, 2, 5]
  Map.of(...).keySet() iterates     [7, 9, 10, 2, 5]
  run this twice and compare those two lines

== 6 - two more, one line each ==
  EnumMap iterates in declaration order {UP=3, DOWN=1}  (J10 covers this)
  PriorityQueue toString                [2, 3, 7, 9, 5, 8]
  PriorityQueue poll order              [2, 3, 5, 7, 8, 9]
```

Four lines in there are the lesson: `20 ticks` against `15 ticks`, `[19, 3, 5, 12]`, `DOWN` where
`UP` was expected, and the two `iterates` lines changing between runs.

Every other line above reproduces byte for byte. Those two will not, and that is the point of them:
your run of `Set.of(2,5,7,9,10)` will print some other order, and so will the next one.

---

## `LiftWork.java` — the three field declarations

```java
    private final NavigableMap<Integer, Integer> stops = new TreeMap<>();
```

**This declaration is the reason `nextStop` has no loop in it.** Every question a lift asks about its
pending stops is a neighbour question, and `NavigableMap` is the interface that answers neighbour
questions. Change it to `Map` and `nextStop` stops compiling on `ceilingKey`. Change it to `HashMap`
and it compiles, `pendingStops()` returns an order that depends on the floor numbers, and the four
neighbour calls become a scan you write by hand.

**The value is a count, so one map replaces two.** Floor to riders-bound-for-it, with 0 meaning "a
hall call nobody has boarded for". The reference solution keeps a `TreeSet<Integer> stops` and a
separate `HashMap<Integer, Integer> ridersFor`; merging them means the set of stops and the rider
counts cannot disagree about which floors exist. Both shapes are defensible, and the invariant here
is stronger: `stops.keySet()` *is* the pending set, by construction.

```java
    private final Map<Integer, Direction> hallCalls = new HashMap<>();
```

**Declared `Map`, not `NavigableMap`, on purpose.** Every read is `hallCalls.get(floor)` for one
exact floor, so order buys nothing and the narrower declaration says so. This field and the one above
it are in the same class for exactly that contrast: same key type, same size, different question,
different type.

**A stop can exist with no entry here.** Somebody inside the car pressed it, so there is no direction
to remember. `directionCalledFor(4)` returns `null` above, and that null is meaningful rather than a
bug — it means "no hall caller is waiting on 4".

```java
    private final Set<Integer> served;
```

**`Set`, because the only question is `served.contains(floor)`.** Not a `List`: `contains` on a
`List` is a scan, and it also lets a floor be added twice. Not a `TreeSet`: nothing asks about
neighbouring floors of the served set. This is `FloorAccess` from the reference, expressed as data
instead of a lambda.

```java
        this.served = Set.copyOf(servedFloors);
```

**`Set.copyOf`, so the caller cannot widen this lift's access after construction.** Without the copy,
the caller's set is this lift's set. `ExpressShaft` has lift 3 stopping only at floors 1 and 6..10,
and that becomes a promise anybody holding the set can break. The cost is stated plainly: the result
rejects `null` elements, and mutating it throws `UnsupportedOperationException` with no message.

```java
    public void accept(Call call) {
        stops.putIfAbsent(call.floor(), 0);
        hallCalls.putIfAbsent(call.floor(), call.direction());
    }
```

**`putIfAbsent` on the first line preserves a boarded rider count.** A passenger presses 7, then a
hall caller on 7 presses UP. Plain `put(7, 0)` would erase the rider, so `load` would be one more
than the riders the map accounts for. When that lift serves floor 7 the passenger never gets out.
There is no C++ shorthand for this: `stops[7] = 0` overwrites, and `stops.emplace(7, 0)` is the
closest match.

**`putIfAbsent` on the second line is the contract's "first direction wins".** Two callers at one
floor collapse to one stop, and the direction remembered is the first one to arrive. Block 4 shows
what a reversed worklist does to it: `UP` becomes `DOWN`, and `pendingStops` is identical either way.

```java
        stops.merge(destinationFloor, 1, Integer::sum);
```

**`merge` is `stops[floor]++` with the absent case handled.** Absent means insert 1; present means
apply the function to the old value and 1. Java has no `operator[]` that default-constructs, so the
by-hand version is a `get`, a null check and a `put`. That is three lines that can each be wrong, and
the null check is mandatory because `get` returns `Integer`. `computeIfAbsent` is the sibling for when
the value is a collection.

```java
        Integer alighting = stops.remove(floor);
        ...
        if (alighting != null) {
            load -= alighting;
        }
```

**`remove` returns the old value, so serving a floor is one map operation.** `Integer`, not `int`,
because absent is `null` — and the null check is what stops `load` being corrupted by a floor that
was never pending. Write `int alighting = stops.remove(floor)` and a missing key gives you a
`NullPointerException` on the unboxing, at this line, naming nothing useful.

```java
    public List<Integer> pendingStops() {
        return List.copyOf(stops.keySet());
    }
```

**Two guarantees in one line.** `keySet()` of a `TreeMap` iterates ascending, which is what
`OperatorConsoleApi.pendingStops` requires. `List.copyOf` makes it a snapshot, so the caller cannot
reach into this lift's work list. That is `A7`'s rule, and the contract states it: *"a snapshot;
mutating it must not affect the building"*.

**Drop the `copyOf` and `keySet()` is a live view.** The caller's `remove` would cancel a real call,
and the failure appears in whichever test runs next rather than here. Block 5 shows the cost of
keeping it: `pendingStops().add(9)` throws `UnsupportedOperationException` with no message, so the
frames are the only diagnosis.

```java
            case UP -> onwardOr(stops.ceilingKey(currentFloor), stops.lastKey());
```

**`ceilingKey` is safe here only because the line above already handled the current floor.**
`stops.containsKey(currentFloor)` returns `currentFloor` first, so by this point the lift is not
standing on a pending stop and `ceilingKey(currentFloor)` is the lowest one strictly above it. Remove
the `containsKey` branch and the lift serves the floor it is on, then serves it again, for ever.

**`lastKey()` is the reversal, and it is correct for a specific reason.** `ceilingKey` returned
`null`, so nothing is pending above; every remaining stop is therefore below, so the highest of them
all is the highest below. `nextStop(10, UP)` prints `9` for that reason. Reaching for `floorKey`
here would give the same answer and read as if it were a different rule.

**`firstKey()` and `lastKey()` throw on an empty map.** `stops.isEmpty()` at the top of the method is
what makes them safe. Delete it and an idle lift gives you
`java.util.NoSuchElementException` with no message from inside `TreeMap`.

```java
    public int owedBelow(int floor) {
        return stops.headMap(floor, false).size();
    }
```

**`headMap` is a view, so this allocates one wrapper and copies nothing.** The `false` is
`inclusive`, and getting it wrong by one floor is the kind of bug that shows up as a lift that
answers a call it should have left alone. Two things the view carries with it: writes go through to
the backing map, and a key outside the range is refused with
`java.lang.IllegalArgumentException: key out of range`.

---

## `ArrivalOrderWork.java` — the version that is not a straw man

FIFO is right for a print spooler and a task queue. Here is what it costs a lift.

```java
    private final Deque<Integer> stops = new ArrayDeque<>();
```

**`Deque` on the left, `ArrayDeque` on the right.** `Deque` has every end operation, so there is no
reason to name the class in the declaration. Declare it `ArrayDeque` and swapping in
`ConcurrentLinkedDeque` for J12 touches every signature that passes it along.

```java
        if (!stops.contains(floor)) {
            stops.addLast(floor);
        }
```

**`contains` on an `ArrayDeque` is a linear scan, and the duplicate check has to be written at all.**
A lift stops at a floor once, so the pending stops are a set by nature. This is the first sign the
container is wrong: you are hand-rolling the property the right container has for free.

```java
    public Integer nextStop(int currentFloor, Direction direction) {
        return stops.peek();
    }
```

**Both parameters are ignored, and that is the bug in one line.** The head is the oldest call, and
the oldest call has nothing to do with where the lift is or which way it is going. The consequence,
unedited:

```
  ArrayDeque, arrival order   serves [9, 2, 7]  in 20 ticks
  TreeMap, direction order    serves [7, 9, 2]  in 15 ticks
```

Five extra ticks on three calls, and the lift passes floor 7 twice with the doors shut. The
acceptance suite asserts on floors and directions after a given number of `step()` calls, so this
fails as a wrong floor rather than as anything mentioning a container.

```java
        List<Integer> ascending = new ArrayList<>(stops);
        ascending.sort(null);
        return List.copyOf(ascending);
```

**Three lines and two allocations to answer what `List.copyOf(stops.keySet())` answers in one.**
`sort(null)` means natural order, and it is the only sort a `List` of `Integer` needs. Note that this
sort is on a *copy*: sorting the deque itself is not possible, because a `Deque` has no `sort`. So
the ordering has to be recomputed on every call, and the contract's "ascending" is restated in this
method instead of being a property of the field.

---

## `Redispatch.java` — the one place a deque belongs

```java
    private final Deque<Call> worklist = new ArrayDeque<>();

    public void add(Call call) {
        worklist.addLast(call);
    }
```

**`addLast`, and the name is doing work.** `add` also appends, and `offer` appends, and `push`
prepends. Three of the four are the same operation. Writing the end into the call is what makes the
next reader sure, and the corresponding drain uses `poll`, which takes the head.

```java
    public void addTheWayPushLooks(Call call) {
        worklist.push(call);
    }
```

**Kept in the file so it can be run.** `std::queue::push` appends; `ArrayDeque.push` prepends. The
same three calls through this method come out reversed:

```
  addLast 2,5,9  toString [2, 5, 9]  drained [2, 5, 9]
  push    2,5,9  toString [9, 5, 2]  drained [9, 5, 2]
```

**`toString` matches the drain order, which is the detail that makes this hard to catch.** A deque
prints head-first, so `[9, 5, 2]` looks like a list that was built backwards rather than a stack.
Compare `Stack`, which prints bottom-first: `[2, 5, 9]` with `pop()` returning 9. One of the two
prints in the order it hands things back, and it is the one nobody should use.

```java
        while (!worklist.isEmpty()) {
            out.add(worklist.poll());
        }
```

**`poll`, not `pop`, and the difference is what happens on empty.** `poll` returns `null`, `pop`
throws `java.util.NoSuchElementException` with no message. Guarded by `isEmpty` neither can fire, so
the choice is about which one fails usefully if the guard is ever removed — and under concurrency, it
will be. `poll` returning null quietly is the worse of the two.
