[QUIZ] Port a Library (#64)

[James_Edward_Gray_II]

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

[Ross_Bamford4 (Ross Bamford)]

(By my calculations it's gone 48 hours now? Hope so, anyway...)

I did "Ruby Murray" - a port of Johan Lodin's Sub::Curry from Perl. It's
not so useful in Ruby I guess but it's fun and pretty flexible. Below is
the uncommented version, but since I can't sleep when I have
undocumented code I did Rdoc it and make the commented version available
at http://roscopeco.co.uk/code/ruby-quiz-entries/64/ .

There's also a translation of the Sub::Curry cookbook I used to drive
development a bit. The original Sub::Curry can be found at
http://search.cpan.org/~lodin/Sub-Curry-0.8/lib/Sub/Curry.pm and the
cookbook is at
http://search.cpan.org/~lodin/Sub-Curry-0.8/lib/Sub/Curry/Cookbook.pod .

Ruby Murray is about a hundred lines for the main Curry class, another
forty or so for convenience methods and the like, and about 70 lines of
tests. It could be smaller but I like (reasonably) readable code and the
TDD makes it more verbose I guess...

Here's a couple of quick examples. See the cookbook and tests (either
below or in the Rdoc linked above if formatting is broken) for more.

Just curry a method:

  c = "string".method(:slice).curry(Curry::HOLE,2)
  c.call(0)
  # => "st"
  c.call(2)
  # => "ri"

Swallow arguments:

  curry = lambda { |*args| args }.curry(1,Curry::ANTISPICE,3)
  curry.call(2,5)
  # => [1,3,5]

Do some mad curry to curry stuff:

  curry = [10,20,30].method(:inject).curry(Curry::HOLE)
  curry.call(0) { |s,i| s + i }
  # => 60

  mult_sum = lambda do |sum, i, mult|
    sum + (i * mult)
  end.curry(Curry::BLACKHOLE, Curry::HOLE)

  double_sum = mult_sum.new(Curry::BLACKHOLE, Curry::WHITEHOLE, 2)
  triple_sum = mult_sum.new(Curry::BLACKHOLE, Curry::WHITEHOLE, 3)

  curry.call(0, &double_sum)
  # => 120

  curry.call(0, &triple_sum)
  # => 180

Obviously it's completely different from the Perl original under the
hood but I tried to make it familiar enough while making good use of
Ruby.

There's a few other ideas I'd like to have tried but I didn't want to
get too far into it ;). One advantage this version has over Perl's is
that it's easy to make custom Spice argument types (HOLE, BLACKHOLE,
etc) so maybe there's some scope for hacking around in there...

=====[CURRY.RB]=====
require 'singleton'

class Curry
  WHITEHOLE = Object.new
  ANTIHOLE = Object.new
  def WHITEHOLE.inspect #:nodoc:
    "<WHITEHOLE>"
  end
  def ANTIHOLE.inspect #:nodoc:
    "<ANTIHOLE>"
  end
  
  class SpiceArg
    def initialize(name)
      @name = name
    end
    def spice_arg(args_remain)
      raise NoMethodError, "Abstract method"
    end
    def inspect
      "<#{@name}>"
    end
  end

  class HoleArg < SpiceArg #:nodoc: all
    include Singleton
    def initialize; super("HOLE"); end
    def spice_arg(args_remain)
      a = args_remain.shift
      if a == ANTIHOLE
        []
      else
        [a]
      end
    end
  end
  
  class BlackHoleArg < SpiceArg #:nodoc: all
    include Singleton
    def initialize; super("BLACKHOLE"); end
    def spice_arg(args_remain)
      if idx = args_remain.index(WHITEHOLE)
        args_remain.slice!(0..idx)[0..-2]
      else
        args_remain.slice!(0..args_remain.length)
      end
    end
  end

  class AntiSpiceArg < SpiceArg #:nodoc: all
    include Singleton
    def initialize; super("ANTISPICE"); end
    def spice_arg(args_remain)
      args_remain.shift
      []
    end
  end

  HOLE = HoleArg.instance
  BLACKHOLE = BlackHoleArg.instance
  ANTISPICE = AntiSpiceArg.instance

  attr_reader :spice
  attr_reader :uncurried

  def initialize(*spice, &block)
    block = block || (spice.shift if spice.first.respond_to?(:call))
    raise ArgumentError, "No block supplied" unless block
    @spice, @uncurried = spice, block
  end

  def call(*args, &blk)
    @uncurried.call(*call_spice(args), &blk)
  end

  # This would be an alias, but it's documented along with call and
  # I couldn't :nodoc: an alias - how do we do that ?
  def [](*args) # :nodoc:
    call(*args)
  end

  def new(*spice)
    Curry.new(*merge_spice(spice), &@uncurried)
  end

  def to_proc
    @extern_proc ||= method(:call).to_proc
  end
  
  private

  def merge_spice(spice)
    largs = spice.dup
    
    res = @spice.inject([]) do |res, sparg|
      if sparg.is_a?(SpiceArg) && !largs.empty?
        res + sparg.spice_arg(largs)
      else
        res << sparg
      end
    end
   
    res + largs
  end

  def call_spice(args)
    sp = merge_spice(args)
    sp.map do |a|
      if a.is_a? SpiceArg
        nil
      else
        a
      end
    end
  end
