<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">package Algorithm::Diff::XS;
use 5.006;
use strict;
use warnings;
use vars '$VERSION';
use Algorithm::Diff;

BEGIN {
    $VERSION = '0.04';
    require XSLoader;
    XSLoader::load( __PACKAGE__, $VERSION );

    my $code = do {
        open my $fh, '&lt;', $INC{'Algorithm/Diff.pm'}
          or die "Cannot read $INC{'Algorithm/Diff.pm'}: $!";
        local $/;
        &lt;$fh&gt;;
    };

    {
        no warnings;
        local $@;
        $code =~ s/Algorithm::Diff/Algorithm::Diff::XS/g;
        $code =~ s/sub LCSidx/sub LCSidx_old/g;
        $code = "#line 1 " . __FILE__ . "\n$code";
        eval $code;
        die $@ if $@;
    }

    no warnings 'redefine';

    sub LCSidx {
        my $lcs = Algorithm::Diff::XS-&gt;_CREATE_;
        my ( @l, @r );
        for my $chunk ( $lcs-&gt;_LCS_(@_) ) {
            push @l, $chunk-&gt;[0];
            push @r, $chunk-&gt;[1];
        }
        return ( \@l, \@r );
    }
}

sub _line_map_ {
    my $ctx = shift;
    my %lines;
    push @{ $lines{ $_[$_] } }, $_ for 0 .. $#_;    # values MUST be SvIOK
    \%lines;
}

sub _LCS_ {
    my ( $ctx, $a, $b ) = @_;
    my ( $amin, $amax, $bmin, $bmax ) = ( 0, $#$a, 0, $#$b );

    while ( $amin &lt;= $amax and $bmin &lt;= $bmax and $a-&gt;[$amin] eq $b-&gt;[$bmin] ) {
        $amin++;
        $bmin++;
    }
    while ( $amin &lt;= $amax and $bmin &lt;= $bmax and $a-&gt;[$amax] eq $b-&gt;[$bmax] ) {
        $amax--;
        $bmax--;
    }

    my $h =
      $ctx-&gt;_line_map_( @$b[ $bmin .. $bmax ] ); # line numbers are off by $bmin

    return $amin + _core_loop_( $ctx, $a, $amin, $amax, $h ) + ( $#$a - $amax )
      unless wantarray;

    my @lcs = _core_loop_( $ctx, $a, $amin, $amax, $h );
    if ( $bmin &gt; 0 ) {
        $_-&gt;[1] += $bmin for @lcs;               # correct line numbers
    }

    map( [ $_ =&gt; $_ ], 0 .. ( $amin - 1 ) ),
      @lcs,
      map( [ $_ =&gt; ++$bmax ], ( $amax + 1 ) .. $#$a );
}

1;

__END__

=head1 NAME

Algorithm::Diff::XS - Algorithm::Diff with XS core loop

=head1 SYNOPSIS

    # Drop-in replacement to Algorithm::Diff, but "compact_diff"
    # and C&lt;LCSidx&gt; will run much faster for large data sets.
    use Algorithm::Diff::XS qw( compact_diff LCSidx );

=head1 DESCRIPTION

This module is a simple re-packaging of Joe Schaefer's excellent
but not very well-known L&lt;Algorithm::LCS&gt; with a drop-in interface
that simply re-uses the installed version of the L&lt;Algorithm::Diff&gt;
module.

Note that only the C&lt;LCSidx&gt; function is optimized in XS at the
moment, which means only C&lt;compact_diff&gt; will get significantly
faster for large data sets, while C&lt;diff&gt; and C&lt;sdiff&gt; will run
in identical speed as C&lt;Algorithm::Diff&gt;.

=head1 BENCHMARK

                      Rate     Algorithm::Diff Algorithm::Diff::XS
Algorithm::Diff     14.7/s                  --                -98%
Algorithm::Diff::XS  806/s               5402%                  --

The benchmarking script is as below:

    my @data = ([qw/a b d/ x 50], [qw/b a d c/ x 50]);
    cmpthese( 500, {
        'Algorithm::Diff' =&gt; sub {
            Algorithm::Diff::compact_diff(@data)
        },
        'Algorithm::Diff::XS' =&gt; sub {
            Algorithm::Diff::XS::compact_diff(@data)
        },
    });

=head1 SEE ALSO

L&lt;Algorithm::Diff&gt;, L&lt;Algorithm::LCS&gt;.

=head1 AUTHORS

Audrey Tang E&lt;lt&gt;cpan@audreyt.orgE&lt;gt&gt;

=head1 COPYRIGHT

Copyright 2008 by Audrey Tang E&lt;lt&gt;cpan@audreyt.orgE&lt;gt&gt;.

Contains derived code copyrighted 2003 by Joe Schaefer,
E&lt;lt&gt;joe+cpan@sunstarsys.comE&lt;gt&gt;.

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.

=cut
</pre></body></html>