From: Holger <hmack.gm@...>
Date: 2007-10-31T02:48:46+09:00
Subject: Re: [QUIZ] Editing Text (#145)

------=_Part_2163_31291114.1193766520716
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

First attempt
- plain gap buffer implementation without much optimization
- only basic operations
- O(n)

Regards
Holger




# Solution to ruby quiz #145
# http://www.rubyquiz.com/quiz145.html
# by Holger
#
# GapBuffer works similar to StringCaret
#
# Some remarks:
# - if gap size is zero before insert it will be set to 64
# - data buffer will never shrink -> gap might be very large
# - lazy up and down methods, but cursor remains in same column (if fits in
line)


class GapBuffer
  # data is in @data
  # gap starts @gap_start
  # gap ends @gap_start + @gap_len

  def initialize(data="", i=0)
    @data = data
    @gap_start = i
    @gap_len = 0
    @GAP = " "*64
  end

  def insert_before(ch)
    if @gap_len.zero?
      @data[@gap_start, 0] = @GAP
      @gap_len = @GAP.length
    end
    @data[@gap_start] = ch
    @gap_start += 1
    @gap_len -= 1
  end

  def insert_after(ch)
    if @gap_len.zero?
      @data[@gap_start, 0] = @GAP
      @gap_len = @GAP.length
    end
    @data[@gap_start+@gap_len-1] = ch
    @gap_len -= 1
  end

  def delete_before
    return if @gap_start.zero?
    @gap_start -= 1
    @gap_len += 1
    @data[@gap_start]
  end

  def delete_after
    return if @gap_start+@gap_len >= @data.length
    @gap_len += 1
    @data[@gap_start+@gap_len-1]
  end

  def left
    return if @gap_start.zero?
    @data[@gap_start+@gap_len-1] = @data[@gap_start-1]
    @gap_start -= 1
    @data[@gap_start]
  end

  def right
    return if @gap_start+@gap_len>=@data.length
    @data[@gap_start] = @data[@gap_start + @gap_len]
    @gap_start += 1
    @data[@gap_start - 1]
  end

  def up
    col = column
    cursor = @gap_start-col
    return if cursor.zero?
    cursor_line = @data.rindex(?\n, cursor-2)
    cursor_line = 0 if cursor_line.nil?
    cursor_line += col+1
    if cursor_line > cursor-1
      cursor_line = cursor-1
    end
    left while @gap_start > cursor_line
    true
  end

  def down
    col = column
    cursor = @data.index(?\n, @gap_start + @gap_len)
    return if cursor.nil?
    cursor_line = cursor+1+col
    cursor = @data.index(?\n, cursor+1)
    cursor = @data.length if cursor.nil?
    cursor_line = cursor if cursor_line > cursor
    right while @gap_start + @gap_len < cursor_line
    true
  end

  def position
    @gap_start
  end

  def column
    lbreak = @data.rindex(?\n, @gap_start-1)
    lbreak.nil? ? @gap_start : (@gap_start-(lbreak+1))
  end

  def to_s
    return @data[0, @gap_start]+@data[@gap_start+@gap_len, @data.length-@gap
_start-@gap_len]
  end
end






GapBuffer.new: 1000x100
insert_before     0.266000   0.000000   0.266000 (  0.266000)
left              0.328000   0.000000   0.328000 (  0.328000)
right             0.406000   0.000000   0.406000 (  0.407000)
up                0.375000   0.000000   0.375000 (  0.375000)
down              0.422000   0.000000   0.422000 (  0.421000)
insert_after      0.391000   0.000000   0.391000 (  0.391000)
delete_before     0.234000   0.000000   0.234000 (  0.234000)
delete_after      0.313000   0.000000   0.313000 (  0.313000)
total             2.735000   0.000000   2.735000 (  2.735000)
GapBuffer.new: 2000x100
insert_before     0.547000   0.000000   0.547000 (  0.547000)
left              0.672000   0.000000   0.672000 (  0.671000)
right             0.796000   0.000000   0.796000 (  0.797000)
up                0.735000   0.000000   0.735000 (  0.735000)
down              0.875000   0.000000   0.875000 (  0.875000)
insert_after      0.797000   0.000000   0.797000 (  0.796000)
delete_before     0.468000   0.000000   0.468000 (  0.469000)
delete_after      0.610000   0.000000   0.610000 (  0.609000)
total             5.500000   0.000000   5.500000 (  5.499000)
GapBuffer.new: 3000x100
insert_before     0.890000   0.000000   0.890000 (  0.891000)
left              1.016000   0.000000   1.016000 (  1.015000)
right             1.188000   0.000000   1.188000 (  1.188000)
up                1.140000   0.000000   1.140000 (  1.140000)
down              1.360000   0.000000   1.360000 (  1.360000)
insert_after      1.156000   0.016000   1.172000 (  1.171000)
delete_before     0.797000   0.000000   0.797000 (  0.813000)
delete_after      0.953000   0.000000   0.953000 (  0.953000)
total             8.500000   0.016000   8.516000 (  8.531000)

------=_Part_2163_31291114.1193766520716--