end

# Undocumented alias for Perl familiarity
module Sub #:nodoc: all
  Curry = ::Curry
end

module Curriable
  def curry(*spice)
    Curry.new(self, *spice)
  end
end

unless defined? NO_CORE_CURRY
  NO_CORE_CURRY = (ENV['NO_CORE_CURRY'] || $SAFE > 3)
end

unless NO_CORE_CURRY
  class Proc
    include Curriable
  end

  class Method
    include Curriable
  end
end

if $0 == __FILE__ || (TEST_CURRY if defined? TEST_CURRY)
  require 'test/unit'

  class TestCurry < Test::Unit::TestCase
    def test_fixed_args
      curry = Curry.new(1,2,3) { |a,b,c| [a,b,c] }
      assert_equal [1,2,3], curry.call
    end

    def test_fixed_array_args
      curry = Curry.new([1],[2,3]) { |*args| args }
      assert_equal [[1],[2,3]], curry.call
    end

    def test_hole
      curry = Curry.new(1,Curry::HOLE,3) { |a,b,c| [a,b,c] }
      assert_equal [1,nil,3], curry.call
      assert_equal [1,2,3], curry.call(2)

      curry = Curry.new(1,Curry::HOLE,3,Curry::HOLE) { |*args| args }
      assert_equal [1,2,3,4], curry.call(2,4)
      assert_equal [1,2,3,4,5,6], curry.call(2,4,5,6)
      assert_equal [1,[2,'two'],3,[4,0],[[14]]],
                   curry.call([2,'two'],[4,0],[[14]])
      
    end

    def test_antihole
      curry = Curry.new(1,Curry::HOLE,3) { |*args| args }
      assert_equal [1,3], curry.call(Curry::ANTIHOLE)

      curry = Curry.new(1,Curry::HOLE,3,Curry::HOLE,4) { |*args| args }
      assert_equal [1,2,3,4,5], curry.call(2,Curry::ANTIHOLE,5)
    end

    def test_antispice
      curry = Curry.new(1,Curry::ANTISPICE,3,Curry::HOLE,4) { |*args|
args }
      assert_equal [1,3,4,5], curry.call(2,Curry::ANTIHOLE,5)
    end

    def test_black_hole
      curry = Curry.new(1,Curry::BLACKHOLE) { |*args| args }
      assert_equal [1,2,3], curry.call(2,3)

      curry = Curry.new(1,Curry::BLACKHOLE,3,4) { |*args| args }
      assert_equal [1,2,10,3,4], curry.call(2,10)
    end

    def test_white_hole
      curry = Curry.new(1,Curry::BLACKHOLE,3,Curry::HOLE,5) { |*args|
args }
      assert_equal [1,2,3,7,5,8,9], curry.call(2,Curry::WHITEHOLE,7,8,9)
      assert_equal [1,10,20,3,nil,5], curry.call(10,20,Curry::WHITEHOLE)
      assert_equal [1,10,20,25,3,4,5],
curry.call(10,20,25,Curry::WHITEHOLE,4)

      curry =
Curry.new(1,Curry::BLACKHOLE,6,Curry::HOLE,3,4,Curry::BLACKHOLE,5) { |
*args| args }
      assert_equal [1,10,20,25,6,40,3,4,50,60,5],
curry.call(10,20,25,Curry::WHITEHOLE,40,50,60)
    end

    def test_curry_from_curry
      curry =
