[QUIZ] Editing Text (#145)
8 Message(s) by 6 Author(s) originally posted in ruby programming
| From: Ruby Quiz |
Date: Friday, October 26, 2007
|
The three rules of
Ruby Quiz:
1. Please don't 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 is not 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
line s vs.
char acters 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 couldn't 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
point s 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
| From: Todd Burch |
Date: Friday, October 26, 2007
|
wrote in message:
All of the basic operations occur around a text cursor. The minimal
operations
on/at the cursor should be:
James, thanks for putting all these challenges together, and thanks to
the contributors too.
Just a terminology thing - the proper term is "
caret ", not a "text
cursor".
Todd
--
Posted via
http://www.ruby-forum.com/.
| From: James Edward Gray II |
Date: Friday, October 26, 2007
|
| From: Todd Burch |
Date: Friday, October 26, 2007
|
wrote in message:
wrote in message:
While I probably would've called it a caret as well, the term
does not seem completely out of line:
Not out of line in the least. Without resorting to cheesey emoticons
(wink wink, smiley, grin, et al), mine was a passing comment. I am sure
no one got confused from your description.
Again, thanks.
--
Posted via
http://www.ruby-forum.com/.
| From: James Edward Gray II |
Date: Friday, October 26, 2007
|
wrote in message:
wrote in message:
wrote in message:
While I probably would've called it a caret as well, the term
does not seem completely out of line:
Not out of line in the least. Without resorting to cheesey emoticons
(wink wink, smiley, grin, et al), mine was a passing comment. I am
sure
no one got confused from your description.
Just to be clear, I did not
write that quiz. Eric Mahurin did.
James Edward Gray II
| From: Rick DeNatale |
Date: Friday, October 26, 2007
|
wrote in message:
wrote in message:
wrote in message:
All of the basic operations occur around a text cursor. The minimal
operations on/at the cursor should be:
> Just a terminology thing - the proper term is "caret", not a "text
> cursor".
While I probably would've called it a caret as well, the term
does not seem completely out of line:
http://en.wikipedia.org/wiki/Cursor
http://en.wikipedia.org/wiki/Cursor_%28computers%29
Actually, I'd say that caret is a UI/View related term (its the name
of the ^ character, traditionally used in blue-pencil editing to mark
a place to insert test.
Cursor is kind of both a view and a model term, and I think we're
talk ing about a model in this quiz.
That said, in general, when I have looked at similar code, the analogous
concept usually used is a selection, which represents a contiguous run
of zero or more characters within the buffer. The quiz seems to be
using a degenerate
version of this where the length is constrained to
be zero.--
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/
| From: Joel VanderWerf |
Date: Friday, October 26, 2007
|
wrote in message:
wrote in message:
All of the basic operations occur around a text cursor. The minimal
operations
on/at the cursor should be:
James, thanks for putting all these challenges together, and thanks to
the contributors too.
Just a terminology thing - the proper term is "caret", not a "text
cursor".
Todd
When the
Macintosh first came out, the little blinking vertical
bar in
text editors was called the insertion point or caret, but, because of
its shape, it was also called the "stick".
It does not matter whether you see it as a caret or a stick, as long as
it provides sufficient motivation for the Quiz. ;) ;) ;)
--
vjoel : Joel VanderWerf :
path berkeley
edu : 510 665 3407
| From: Eric Mahurin |
Date: Saturday, October 27, 2007
|
wrote in message:
wrote in message:
wrote in message:
>
wrote in message:
> All of the basic operations occur around a text cursor. The minimal
> operations on/at the cursor should be:
>
> > Just a terminology thing - the proper term is "caret", not a "text
> > cursor".
>
> While I probably would've called it a caret as well, the term
> does not seem completely out of line:
>
>
http://en.wikipedia.org/wiki/Cursor
>
>
http://en.wikipedia.org/wiki/Cursor_%28computers%29
Actually, I'd say that caret is a UI/View related term (its the name
of the ^ character, traditionally used in blue-pencil editing to mark
a place to insert test.
Cursor is kind of both a view and a model term, and I think we're
talking about a model in this quiz.
Correct. I have also seen the term cursor being used with databases
(pointer to what
row is being operated on). It has also been used to
mean the same as what rubyists call an "external iterator" (ruby
mainly uses "internal iterators" or what others might call visitors).
Before mice came on the scene the symbol representing the text
insertion point was also called a "cursor". I did not realize that
"cursor" is now mainly used for the mouse now and the text cursor has
been demoted to "caret". I usually just say "mouse pointer" and "text
cursor". According to how the term "cursor" is used in data
structures, I think the text cursor/caret deserves to use this term
more than a mouse pointer/cursor does.
That said, in general, when I have looked at similar code, the analogous
concept usually used is a selection, which represents a contiguous run
of zero or more characters within the buffer. The quiz seems to be
using a degenerate version of this where the length is constrained to
be zero.
Do not let the test in this quiz stop you. I just provided a benchmark
for the simple stuff.
Feel free to implement other text editor
operations in addition to the simple operations that the benchmark
uses. And do not let the benchmark restrict your API. If the model
that the benchmark assumes does not match your model (i.e. a selection
in your case?), change the benchmark test to what you need. Also,
achieving the best absolute performance on this benchmark is not
necessarily the most important, but you should get reasonable big-O
performance. I'd like to see what data structures some of you come up
with and how far you can take them in terms of functionality. I think
there are lots of solutions with a variety of data structures.
Have fun!
Eric
Blogs related to [QUIZ] Editing Text (#145)
International site. Check it now for a lot of offers.
prostate seeding procedure writing supplies for inmates. mafia y crimen represivo stella rae sneddon peploe english and spanish words spelled the same Osama bin-laden big photo. zachary spencer 48867. marley
ruby usb windows boot
...
sitemap
Don’t spend money on software; Download Free GPS Mapping Software; Download free video
editing software at Videothang.com; Download More Free GPS Software - Continued; Download software updates, patches, and upgrades with UpdateStar
...
Ksbe
Ksbe Source: www.ksbe.state.ks.us Highly Gifted Children Links to resources for parents of highly gifted students Highly gifted children are generally those who have IQ scores of
145 and candle highly scented votive above (Sayer,
...
Editing Text (#145)
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.
...