Next: rope API, Previous: guile-rope, Up: guile-rope [Contents][Index]
1 Introduction
This library implements immutable ropes for GNU Guile under the name ‘(data rope)’.
A rope is a data structure that represents text strings. It is useful for text editing, because text can be inserted at an arbitrary point without requiring the moving of a lot of data. In this chapter we describe how ropes work: how to balance them, and how to insert text.
Ropes are also described in H-J. Boehm, R. Atkinson, M. Plass. ‘Ropes: An Alternative to Strings’. https://doi.org/10.1002/spe.4380251203; this library is largely based on that article.
For example, a rope that represents the string ‘Will to power’ might look like this:
Figure 1.1: A rope with three leaves representing the string ‘Will to power’.
This representation is not unique. Another one with four leaves:
Figure 1.2: A rope with four leaves representing the same string.
Ropes are intended to represent entire text files. As one may imagine, some representations can get quite unwieldy, with the most extreme case that of the entire text being represented by a linked list of characters. In the above paper by Boehm et al (1995), the most important algorithm shared is that of balancing the rope. To explain the algorithm, we find it beneficial to first explain some other properties of ropes. The final two sections deal with the problem of inserting text in an immutable rope.