One Waitress, Many Menus (Iterator & Composite)
One loop that walks any shape, and one recursive call that treats a leaf and a whole tree exactly alike.
The idea
Three restaurants merge. The Pancake House keeps its menu in a growable list, the Diner in a fixed-size array, the Cafe in a map keyed by dish name. The waitress has to read all three out loud every morning, so her code grows three different loops. When a fourth restaurant joins with yet another structure, she writes a fourth. The real smell is that she is coupled to how each menu stores its items, which is none of her business.
The fix is embarrassingly small. Each menu hands out a little object that answers two questions: is there another item, and give me the next one. That is an iterator. The array menu's iterator remembers an index, the map menu's iterator walks values, and the waitress cannot tell the difference. She writes one loop and it works on structures that do not exist yet. Every for-of and for-in loop you have ever written is this pattern baked into the language; here you build the machinery underneath the sugar.
Then the menus grow branches. The Diner wants a dessert sub-menu, and the Cafe wants drinks nested inside that. Now an item might be a single dish or a whole menu, nested arbitrarily deep. Composite gives dishes and menus a common supertype, so the waitress holds one reference to the root and calls print on it: leaves print themselves, menus print their name and tell their children to print. One polymorphic call recursing down the tree replaces every special case.
Composite makes an honest trade. A menu item inherits child-management methods like add and remove that make no sense on a leaf, so calling them throws. That is type safety traded for transparency: the client gets to not care what it is holding. It is worth it when uniform treatment is the dominant use case, and you should be able to say when it is not.
The bench — 4 exercises
Three Menus, One Loop
Collapse a waitress with three storage-specific loops into a single loop driven by a two-method iterator interface, then prove a menu you never wrote works with it.
- Write three menus for real: one backed by a growable list, one by a fixed-size array with a capacity larger than its contents, one by a map. Give the waitress three back-to-back loops that poke at each menu's internals.
- Define your own Iterator interface with just hasNext and next, and a Menu interface with createIterator.
- Write an iterator per menu; the array one must report hasNext as false at the first empty slot rather than emitting nulls.
- Rewrite the waitress as one private loop that takes an iterator, called once per menu.
- Add a fourth menu backed by a stack and run the waitress against it without editing a line of her code.
hint
The Diner iterator is the instructive one: capacity six, maybe four real items. hasNext is where that knowledge now lives.
hint
If the waitress still mentions a list, array index, or map type anywhere, the coupling has not actually moved.
hint
Use an insertion-ordered map so the printed order is deterministic.
DONE WHEN
· The full printout is byte-identical to the pre-refactor output
· The waitress source references only Menu and Iterator, no concrete storage
· The fourth menu prints correctly with zero edits to the waitress
· An array menu with empty trailing slots prints no nulls and does not crash
The Menu Grows a Tree
Build a Composite where dishes and menus share a supertype, so print, price, and filter each become one call on the root no matter how deep it nests.
- Write a fixture file describing three top menus, two nested sub-menus, and about twenty items with name, price in integer cents, and a vegetarian flag.
- Define an abstract MenuComponent whose child-management and item methods throw unsupported by default.
- Implement MenuItem as a leaf and Menu as a composite holding children, with print recursing into them.
- Give the waitress printEverything, totalPrice, and printVegetarianMenu, each a single call on the root, with no instanceof or type narrowing anywhere.
- Rebuild the tree from an alternate fixture nested six levels deep and re-run all three operations unchanged.
hint
Write the leaf's print first, then the composite's as "print my own header, then loop children calling print".
hint
If the composite's print contains anything item-specific, the leaf's job leaked upward.
hint
Indentation is just a depth parameter threaded through the recursion.
DONE WHEN
· Indented tree output is stable and depth-correct at six levels
· totalPrice is exact to the cent and the vegetarian listing matches exactly the flagged leaves
· Client code contains zero instanceof or isinstance checks on menu types
· Calling add on a MenuItem raises the documented unsupported-operation error
Iterating the Whole Tree
Write an external iterator over the nested menu with an explicit stack of child iterators, so the flat loop from exercise one walks a tree without knowing it is one.
- Implement CompositeIterator using a stack of iterators, no recursion and no flatten-into-a-list.
- Make Menu.createIterator return one and MenuItem.createIterator return a NullIterator whose hasNext is always false.
- Fix the traversal order as pre-order: composite before its children, children in insertion order.
- Reimplement printVegetarianMenu a second way, as the flat loop plus a vegetarian check driven by this iterator.
- Optional: rewrite the whole thing with generators in about five lines and rerun your checks.
hint
next: peek the top iterator; if exhausted, pop and retry. Otherwise take its next component, and if that component is a composite push its iterator before returning it.
hint
Make hasNext idempotent: calling it twice in a row must change nothing. That is where first versions break.
hint
Laziness is the whole point; a sub-iterator for an unvisited branch should never be constructed.
DONE WHEN
· Draining the iterator yields components in exactly the order the recursive print visits them
· Pulling only the first three items creates no iterators for unvisited branches
· Calling hasNext twice in a row returns the same answer and skips nothing
· Both vegetarian implementations produce identical output
Composite in the Wild: the Filesystem
Reinstantiate both patterns on a real directory tree, where the OS already built the composite and you build the walk. This is du, find, and tree in one shape.
- Check a fixture directory tree into your repo with a few dozen files, several levels, mixed extensions, and one empty directory.
- Model it as FsComponent, FsFile, and FsDir, with a loader that wraps the real directory using stdlib filesystem calls.
- Implement totalSize as a recursive rollup, printTree as indented output with directories first, and find(predicate) returning an iterator of matching files.
- Reuse the stack machinery from the previous exercise without importing anything from the menu code.
- Compare your totalSize and find results against a plain stdlib directory walk over a randomly generated tree.
hint
If your earlier iterator was written against MenuComponent concretely, extract the shape it actually needed: give me your children's iterator.
hint
An empty directory is a legal composite: it prints, and it sizes to zero.
hint
Generate the random comparison tree in a temp directory and delete it after.
DONE WHEN
· totalSize matches an independent stdlib walk on both the fixture and a random tree
· find for a .md suffix yields exactly the expected files, in traversal order
· printTree output is stable and the empty directory appears with zero size
· The filesystem code imports nothing from the menu exercise
Go deeper (after the bench)
Read Head First Design Patterns Ch. 9 now: the waitress dialogue is exercise one in narrative form, and the book's CompositeIterator walkthrough with its stack diagram is effectively the spec for exercise three. Pay attention to the internal-versus-external iterator aside, since this module deliberately makes you build the external kind. For a second angle, Refactoring Guru's free Iterator and Composite pages have clean structure diagrams and honest pros-and-cons tables in nine languages.