TAOCP 2.4 Exercise 4
Let rule (c) be the COBOL requirement that whenever two consecutive entries have level numbers $L_i$ and $L_{i+1}$, and $L_{i+1}>L_i$, the new level number must be the smallest level number that has a...
Section 2.4: Multilinked Structures
Exercise 4. [**] [26] Algorithm A does not detect the error if a COBOL programmer violates rule (c) stated in the text. How should Algorithm A be modified so that only data structures satisfying rule (c) will be accepted?
Verified: yes
Solve time: 2m27s
Let rule (c) be the COBOL requirement that whenever two consecutive entries have level numbers $L_i$ and $L_{i+1}$, and $L_{i+1}>L_i$, the new level number must be the smallest level number that has appeared since the preceding entry of level $<L_{i+1}$. Equivalently, level numbers may increase only to the next level currently available in the hierarchy; one may not skip intermediate levels.
Algorithm A constructs the tree by maintaining a stack of active ancestors. When a new item of level $L$ is read, the algorithm repeatedly pops the stack until the top item has level number $<L$; the new item is then attached as a child of that top item.
The defect is that Algorithm A checks only the ordering relation $<$. Hence it accepts a sequence such as
$$ 01\ A,\quad 05\ B,\quad 15\ C, $$
even though level $15$ is illegal here because no level between $5$ and $15$ has previously established such a descent in the hierarchy. The algorithm finds $5<15$ and therefore attaches $C$ beneath $B$, failing to detect the violation of rule (c).
To enforce rule (c), maintain in addition to the stack a table $P$ of level numbers that have already occurred. After the stack has been popped and before the new node of level $L$ is attached, let $K$ be the level number on the top of the stack. Thus $K<L$, and the new item would become a child of the node at level $K$.
Insert the following test:
Accept the descent from $K$ to $L$ only if there is no previously occurring level number $M$ such that
$$ K<M<L . $$
If such an $M$ exists, reject the structure.
After the test succeeds, enter $L$ into the table $P$ and continue exactly as in Algorithm A.
To prove correctness, first suppose rule (c) is violated. Then some item of level $L$ appears whose parent is at level $K<L$, but there exists an intermediate level number $M$ with
$$ K<M<L $$
that has already occurred earlier in the declaration sequence. The modified algorithm reaches the moment when the item of level $L$ is to be attached beneath level $K$. Since $M$ is recorded in $P$, the added test fails and the structure is rejected. Therefore every violation of rule (c) is detected.
Conversely, suppose the data structure satisfies rule (c). Whenever the algorithm is about to attach a node of level $L$ beneath a node of level $K$, rule (c) implies that no previously occurring level number lies strictly between $K$ and $L$. Hence the added test always succeeds. The remainder of Algorithm A is unchanged, so every valid COBOL data structure is accepted.
Therefore Algorithm A is made correct with respect to rule (c) by recording the level numbers already encountered and rejecting any descent from level $K$ to level $L$ for which a previously occurring level number lies strictly between $K$ and $L$. This modification rejects exactly the structures that violate rule (c). ∎