TAOCP 2.3.5 Exercise 10

Use the `REF` fields temporarily to record the correspondence between original nodes and copied nodes.

taocpmathematicsalgorithmsvolume-1

Section 2.3.5: Lists and Garbage Collection

Exercise 10. [**] [28] Design an algorithm that copies a List structure, assuming that an internal representation like that in (7) is being used. (Thus, if your procedure is asked to copy the List whose head is the node at the upper left corner of (7), a new set of Lists having 14 nodes, and with structure and information identical to that shown in (7), should be created.)

Assume that the List structure is stored in memory using S, T, REF, and RLINK fields as in (9), and that NODE(P0) is the head of the List to be copied. Assume further that the REF field in each List head node is \Lambda; to avoid the need for additional memory space, your copying procedure should make use of the REF fields (and reset them to \Lambda again afterwards).

Verified: yes
Solve time: 1m07s

Use the REF fields temporarily to record the correspondence between original nodes and copied nodes. First traverse the structure reachable from P_0. Whenever a node P is encountered for the first time, allocate a new node P'; copy the fields S, T, and RLINK from P into P'; then store the pointer to P' in REF(P). If P is a List head (T=0), continue recursively through the elements of that List. If P is a sub-List element (T=1), follow the pointer originally contained in REF(P) and continue recursively from the corresponding List head. If a node is encountered whose REF field is already nonnull, no new node is created; the value of REF already gives the copy of that node. After this pass every original node has a unique copy, and every original node P satisfies REF(P)=P', where P' is its copy.

Make a second traversal. For each original node P, let P'=\mathrm{REF}(P). If T(P)=1, the copied node must point to the copy of the same sub-List, so replace the pointer field of P' by \mathrm{REF}(Q)$, where $Q$ is the original List head referenced by P. If RLINK(P)=Q\ne\Lambda, replace RLINK(P')by\mathrm{REF}(Q); if RLINK(P)=\Lambda, leave it unchanged. Thus every pointer in the copied structure is redirected from an original node to the corresponding copied node. Finally make a third traversal of the original structure and set REF(P)\leftarrow\Lambdafor every List head, restoring the representation. The nodes reached from\mathrm{REF}(P_0)` before this restoration constitute a complete copy of the original List structure, with all sharing and circularities reproduced exactly. ∎