[QUIZ] Port a Library (#64)

[Ruby Quiz]

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.

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

Twice this week, I've gone looking for the Ruby equivalent to a simple Perl
module and had trouble finding what I was after. Both times I've peeked inside
the source and been surprised at how trivial the operations are. "I could port
that in no time," I thought. This quiz is my thinly disguised attempt to pass
my homework on to others.

Seriously, this quiz is *not* intended to be a lot of work. Don't underestimate
the power of a simple library. (See the "Rethinking Memoization" thread where
we are trying to improve a very helpful library that is literally 10 lines of
code, in one of the forms presented.)

Given all that, this is a build-it-yourself Ruby Quiz. Most of us are familiar
with another language. Go into their libraries and find something you like,
that is also simple, and port the library to Ruby. (You might want to search
the RAA and RubyForge first, just to make sure someone hasn't done similar work
already.) If a library is over 200 lines, forget it. This one is for the
little guys!

If you'll allow a brief aside here, it can be interesting to consider what the
word "port" means. Obviously, the goal of this is to build a library that does
the same things for Ruby. Don't think that means you should copy every method,
verbatim though. If you don't think a method is needed, leave it out. See a
better way to do something, use your way. Most important though, remember to
Rubyize the interface. It's fine to port your favorite Java library, but Ruby
programmers don't want to call methodsNamedLikeThis(). Watch for chances to use
blocks and jump on them *when they lead to a better experience*. Just remember
the adage, "If it ain't broke, don't fix it."

A few more details: Please tell us what your library does and show an example
of simple usage in your submission email. Be kind to your quiz summarizer.
Also, please credit the original library and author who worked so hard to give
you something cool to play with!

Now, if you have no idea what to port, here are two suggestions. (Please feel
free to post other suggestions to Ruby Talk. These are *not* spoilers!)

File::ReadBackwards

This is a Perl module (by Uri Guttman) for reading a file in reverse,
line-by-line. This can often be helpful for things like log files, where the
interesting information is usually at the end.

Don't worry about the Perl interface on this one, copy Ruby's File instead.
Heck, all I really want is a foreach() iterator. Anything else is extra.

This module is so well commented, you should be able to understand how it works,
even if you aren't familiar with Perl. Here's a link straight to the source:

http://search.cpan.org/src/URI/File-ReadBackwards-1.04/ReadBackwards.pm

WWW::RobotRules

This is another Perl module (by Gisle Aas) and it is actually over the 200 line
limit. Trust me though, it doesn't need to be.

The idea here is that many web sites provide a /robots.txt file, telling spider
programs which pages they should not visit. This module gives you a way to
parse these rules and make queries about what you are allowed to visit. You can
learn all about the interface and even the file format of /robots.txt at:

http://search.cpan.org/~gaas/libwww-perl-5.805/lib/WWW/RobotRules.pm

 

[Daniel Berger]

Ruby Quiz wrote:

Now, if you have no idea what to port, here are two suggestions. (Please feel
free to post other suggestions to Ruby Talk. These are *not* spoilers!)

File::ReadBackwards

See ruby-talk:13185 and the following discussion. I was such a noob
then.

Regards,

Dan

 

[James Edward Gray II]

Seriously, this quiz is *not* intended to be a lot of work.

I just know people aren't going to believe me on this, so here's my
attempt to put my code where my mouth is. This is my port of
File::ReadBackwards. Translating the heart of the algorithm took me
well under an hour, though I did spend a bit more time adding
interface methods and documentation.

James Edward Gray II

#!/usr/local/bin/ruby -w

# elif.rb
#
# Created by James Edward Gray II on 2006-01-28.
# Copyright 2006 Gray Productions. All rights reserved.

#
# A File-like object for reading lines from a disk file in reverse
order. See
# Elif::new and Elif#gets for details. All other methods are just
interface
# conveniences.
#
# Based on Perl's File::ReadBackwards module, by Uri Guttman.
#
class Elif
# The size of the reads we will use to add to the line buffer.
MAX_READ_SIZE = 1 << 10 # 1024

# Works just line File::foreach, save that the lines come in
reverse order.
def self.foreach( name, sep_string = $/ )
open(name) do |file|
while line = file.gets(sep_string)
yield line
end
end
end

# Works just line File:pen.
def self.open( *args )
file = new(*args)
if block_given?
begin
yield file
ensure
file.close
end
else
file
end
end

#
# Works just line File::readlines, save that line Array will be in
# reverse order.
#
def self.readlines( name, sep_string = $/ )
open(name) { |file| file.readlines(sep_string) }
end

#
# The first half of the Elif algorithm (to read file lines in
reverse order).
# This creates a new Elif object, shifts the read pointer to the
end of the
# file, and prepares a buffer to hold read lines until they can be
returned.
# This method also sets the <tt>@read_size</tt> to the remainer of
File#size
# and +MAX_READ_SIZE+ for the first read.
#
# Technically +args+ are delegated straight to File#new, but you
must open the
# File object for reading for it to work with this algorithm.
#
def initialize( *args )
# Delegate to File::new and move to the end of the file.
@file = File.new(*args)
@file.seek(0, IO::SEEK_END)

