Problem Detail: 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)$.
Asked By : Alex ten Brink
Answered By : jbapple
Fredman and Saks show in “The cell probe complexity of dynamic data structures” that you cannot do better than $Thetaleft(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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/154