Curry.new(1,Curry::BLACKHOLE,6,Curry::HOLE,3,4,Curry::BLACKHOLE,5) { |
*args| args }
      curry = curry.new(Curry::HOLE,Curry::WHITEHOLE,8,9,10)
      assert_equal [1,Curry::HOLE,6,8,3,4,9,10,5], curry.spice

      curry = curry.new(Curry::HOLE, 4, Curry::BLACKHOLE)
      assert_equal [1,Curry::HOLE,6,8,3,4,9,10,5,4,Curry::BLACKHOLE],
curry.spice

      curry = curry.new(Curry::ANTIHOLE)
      assert_equal [1,6,8,3,4,9,10,5,4,Curry::BLACKHOLE], curry.spice

      curry = curry.new(3,Curry::BLACKHOLE,Curry::WHITEHOLE,0)
      assert_equal [1,6,8,3,4,9,10,5,4,3,Curry::BLACKHOLE,0],
curry.spice
      assert_equal [1,6,8,3,4,9,10,5,4,3,2,1,0], curry.call(2,1)
    end

    def test_cant_block_to_curried_block
      a = Curry.new(1,2) { |*args| args }

      assert_equal [1,2,3], a.call(3) { |b| }
    end

    def test_curry_proc
      a = [1,2,3,4,5]
      c = Curry.new(*a) { |*args| args * 2 }
      assert_equal [1,2,3,4,5,1,2,3,4,5], c.call

      if NO_CORE_CURRY
        warn "Skipping Proc extension test"
      else
        c = lambda { |*args| args * 2 }.curry(*a)
        assert_equal [1,2,3,4,5,1,2,3,4,5], c.call
      end
    end

    def test_curry_method
      a = [1,2,3,4,5]
      injsum = Curry.new(a.method(:inject),0)
      assert_equal 15, injsum.call { |s,i| s + i }

      if NO_CORE_CURRY
        warn "Skipping Method extension test"
      else
        injsum = a.method(:inject).curry(0)
        assert_equal 15, injsum.call { |s,i| s + i }
      end
    end

    def test_curry_to_proc
      curry = Curry.new(Curry::HOLE, Curry::HOLE, 'thou') { |ary,i,msg|
ary << "#{i} #{msg}" }
      assert_equal ["1 thou", "2 thou", "3 thou"],
[1,2,3].inject([],&curry)
    end

    def test_alt_bits
      curry = Curry.new(Curry::BLACKHOLE, 'too', 'true') { |one, two,
*rest| [one, two, rest] }
      assert_equal [1,2,['too','true']], curry[1,2]
    end

    def test_perlish
      s = "str"
      s = Sub::Curry.new(s.method(:+), "ing")
      assert_equal "string", s.call
    end
  end

  if ARGV.member?('--doc') || !File.exist?('doc')
    ARGV.reject! { |a| a == '--doc' }
    system("rdoc #{__FILE__} #{'currybook.rdoc' if
File.exists?('currybook.rdoc')} --main Curry")
  end
end

__END__

···

--
Ross Bamford - rosco@roscopeco.REMOVE.co.uk

[James_Edward_Gray_II]

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

···

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

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

#
# 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::open.
   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_D_Moss]

There aren't any particular libraries I've used anytime recently...
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 = klass, cons, args
      end

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

   # Class methods
   class << Bounce
      alias_method :old_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 = prefix
   end

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

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

puts "start"
errors = 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 = 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

