Elements of Programming

Chapter 8

Coordinates with Mutable Successors

This chapter introduces iterator and coordinate structure concepts that allow relinking:modifying successor or other traversal functions for a particular coordinate. Relinking allows us to implement rearrangements, such as sorting, that preserve the value of source at a coordinate. We introduce relinking machines that preserve certain structural properties of the coordinates. We conclude with a machine allowing certain traversals of a tree without the use of a stack or predecessor links, by temporarily relinking the coordinates during the traversal.

8.1 Linked Iterators

In Chapter 6 we viewed the successor of a given iterator as immutable: Applying successor to a particular iterator value always returns ...