Peter Hancock wrote:
[snip]
> To improve performance, I thought one can represent line structure. I
> think that the original editor just represented the text by a
> character sequence with a cursor, where \n was among the characters.
> Here one could have a line sequence with a cursor, and a character
> sequence with a cursor for the current line. So the state would be
> something like
>
> lbef : [ String ] -- complete lines before the cursor
> cbef : String -- characters before cursor in current line
> caft : String
> laft : [ String ] -- complete lines after cursor.
[snip]
You need random access into the strings, or else how am I going to search
for all occurrences of "wombat" in columns 50-59, or how indeed is the
Boyer-Moore algorithm going to be implemented? The obvious solution, which
will be quite efficient for everyone except loonies, computers being as fast
as they are these days, would be to keep every line in a packed string.
Supposing though users are going to be silly enough to edit files with
lines millions of characters long, I propose that the editor divide
lines into chunks of (say) between 100-200 characters each. (This constraint
would be enforced by splitting and recombining as necessary.) These
chunks would be stored in a balanced tree, where each node contains the
total length of its children.
