Collections, mapped from the STL

The idea

The container you pick is a claim about order

A lift's pending stops arrive one call at a time, so the container that comes to mind is a queue. std::queue<int> is spelled ArrayDeque<Integer> here, and the code writes itself:

Deque<Integer> stops = new ArrayDeque<>();

Lift 1 stands on floor 4 travelling UP. Calls arrive for 9, then 2, then 7. Taking them off the head, it serves [9, 2, 7] in 20 ticks and sails past floor 7 twice without opening its doors. ElevatorApi says stops are served in direction order, not arrival order. Arrival order is the one thing a queue is built to remember, and the one thing a lift has to throw away.

What the lift asks is "which pending floor is nearest at or above me". That is a question about order, so the container has to keep order:

NavigableMap<Integer, Integer> stops = new TreeMap<>();  // floor -> riders bound for it
stops.ceilingKey(4);                                     // 7

Now it serves [7, 9, 2] in 15 ticks. std::map did this for you, and its Java spelling is TreeMap — HashMap is unordered_map.

Then pendingStops() has to hand the floors back ascending, and a HashSet<Integer> looks like it already does. In the ten-floor building it does: adding 9, 2, 7, 4 iterates [2, 4, 7, 9], because Integer.hashCode() is the value itself. Move to a twenty-floor tower and adding 19, 3, 12, 5 iterates [19, 3, 5, 12].

Nothing threw. Every test you wrote against ten floors still passes.

Coming from C++

From C++ — the same containers under different names, and the three places the mapping lies

You know what a hash map is. What you need is the spelling, and the two names that map to nothing you have used. Then the places where the obvious translation is wrong at run time rather than at compile time. Every example below is the elevator: corpus/elevator/, floors 1..10, three lifts.

The mapping table

Two classes in there deserve one sentence and no more. Vector and Stack exist, they are synchronized on every method, and nobody should use either. Vector predates ArrayList and Stack extends it, which is why Stack.get(0) returns the bottom while pop() returns the top; use ArrayList and ArrayDeque instead.

ArrayDeque answers three C++ classes, and that is the useful fact here

There is no separate queue class worth using and no separate stack class worth using. ArrayDeque is both, and it is also std::deque. So the shape of your code no longer tells a reader which one you meant — the method names do, and that is where the mapping bites.

push and pop operate on the head. push is addFirst, pop is removeFirst. So ArrayDeque is a stack from the front, and if you reach for push because std::queue::push appends, your order silently inverts. Real output from worked/:

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

The elevator has a place where that matters. takeOutOfService hands back the calls a withdrawn lift can no longer answer, and every one is re-placed on another lift. The re-dispatch worklist is the one genuine deque in this problem. And when two callers pressed opposite directions at the same floor, the contract says the lift keeps one stop and the first direction to arrive:

  two callers on floor 7, UP first then DOWN:
    directionCalledFor(7)             UP
    same two calls, drained by push   DOWN
    pendingStops in both cases        [7]

pendingStops is identical either way, so no assertion about pending stops catches this. The lift answers with the wrong direction, and a later re-dispatch picks the wrong lift for it.

Two more differences worth having: ArrayDeque rejects null with a NullPointerException, and it has two families of end operations. poll and peek return null on empty; pop and removeFirst throw java.util.NoSuchElementException. C++ gave you neither — front() on an empty deque is undefined behaviour.

Declare the interface, construct the implementation

private final NavigableMap<Integer, Integer> stops = new TreeMap<>();
private final Map<Integer, Direction> hallCalls = new HashMap<>();
private final Set<Integer> served;

The left of each = is the narrowest type that answers the questions this field is asked. The right is today's implementation. That split is the same idea as the corpus's policy seams, one level down, and it buys two specific things.

Swapping the implementation is one line. hallCalls is a HashMap because every lookup is by exact floor. If a requirement arrives that needs the nearest hall call above a floor, the field becomes NavigableMap plus new TreeMap<>(), and no caller changes. Declare it HashMap and every method signature that passed it around has to be edited too.

