I need to create a specialized text editor capable of handling text up to billions of characters long, with no line breaks.
I've read of multiple data structures to manage the text itself, including ropes, zippers, piece tables, gap buffers, and more.
However, I also need to support annotations on the text. Like comments in MS Word, each annotation lies over a range of positions. (Unlike MS Word comments, each annotation may lie over multiple non-intersecting ranges.)
Annotations can cover a single character or the whole text. Annotations may be created before, in between, or after text edits.
There can be tens to hundreds of thousands of annotations. Reacting to each edit by adjusting the coordinates of every single feature would incur a large, linear cost.
What are data structures that would support the following, even as coordinates change due to text editing, whose complexity does not include the number of annotations as a factor?
- Finding the coordinates of features discovered by text search, in the current coordinate system resulting from text edits made after the annotations.
- Finding annotations that intersect a range presented to the user, in the current coordinate system resulting from text edits made after the annotations.
For 1, one idea I've had is to store a history of coordinate-system changes, and apply all of those made after the feature's creation. However, the cost of this grows linearly with the number of edits.
For 2, one idea I've had is to create a custom R-tree of annotations which reacts to text edits by modifying its own coordinate system but not its clustering. But not sure how to handle new features, which don't necessarily lie anywhere in the original coordinate system. And again, the cost of this could grow linearly with the number of edits.