October 24, 2017

Ropes? Gap Buffers? Just Use A String

There are numerous data structures for editing text. For instance, there’s a Rope, which allows for efficient insertion and deletion in a string by storing it as a tree. There’s also the Gap Buffer that allocates a block of space all at once when you start typing, since you’re likely to enter several characters without moving your cursor. In both cases, the original O(n) insert time is improved.

While all of these result in much faster editing than a string, they only address storing the string in memory — you still have to display the text on a screen, you still have to wrap lines. If a line gets too long, words move to the next line, pushing more words down and reflowing the entire paragraph. I’m sure there’s some esoteric optimization that can wrap lines faster, but a standard solution for proportional fonts requires looking at each character in the line — an O(n) operation. You can optimize it by caching the previous wrap and only re-wrapping after the inserted character, but it’s still O(n).

The text editor I’m building stores text as an array of lines. If wrapping a line is O(n), it doesn’t matter if insertions are faster into the stored data structure. To the user looking at the screen, it will still feel like O(n).