# Re: Editing Text (#145)

**URL:** <https://www.ruby-forum.com/t/re-editing-text-145/229124>\
**Category:** Ruby\
**Created:** [November 5, 2007, 11:37pm UTC](https://www.ruby-forum.com/t/re-editing-text-145/229124 "2007-11-05T23:37:51Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [November 5, 2007, 11:37pm UTC](https://www.ruby-forum.com/t/re-editing-text-145/229124/1 "2007-11-05T23:37:51Z")

</div>

(I thought I had sent in my solution yesterday, but it didn’t send,  
since I didn’t realize that Yahoo now sometimes demands a CAPTCHA.)

I’ve been busy these past few weeks, and thus didn’t get around to this  
quiz until yesterday (Hurrah for the extension!). Even then, I only  
implemented the minimum (save for the inspect/to\_s method to make  
testing easier, which doesn’t count).

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.

The cursor should be thought to lie between two characters rather than  
on a character. Because of this, insertign 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.

All insertions and deletions should be O(n), where n is the length of  
the line. Moving the cursor should be O(1).

class ListNode  
attr\_accessor :prev,:nxt,:val

def initialize(prev=nil,nxt=nil,val="")  
@prev,@nxt,@val = prev,nxt,val  
end

def to\_a  
first = self  
first = first.prev while first.prev

```
arr = []
node = first
while node.nxt
  arr << node
  node = node.nxt
end
arr << node
arr

```

end  
end

###Partitions string into a linked list of lines  
###For all lines, the last character is guaranteed to be a newline  
###That includes the last, for simplicity’s sake

### 

###The cursor is between characters rather than on a character. Thus,  
inserting after  
###is the same as inserting before  
class LinkedListBuffer  
def initialize(str="")  
str \<\< “\n” unless str[-1,1] == “\n”  
list = str.scan(/[^\n]\*?\n/).map{|s| ListNode.new(nil,nil,s)}  
list.each\_with\_index do |node, idx|  
node.prev = list[idx-1] unless idx == 0  
node.nxt = list[idx+1]  
end  
@cur\_line = list.first  
@line\_idx = 0  
end

def at\_end?  
!@cur\_line.nxt and @line\_idx == @cur\_line.val.length-1  
end

def at\_begin?  
!@cur\_line.prev and @line\_idx == 0  
end

##The construct “”\<\<ch is used so that ch may be either a string or an  
integer

def insert(ch)  
unless “\n” == “” \<\< ch  
@cur\_line.val[@line\_idx,1] = “”\<\<ch\<\<@cur\_line.val[@line\_idx]  
else  
@cur\_line.val[@line\_idx,1] = “”\<\<ch\<\<@cur\_line.val[@line\_idx]  
line =  
ListNode.new(@cur\_line,@cur\_line.nxt,@cur\_line.val.slice!((@line\_idx+1)…-1))  
@cur\_line.nxt.prev = line if @cur\_line.nxt  
@cur\_line.nxt = line  
end  
end

def del\_after  
unless @cur\_line.val[@line\_idx] == ?\n or at\_end?  
@cur\_line.val.slice!(@line\_idx,1)  
else  
if at\_end?  
nil  
else  
@cur\_line.val[-1,1] = @cur\_line.nxt.val  
@cur\_line.nxt = @cur\_line.nxt.nxt  
“\n”  
end  
end  
end

def del\_before  
unless at\_begin?  
cursor\_left  
del\_after  
else  
nil  
end  
end

def cursor\_left  
if at\_begin?  
nil  
elsif @line\_idx == 0  
@cur\_line = @cur\_line.prev  
@line\_idx = @cur\_line.val.length-1  
“\n”  
else  
@line\_idx -= 1  
@cur\_line.val[@line\_idx,1]  
end  
end

def cursor\_right  
if at\_end?  
nil  
elsif @line\_idx + 1 == @cur\_line.val.length  
@line\_idx = 0  
@cur\_line = @cur\_line.nxt  
“\n”  
else  
@line\_idx += 1  
@cur\_line.val[@line\_idx-1,1]  
end  
end

def cursor\_up  
if @cur\_line.prev  
@cur\_line = @cur\_line.prev  
@line\_idx = [@line\_idx,@cur\_line.val.length-1].min  
else  
nil  
end  
end

def cursor\_down  
if @cur\_line.nxt  
@cur\_line = @cur\_line.nxt  
@line\_idx = [@line\_idx,@cur\_line.val.length-1].min  
else  
nil  
end  
end

def to\_s  
@cur\_line.val =  
@cur\_line.val[0…@line\_idx]+"|"+@cur\_line.val[@line\_idx…-1]  
str = @cur\_line.to\_a.map{|node| node.val}.join  
@cur\_line.val.slice!(@line\_idx)  
str  
end  
alias inspect to\_s  
end

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [November 6, 2007, 9:15pm UTC](https://www.ruby-forum.com/t/re-editing-text-145/229124/2 "2007-11-06T21:15:32Z")

</div>

On 11/5/07, James K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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