22
$\begingroup$

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)$.
$\endgroup$
14
$\begingroup$

Fredman and Saks show in "The cell probe complexity of dynamic data structures" that you cannot do better than $\Theta\left(\frac{\lg m}{\lg \lg m}\right)$ amortized time for the operations you are looking for. They call this problem "list representation".

Dietz presented a data structure in "Optimal Algorithms for List Indexing and Subset Rank" that achieves this bound.

$\endgroup$
  • $\begingroup$ Can you give a link for the first article? $\endgroup$ – Raphael Mar 23 '12 at 1:27
  • $\begingroup$ There is no free version that I am aware of. $\endgroup$ – jbapple Mar 23 '12 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.