Eric Mahurin
11/6/2007 8:14:00 PM
On 11/5/07, James Koppel <jamesbkoppel@yahoo.com> wrote:
> My solution uses a doubly-linked list of lines. Each line is guaranteed to be terminated by a newline; each newline is guaranteed to terminate a line. This means that strings that don't end in a newline will have one added.
I'm glad to see a linked-list solution. Another approach to use is to
leave the newlines out of the "lines". Newlines would be implied to
be between them (no implied newline after the last line).
> The cursor should be thought to lie between two characters rather than on a character. Because of this, inserting before and after is the same. The cursor is represented by the node containing the line that the cursor is on, and the index of the character to the right of the cursor.
Actually, they are different. Both insert the character at the same
point in the text. The difference is the final position of the
cursor/caret. insert_after is not a normal editor operation though.
It is equivalent to typing right-to-left instead of left-to-right
(what insert_before does). Since insert_after isn't a common
operation, and it can be done using insert_before followed by left, it
isn't needed. The main reason I threw it in was symmetry.
> All insertions and deletions should be O(n), where n is the length of the line. Moving the cursor should be O(1).
You could make it completely O(1) by using something like a gap buffer
for a line (or while editing one). But, it may not matter too much as
long as the line size is small enough (ruby overhead may dominate the
O(n) C code).
Also, the API given in the quiz was really only meant to be a
suggestion. Your implementation is probably better off taking a
string instead of a character to insert.
Eric