[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= "Ok,\n this is a test sentence\n which will be edited."
edited ="Ok,\n this is a sample phrase\n which has been edited."
change="Hello World,\n this is a test phrase\n which I edited."

puts "\nSplit by lines\n--------------------"
$;="\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--------------------"
$;=" "
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, <jsmith@cpan.org>
# 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 <adam.shelly@gmail.com>

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 = []

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

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

    diff_a = 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 = 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 = 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=>no_change, :CONFLICT=>conflict,
        :A_DIFF=> diff_a, :B_DIFF=>diff_b, :C_DIFF=>diff_c}
    )
    return ret
  end

  #callbacks for Diff::LCS
  class LCS_Traverse_Callbacks
    def initialize diffs
      @diffs = diffs
    end
    def [] l,r
      @diffs[@left=l]=[]
      @diffs[@right=r]=[]
      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=nil
  AB_A=32
  AB_B=16
  AC_A=8
  AC_C=4
  BC_B=2
  BC_C=1
  CB_B=5 #not used in calculations
  CB_C=3 #not used in calculations
  @base_doc = {AB_A=>:A,AB_B=>:B,AC_A=>:A,AC_C=>:C,BC_B=>:B,BC_C=>:C}

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

        # callbacks#match:: Called when +a+ and +b+ are pointing
        # 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 comprising
        # the action ("=", "+", or "-", respectively), the indicies +ii+ and
        # +jj+, and the elements <tt>:A[ii]</tt> and <tt>:B[jj]</tt>. Return
        # values are discarded by #traverse_sequences.

    ts_callbacks = 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] != diffs[BC_B] || diffs[CB_C] != 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 = bdoc.size, cdoc.size
        bdoc_save = bdoc.slice!(target_len..-1)
        cdoc_save = 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] += (target_len..b_len).to_a if target_len < b_len
        diffs[BC_C] += (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 = {:A=>0,:B=>0,:C=>0}
    sizes ={:A=>adoc.size, :B=>bdoc.size, :C=>cdoc.size}
    matches=[]
    noop = 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 = [
        [ callbacks[:NO_CHANGE], :A, :B, :C ], # 0 - no matches
        [ noop, ], # 1 -
        BC_C
        [ callbacks[:B_DIFF], :B ], #*2 - BC_B
        [ noop, ], # 3 -
   BC_B BC_C
        [ noop, ], # 4 - AC_C
        [ callbacks[:C_DIFF], :C ], # 5 -
AC_C BC_C
        [ noop, ], # 6 - AC_C BC_B
        [ noop, ], # 7 -
AC_C BC_B BC_C
        [ callbacks[:A_DIFF], :A ], # 8 - AC_A
        [ noop, ], # 9 - AC_A
        BC_C
        [ callbacks[:C_DIFF], :A, :B ], # 10 - AC_A BC_B
        [ callbacks[:C_DIFF], :A, :B, ], # 11 - AC_A
   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 BC_B
        [ callbacks[:C_DIFF], :A, :B, :C ], # 15 - AC_A
AC_C BC_B BC_C
        [ noop, ], # 16 - AB_B
        [ noop, ], # 17 - AB_B
        BC_C
        [ callbacks[:B_DIFF], :B ], # 18 - AB_B BC_B
        [ noop, ], # 19 - AB_B
   BC_B BC_C
        [ callbacks[:A_DIFF], :B, :C ], # 20 - AB_B AC_C
        [ noop, ], # 21 - AB_B
AC_C BC_C
        [ noop, ], # 22 - AB_B AC_C BC_B
        [ callbacks[:CONFLICT], :A, :B, :C ], # 23 - AB_B
AC_C BC_B BC_C
        [ callbacks[:B_DIFF], :B ], # 24 - AB_B AC_A
        [ noop, ], # 25 - AB_B AC_A
        BC_C
        [ callbacks[:C_DIFF], :B, :C ], # 26 - AB_B AC_A BC_B
        [ noop, ], # 27 - AB_B AC_A
   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 BC_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
        BC_C
        [ noop, ], # 34 - AB_A BC_B
        [ callbacks[:B_DIFF], :A, :C ], # 35 - AB_A
   BC_B BC_C
        [ noop, ], # 36 - AB_A AC_C
        [ noop, ], # 37 - AB_A
AC_C BC_C
        [ noop, ], # 38 - AB_A AC_C BC_B
        [ noop, ], # 39 - AB_A
AC_C BC_B BC_C
        [ callbacks[:A_DIFF], :A, ], # 40 - AB_A AC_A
        [ noop, ], # 41 - AB_A AC_A
        BC_C
        [ callbacks[:A_DIFF], :A ], # 42 - AB_A AC_A BC_B
        [ noop, ], # 43 - AB_A AC_A
   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 BC_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
        BC_C
        [ noop, ], # 50 - AB_A AB_B BC_B
        [ callbacks[:B_DIFF], :A, :B, :C ], # 51 - AB_A AB_B
   BC_B BC_C
        [ callbacks[:A_DIFF], :B, :C ], # 52 - AB_A AB_B AC_C
        [ noop, ], # 53 - AB_A AB_B
AC_C BC_C
        [ noop, ], # 54 - AB_A AB_B AC_C BC_B
        [ callbacks[:C_DIFF], :C ], # 55 - AB_A AB_B
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
        BC_C
        [ callbacks[:CONFLICT], :A, :B, D ], # 58 - AB_A AB_B AC_A
   BC_B ##ADS: I changed this one to :CONFLICT
        [ noop, ], # 59 - AB_A AB_B AC_A
   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 BC_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=[:A,:B,:C].inject([]) do |ms,i|
        ms+diffs.find_all {|k,v|@base_doc[k]==i && v[0]==pos[i]}
      end
      callback_num=matchset.uniq.inject(0){|cb,val| (cb|val[0])}
      callback = callback_Map[callback_num]
      args = callback[1..-1]
      callback[0].call(args.map{|ar| ar&&pos[ar]})

      args.each do |n|
        pos[n]+=1 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={:A=>4,:B=>2,:C=>1}
    while [:A,:B,:C].find{|n|pos[n]<sizes[n]}
      match = 0
      args=[]
      [:A,:B,:C].each do |i|
        if pos[i]<sizes[i]
          match>=bits[i]
          args << pos[i]
          pos[i]+=1
        end
      end
      switch = [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 = proc do |args|
        ["<!-- ------ START CONFLICT ------ -->",
        args[1],
        "<!-- ---------------------------- -->",
        args[2],
        "<!-- ------ END CONFLICT ------ -->}"]
      end

    diff = diff3(pivot, doc_a, doc_b);

    ret = []
    conflict = [[],[],[]]

    diff.each do |diffline|
      i = 0
      if diffline[0] == '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].empty?)
          ret << (block_given? ? yield(conflict) :
conflict_callback.call(conflict))
          conflict = [[],[],[]]
        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

[amrangaye]

Hello.

This is my first rubyquiz, and I am still learning Ruby. I decided to
go with something simple but fun. So I did a search on the CPAN (I've
used Perl before) for the Acme modules, and chose Acme::Bleach
(http://search.cpan.org/~dconway/Acme-Bleach-1.12/lib/Acme/Bleach.pm)
to implement. I couldn't find a Ruby version on either RAA or
rubyforge.

Acme::Bleach is a module by Damian Conway, and it literally bleaches
your program, whilst still leaving it in a runnable state. It's a
really cool little module, and I stuck as close to the original as
possible - even using nearly the same method names. Here it is in its
entirety. Any suggestions, criticisms, etc. are highly welcome.

#Ruby port of Acme::Bleach - by Amran Gaye
#You can use this by doing an "include 'Bleach' " at the top of your
program

$tie="\t"*8

def whiten(laundry)
  #Change laundry to binary 1s and 0s...
  #then change those to tab and space characters. Finally add newlines
after every 9th character
  result = laundry.unpack('b*').to_s.tr('01',"
\t").gsub(/(.{9})/,"\\1\n")
  return $tie + result #Add a tie to the washed shirt, and
return it
end

def brighten(laundry)
  #Does the opposite of whiten
  laundry.sub!(/\t{8}/,'') #Remove tie
  laundry.tr!("\n",'') #Remove newlines
  laundry.tr(" \t",'01').to_a.pack('b*') #Change spaces and tabs to 0s
and 1s, then repack them as binary
end

def dirty?(laundry) #Laundry is dirty only if it contains
non-space characters
  laundry =~ /\S/
end

def proper?(laundry) #shirt is proper if it contains a
tie
  laundry =~ /^#$tie/
end

shirt = IO.readlines($0).to_s #Read in current program
shirt.sub!("require 'Bleach'",'') #Remove require line

if(not dirty?(shirt) and proper?(shirt))
  eval brighten(shirt)
else
  file = File.new($0,"w")
  file.puts("require 'Bleach'")
  file.puts(whiten(shirt))
  file.close
end

[James_Edward_Gray_II]

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

···

On Jan 29, 2006, at 10:23 AM, James Edward Gray II wrote:

This is my port of File::ReadBackwards.

[James_Edward_Gray_II]

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&quot;

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&quot; )
false
rules.allowed?( "http://pragmaticprogrammer.com/imagination&quot; )
true

James Edward Gray II

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

# robot_rules.rb

···

On Jan 29, 2006, at 10:23 AM, James Edward Gray II wrote:

This is my port of File::ReadBackwards.

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

[amrangaye]

Soon after I posted this, I saw Rubyquiz #34 (Whiteout) and - much to
my chagrin - it was the same problem! Seems I arrived too late to
the party. Still, I hope someone found it interesting.