# Record where we are.
@current_pos = @file.pos

# Get the size of the next of the first read, the dangling bit
of the file.
@read_size = @file.pos % MAX_READ_SIZE
@read_size = MAX_READ_SIZE if @read_size.zero?

# A buffer to hold lines read, but not yet returned.
@line_buffer = Array.new
end

#
# The second half on the Elif algorthim (see Elif::new). This
method returns
# the next line of the File, working from the end to the beginning
in reverse
# line order.
#
# It works by moving the file pointer backwords +MAX_READ_SIZE+ at
a time,
# storing seen lines in <tt>@line_buffer</tt>. Once the buffer
contains at
# least two lines (ensuring we have seen on full line) or the file
pointer
# reaches the head of the File, the last line from the buffer is
returned.
# When the buffer is exhausted, this will throw +nil+ (from the
empty Array).
#
def gets( sep_string = $/ )
#
# If we have more than one line in the buffer or we have reached
the
# beginning of the file, send the last line in the buffer to the
caller.
# (This may be +nil+, if the buffer has been exhausted.)
#
return @line_buffer.pop if @line_buffer.size > 2 or
@current_pos.zero?

#
# If we made it this far, we need to read more data to try and
find the
# beginning of a line or the beginning of the file. Move the
file pointer
# back a step, to give us new bytes to read.
#
@current_pos -= @read_size
@file.seek(@current_pos, IO::SEEK_SET)

#
# Read more bytes and prepend them to the first (likely partial)
line in the
# buffer.
#
@line_buffer[0] = "#{@file.read(@read_size)}#{@line_buffer[0]}"
@read_size = MAX_READ_SIZE # Set a size for the next read.

#
# Divide the first line of the buffer based on +sep_string+ and
#flatten!
# those new lines into the buffer.
#
@line_buffer[0] = @line_buffer[0].scan(/.*?#{Regexp.escape
(sep_string)}|.+/)
@line_buffer.flatten!

# We have move data now, so try again to read a line...
gets(sep_string)
end

# Works just line File#each, save that the lines come in reverse
order.
def each( sep_string = $/ )
while line = gets(sep_string)
yield line
end
end
alias_method :each_line, :each # Works just like File#each_line.
include Enumerable # Support all the standard iterators.

# Works just line File#readline, save that the lines come in
reverse order.
def readline( sep_string = $/ )
gets(sep_string) || raise(EOFError, "end of file reached")
end

#
# Works just line File#readlines, save that line Array will be in
# reverse order.
#
def readlines( sep_string = $/ )
lines = Array.new
while line = gets(sep_string)
lines << line
end
lines
end

# Works just line File#close.
def close
@file.close
end
end

 

[Matthew Moss]

There aren't any particular libraries I've used anytime recently...=20
all my work is in-house code. But I took a quick glance over CPAN for
something relatively small and simple... the latter because I stopped
coding in Perl years ago and don't remember all the syntax very well,
especially the stuff that has been added for objects.

In any case, I found a simple library called Trampoline by Steven
Lembark which allows you to create an object but delay actual
construction... which is useful to have something with expensive
construction cost ready to go but not actually constructed until used.

