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 ...

Get Elements of Programming now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.