From: James Koppel <jamesbkoppel@...>
Date: 2007-11-06T07:24:53+09:00
Subject: Re: [QUIZ] Editing Text (#145)

(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


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com