Below I provide a really basic implementation that is probably not
rock-solid and could probably be done better ... I'm still such a
n00b, especially when it comes to metaclasses (or eigenclasses, or
whatever they want to be called this week). It also doesn't do
everything the Perl lib did, just what I found useful and could
understand.

Anyway, here's the code (trampoline.rb), with a couple of use examples
at the bottom.

module Trampoline
# Instance methods
class Bounce
def initialize(cons, klass, *args)
@klass, @cons, @args =3D klass, cons, args
end

def method_missing(method, *args)
@obj =3D @klass.send(@cons, *@args) unless @obj
@obj.send(method, *args)
end
end

# Class methods
class << Bounce
alias_method ld_new, :new

def new(*args)
old_newnew, *args)
end

def method_missing(method, *args)
old_new(method, *args)
end
end
end



And now, example use. Obviously, this class is not in need of delayed
construction; just using it as an example.

require 'trampoline'
class Logger
def initialize(prefix)
puts 'Constructing Logger...'
@prefix =3D prefix
end

def Logger.make(prefix)
Logger.new(prefix)
end

def log(msg)
puts "#{@prefix}: #{msg}"
end
end

puts "start"
errors =3D Trampoline::Bounce.new(Logger, 'ERROR')
puts "made bouncer, about to log message"
errors.log('Hello, world!')
puts "about to log second message"
errors.log('Goodbye, world!')
puts "message logged"

# This is really the same, but eventually calls Logger.make to construct.
puts "start"
warns =3D Trampoline::Bounce.make(Logger, 'WARNING')
puts "made bouncer, about to log message"
warns.log('Hello, world!')
puts "about to log second message"
warns.log('Goodbye, world!')
puts "message logged"


Output from the example code:

start
made bouncer, about to log message
Constructing Logger...
ERROR: Hello, world!
about to log second message
ERROR: Goodbye, world!
message logged
start
made bouncer, about to log message
Constructing Logger...
WARNING: Hello, world!
about to log second message
WARNING: Goodbye, world!
message logged

 

[James Edward Gray II]

This is my port of File::ReadBackwards.

I just noticed that everyone provided sample usage (just as I asked
them too), but me! Egad. Here's Elif at work:

$ cat sample_data.txt
This is line one.
This is line two.
This is line three.
...
$ ruby -r elif -e 'puts Elif.readlines(ARGV.first)' sample_data.txt
...
This is line three.
This is line two.
This is line one.
$ ruby -r elif -e 'Elif.foreach(ARGV.first) { |line| puts line if
line =~ /t[a-z]+.$/ }' sample_data.txt
This is line three.
This is line two.

James Edward Gray II

 

[James Edward Gray II]

This is my port of File::ReadBackwards.

I haven't had time to document it yet, but here is the other port of
WWW::RobotRules. You use it something like this:

#!/usr/local/bin/ruby -w

require "robot_rules"
require "open-uri"

rules = RobotRules.new("RubyQuizBrowser 1.0")
robots_url = "http://pragmaticprogrammer.com/robots.txt"

open(robots_url) do |url|
data = url.read

puts "/robots.txt:"
puts data
puts

rules.parse(robots_url, data)
end

