Someone I know is planning on implementing a text editor in the near future, which prompted me to think about what kind of data structures are fast for a text editor. The most used structures are apparently ropes or gap buffers.
Van Emde Boas trees are just about the fastest priority queues around, if you don't mind an upper bound on the number of items you can put into it and a large initialization cost. My question is whether there exists some data structure that is just as fast as the van Emde Boas tree, but supports text editor operations.
We only need to support up to $m$ characters in our data structure (so if $\log m = 32$, then we support up to 4GB worth of ASCII characters). We are allowed $\sqrt{m}$ time to initialize a new data structure. We'd like to support the following operations:
- Insert a character at position $i$ in $O(\log \log m)$ (and thereby increasing the position of every subsequent character by 1).
- Delete a character at position $i$ in $O(\log \log m)$.
- Return the character at position $i$ in $O(\log \log m)$.
So, insert(0,'a') followed by insert(0,'b') results in "ba".
Even better would be this:
- Return a 'pointer' to some index $i$ in $O(\log \log m)$.
- Given a 'pointer', return the character at this position in $O(1)$.
- Given a 'pointer', remove the character at this position in $O(1)$.
- Given a 'pointer', add a character at this position in $O(1)$ and return a pointer to the following position.
- (optional) Given a 'pointer', return a 'pointer' to the next/previous character in $O(1)$.