The declaration states the guarantee. NavigableMap on stops says "this thing is ordered and that is load-bearing". Map on hallCalls says "order is not promised, do not rely on it". A reviewer, and an interviewer, reads the field declarations first.

The exception is worth stating so it does not look like a rule with no edges. Declare the concrete type when you need a method the interface does not have. ArrayDeque implements Deque, and Deque has everything, so Deque<Call> is right. There is no NavigableList, so a field needing ArrayList.ensureCapacity is declared ArrayList.

TreeMap only earns its place when you need order, and then it earns it enormously

The cost first, so the choice is honest. TreeMap is O(log n) where HashMap is O(1), it allocates a node per entry, and it throws NullPointerException on a null key where HashMap accepts one. On ten floors none of that is measurable, and the constant factor argument is not why you choose either.

You choose TreeMap when the question you ask is about neighbours. Here is ElevatorApi's entire direction-order rule, against a NavigableMap<Integer, Integer> of pending stops:

    public Integer nextStop(int currentFloor, Direction direction) {
        if (stops.isEmpty()) {
            return null;
        }
        if (stops.containsKey(currentFloor)) {
            return currentFloor;      // finish where you are before you move
        }
        return switch (direction) {
            case UP -> onwardOr(stops.ceilingKey(currentFloor), stops.lastKey());
            case DOWN -> onwardOr(stops.floorKey(currentFloor), stops.firstKey());
            case IDLE -> nearest(currentFloor);
        };
    }

Four queries, no loop, no sort, no index arithmetic. Real output from worked/, with stops pending at 2, 5 and 9:

  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
  nextStop(4, UP)                    5
  nextStop(4, DOWN)                  2
  nextStop(4, IDLE)                  5
  nextStop(10, UP) turns round       9

The names, against the std::map calls you already use:

Three details the C++ versions do not have. Absent is null, not an end iterator, so ceilingKey(10) above returns null rather than something you must compare against end(). On an empty map, firstKey() throws java.util.NoSuchElementException while ceilingKey returns null — the neighbour queries are the null-safe family. And headMap is a live view, not a copy: writing through it writes through to the map, and a key outside its range is refused with java.lang.IllegalArgumentException: key out of range.

Writing nextStop against an ArrayList instead means a scan, a comparison and two edge cases per branch. That is where a candidate loses ten minutes in a round, and it is the reason to know these seven method names cold.

The trap that actually bites: the factory that hands back a view

List.of, Map.of, Set.of and Arrays.asList all look like constructors and none of them returns something you can write to. Nothing warns you at compile time. Real output, caught and printed by worked/Main.java:

  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)

The exception carries no message. Uncaught, that is the whole of what you get:

Exception in thread "main" java.lang.UnsupportedOperationException
	at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:142)
	at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:147)
	at Probe2.main(Probe2.java:18)

The frame naming ImmutableCollections is the only clue, and Arrays.asList does not even give you that — its trace reads at java.base/java.util.AbstractList.add(AbstractList.java:155) and never mentions Arrays. So recognise the two traces, because the exception itself tells you nothing.

Three shapes, and they differ:

Arrays.asList is the one that surprises people twice. It is fixed-size rather than immutable, and it wraps the array you passed rather than copying it. If you need a mutable list from a fixed one, new ArrayList<>(List.of(...)) is the copy.

Map.of has two more edges

Duplicate keys are refused, at construction. Two hall calls for floor 7 in one literal:

  Map.of(7, UP, 7, DOWN)            java.lang.IllegalArgumentException: duplicate key: 7

Set.of matches it with duplicate element: 7. A HashMap would have taken the second value quietly, so this is the safer behaviour — provided the keys are literals you control.

Null is refused, key or value. Map.of(7, null) and List.of(2, null, 9) both throw java.lang.NullPointerException with no message. HashMap and ArrayList both accept nulls, so this bites when you build a Map.of from parsed input.

