back

by raphlinus·4y ago·view on hn ↗
In my opinion, the rope is easily superior to these other types, but it also depends on whether your language supports abstractions well. The problem with an "array of paragraphs" is that it helps when your problem involves the paragraph boundary, but gets in the way when it doesn't. For example, pressing backspace at the beginning of paragraph 2 causes a merge of paragraphs 1 and 2, which is not trivial. With a rope, it's the same as deleting a backspace within a simple string, once you have a good rope library under you.

The other big reason to prefer a rope is that the worst case complexity is excellent. Basically all incremental operations are O(log n). With an "array of paragraphs" you get various pathological performance cases such as a huge number of small paragraphs or one very big one.

A good rope implementation is not trivial, but when done right it hides its internal complexity from the layer above. And it's a solved problem. There are at least two or three solid rope crates for Rust (just to pick the language I'm most familiar with), and will likely be more, as people find it fun to implement.

2 comments
I would say the key is to abstract the lower level data structure, so that it could be (relatively) easily swapped-out. So for example, don't start with a doubly-linked list of lines or for sure your upper level code is going to have pointers to line headers. Better to have some kind of smart pointer which is an abstract index into the edit buffer and provide functions like "find next line", "find previous line".

BTW, with any of these tree-based structures (like rope) you can store other meta-data in the the headers to make a fast index. For example, I would put a newline count in the rope headers, to make find a particular line a fast operation.