The three rules of Ruby Q.:
-
Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message. -
Support Ruby Q. by submitting ideas as often as you can:
- Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
by Eric M.
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:
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 \
[ [ ] …]
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
