Devising an undo-capable data structure using a rope

Traditionally, a string is represented using an array of characters. To access it, you would have to sequentially traverse it, which is far from efficient, especially if the string gets long. Besides, such implementation relies on a mutable state; any update on the strings that are implemented as char arrays will necessarily destroy any older versions of them. This will leave us with no option, but to maintain the history through inefficient copying if we need to track the different versions of a particular long string, as text editors do, for instance.

A rope is an interesting alternative to character arrays as far as string representation is concerned. In addition to this, ropes are inherently persistent, that is, updating them is not destructive and stands as a very elegant solution for text editors, for instance, as they are able to handle very large texts and are able to still permit undo capability very easily. A rope is a binary...