From: Matthew Moss <matthew.moss.coder@...>
Date: 2007-11-06T13:39:36+09:00
Subject: Re: [QUIZ] Editing Text (#145)

My solution is a deque... The text before the cursor is kept
left-to-right, while the part after the cursor is reversed. This makes
for some very simple code for the basic operations, using mostly
push/pop. It might be worthwhile to not reverse the data, and make the
code slightly more assymetric by combining the push/pop with
unshift/shift. (Didn't try that, though...)

Initially, the "left" method was @post.push(@prev.pop), with the
"right" method similar. This proved to be terribly slow, so I kept a
"temporary" cursor that would collapse multiple left/right operations
into a single "sift" (i.e. moving n chars from one to the other). The
"sync" calls ensure that we do that sift before other operations.

The most complex methods (and slowest) here are "up" and "down".
Breaking the internals down into multiple lines rather than just the
@prev/@post pair, or somehow keeping track of the newlines would help
with the speed of up/down, but I got lazy.  =)


class DequeBuffer
	def initialize(data = "", i = 0)
		@prev, @post = data[0, i].unpack("c*"), data[i..-1].unpack("c*").reverse
		@curs = 0
	end

	def insert_before(ch)
		sync
		@prev.push(ch)
	end

	def insert_after(ch)
		sync
		@post.push(ch)
	end

	def delete_before
		sync
		@prev.pop
	end

	def delete_after
		sync
		@post.pop
	end

	def left
		@curs -= 1 if @curs > -@prev.length
	end

	def right
		@curs += 1 if @curs <  @post.length
	end
	
	def up
		sync
		c = @prev.rindex(?\n)
		if c
			c -= @prev.length
			sift(c)					# move to end of prev line
			d = (@prev.rindex(?\n) || -1) - @prev.length - c
			sift(d) if d < 0		# move to column
			true
		end
	end

	def down
		sync
		c = @post.rindex(?\n)
		if c
			c -= @post.length
			sift(-c)					# move to start of next line
			d = (@post.rindex(?\n) || -1) - @post.length - c
			sift(-d) if d < 0		# move to column
			true
		end
	end

	def to_s
		(@prev + @post.reverse).pack("c*")
	end

	private

	def sift(n)
		if n < 0
			@post.concat(@prev.slice!( n, -n).reverse)
		elsif n > 0
			@prev.concat(@post.slice!(-n,  n).reverse)
		end
	end

	def sync
		sift(@curs)
		@curs = 0
	end
end


Running the test using simple string solution as comparison:

ruby -r deque.rb edit_test.rb 1 Simple.new 2000 100 DequeBuffer.new 2000 100
Simple.new: 2000x100
insert_before     0.890000   0.000000   0.890000 (  0.889501)
left              0.170000   0.000000   0.170000 (  0.173849)
right             0.190000   0.000000   0.190000 (  0.184943)
up                0.200000   0.000000   0.200000 (  0.204166)
down              0.210000   0.000000   0.210000 (  0.205926)
insert_after      4.790000   0.010000   4.800000 (  4.802009)
delete_before     3.480000   0.000000   3.480000 (  3.484238)
delete_after      1.760000   0.010000   1.770000 (  1.764394)
total            11.690000   0.020000  11.710000 ( 11.709026)
DequeBuffer.new: 2000x100
insert_before     0.280000   0.000000   0.280000 (  0.285044)
left              0.180000   0.000000   0.180000 (  0.182072)
right             0.160000   0.000000   0.160000 (  0.160996)
up                1.530000   1.850000   3.380000 (  3.373222)
down              0.780000   0.920000   1.700000 (  1.714187)
insert_after      0.290000   0.000000   0.290000 (  0.285273)
delete_before     0.250000   0.000000   0.250000 (  0.251946)
delete_after      0.250000   0.000000   0.250000 (  0.257460)
total             3.720000   2.770000   6.490000 (  6.510201)