And the iteration order is deliberately randomised between JVM runs. The same program, twice, no recompile:

  Set.of(2,5,7,9,10) iterates       [7, 9, 10, 2, 5]
  Map.of(...).keySet() iterates     [7, 9, 10, 2, 5]

  Set.of(2,5,7,9,10) iterates       [10, 2, 5, 7, 9]
  Map.of(...).keySet() iterates     [10, 2, 5, 7, 9]

A per-JVM salt is mixed into the layout on purpose, to stop anybody depending on the order. A test that asserts on the order of a Map.of keySet passes locally, passes in CI, and fails on some later run with no change to blame. Do not iterate Map.of or Set.of for anything observable. If you need ascending, say so: new TreeSet<>(Set.of(...)), or List.copyOf of a TreeMap's keys.

The trap one level down: HashSet<Integer> looks sorted

This is the trap that survives review, because the evidence supports it. Integer.hashCode() returns the value, and a HashSet puts a key in bucket hash & (tableSize - 1). With floors 1..10 and a default table of 16, every floor lands in its own bucket in order:

  10-floor building, added 9,2,7,4   [2, 4, 7, 9]

So pendingStops() backed by a HashSet satisfies the contract's "ascending" every single time you run it against the building Entry.create() builds. Now the same code in a twenty-floor tower, where 19 and 3 collide because 19 & 15 == 3:

  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]

The threshold is exact: with the default capacity of 16, HashSet<Integer> iterates ascending only while every value is distinct modulo the table size. It is never a guarantee, at any size. If a caller can see the order, the type has to promise it.

PriorityQueue — two differences, both silent

Java's PriorityQueue is a min-heap. std::priority_queue is a max-heap. So the direct translation of C++ code inverts the priority, and neither compiler says a word. For largest-first, pass Comparator.reverseOrder().

And it is a heap, not a sorted container. toString and iteration show heap order:

  PriorityQueue toString                [2, 3, 7, 9, 5, 8]
  PriorityQueue poll order              [2, 3, 5, 7, 8, 9]

Only poll is ordered. C++ never let you iterate a priority_queue at all, so there was no way to form this habit; Java lets you, and the result looks almost sorted.

EnumMap, in one line

An enum key means EnumMap: an array indexed by ordinal(), no hashing, iterating in declaration order. worked/Main.java prints {UP=3, DOWN=1} for a Map<Direction, Integer>. J10 covers why that matters, and it is more than the array.

The choosing rule, in the order to ask it

Ten seconds, top to bottom, first match wins:

1. Key is an enum → EnumMap. See J10
2. You ask about order — nearest above, ranges, first, last, sorted output → TreeMap / TreeSet
3. You add and remove at both ends → ArrayDeque
4. You only ask "is it in there" → HashSet
5. Key to value, looked up by exact key → HashMap
6. Otherwise → ArrayList

The reason the order matters is that rules 2 and 4 both look like rule 5 from inside a method. The elevator has all three in one class: stops is asked for neighbours, so TreeMap; hallCalls is asked for one exact floor, so HashMap; served is asked only for membership, so a Set.

When the default is wrong

Rule 6 is wrong when a caller can see the iteration order. ArrayList keeps insertion order, which is a promise you probably did not mean to make — the FIFO route at the top of this page is that promise being kept faithfully.

Rule 5 is wrong the moment you need "the entry nearest to k". Reaching for a HashMap and sorting its keys on each call is the tell. Two sorts per tick costs more than a TreeMap, and the sort is a line of code that can be wrong.

Rule 4 is wrong when the set is the answer rather than a filter. pendingStops() returns a List, ascending, because the operator's console draws it. A HashSet behind it satisfies the contract on ten floors and breaks on twenty.

Rules 2 and 3 are wrong when you have not been asked for order at all. A TreeMap keyed by lift id, holding lifts 1, 2 and 3, is a sorted structure over a dense range. The reference uses List.copyOf and lifts.get(liftId - 1), which is one array read.

Worked walkthrough

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

    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.

    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".

    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.

        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.

    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.

        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.

        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.

    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.

            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.

    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.

    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.

        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.

    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.

        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

    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.

    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.

        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.

Worked source

