I am developing a rope data structure in Swift. A rope is a balanced
binary tree representation for a string that makes operations like
"insert," "delete," and "substring" scale to very large strings. Each
internal node represents the concatenation of the strings in its
subnodes. In my implementation, every leaf is a String.
In a rope, integer indices are used to address individual characters
and ranges of characters. Internal nodes are labeled with the length
of their left subtree, and methods like character(at:) or substring(_)
steer their search by comparing the length at each node with the target
I'm trying to come up with Swift-y integer indices for my rope
structure. My first impulse was to use String.IndexDistance as my rope
index. However, to index a character within a leaf, I have to convert
from String.IndexDistance to String.Index using index(_:offsetBy:).
That has O(k) complexity, which is not suitable for my purposes.
To avoid the O(k) complexity, it looks to me like I need to use an index
on a view that conforms to RandomAccessCollection. In Swift 4.2 and
earlier, the sole random-access view is .unicodeScalars. (I am frankly
surprised that it is not .utf16.) I have surmised that the preferred,
random-access view in Swift 5 may be .utf8. Maybe someone can tell me
if I am on the right track here?
 Hans-J. Boehm, Russ Atkinson, and Michael Plass. "Ropes: an
Alternative to Strings." Software—Practice and Experience,
vol. 25, no. 12, December 1995, pp. 1315-1330.