TAOCP 1.4.4 Exercise 12

To modify the CONTROL coroutine for card input so that input terminates upon reading a card with a `".

taocpmathematicsalgorithmsvolume-1medium

Section 1.4.4: Input and Output

Exercise 12. [24] Suppose that the multiple buffering algorithm in the text is being used for card input, and suppose the input is to terminate as soon as a card with "." in column 80 has been read. Show how the CONTROL coroutine (Algorithm B and Program B) should be changed so that input is shut off in this way.

Verified: no
Solve time: -

Solution

To modify the CONTROL coroutine for card input so that input terminates upon reading a card with a "." in column 80, we must integrate an end-of-input check into the existing multiple-buffer input mechanism. The original CONTROL coroutine alternately assigns buffers for reading cards and manages the ASSIGN and RELEASE operations. Our goal is to detect the terminating card before passing its data to the main program, thereby preventing anticipated input beyond the final card.

Let the following notation and variables be retained from the original CONTROL coroutine:

  • BUF_i: the $i$th buffer available for card input.
  • ASSIGN(BUF_i): assign buffer BUF_i to the INPUT coroutine.
  • RELEASE(BUF_i): release buffer BUF_i after processing.
  • OUT BUF_i: pass buffer contents to the main program.
  • CARD: the current card being examined.
  • END_FLAG: a logical variable indicating that the terminating card has been read.

The modified algorithm proceeds as follows:

Step 1. Initialize all buffers and set END_FLAG ← false. Assign the first buffer to begin reading cards.

Step 2. Whenever a buffer becomes available for assignment:

  1. Check END_FLAG. If END_FLAG = true, do not assign this buffer for input; skip the ASSIGN operation.
  2. Otherwise, perform ASSIGN(BUF_i) to begin reading the next card into buffer BUF_i.

Step 3. After a buffer is filled (i.e., after the INPUT coroutine has read a card into BUF_i):

  1. Examine the last column of the card in the buffer: if column 80 contains ".", set END_FLAG ← true.
  2. Pass the buffer to the main program using OUT BUF_i.
  3. Release the buffer with RELEASE(BUF_i) after the main program has finished processing it.

Step 4. Continue alternating buffers as in the original multiple-buffer algorithm, but skip further assignments once END_FLAG = true. This ensures that anticipated input does not occur after the terminating card. The main program continues processing any remaining filled buffers until all assigned buffers have been released.

Step 5. Terminate the CONTROL coroutine when all buffers have been released and no further assignments are pending. At this point, the input process has concluded, and the last card containing "." in column 80 has been read and processed.

This modification ensures that multiple buffering and buffer swapping continue to function efficiently while providing a precise termination condition based on the sentinel character "." in column 80. No further changes to the underlying INPUT coroutine are required; only the CONTROL coroutine is augmented to detect the terminating card and inhibit subsequent buffer assignments.

This completes the proof.

∎