1.5 Insertions in immutable ropes

To manipulate the leaf of an immutable rope, we have to reconstruct parts of the rope. The description that follows is a standard technique for modifying immutable trees, and hopefully it is not shrouded in too much mathematical jargon. The leaves of the rope bijectively correspond to maximal paths in the rope, i.e. paths from the root down to that given leaf. Assume we have such a path ν₀⟶ν₁⟶…⟶ν_k of length k where the first node is root and the last is leaf. We intend to modify the contents of ν_k, and as a result, every node in that chain must be modified in reverse order: first we allocate a new ν'_k, then a new ν'_k-1 that will point to ν'_k and so on until we reach a new root ν'₀. Note that precisely k allocations have taken place and no more. In balanced ropes, k ≈ log₂(n) where n is the number of internal nodes of the rope, and so thankfully only logarithmically many modifications need to be performed.

To perform these manipulations what we need is, given an index, to be able to find the leaf ν_k matching the index, and its entire sequence ν_k, ν_k-1, …, ν₀ of nodes of the maximal path in reverse order. There is already a data structure that contains all that information: it is the graph with the same structure as the rope, but whose arrows are reversed. In mathematical lingo, this graph is called the transpose graph of the rope.²

The following data structure is devised to accomodate our needs:

(define-immutable-record-type <rope-transpose>
  (rope-transpose node parent right-child?)
  rope-transpose?
  (node      rope-transpose-node set-rope-transpose-node)
  (parent    rope-transpose-parent)
  ;; Is node a left child or right child of parent?
  (right-child? rope-transpose-right-child?))

We define a rope transpose API to go along with this record. This sister API of the rope API is aiding us in manipulating ropes. For example, we can define a cursor for a rope using this API. We can walk the rope tree forward or backward, and we can manipulate leaves. Although many of the details are abstracted away using eager comprehensions, it is still exported for any low-level requirements.

To summarize, a <rope-transpose> value is a maneuverable pointer to a rope node, useful for manipulating ropes themselves.