The 6 files of the worked design

Every file below is the one the app opens, verbatim. This is the part worth reading slowly: the prose above argues for a shape, and these are the lines that have it.

• worked/src/ArrivalOrderWork.java 42 lines
• worked/src/Call.java 23 lines
• worked/src/Direction.java 11 lines
• worked/src/LiftWork.java 151 lines
• worked/src/Redispatch.java 36 lines
• worked/src/Main.java 270 lines

worked/src/ArrivalOrderWork.java42 lines

// ArrivalOrderWork.java
//
// The container a C++ developer reaches for first, kept so the failure is visible rather than
// described. Calls arrive one at a time, so a queue. std::queue<int> spells itself ArrayDeque here.
//
// It is not a straw man: FIFO is right for a print spooler, a task queue and a rate limiter's
// window. It is wrong for a lift, and the reason is one sentence in ElevatorApi's javadoc.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public final class ArrivalOrderWork {

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

    /** Duplicates have to be filtered by hand, because a queue is not a set. */
    public void accept(int floor) {
        if (!stops.contains(floor)) {
            stops.addLast(floor);
        }
    }

    public void serveHere(int floor) {
        stops.remove(floor);
    }

    /** The head, which is the oldest call. Nothing here knows where the lift is standing. */
    public Integer nextStop(int currentFloor, Direction direction) {
        return stops.peek();
    }

    /**
     * The contract says ascending. This returns arrival order, so it needs a sort on every call —
     * and a sort of what a queue holds is a copy of it.
     */
    public List<Integer> pendingStops() {
        List<Integer> ascending = new ArrayList<>(stops);
        ascending.sort(null);
        return List.copyOf(ascending);
    }
}

worked/src/Call.java23 lines

// Call.java — copied from corpus/elevator/reference/src/Call.java.
//
// A record, so two calls for the same floor and direction are equal and hash alike. That is what
// lets a Set or a Map key collapse duplicate requests, and it is J6's territory rather than this
// lesson's. It matters here only because a collection is exactly as good as the equals it is given.

/**
 * A request for a lift to visit a floor, and which way the person there wants to go.
 *
 * The direction has to outlive the {@code hallCall} that carried it: when a lift is withdrawn its
 * calls are re-dispatched, and re-dispatching needs the direction the caller originally asked for.
 */
public record Call(int floor, Direction direction) {

    public Call {
        if (floor < 1) {
            throw new IllegalArgumentException("floors are 1-based, got " + floor);
        }
        if (direction == null || direction == Direction.IDLE) {
            throw new IllegalArgumentException("a call must ask for UP or DOWN, got " + direction);
        }
    }
}

worked/src/Direction.java11 lines

// Direction.java — copied unchanged from corpus/elevator/contract/Direction.java.
//
// Here so this lesson compiles on its own. In a real attempt it is a GIVEN file you do not edit.

/**
 * Which way a lift is travelling, or which way a waiting passenger wants to go.
 *
 * {@code IDLE} means "standing still with nothing to do". A hall call must ask for
 * {@code UP} or {@code DOWN} — {@code IDLE} is not a request.
 */
public enum Direction { UP, DOWN, IDLE }

worked/src/LiftWork.java151 lines

// LiftWork.java
//
// The outstanding work of one lift: which floors it owes a visit, which way each hall caller wanted
// to go, and which floors this shaft can physically reach.
//
// Three collections, three different questions, three different types. The whole lesson is in the
// three field declarations.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.TreeMap;

public final class LiftWork {

    /**
     * Pending stops: floor -> how many passengers aboard are bound for it. A hall call nobody has
     * boarded for maps to 0.
     *
     * Ordered, because every question this lift asks about it is a neighbour question: what is the
     * next stop at or above me, what is the highest one below me, what are the two ends of the run.
     * A HashMap answers none of those without a full scan and a sort.
     */
    private final NavigableMap<Integer, Integer> stops = new TreeMap<>();