puts "URL tests:"
%w{ http://pragmaticprogrammer.com/images/dave.jpg
http://pragmaticprogrammer.com/imagination }.each do |test|
puts "rules.allowed?( #{test.inspect} )"
puts rules.allowed?(test)
end

__END__

Which prints:

/robots.txt:
User-agent: *
Disallow: images

URL tests:
rules.allowed?( "http://pragmaticprogrammer.com/images/dave.jpg" )
false
rules.allowed?( "http://pragmaticprogrammer.com/imagination" )
true

James Edward Gray II

#!/usr/local/bin/ruby -w

# robot_rules.rb
#
# Created by James Edward Gray II on 2006-01-31.
# Copyright 2006 Gray Productions. All rights reserved.

require "uri"

# Based on Perl's WWW::RobotRules module, by Gisle Aas.
class RobotRules
def initialize( user_agent )
@user_agent = user_agent.scan(/\S+/).first.sub(%r{/.*},
"").downcase
@rules = Hash.new { |rules, rule| rules[rule] = Array.new }
end

def parse( text_uri, robots_data )
uri = URI.parse(text_uri)
location = "#{uri.host}:#{uri.port}"
@rules.delete(location)

rules = robots_data.split(/[\015\012]+/).
map { |rule| rule.sub(/\s*#.*$/, "") }
anon_rules = Array.new
my_rules = Array.new
current = anon_rules
rules.each do |rule|
case rule
when /^\s*User-Agent\s*:\s*(.+?)\s*$/i
break unless my_rules.empty?

current = if $1 == "*"
anon_rules
elsif $1.downcase.index(@user_agent)
my_rules
else
nil
end
when /^\s*Disallow\s*:\s*(.*?)\s*$/i
next if current.nil?

if $1.empty?
current << nil
else
disallow = URI.parse($1)

next unless disallow.scheme.nil? or disallow.scheme ==
uri.scheme
next unless disallow.port.nil? or disallow.port == uri.port
next unless disallow.host.nil? or
disallow.host.downcase == uri.host.downcase

disallow = disallow.path
disallow = "/" if disallow.empty?
disallow = "/#{disallow}" unless disallow[0] == ?/

current << disallow
end
end
end

@rules[location] = if my_rules.empty?
anon_rules.compact
else
my_rules.compact
end
end

def allowed?( text_uri )
uri = URI.parse(text_uri)
location = "#{uri.host}:#{uri.port}"
path = uri.path

return true unless %w{http https}.include?(uri.scheme)

not @rules[location].any? { |rule| path.index(rule) == 0 }
end
end

 

[Adam Shelly]

I went browsing in CPAN to find something interesting, and came up
with Algorithm::Merge.
I don't use the perl version, but 3 way merging is something I do
often since we allow concurrent access with our source control at
work.

Merge.rb is a fairly straight port of the perl version. I did change
a callback to a block, and added some symbols in place of numeric
constants. I need to add better documentation, but I wanted to get
this in before it was too late for the summary.

Usage:
original=3D "Ok,\n this is a test sentence\n which will be edited."
edited =3D"Ok,\n this is a sample phrase\n which has been edited."
change=3D"Hello World,\n this is a test phrase\n which I edited."

puts "\nSplit by lines\n--------------------"
$;=3D"\n"
Merge::diff3(original.split, edited.split, change.split).each{|l| puts
l.inspect}
puts Merge::merge(original.split, edited.split, change.split)
puts "\nSplit by words\n--------------------"
$;=3D" "
Merge::diff3(original.split, edited.split, change.split).each{|l| puts
l.inspect}
puts Merge::merge(original.split, edited.split,
change.split){|conflicts|
["<<"]+conflicts[1]+["|"]+conflicts[2]+[">>"]}.join(' ')

yields:
Split by lines
--------------------
["r", "Ok,", "Ok,", "Hello World,"]
["c", " this is a test sentence", " this is a sample phrase", " this
is a test phrase"]
["c", " which will be edited.", " which has been edited.", " which I edited=
"]
Hello World,
<!-- ------ START CONFLICT ------ -->
this is a sample phrase
which has been edited.
<!-- ---------------------------- -->
this is a test phrase
which I edited.
<!-- ------ END CONFLICT ------ -->}

Split by words
--------------------
["r", "Ok,", "Ok,", "Hello"]
["r", nil, nil, "World,"]
["u", "this", "this", "this"]
["u", "is", "is", "is"]
["u", "a", "a", "a"]
["l", "test", "sample", "test"]
["o", "sentence", "phrase", "phrase"]
["u", "which", "which", "which"]
["c", "will", "has", "I"]
["c", "be", "been", nil]
["u", "edited.", "edited.", "edited."]
Hello World, this is a sample phrase which << has been | I >> edited.


Bugs:
- Merge::diff3(original,edited, change) - does a character-based diff,
but returns inconsistent results (lines like [u, e, s, e]). I think
this is because the callback_map has some no-ops where it should have
valid callbacks, but it could be due to a porting error. I am still
struggling to completely grok the use of the callback_map, with hopes
of simplifying/clarifying it.

Question:
Can I add to or replace the Perl license with the ruby one?

Source:
---- Merge.rb -----
module Merge

# Module Merge
# Three-way merge and diff
#
# based on perl's Algorithm::Merge
# by James G. Smith, <[email protected]>
# Copyright (C) 2003 Texas A&M University. All Rights Reserved.
# This module is free software; you may redistribute it and/or
# modify it under the same terms as Perl itself.
# ported to Ruby
# by Adam Shelly <[email protected]>


require 'diff/lcs'


# Given references to three lists of items, diff3 performs a
# three-way difference.
# This function returns an array of operations describing how the
# left and right lists differ from the original list. In scalar
# context, this function returns a reference to such an array.
#
# Given the following three lists,
# original: a b c e f h i k
# left: a b d e f g i j k
# right: a b c d e h i j k
#
# merge: a b d e g i j k
#
# we have the following result from diff3:
#
# [ 'u', 'a', 'a', 'a' ],
# [ 'u', 'b', 'b', 'b' ],
# [ 'l', 'c', undef, 'c' ],
# [ 'o', undef, 'd', 'd' ],
# [ 'u', 'e', 'e', 'e' ],
# [ 'r', 'f', 'f', undef ],
# [ 'o', 'h', 'g', 'h' ],
# [ 'u', 'i', 'i', 'i' ],
# [ 'o', undef, 'j', 'j' ],
# [ 'u', 'k', 'k', 'k' ]
#
# The first element in each row is the array with the difference:
# c - conflict (no two are the same)
# l - left is different
# o - original is different
# r - right is different
# u - unchanged
# The next three elements are the lists from the original, left,
# and right arrays respectively that the row refers to (in the synopsis,
#

def Merge::diff3( pivot, doc_a, doc_b)
ret =3D []

no_change =3D proc do |args|
ret << ['u', pivot[args[0]], doc_a[args[1]], doc_b[args[2]] ]
end

conflict =3D proc do |args|
p=3D pivot[args[0]] if args[0]
a=3D doc_a[args[1]] if args[1]
b=3D doc_b[args[2]] if args[2]
ret << ['c', p, a, b]
end

diff_a =3D proc do |args|
case args.size
when 1
ret << ['o',pivot[args[0]], nil, nil]
when 2
ret << ['o',nil, doc_a[args[0]], doc_b[args[1]]]
when 3
ret << ['o', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
end
end

diff_b =3D proc do |args|
case args.size
when 1
ret << ['l', nil, doc_a[args[0]], nil]
when 2
ret << ['l', pivot[args[0]], nil, doc_b[args[1]]]
when 3
ret << ['l', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
end
end

diff_c =3D proc do |args|
case args.size
when 1
ret << ['r', nil, nil, doc_b[args[0]]]
when 2
ret << ['r', pivot[args[0]], doc_a[args[1]], nil]
when 3
ret << ['r', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
end
end

traverse_sequences3(pivot, doc_a, doc_b,
{:NO_CHANGE=3D>no_change, :CONFLICT=3D>conflict,
:A_DIFF=3D> diff_a, :B_DIFF=3D>diff_b, :C_DIFF=3D>diff_c}
)
return ret
end


#callbacks for Diff::LCS
class LCS_Traverse_Callbacks
def initialize diffs
@diffs =3D diffs
end
def [] l,r
@diffs[@left=3Dl]=3D[]
@diffs[@right=3Dr]=3D[]
self
end
def match *args
end
def discard_a event
@diffs[@left]<<event.old_position
end
def discard_b event
@diffs[@right]<<event.new_position
end
end


# constants for traverse_sequences
D=3Dnil
AB_A=3D32
AB_B=3D16
AC_A=3D8
AC_C=3D4
BC_B=3D2
BC_C=3D1
CB_B=3D5 #not used in calculations
CB_C=3D3 #not used in calculations
@base_doc =3D {AB_A=3D>:A,AB_B=3D>:B,AC_A=3D>:A,AC_C=3D>:C,BC_B=3D>:B,BC_=
C=3D>:C}


def Merge::traverse_sequences3(adoc, bdoc, cdoc, callbacks =3D {})
target_len =3D [bdoc.size,cdoc.size].min
bc_different_len =3D (bdoc.size !=3D cdoc.size)
diffs =3D Hash.new([])


# callbacks#match:: Called when +a+ and +b+ are point=
ing
# to common elements in +:A+ and +:=
B+.
# callbacks#discard_a:: Called when +a+ is pointing to an
# element not in +:B+.
# callbacks#discard_b:: Called when +b+ is pointing to an
# element not in +:A+.
# The methods for <tt>callbacks#match</tt>,
<tt>callbacks#discard_a</tt>,
# and <tt>callbacks#discard_b</tt> are invoked with an event compri=
sing
# the action ("=3D", "+", or "-", respectively), the indicies +ii+ =
and
# +jj+, and the elements <tt>:A[ii]</tt> and <tt>:B[jj]</tt>. Retur=
n
# values are discarded by #traverse_sequences.

ts_callbacks =3D LCS_Traverse_Callbacks.new(diffs)

Diff::LCS::traverse_sequences(adoc, bdoc, ts_callbacks[AB_A, AB_B])
Diff::LCS::traverse_sequences(adoc, cdoc, ts_callbacks[AC_A,AC_C])

if (bc_different_len)
Diff::LCS::traverse_sequences(cdoc, bdoc, ts_callbacks[CB_C,CB_B])
Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])

if diffs[CB_B] !=3D diffs[BC_B] || diffs[CB_C] !=3D diffs[BC_C]
puts "Diff::diff is not symmetric for second and third
sequences - results might not be correct";

#trim to equal lengths and try again
b_len, c_len =3D bdoc.size, cdoc.size
bdoc_save =3D bdoc.slice!(target_len..-1)
cdoc_save =3D cdoc.slice!(target_len..-1)
Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])

#mark the trimmed part as different and then restore
diffs[BC_B] +=3D (target_len..b_len).to_a if target_len < b_len
diffs[BC_C] +=3D (target_len..c_len).to_a if target_len < c_len
bdoc.concat bdoc_save
cdoc.concat cdoc_save
end

else # not bc_different_len
Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])
end
pos =3D {:A=3D>0,:B=3D>0,:C=3D>0}
sizes =3D{:A=3D>adoc.size, :B=3D>bdoc.size, :C=3D>cdoc.size}
matches=3D[]
noop =3D proc {}

# Callback_Map is indexed by the sum of AB_A, AB_B, ..., as
indicated by @matches
# this isn't the most efficient, but it's a bit easier to maintain =
and
# read than if it were broken up into separate arrays
# half the entries are not noop - it would seem then that no
# entries should be noop. I need patterns to figure out what the
# other entries are.

callback_Map =3D [
[ callbacks[:NO_CHANGE], :A, :B, :C ], # 0 - no matches
[ noop, ], # 1 - =20
BC_C
[ callbacks[:B_DIFF], :B ], #*2 - B=
C_B
[ noop, ], # 3 - =20
BC_B BC_C
[ noop, ], # 4 - AC_C
[ callbacks[:C_DIFF], :C ], # 5 - =20
AC_C BC_C
[ noop, ], # 6 - AC_C B=
C_B
[ noop, ], # 7 - =20
AC_C BC_B BC_C
[ callbacks[:A_DIFF], :A ], # 8 - AC_A
[ noop, ], # 9 - AC_A =20
BC_C
[ callbacks[:C_DIFF], :A, :B ], # 10 - AC_A B=
C_B
[ callbacks[:C_DIFF], :A, :B, ], # 11 - AC_A =20
BC_B BC_C
[ noop, ], # 12 - AC_A AC_C
[ noop, ], # 13 - AC_A
AC_C BC_C
[ callbacks[:C_DIFF], :A, :B, ], # 14 - AC_A AC_C B=
C_B
[ callbacks[:C_DIFF], :A, :B, :C ], # 15 - AC_A
AC_C BC_B BC_C
[ noop, ], # 16 - AB_B
[ noop, ], # 17 - AB_B =20
BC_C
[ callbacks[:B_DIFF], :B ], # 18 - AB_B B=
C_B
[ noop, ], # 19 - AB_B =20
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 20 - AB_B AC_C
[ noop, ], # 21 - AB_B =20
AC_C BC_C
[ noop, ], # 22 - AB_B AC_C B=
C_B
[ callbacks[:CONFLICT], :A, :B, :C ], # 23 - AB_B =20
AC_C BC_B BC_C
[ callbacks[:B_DIFF], :B ], # 24 - AB_B AC_A
[ noop, ], # 25 - AB_B AC_A =20
BC_C
[ callbacks[:C_DIFF], :B, :C ], # 26 - AB_B AC_A B=
C_B
[ noop, ], # 27 - AB_B AC_A =20
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 28 - AB_B AC_A AC_C
[ noop, ], # 29 - AB_B AC_A
AC_C BC_C
[ noop, ], # 30 - AB_B AC_A AC_C B=
C_B
[ callbacks[:B_DIFF], :B ], # 31 - AB_B AC_A
AC_C BC_B BC_C
[ callbacks[:NO_CHANGE], :A, :B, :C ], # 32 - AB_A
[ callbacks[:B_DIFF], :A, :C ], # 33 - AB_A =20
BC_C
[ noop, ], # 34 - AB_A B=
C_B
[ callbacks[:B_DIFF], :A, :C ], # 35 - AB_A =20
BC_B BC_C
[ noop, ], # 36 - AB_A AC_C
[ noop, ], # 37 - AB_A =20
AC_C BC_C
[ noop, ], # 38 - AB_A AC_C B=
C_B
[ noop, ], # 39 - AB_A =20
AC_C BC_B BC_C
[ callbacks[:A_DIFF], :A, ], # 40 - AB_A AC_A
[ noop, ], # 41 - AB_A AC_A =20
BC_C
[ callbacks[:A_DIFF], :A ], # 42 - AB_A AC_A B=
C_B
[ noop, ], # 43 - AB_A AC_A =20
BC_B BC_C
[ noop, ], # 44 - AB_A AC_A AC_C
[ callbacks[:C_DIFF], :A, D, :C ], # 45 - AB_A AC_A
AC_C BC_C ##ADS: I think this should be :CONFLICT??
[ noop, ], # 46 - AB_A AC_A AC_C B=
C_B
[ noop, ], # 47 - AB_A AC_A
AC_C BC_B BC_C
[ noop, ], # 48 - AB_A AB_B
[ callbacks[:B_DIFF], :A, :C ], # 49 - AB_A AB_B =20
BC_C
[ noop, ], # 50 - AB_A AB_B B=
C_B
[ callbacks[:B_DIFF], :A, :B, :C ], # 51 - AB_A AB_B =20
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 52 - AB_A AB_B AC_C
[ noop, ], # 53 - AB_A AB_B =20
AC_C BC_C
[ noop, ], # 54 - AB_A AB_B AC_C B=
C_B
[ callbacks[:C_DIFF], :C ], # 55 - AB_A AB_B =20
AC_C BC_B BC_C
[ callbacks[:B_DIFF], :A, :C ], # 56 - AB_A AB_B AC_A
[ noop, ], # 57 - AB_A AB_B AC_A =20
BC_C
[ callbacks[:CONFLICT], :A, :B, D ], # 58 - AB_A AB_B AC_A =20
BC_B ##ADS: I changed this one to :CONFLICT
[ noop, ], # 59 - AB_A AB_B AC_A =20
BC_B BC_C
[ callbacks[:A_DIFF], :A, :B, :C ], # 60 - AB_A AB_B AC_A AC_C
[ callbacks[:CONFLICT], :A, D, :C ], # 61 - AB_A AB_B AC_A
AC_C BC_C
[ callbacks[:CONFLICT], :A, :B, D ], # 62 - AB_A AB_B AC_A AC_C B=
C_B
[ callbacks[:CONFLICT], :A, :B, :C ], # 63 - AB_A AB_B AC_A
AC_C BC_B BC_C
]

#while there is something to work with
while diffs.values.find{|e|e.size>0} && [:A,:B,:C].find{|n|pos[n]<sizes=
[n]}


#find all the differences at the current position of each doc
matchset=3D[:A,:B,:C].inject([]) do |ms,i|
ms+diffs.find_all {|k,v|@base_doc[k]=3D=3Di && v[0]=3D=3Dpos}
end
callback_num=3Dmatchset.uniq.inject(0){|cb,val| (cb|val[0])}
callback =3D callback_Map[callback_num]
args =3D callback[1..-1]
callback[0].call(args.map{|ar| ar&&pos[ar]})


args.each do |n|
pos[n]+=3D1 if n
case n
when :A
diffs[AB_A].shift while diffs[AB_A][0] && ( diffs[AB_A][0]
< pos[n] )
diffs[AC_A].shift while diffs[AC_A][0] && ( diffs[AC_A][0]
< pos[n] )
when :B
diffs[AB_B].shift while diffs[AB_B][0] && ( diffs[AB_B][0]
< pos[n] )
diffs[BC_B].shift while diffs[BC_B][0] && ( diffs[BC_B][0]
< pos[n] )
when :C
diffs[AC_C].shift while diffs[AC_C][0] && ( diffs[AC_C][0]
< pos[n] )
diffs[BC_C].shift while diffs[BC_C][0] && ( diffs[BC_C][0]
< pos[n] )
end
end #args.each
#raise "args empty" if args.empty? ##ADS: args.empty? is true
if the callback was a no-op. I don't think that should happen.
break if args.empty?
end

#this part takes care of the leftovers
bits=3D{:A=3D>4,:B=3D>2,:C=3D>1}
while [:A,:B,:C].find{|n|pos[n]<sizes[n]}
match =3D 0
args=3D[]
[:A,:B,:C].each do |i|
if pos<sizes
match|=3Dbits
args << pos
pos+=3D1
end
end
switch =3D [0,5,24,17,34,8,10,0][match] #ADS: I totally don't
understand how these callbacks were chosen
callback_Map[switch][0].call(*args) if callback_Map[switch][0]
end
end

# Given references to three lists of items, merge performs a three-way
# merge. The merge function uses the diff3 function to do most of
# the work.
#
# The optional block parameter is called for conflicts. It should
# accept an array of 3 arrays
# The first array holds a list of elements from the original list.
# The second array has a list of elements from the left list.
# The last array holds a list of elements from the right list.
# The block should return a list of elements to place in the merged
# list in place of the conflict.
#
# The default conflict handler returns:
# ["<!-- ------ START CONFLICT ------ -->",
# args[1],
# "<!-- ---------------------------- -->",
# args[2],
# "<!-- ------ END CONFLICT ------ -->}"]

def Merge::merge(pivot,doc_a, doc_b)

conflict_callback =3D proc do |args|
["<!-- ------ START CONFLICT ------ -->",
args[1],
"<!-- ---------------------------- -->",
args[2],
"<!-- ------ END CONFLICT ------ -->}"]
end

diff =3D diff3(pivot, doc_a, doc_b);

ret =3D []
conflict =3D [[],[],[]]

diff.each do |diffline|
i =3D 0
if diffline[0] =3D=3D 'c' # conflict
conflict[0] << diffline[1] if diffline[1];
conflict[1] << diffline[2] if diffline[2];
conflict[2] << diffline[3] if diffline[3];
else
unless (conflict[0].empty? && conflict[1].empty? && conflict[2].emp=
ty?)
ret << (block_given? ? yield(conflict) :
conflict_callback.call(conflict))
conflict =3D [[],[],[]]
end
case diffline[0]
when 'u' # unchanged
ret << diffline[2] || diffline[3];
when 'o','l' # added by both or left
ret << diffline[2] if diffline[2]
when 'r' #added by right
ret << diffline[3] if diffline[3]
end
end
end
unless (conflict[0].empty? && conflict[1].empty? && conflict[2].empty?)
ret << (block_given? ? yield(conflict) :
conflict_callback.call(conflict))
end

ret
end

end