TAOCP 7.2.2.1 Exercise 163

Exercise 163. [20] [20] Explain the possible rules for setting $p$ in (12).

Verified: no
Solve time: 1m25s

Solution

In (12), the variable $p$ is used to traverse exactly the vertical list of nodes that correspond to active options containing item $i$. This vertical list is a circular doubly linked list whose header is the item node $i$, with $\mathrm{DLINK}(i)$ pointing to the first node below $i$ and $\mathrm{ULINK}(i)$ pointing to the last node above $i$.

The rule “set $p \leftarrow \mathrm{DLINK}(i)$” in (12) is therefore only one convenient choice of entry point into this cycle. Any rule that selects one node of the vertical list as a starting point and then traverses the list exactly once around the cycle is valid.

One possible family of rules is to begin at $\mathrm{DLINK}(i)$ and iterate downward by setting $p \leftarrow \mathrm{DLINK}(p)$ at each step. This visits all nodes $p$ with $\mathrm{TOP}(p)=i$ in the order determined by successive downward links until the traversal returns to $i$, which terminates the loop condition $p \ne i$.

A symmetric alternative is to begin at $\mathrm{ULINK}(i)$ and iterate upward by setting $p \leftarrow \mathrm{ULINK}(p)$ at each step. This visits the same set of nodes in reverse cyclic order, again terminating when the traversal returns to $i$.

More generally, any node $p_0$ in the vertical cycle of item $i$ may be chosen as the initial value of $p$, provided that subsequent updates follow a fixed direction, either $p \leftarrow \mathrm{DLINK}(p)$ or $p \leftarrow \mathrm{ULINK}(p)$. In all cases, the cycle structure guarantees that every node in the column is encountered exactly once before returning to $i$.

The correctness of (12) depends only on the fact that each node $p$ with $\mathrm{TOP}(p)=i$ is processed exactly once by $\mathrm{hide}(p)$, not on the particular cyclic ordering used to select these nodes. This completes the analysis. ∎