    /**
     * The direction each hall call asked for, kept so a withdrawal can re-dispatch it as the same
     * request. Looked up by exact floor and never by neighbour, so order buys nothing here.
     */
    private final Map<Integer, Direction> hallCalls = new HashMap<>();

    /** Which floors this shaft reaches. Membership only, so a set, and immutable once built. */
    private final Set<Integer> served;

    private final int capacity;
    private int load;

    public LiftWork(int capacity, Set<Integer> servedFloors) {
        this.capacity = capacity;
        this.served = Set.copyOf(servedFloors);
    }

    public boolean serves(int floor) {
        return served.contains(floor);
    }

    public int load() {
        return load;
    }

    /**
     * Accept a hall call. Two callers at the same floor wanting opposite directions collapse into
     * one stop, and the first direction to arrive is the one remembered for a re-dispatch.
     */
    public void accept(Call call) {
        stops.putIfAbsent(call.floor(), 0);
        hallCalls.putIfAbsent(call.floor(), call.direction());
    }

    /** A passenger boards and presses a floor. @return false if the lift is already full */
    public boolean board(int destinationFloor) {
        if (load >= capacity) {
            return false;
        }
        load++;
        stops.merge(destinationFloor, 1, Integer::sum);
        return true;
    }

    /** Serve the floor the lift is standing on: the stop goes, and everybody bound for it gets out. */
    public void serveHere(int floor) {
        Integer alighting = stops.remove(floor);
        hallCalls.remove(floor);
        if (alighting != null) {
            load -= alighting;
        }
    }

    /** What {@code OperatorConsoleApi.pendingStops} owes its caller: every floor, ascending. */
    public List<Integer> pendingStops() {
        return List.copyOf(stops.keySet());
    }

    /** The lowest pending stop at or above {@code floor}, or null if there is none. */
    public Integer nextStopAtOrAbove(int floor) {
        return stops.ceilingKey(floor);
    }

    /** The highest pending stop at or below {@code floor}, or null if there is none. */
    public Integer highestStopAtOrBelow(int floor) {
        return stops.floorKey(floor);
    }

    /** Which way the person who called from this floor wanted to go, or null if nobody called. */
    public Direction directionCalledFor(int floor) {
        return hallCalls.get(floor);
    }

    /** The hall calls somebody else must answer once this lift is withdrawn. */
    public List<Call> orphans() {
        List<Call> out = new ArrayList<>(hallCalls.size());
        for (Map.Entry<Integer, Direction> pending : hallCalls.entrySet()) {
            out.add(new Call(pending.getKey(), pending.getValue()));
        }
        return out;
    }

    /**
     * The whole direction-order rule from {@code ElevatorApi}'s javadoc, in four neighbour queries.
     *
     * @return the floor to head for, or null for "nothing to do"
     */
    public Integer nextStop(int currentFloor, Direction direction) {
        if (stops.isEmpty()) {
            return null;
        }
        if (stops.containsKey(currentFloor)) {
            return currentFloor;      // finish where you are before you move
        }
        return switch (direction) {
            case UP -> onwardOr(nextStopAtOrAbove(currentFloor), stops.lastKey());
            case DOWN -> onwardOr(highestStopAtOrBelow(currentFloor), stops.firstKey());
            case IDLE -> nearest(currentFloor);
        };
    }

    /** Carry on this way if anything is left this way; otherwise turn round and take the far end. */
    private Integer onwardOr(Integer onward, Integer afterReversing) {
        return onward != null ? onward : afterReversing;
    }

    /** A standing lift has no momentum to respect. Tie goes to the lower floor, so it is repeatable. */
    private Integer nearest(int currentFloor) {
        Integer below = highestStopAtOrBelow(currentFloor);
        Integer above = nextStopAtOrAbove(currentFloor);
        if (below == null) {
            return above;
        }
        if (above == null) {
            return below;
        }
        return currentFloor - below <= above - currentFloor ? below : above;
    }

    /** How many stops this lift still owes strictly below {@code floor}. A view, not a copy. */
    public int owedBelow(int floor) {
        return stops.headMap(floor, false).size();
    }
}

worked/src/Redispatch.java36 lines

