R
Ruby Quiz
Implementing an efficient data structure for this problem can be tricky. A
couple of the solutions turned out to have a higher complexity than it first
appeared. That doesn't mean they aren't valuable to examine though.
Let's have a look at Holger's code below. It's an implementation of the
quiz-recommended gap buffer data structure. It's a very clean implementation of
the idea that helped me understand what a gap buffer really is. Here's the
constructor:
class GapBuffer
def initialize(data="", i=0)
@data = data
@gap_start = i
@gap_len = 0
@GAP = " "*64
end
# ...
The actual content of our text editing session will be kept in @data. However,
that data may contain some extra material called a "gap," which will begin at
the index @gap_start and be @gap_len characters long. @GAP is just a constant
used to insert new gaps when that last one is exhausted.
How this interacts in usage is well shown by the insert methods:
# ...
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
# ...
The idea for both of these methods is simple. To add content, we place it in
either end of the gap, shrinking the space available there. To insert a
character before the caret we must add the character to the beginning of the
gap, bump the gap start index beyond the new character, and decrease our count
of available space in the gap. Adding after the caret just means placing the
character at the end and decreasing the length counter.
The if statement at the beginning of both of these methods watches for the gap
to be exhausted. When we run out of space, a new gap is inserted and our length
counter is reset.
Deleting characters is just the opposite operation:
# ...
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
# ...
To remove something all we really have to do is to manipulate our index and/or
length to put the discarded character back into the gap. Once there, later
operations can overwrite it normally.
Note that the last lines of these methods return the "deleted" character and the
first lines skip the operations when there are no characters beyond the gap.
Now the harder operations of a gap buffer are moving the caret. We'll start
with left() and right(), which are the easier moves:
# ...
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>[email protected]
@data[@gap_start] = @data[@gap_start + @gap_len]
@gap_start += 1
@data[@gap_start - 1]
end
# ...
Moving the caret to either side means transferring a character from one end of
the buffer to the other. Then we can just expand the gap to include the moved
character's previous location, so future editing operations will swallow in up.
For example, given the following data:
The gap buffer[ ], or our caret, is shown here with brackets.
A move to the left() is gives us:
The gap buffe[r ]r, or our caret, is shown here with brackets.
The moved character is on the right of the buffer while the original is inside.
Characters inside the buffer don't really exist in the content so we don't have
any duplication here.
Now for the hard moves:
# ...
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
# ...
While this looks like a lot of code, the procedure is simple.
The column() helper method, which we will see shortly, figures out where we are
in the current line. For the down() method, that's really all we need to mark
our current location. When moving up() though, we want to reach the line before
ours, or somewhere between one and two newlines back. To make that easier, up()
first backs up by the column count to start the search from the beginning of the
line.
Then we have a terrific use index()/rindex() with the optional minimum index
parameter to find the next newline past the end of the gap buffer. When that
search fails, the caret is moved to the beginning or end of the data which must
be the last line we needed to cross. Having found the desired line, the current
column is added on, and trimmed to match the data if it exceeds the line.
Together, these operations give us a where we are and where we need to get to.
The actual move is performed with repeated calls to left()/right(), one for each
character we need to travel.
Here are a couple of location methods, one of which we just saw in use:
# ...
def position
@gap_start
end
def column
lbreak = @data.rindex(?\n, @gap_start-1)
lbreak.nil? ? @gap_start : (@gap_start-(lbreak+1))
end
# ...
As you can see, position() is just an alias for @gap_start. The column() method
though is just more clever use of the rindex() method. It really works just
like we saw in up(), save that it doesn't need to skip over a newline.
The last operation supported by this solution is to stringify the data:
# ...
def to_s
return @data[0, @gap_start] +
@data[@gap_start+@gap_len, @data.length-@gap_start-@gap_len]
end
end
The actual data is just the concatenation of what's on both sides of the gap.
The code above assembles that with simple indexing.
Holger had hoped the solution was O(n), but unfortunately it turns out to be
O(n**2). Eric explains why this is and provides tips for how to get it to O(n)
in this email:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/277308
While the code does need the mentioned changes to reduce its complexity, I still
felt it was a very clean implementation of the gap buffer and quite easy to
follow. This should make fixing it up a snap.
My thanks to those who did manage to find the time for the quiz. It was a
tricky problem to do well and all of the solutions showed off neat approaches.
Tomorrow we will do some vehicle counting, programmer style...
couple of the solutions turned out to have a higher complexity than it first
appeared. That doesn't mean they aren't valuable to examine though.
Let's have a look at Holger's code below. It's an implementation of the
quiz-recommended gap buffer data structure. It's a very clean implementation of
the idea that helped me understand what a gap buffer really is. Here's the
constructor:
class GapBuffer
def initialize(data="", i=0)
@data = data
@gap_start = i
@gap_len = 0
@GAP = " "*64
end
# ...
The actual content of our text editing session will be kept in @data. However,
that data may contain some extra material called a "gap," which will begin at
the index @gap_start and be @gap_len characters long. @GAP is just a constant
used to insert new gaps when that last one is exhausted.
How this interacts in usage is well shown by the insert methods:
# ...
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
# ...
The idea for both of these methods is simple. To add content, we place it in
either end of the gap, shrinking the space available there. To insert a
character before the caret we must add the character to the beginning of the
gap, bump the gap start index beyond the new character, and decrease our count
of available space in the gap. Adding after the caret just means placing the
character at the end and decreasing the length counter.
The if statement at the beginning of both of these methods watches for the gap
to be exhausted. When we run out of space, a new gap is inserted and our length
counter is reset.
Deleting characters is just the opposite operation:
# ...
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
# ...
To remove something all we really have to do is to manipulate our index and/or
length to put the discarded character back into the gap. Once there, later
operations can overwrite it normally.
Note that the last lines of these methods return the "deleted" character and the
first lines skip the operations when there are no characters beyond the gap.
Now the harder operations of a gap buffer are moving the caret. We'll start
with left() and right(), which are the easier moves:
# ...
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>[email protected]
@data[@gap_start] = @data[@gap_start + @gap_len]
@gap_start += 1
@data[@gap_start - 1]
end
# ...
Moving the caret to either side means transferring a character from one end of
the buffer to the other. Then we can just expand the gap to include the moved
character's previous location, so future editing operations will swallow in up.
For example, given the following data:
The gap buffer[ ], or our caret, is shown here with brackets.
A move to the left() is gives us:
The gap buffe[r ]r, or our caret, is shown here with brackets.
The moved character is on the right of the buffer while the original is inside.
Characters inside the buffer don't really exist in the content so we don't have
any duplication here.
Now for the hard moves:
# ...
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
# ...
While this looks like a lot of code, the procedure is simple.
The column() helper method, which we will see shortly, figures out where we are
in the current line. For the down() method, that's really all we need to mark
our current location. When moving up() though, we want to reach the line before
ours, or somewhere between one and two newlines back. To make that easier, up()
first backs up by the column count to start the search from the beginning of the
line.
Then we have a terrific use index()/rindex() with the optional minimum index
parameter to find the next newline past the end of the gap buffer. When that
search fails, the caret is moved to the beginning or end of the data which must
be the last line we needed to cross. Having found the desired line, the current
column is added on, and trimmed to match the data if it exceeds the line.
Together, these operations give us a where we are and where we need to get to.
The actual move is performed with repeated calls to left()/right(), one for each
character we need to travel.
Here are a couple of location methods, one of which we just saw in use:
# ...
def position
@gap_start
end
def column
lbreak = @data.rindex(?\n, @gap_start-1)
lbreak.nil? ? @gap_start : (@gap_start-(lbreak+1))
end
# ...
As you can see, position() is just an alias for @gap_start. The column() method
though is just more clever use of the rindex() method. It really works just
like we saw in up(), save that it doesn't need to skip over a newline.
The last operation supported by this solution is to stringify the data:
# ...
def to_s
return @data[0, @gap_start] +
@data[@gap_start+@gap_len, @data.length-@gap_start-@gap_len]
end
end
The actual data is just the concatenation of what's on both sides of the gap.
The code above assembles that with simple indexing.
Holger had hoped the solution was O(n), but unfortunately it turns out to be
O(n**2). Eric explains why this is and provides tips for how to get it to O(n)
in this email:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/277308
While the code does need the mentioned changes to reduce its complexity, I still
felt it was a very clean implementation of the gap buffer and quite easy to
follow. This should make fixing it up a snap.
My thanks to those who did manage to find the time for the quiz. It was a
tricky problem to do well and all of the solutions showed off neat approaches.
Tomorrow we will do some vehicle counting, programmer style...