[QUIZ] Port a Library (#64)

Discussion in 'Ruby' started by Ruby Quiz, Jan 27, 2006.

  1. Ruby Quiz

    Ruby Quiz Guest

    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
    Ruby Quiz, Jan 27, 2006
    #1
    1. Advertising

  2. Re: Port a Library (#64)

    Ruby Quiz wrote:

    <snip>

    >
    > 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
    Daniel Berger, Jan 29, 2006
    #2
    1. Advertising

  3. On Jan 27, 2006, at 7:52 AM, Ruby Quiz wrote:

    > 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::eek: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
    James Edward Gray II, Jan 29, 2006
    #3
  4. Ruby Quiz

    Matthew Moss Guest

    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 :eek:ld_new, :new

    def new(*args)
    old_new:)new, *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
    Matthew Moss, Jan 30, 2006
    #4
  5. On Jan 29, 2006, at 10:23 AM, James Edward Gray II wrote:

    > 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, Jan 31, 2006
    #5
  6. On Jan 29, 2006, at 10:23 AM, James Edward Gray II wrote:

    > 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
    James Edward Gray II, Jan 31, 2006
    #6
  7. Ruby Quiz

    Adam Shelly Guest

    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, <>
    # 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 <>


    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
    Adam Shelly, Jan 31, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    367
    James Edward Gray II
    Jan 18, 2005
  2. David Tran
    Replies:
    9
    Views:
    187
    David Tran
    Jan 21, 2005
  3. Ruby Quiz

    [QUIZ] 1-800-THE-QUIZ (#20)

    Ruby Quiz, Feb 18, 2005, in forum: Ruby
    Replies:
    15
    Views:
    325
    gabriele renzi
    Feb 24, 2005
  4. Marcelo Alvim

    [QUIZ] Newbie doubts about the quiz

    Marcelo Alvim, Aug 15, 2006, in forum: Ruby
    Replies:
    15
    Views:
    252
    Marcelo Alvim
    Aug 16, 2006
  5. Daniel Moore
    Replies:
    10
    Views:
    307
    James Gray
    Jan 31, 2009
Loading...

Share This Page