// Redispatch.java
//
// takeOutOfService hands back the calls a withdrawn lift can no longer answer, and every one of
// them has to be placed on another lift. That is a worklist, and it is the one place in this
// problem where a deque is the right container: things go in at one end and come out at the other.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public final class Redispatch {

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

    /**
     * addLast, not push. `push` on an ArrayDeque inserts at the HEAD, so it would turn this into a
     * stack and drain the calls newest-first. See NOTES.md for what that costs.
     */
    public void add(Call call) {
        worklist.addLast(call);
    }

    /** The same shape written the way C++ muscle memory writes it. Kept to be run, not admired. */
    public void addTheWayPushLooks(Call call) {
        worklist.push(call);
    }

    /** Drain from the head. poll returns null on empty; pop throws NoSuchElementException. */
    public List<Call> drain() {
        List<Call> out = new ArrayList<>(worklist.size());
        while (!worklist.isEmpty()) {
            out.add(worklist.poll());
        }
        return out;
    }
}

worked/src/Main.java270 lines

// Main.java — every claim in idea.md and from-cpp.md, run rather than asserted.
//
// Compile and run from this directory:
//     ..\..\..\.toolchain\jdk-21\bin\javac.exe -d out *.java
//     ..\..\..\.toolchain\jdk-21\bin\java.exe -cp out Main
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.EnumMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

public final class Main {

    public static void main(String[] args) {
        arrivalOrderAgainstDirectionOrder();
        neighbourQueries();
        ascendingIsNotFree();
        theWorklistThatReversedItself();
        theViewsThatThrow();
        twoOneLiners();
    }

    // ---------------------------------------------------------------- block 1

    /** The same three calls, the same starting floor, two containers. */
    private static void arrivalOrderAgainstDirectionOrder() {
        System.out.println("== 1 - lift 1 stands on floor 4, travelling UP. Calls arrive: 9, 2, 7 ==");

        ArrivalOrderWork fifo = new ArrivalOrderWork();
        fifo.accept(9);
        fifo.accept(2);
        fifo.accept(7);
        System.out.println("  ArrayDeque, arrival order   serves " + fifoRun(fifo));

        LiftWork ordered = tenFloorLift();
        ordered.accept(new Call(9, Direction.DOWN));
        ordered.accept(new Call(2, Direction.UP));
        ordered.accept(new Call(7, Direction.DOWN));
        System.out.println("  TreeMap, direction order    serves " + orderedRun(ordered));
        System.out.println();
    }

    /** One tick loop, written twice because the container is the only difference between them. */
    private static String fifoRun(ArrivalOrderWork work) {
        List<Integer> served = new ArrayList<>();
        int floor = 4;
        Direction direction = Direction.UP;
        int ticks = 0;
        while (ticks < 100) {
            Integer target = work.nextStop(floor, direction);
            if (target == null) {
                break;
            }
            ticks++;
            if (target == floor) {
                work.serveHere(floor);
                served.add(floor);
                continue;
            }
            direction = target > floor ? Direction.UP : Direction.DOWN;
            floor += target > floor ? 1 : -1;
        }
        return served + "  in " + ticks + " ticks";
    }

    private static String orderedRun(LiftWork work) {
        List<Integer> served = new ArrayList<>();
        int floor = 4;
        Direction direction = Direction.UP;
        int ticks = 0;
        while (ticks < 100) {
            Integer target = work.nextStop(floor, direction);
            if (target == null) {
                break;
            }
            ticks++;
            if (target == floor) {
                work.serveHere(floor);
                served.add(floor);
                continue;
            }
            direction = target > floor ? Direction.UP : Direction.DOWN;
            floor += target > floor ? 1 : -1;
        }
        return served + "  in " + ticks + " ticks";
    }

    // ---------------------------------------------------------------- block 2

