From: Ruby Quiz <james@...>
Date: 2007-10-26T22:03:20+09:00
Subject: [QUIZ] Editing Text (#145)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eric Mahurin

Have you ever wondered how a text buffer might be represented in a text editor
or word processor? A simple string to represent text buffer isn't efficient
enough because inserting (i.e. typing) and deleting (backspace) in the middle
would result in moving all of the text to the end for each operation. A data
structure that can efficiently insert and delete in the middle is needed.

The task is to implement data structures for efficiently editing text. One
common data structure is a gap buffer:

	http://en.wikipedia.org/wiki/Gap_buffer

Other options to consider include: ropes (see quiz #137), linked lists, simple
strings, or a multi-level combination of data structures (i.e. for lines vs.
characters in a line). There are many data structures that may work efficiently
with simple editing operations, but not all of those data structures will work
well for more complex functionality.

All of the basic operations occur around a text cursor. The minimal operations
on/at the cursor should be:

	* Insert a character before or after the cursor.
	* Delete a character before or after the cursor and return the
	  deleted character.
	* Move the cursor left or right (crossing line boundaries if
	  necessary) and return the character or nil at the beginning
	  or end of the buffer.
	* Move the cursor up or down a line and return nil/false only if a
	  line boundary could not be crossed.  The cursor may be placed in
	  the most natural column for the data structure.

Additional useful operations that you might find in a typical text editor can
also be added:

	* Get current line and column numbers
	* Copy some amount of text before or after the cursor and return  
	  this buffer.
	* Display some context around the cursor.
	* Cut some amount of text before or after the cursor and return
	  this buffer.
	* Paste a copy/cut buffer before or after the cursor.
	* Insert a file.
	* Write to a file.
	* Goto a specific line or column.
	* Goto the begin/end of the line/buffer.
	* Copy or cut to a specific line/column.
	* Filter some text through a ruby block.
	* Search (and possibly replace) using a regular expression.
	* Undo/redo.

Major bonus points for the following where gap buffers probably won't work:

	* Only store changes to a file.
	* Handle multiple efficient cursors in a text buffer.

Although the focus is on data structures and making the ruby DSL equivalent to
unix "ed" or DOS "edlin", a GUI could be added to make a full-screen/window text
editor.

Here is a benchmark for testing that needs the minimal implementation
(#insert_before, #insert_after, #delete_before, #delete_after, #left, #right,
#up, #down):

	# edit_test.rb
	# usage: ruby -r klass.rb edit_test.rb <iter> \
	#        [<constructor> [<lines> <columns>] ...]
	
	require 'benchmark'
	require 'test/unit/assertions'
	include Test::Unit::Assertions
	
	# char = byte pre 1.9, each_char already defined in 1.9
	unless "".respond_to?(:each_char)
	  class String;alias_method(:each_char, :each_byte);end
	end
	
	iterations = ARGV.shift.to_i
	
	while cursor = ARGV.shift
	  nlines = (ARGV.shift || 10000).to_i
	  ncolumns = (ARGV.shift || 100).to_i
	  n = nlines*ncolumns
	  chars = (?a..?z).to_a
	  line = (0...ncolumns).inject("") { |line, i|
	    line << chars[i%chars.length]
	  }
	  line[-1] = ?\n
	  
	  iterations.times { eval(cursor).instance_eval {
	    Benchmark.benchmark(
	      "#{cursor}: #{nlines}x#{ncolumns}\n",16,nil,"total"
	    ) { |b|
	      
	      total = b.report("insert_before") {
	        nlines.times { line.each_char { |ch| insert_before(ch) } }
	      }
	      i = 0
	      total += b.report("left") { i += 1 while left }
	      assert_equal(n, i)
	      i = 0
	      total += b.report("right") { i += 1 while right }
	      assert_equal(n, i)
	      i = 0
	      total += b.report("up") { i += 1 while up }
	      assert_equal(nlines, i)
	      i = 0
	      total += b.report("down") { i += 1 while down }
	      assert_equal(nlines, i)
	      total += b.report("insert_after") {
	        nlines.times { line.each_char { |ch| insert_after(ch) } }
	      }
	      i = 0
	      total += b.report("delete_before") {
	        i += 1 while delete_before
	      }
	      assert_equal(n, i)
	      i = 0
	      total += b.report("delete_after") {
	        i += 1 while delete_after
	      }
	      assert_equal(n, i)
	      
	      [total]
	        
	    }
	  } }
	end