Glad to see this here. This is was my original thought too as one of the original data structures for text editing. It's used to quickly insert/delete within a very large string.
Has anyone used other mechanisms for large document types? It seems like an array of paragraphs, each containing a simple string could probably handle most editing tasks and might be easier to layout and manage. Curious what other data structures people have used!
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.
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.
I used a double-linked list of gap buffers (each in its own fixed length block that can swapped out to disk) for JOE. It works great on large files, but still I would start with rope these days.
Gap buffer was appealing on really slow machines, where you are counting cycles on each key-press. If the gap is at the right position, the cycle count is very low. But you can probably do the same even with a tree-structure: you need to keep a pointer to the leaf in the abstract pointer used for the cursor.
Also I would tie in the undo system to the data structure if possible. Rope does this with copy-on-write. Every version of the file could be a different top-node, and most middle and leaf nodes would be shared between revisions.
Comments
Glad to see this here. This is was my original thought too as one of the original data structures for text editing. It's used to quickly insert/delete within a very large string.
Has anyone used other mechanisms for large document types? It seems like an array of paragraphs, each containing a simple string could probably handle most editing tasks and might be easier to layout and manage. Curious what other data structures people have used!
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.
I'll plug your (awesome) blog for you:
https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.h...
Which points to https://xi-editor.io/docs/rope_science_00.html
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.
I used a double-linked list of gap buffers (each in its own fixed length block that can swapped out to disk) for JOE. It works great on large files, but still I would start with rope these days.
Gap buffer was appealing on really slow machines, where you are counting cycles on each key-press. If the gap is at the right position, the cycle count is very low. But you can probably do the same even with a tree-structure: you need to keep a pointer to the leaf in the abstract pointer used for the cursor.
Also I would tie in the undo system to the data structure if possible. Rope does this with copy-on-write. Every version of the file could be a different top-node, and most middle and leaf nodes would be shared between revisions.