    private static void neighbourQueries() {
        System.out.println("== 2 - what a lift actually asks its pending stops ==");
        LiftWork work = tenFloorLift();
        work.accept(new Call(2, Direction.UP));
        work.accept(new Call(5, Direction.DOWN));
        work.accept(new Call(9, Direction.DOWN));

        System.out.println("  pendingStops()                    " + work.pendingStops());
        System.out.println("  nextStopAtOrAbove(4)  ceilingKey   " + work.nextStopAtOrAbove(4));
        System.out.println("  nextStopAtOrAbove(5)  ceilingKey   " + work.nextStopAtOrAbove(5));
        System.out.println("  nextStopAtOrAbove(10) ceilingKey   " + work.nextStopAtOrAbove(10));
        System.out.println("  highestStopAtOrBelow(4) floorKey   " + work.highestStopAtOrBelow(4));
        System.out.println("  highestStopAtOrBelow(1) floorKey   " + work.highestStopAtOrBelow(1));
        System.out.println("  owedBelow(5)          headMap      " + work.owedBelow(5));
        System.out.println("  directionCalledFor(5) HashMap.get  " + work.directionCalledFor(5));
        System.out.println("  directionCalledFor(4) HashMap.get  " + work.directionCalledFor(4));
        System.out.println("  nextStop(4, UP)                    " + work.nextStop(4, Direction.UP));
        System.out.println("  nextStop(4, DOWN)                  " + work.nextStop(4, Direction.DOWN));
        System.out.println("  nextStop(4, IDLE)                  " + work.nextStop(4, Direction.IDLE));
        System.out.println("  nextStop(10, UP) turns round       " + work.nextStop(10, Direction.UP));
        System.out.println();
    }

    // ---------------------------------------------------------------- block 3

    private static void ascendingIsNotFree() {
        System.out.println("== 3 - pendingStops must be ascending. A HashSet of floors looks ascending ==");

        Set<Integer> tenFloors = new HashSet<>();
        for (int floor : new int[] {9, 2, 7, 4}) {
            tenFloors.add(floor);
        }
        System.out.println("  10-floor building, added 9,2,7,4   " + tenFloors);

        Set<Integer> tower = new HashSet<>();
        for (int floor : new int[] {19, 3, 12, 5}) {
            tower.add(floor);
        }
        System.out.println("  20-floor tower,   added 19,3,12,5  " + tower);

        Set<Integer> towerAgain = new HashSet<>();
        for (int floor : new int[] {3, 19, 20, 4}) {
            towerAgain.add(floor);
        }
        System.out.println("  20-floor tower,   added 3,19,20,4  " + towerAgain);
        System.out.println("  TreeSet of 19,3,12,5               " + new TreeSet<>(List.of(19, 3, 12, 5)));
        System.out.println();
    }

    // ---------------------------------------------------------------- block 4

    private static void theWorklistThatReversedItself() {
        System.out.println("== 4 - lift 3 is withdrawn. Its calls go on a worklist and get re-placed ==");

        Deque<Integer> byTail = new ArrayDeque<>();
        Deque<Integer> byPush = new ArrayDeque<>();
        for (int floor : new int[] {2, 5, 9}) {
            byTail.addLast(floor);
            byPush.push(floor);
        }
        System.out.println("  addLast 2,5,9  toString " + byTail + "  drained " + drain(byTail));
        System.out.println("  push    2,5,9  toString " + byPush + "  drained " + drain(byPush));

        System.out.println("  two callers on floor 7, UP first then DOWN:");
        LiftWork arrivalOrder = tenFloorLift();
        arrivalOrder.accept(new Call(7, Direction.UP));
        arrivalOrder.accept(new Call(7, Direction.DOWN));
        System.out.println("    directionCalledFor(7)             " + arrivalOrder.directionCalledFor(7));

        LiftWork reversed = tenFloorLift();
        reversed.accept(new Call(7, Direction.DOWN));
        reversed.accept(new Call(7, Direction.UP));
        System.out.println("    same two calls, drained by push   " + reversed.directionCalledFor(7));
        System.out.println("    pendingStops in both cases        " + reversed.pendingStops());
        System.out.println();
    }

