[ANN] Diff::LCS 1.1.0, Diff::LCS 1.0.4

Discussion in 'Ruby' started by Austin Ziegler, Aug 8, 2004.

  1. It is with pleasure that I announce the latest versions of Diff::LCS,
    a pure-Ruby differencing algorithm.

    Version 1.0.4 is an incremental bugfix that improves the installer (it
    is not entirely fixed for ri document generation; I believe that I
    have done most of what I can do with this), fixes a problem of missing
    left-side changes when comparing against an empty sequence, and fixes
    a problem with ldiff output, especially for unified diff output.

    Version 1.1.0 is a feature release that includes all bugfixes up to
    and including 1.0.4. In addition, it adds a new standard callback
    (ContextDiffCallback) that works similarly to SDiffCallback but
    produces a smaller diff set.

    More importantly, it is now possible to patch a sequence with a diff
    set to produce the second sequence. If the patch is performed without
    specifying direction, then it will be examined to see which direction
    in which the patch will be performed. If the patch is performed by
    specifying the direction, then the patch will be performed without
    verification that the patch set applies to the source sequence.

    Using version 1.0.4, I have produced a couple of patches today for
    both rdoc and for Ruby's dir.c that look *exactly* like they do from
    unix diff (at least the version included with cygwin).

    Both versions can be found in the Ruwiki project filelist:
    http://rubyforge.org/frs/?group_id=84

    -austin

    Diff::LCS README
    ================
    Diff::LCS is a port of Algorithm::Diff[1] that uses the McIlroy-Hunt
    longest common subsequence (LCS) algorithm to compute intelligent
    differences between two sequenced enumerable containers[2]. The
    implementation is based on Mario I. Wolczko's[3] Smalltalk version
    (1.2, 1993)[4] and Ned Konz's[5] Perl version (Algorithm::Diff)[6].

    This release is version 1.1.0 with the addition of new features,
    including the ability to #patch and #unpatch changes as well as a new
    contextual diff callback, Diff::LCS::ContextDiffCallbacks, that should
    improve the context sensitivity of patching.

    Using this module is quite simple. By default, Diff::LCS does not
    extend objects with the Diff::LCS interface, but will be called as if
    it were a function:

    require 'diff/lcs'

    seq1 = %w(a b c e h j l m n p)
    seq2 = %w(b c d e f j k l m r s t)

    lcs = Diff::LCS.LCS(seq1, seq2)
    diffs = Diff::LCS.diff(seq1, seq2)
    sdiff = Diff::LCS.sdiff(seq1, seq2)
    seq = Diff::LCS.traverse_sequences(seq1, seq2, callback_obj)
    bal = Diff::LCS.traverse_balanced(seq1, seq2, callback_obj)
    seq2 == Diff::LCS.patch!(seq1, diffs)
    seq1 == Diff::LCS.unpatch!(seq2, diffs)
    seq2 == Diff::LCS.patch!(seq1, sdiff)
    seq1 == Diff::LCS.unpatch!(seq2, sdiff)

    Objects can be extended with Diff::LCS:

    seq1.extend(Diff::LCS)
    lcs = seq1.lcs(seq2)
    diffs = seq1.diff(seq2)
    sdiff = seq1.sdiff(seq2)
    seq = seq1.traverse_sequences(seq2, callback_obj)
    bal = seq1.traverse_balanced(seq2, callback_obj)
    seq2 == seq1.patch!(diffs)
    seq1 == seq2.unpatch!(diffs)
    seq2 == seq1.patch!(sdiff)
    seq1 == seq2.unpatch!(sdiff)

    By requiring 'diff/lcs/array' or 'diff/lcs/string', Array or String
    will be extended for use this way.

    Copyright
    =========
    # Copyright 2004 Austin Ziegler <>
    # adapted from:
    # Algorithm::Diff (Perl) by Ned Konz <>
    # Smalltalk by Mario I. Wolczko <>
    # implements McIlroy-Hunt diff algorithm
    #
    # This program is free software. It may be redistributed and/or modified
    # under the terms of the GPL version 2 (or later), the Perl Artistic
    # licence, or the Ruby licence.
    #
    # $Id: README,v 1.5 2004/08/08 20:33:09 austin Exp $

    Footnotes
    =========
    [1] This library is called Diff::LCS because there are multiple
    Ruby libraries called Algorithm::Diff maintained by other authors.
    [2] By sequenced enumerable, I mean that the order of enumeration is
    predictable and consistent for the same set of data. While it is
    theoretically possible to generate a diff for unordereded hash, it
    will only be meaningful if the enumeration of the hashes is
    consistent. In general, this will mean that containers that behave
    like String or Array will perform best.
    [3]
    [4] ftp://st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st
    [5]
    [6] http://search.cpan.org/~nedkonz/Algorithm-Diff-1.15/
    --
    Austin Ziegler *
    * Alternate:
     
    Austin Ziegler, Aug 8, 2004
    #1
    1. Advertising

  2. On Mon, Aug 09, 2004 at 06:25:26AM +0900, Austin Ziegler wrote:
    > It is with pleasure that I announce the latest versions of Diff::LCS,
    > a pure-Ruby differencing algorithm.

    [...]
    > Version 1.1.0 is a feature release that includes all bugfixes up to
    > and including 1.0.4. In addition, it adds a new standard callback
    > (ContextDiffCallback) that works similarly to SDiffCallback but
    > produces a smaller diff set.


    I have just updated the package in the preliminary Ruby Production Archive
    (RPA) repository (http://rubyforge.org/frs/?group_id=265)

    $ rpa query diff-lcs
    Matching available ports:
    diff-lcs 1.1.0-1 LCS algorithm to compute differences between two
    enumerable containers

    As usual, it can be installed/upgraded with
    rpa install diff-lcs

    When reviewing the library while packaging, I have found some small
    quirks, which I fixed in the RPA package (note that the following is
    not the exact patch I applied):

    batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u htmldiff.orig htmldiff
    --- htmldiff.orig 2004-08-08 23:47:38 +0200
    +++ htmldiff 2004-08-08 23:48:11 +0200

    @@ -1,4 +1,4 @@
    -#! /usr/bin/env ruby
    +#!/usr/bin/env ruby
    #--
    # Copyright 2004 Austin Ziegler <>
    # adapted from:
    @@ -17,7 +17,7 @@
    require 'rubygems'
    require_gem 'diff-lcs', "1.1.0"
    require 'diff/lcs/string'
    -rescue
    +rescue LoadError
    require 'diff/lcs/string'
    end


    batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u ldiff.orig ldiff
    --- ldiff.orig 2004-08-08 23:47:41 +0200
    +++ ldiff 2004-08-08 23:48:34 +0200

    @@ -1,4 +1,4 @@
    -#!/user/bin/env ruby
    +#!/usr/bin/env ruby
    # = Diff::LCS 1.1.0
    # == ldiff Usage
    # ldiff [options] oldfile newfile
    @@ -33,7 +33,7 @@
    begin
    require 'rubygems'
    require_gem 'diff-lcs', "1.1.0"
    -rescue
    +rescue LoadError
    require 'diff/lcs'
    end

    --
    Running Debian GNU/Linux Sid (unstable)
    batsman dot geo at yahoo dot com
     
    Mauricio Fernández, Aug 8, 2004
    #2
    1. Advertising

  3. Austin Ziegler

    jm Guest

    As sad as it is I think you just made my day.


    J.

    On 09/08/2004, at 7:25 AM, Austin Ziegler wrote:

    > Version 1.1.0 is a feature release that includes all bugfixes up to
    > and including 1.0.4. In addition, it adds a new standard callback
    > (ContextDiffCallback) that works similarly to SDiffCallback but
    > produces a smaller diff set.
    >
     
    jm, Aug 9, 2004
    #3
  4. The changes the Mauricio found have been checked in. I will be
    re-releasing these files in the morning sometime. Because the changes
    are so small, I am *not* renumbering the version (e.g., it will not be
    1.1.1), but the packages will be clearly marked (e.g.,
    diff-lcs-1.1.0-1.tar.gz), excepting the Gems release, which will be
    either 1.1.0.1 or 1.1.0 depending on whether my tests indicate that
    Gems can handle 4-level versioning. Agh. I *hate* making this sort of
    error.

    If this maintaining the versioning scheme will cause problems for
    anyone, please let me know ASAP.

    -austin

    On Mon, 9 Aug 2004 07:12:29 +0900, Mauricio Fernández
    <> wrote:
    > On Mon, Aug 09, 2004 at 06:25:26AM +0900, Austin Ziegler wrote:
    > > It is with pleasure that I announce the latest versions of Diff::LCS,
    > > a pure-Ruby differencing algorithm.

    > [...]
    > > Version 1.1.0 is a feature release that includes all bugfixes up to
    > > and including 1.0.4. In addition, it adds a new standard callback
    > > (ContextDiffCallback) that works similarly to SDiffCallback but
    > > produces a smaller diff set.

    >
    > I have just updated the package in the preliminary Ruby Production Archive
    > (RPA) repository (http://rubyforge.org/frs/?group_id=265)
    >
    > $ rpa query diff-lcs
    > Matching available ports:
    > diff-lcs 1.1.0-1 LCS algorithm to compute differences between two
    > enumerable containers
    >
    > As usual, it can be installed/upgraded with
    > rpa install diff-lcs
    >
    > When reviewing the library while packaging, I have found some small
    > quirks, which I fixed in the RPA package (note that the following is
    > not the exact patch I applied):
    >
    > batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u htmldiff.orig htmldiff
    > --- htmldiff.orig 2004-08-08 23:47:38 +0200
    > +++ htmldiff 2004-08-08 23:48:11 +0200
    >
    > @@ -1,4 +1,4 @@
    > -#! /usr/bin/env ruby
    > +#!/usr/bin/env ruby
    > #--
    > # Copyright 2004 Austin Ziegler <>
    > # adapted from:
    > @@ -17,7 +17,7 @@
    > require 'rubygems'
    > require_gem 'diff-lcs', "1.1.0"
    > require 'diff/lcs/string'
    > -rescue
    > +rescue LoadError
    > require 'diff/lcs/string'
    > end
    >
    > batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u ldiff.orig ldiff
    > --- ldiff.orig 2004-08-08 23:47:41 +0200
    > +++ ldiff 2004-08-08 23:48:34 +0200
    >
    > @@ -1,4 +1,4 @@
    > -#!/user/bin/env ruby
    > +#!/usr/bin/env ruby
    > # = Diff::LCS 1.1.0
    > # == ldiff Usage
    > # ldiff [options] oldfile newfile
    > @@ -33,7 +33,7 @@
    > begin
    > require 'rubygems'
    > require_gem 'diff-lcs', "1.1.0"
    > -rescue
    > +rescue LoadError
    > require 'diff/lcs'
    > end
    >
    > --
    > Running Debian GNU/Linux Sid (unstable)
    > batsman dot geo at yahoo dot com
    >
    >



    --
    Austin Ziegler *
    * Alternate:
     
    Austin Ziegler, Aug 9, 2004
    #4
    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. Cyril Vi?ville

    diff Process under diff users

    Cyril Vi?ville, Jun 29, 2004, in forum: Perl
    Replies:
    1
    Views:
    513
    Joe Smith
    Jun 29, 2004
  2. Austin Ziegler

    [ANN] Diff::LCS 1.0

    Austin Ziegler, Jul 5, 2004, in forum: Ruby
    Replies:
    0
    Views:
    96
    Austin Ziegler
    Jul 5, 2004
  3. Austin Ziegler

    [ANN] Diff::LCS 1.0.1

    Austin Ziegler, Jul 5, 2004, in forum: Ruby
    Replies:
    0
    Views:
    114
    Austin Ziegler
    Jul 5, 2004
  4. Austin Ziegler

    [ANN] Diff::LCS 1.1.1

    Austin Ziegler, Sep 26, 2004, in forum: Ruby
    Replies:
    5
    Views:
    145
    David Ross
    Sep 26, 2004
  5. Venkat Kumar

    require 'diff/lcs/Array'

    Venkat Kumar, Feb 25, 2009, in forum: Ruby
    Replies:
    6
    Views:
    117
    James Gray
    Feb 26, 2009
Loading...

Share This Page