Skip to main content

Walkthrough — Module 03: Information Structures

Read this AFTER a stage is green — it explains how the reference solution is built and why.

Stage 1: Stacks and queues in sequential storage​

The reference makes error policy an explicit part of the contract: push/enqueue return Result<(), Overflow> and pop/dequeue return Result<_, Underflow>, mirroring Knuth's OVERFLOW/UNDERFLOW as reportable conditions rather than panics — because whether a full structure should grow, purge, or abort is the caller's decision. ArrayStack lets the Vec's length stand in for Knuth's pointer T. ArrayQueue is the instructive one: it stores front and an explicit len instead of the classic two pointers F and R, and computes the rear as (front + len) % capacity. That single extra field cures the ambiguity Knuth flags in exercise 2.2.2-1, where two bare pointers make a full queue indistinguishable from an empty one and force you to waste a cell; here all capacity cells are usable. stack_permutable is a greedy single-siding simulation, and it is provably optimal: when the wanted car is on top you must pop it now or bury it forever, and when it hasn't arrived you must keep pushing — there is never a real choice, so greedy is exact. It also rejects non-permutations up front, and the number of realizable orders is the Catalan number.

Stage 2: Linked allocation with an AVAIL list​

LinkedArena is the module's thesis in code: Knuth's MIX linked memory becomes two parallel Vecs (INFO and LINK) addressed by usize, with Λ = LAMBDA = usize::MAX, and no Rc<RefCell>. Storing INFO as Option<T> does double duty — a cell sitting on the AVAIL stack holds None, so free can .take() the value out and info() can assert a cell is really in use. The allocation policy is the whole point: allocate reuses the AVAIL head when one exists and only grows the backing Vec when AVAIL is empty, so cells_in_memory() stays bounded by the peak number of simultaneously live nodes rather than the total ever allocated — the reference test asserts exactly this by freeing a cell and checking the next allocation draws no new memory. delete_after deletes a node's successor (Q <- LINK(P); LINK(P) <- LINK(Q); AVAIL <= Q) because that is the O(1) deletion a singly linked list actually supports; deleting the node itself would need its predecessor.

Stage 3: Topological sorting​

The reference is a faithful Algorithm T: a count array of unmet predecessors and a per-object successor list, built in one pass over the relations. The design choice that makes the output deterministic is the queue discipline — successors are stored in input order, the initial scan enqueues zero-count objects in increasing order 1..=n, and the queue is strict FIFO — which is exactly Knuth's QLINK threading and is why the reference reproduces the book's worked answer 1 9 3 2 7 5 4 8 6 rather than some other valid order. Cycle detection falls out for free: if fewer than n objects are emitted, the leftovers all have positive counts and lie on or beyond a cycle, so the function returns None; a self-loop (j, j) is caught immediately. Using a VecDeque for the queue is the idiomatic stand-in for the array-threaded queue, and the O(V + E) bound comes from touching each relation exactly once when its source is output.

Stage 4: Traversing binary trees​

inorder is the explicit-stack Algorithm 2.3.1T, deliberately not recursion — the while p != LAMBDA inner loop drives left pushing nodes, then a pop visits and steps right. The reference then shows how little the skeleton changes to get the other orders: preorder visits at the moment of pushing (on the way down) instead of on the pop, and postorder uses the elegant two-stack trick — a "root, right, left" walk reversed is exactly postorder — which sidesteps the awkward "have I visited the right child yet?" bookkeeping a direct postorder needs. from_traversals reconstructs the unique tree from preorder+inorder by recursion on slices: pre[0] is the root, its position in the inorder slice splits left from right, and nodes are built bottom-up so each parent is created only after its children's arena indices exist. The reference tests build one shared expression tree a*(b-c)+d/e and check all three traversals plus a round-trip through from_traversals, which validates the reconstruction against the traversals it must invert.

Stage 5: Threaded binary trees​

This is the module's cleverest structure. Every would-be Λ link becomes a tagged thread to the node's inorder predecessor (left) or successor (right), and a list head at index 0 anchors both ends — its LLINK is the tree root and RLINK(head) = head always. The invariant that makes Algorithm S correct: RTAG set means RLINK points straight at the successor, so successor returns it immediately; otherwise it steps once right and descends left links while LTAG is clear, landing on the leftmost node of the right subtree. Because threads carry all the state, a full traversal iterates successor from the head back to the head with O(1) extra space — no stack, unlike Stage 4. The insertion routines (insert_left/insert_right) are mirror images that each perform Knuth's three-step patch: the new node inherits the parent's link and tag on one side and gets a thread back to the parent on the other, the parent's link is redirected, and — the step people forget — if the new node acquired a real subtree, the old thread that pointed into the parent from that subtree's extreme node is retargeted to the new node. The reference's inorder_via_threads_counting even accounts every link it follows and asserts the total is <= 2n + 2, making concrete the claim that although one successor call can cost O(height), the whole traversal is O(n).