    private static List<Integer> drain(Deque<Integer> deque) {
        List<Integer> out = new ArrayList<>();
        while (!deque.isEmpty()) {
            out.add(deque.poll());
        }
        return out;
    }

    // ---------------------------------------------------------------- block 5

    private static void theViewsThatThrow() {
        System.out.println("== 5 - the factories that hand back something you cannot write to ==");

        LiftWork work = tenFloorLift();
        work.accept(new Call(2, Direction.UP));
        List<Integer> snapshot = work.pendingStops();
        report("pendingStops().add(9)", () -> snapshot.add(9));
        framesOf("pendingStops().add(9)", () -> snapshot.add(9));

        List<Integer> served = Arrays.asList(1, 6, 7, 8, 9, 10);
        report("Arrays.asList(...).add(5)", () -> served.add(5));
        report("Arrays.asList(...).set(0, 2)", () -> served.set(0, 2));

        Set<Integer> expressFloors = Set.of(1, 6, 7, 8, 9, 10);
        report("Set.of(...).add(5)", () -> expressFloors.add(5));

        Map<Integer, Direction> fixed = Map.of(2, Direction.UP, 9, Direction.DOWN);
        report("Map.of(...).put(5, DOWN)", () -> fixed.put(5, Direction.DOWN));
        report("Map.of(7, UP, 7, DOWN)", () -> Map.of(7, Direction.UP, 7, Direction.DOWN));
        report("Map.of(7, null)", () -> Map.of(7, (Direction) null));
        report("List.of(2, null, 9)", () -> List.of(2, null, 9));

        System.out.println("  Set.of(2,5,7,9,10) iterates       " + Set.of(2, 5, 7, 9, 10));
        System.out.println("  Map.of(...).keySet() iterates     "
                + Map.of(2, Direction.UP, 5, Direction.DOWN, 7, Direction.UP,
                         9, Direction.DOWN, 10, Direction.DOWN).keySet());
        System.out.println("  run this twice and compare those two lines");
        System.out.println();
    }

    private static void report(String what, Runnable attempt) {
        String pad = " ".repeat(Math.max(1, 34 - what.length()));
        try {
            attempt.run();
            System.out.println("  " + what + pad + "no throw");
        } catch (RuntimeException e) {
            String message = e.getMessage() == null ? " (no message)" : ": " + e.getMessage();
            System.out.println("  " + what + pad + e.getClass().getName() + message);
        }
    }

    /** The frames are the whole diagnosis, because UnsupportedOperationException has no message. */
    private static void framesOf(String what, Runnable attempt) {
        try {
            attempt.run();
        } catch (RuntimeException e) {
            System.out.println("    top frames of " + what + ":");
            StackTraceElement[] frames = e.getStackTrace();
            for (int i = 0; i < Math.min(3, frames.length); i++) {
                System.out.println("      at " + frames[i]);
            }
        }
    }

    // ---------------------------------------------------------------- block 6

    private static void twoOneLiners() {
        System.out.println("== 6 - two more, one line each ==");

        Map<Direction, Integer> waiting = new EnumMap<>(Direction.class);
        waiting.put(Direction.UP, 3);
        waiting.put(Direction.DOWN, 1);
        System.out.println("  EnumMap iterates in declaration order " + waiting + "  (J10 covers this)");

        Queue<Integer> pq = new PriorityQueue<>();
        for (int floor : new int[] {9, 2, 7, 5, 3, 8}) {
            pq.offer(floor);
        }
        System.out.println("  PriorityQueue toString                " + pq);
        List<Integer> polled = new ArrayList<>();
        while (!pq.isEmpty()) {
            polled.add(pq.poll());
        }
        System.out.println("  PriorityQueue poll order              " + polled);
    }

    // ----------------------------------------------------------------

    /** The building Entry.create() builds: 10 floors, every lift stops everywhere, capacity 4. */
    private static LiftWork tenFloorLift() {
        Set<Integer> everyFloor = new HashSet<>();
        for (int floor = 1; floor <= 10; floor++) {
            everyFloor.add(floor);
        }
        return new LiftWork(4, everyFloor);
    }
}