package Algorithm::LCS;
use 5.008;
use strict;
use warnings;
our $VERSION = '1.04';
require XSLoader;
XSLoader::load('Algorithm::LCS', $VERSION);
##############################
# code adapted from Algorithm::Diff
sub line_map {
my $ctx = shift;
my %lines;
push @{ $lines{$_[$_]} }, $_ for 0..$#_; # values MUST be SvIOK
\%lines;
}
sub callback {
my ($ctx, @b) = @_;
my $h = $ctx->line_map(@b);
sub { @_ ? _core_loop($ctx, $_[0], 0, $#{$_[0]}, $h) : @b }
}
sub LCS {
my ($ctx, $a, $b) = @_;
my ($amin, $amax, $bmin, $bmax) = (0, $#$a, 0, $#$b);
while ($amin <= $amax and $bmin <= $bmax and $a->[$amin] eq $b->[$bmin]) {
$amin++;
$bmin++;
}
while ($amin <= $amax and $bmin <= $bmax and $a->[$amax] eq $b->[$bmax]) {
$amax--;
$bmax--;
}
my $h = $ctx->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 > 0) {
$_->[1] += $bmin for @lcs; # correct line numbers
}
map([$_ => $_], 0 .. ($amin-1)),
@lcs,
map([$_ => ++$bmax], ($amax+1) .. $#$a);
}
1;
__END__
=head1 NAME
Algorithm::LCS - Fast (XS) implementation of the
Longest Common Subsequence (LCS) Algorithm
=head1 SYNOPSIS
use Algorithm::LCS;
$alg = Algorithm::LCS->new;
@lcs = $alg->LCS(\@a,\@b);
$cb = $alg->callback(@b); # closure
@lcs = $cb->(\@a); # same result as prior LCS() call
=head1 ABSTRACT
Algorithm::LCS reimplements Algorithm::Diff's core loop in XS,
and provides a simple OO interface to it.
Extract from the Algorithm::Diff v1.15 manpage:
The algorithm is that described in
I<A Fast Algorithm for Computing Longest Common Subsequences>,
CACM, vol.20, no.5, pp.350-353, May 1977, with a few
minor improvements to improve the speed.
=head1 DESCRIPTION
=head2 CONSTRUCTOR
=over 4
=item new()
Creates a new object which maintains internal storage areas
for the LCS computation. Use one of these per concurrent
LCS() call.
=back
=head2 METHODS
=over 4
=item line_map(@lines)
Send @lines to a hashref containing elements of the form
value => [(increasing) list of matching indices]
=item callback(@lines)
Generates a closure capturing the object and line_map hash for @lines.
Most useful when computing multiple LCSs against a single file.
=item LCS(\@a,\@b)
Finds a Longest Common Subsequence, taking two arrayrefs as method
arguments. In scalar context the return value is the length of the
subsequence. In list context it yields a list of corresponding
indices, which are represented by 2-element array refs. See the
L<Algorithm::Diff> manpage for more details.
=back
=head2 EXPORT
None by design.
=head1 SEE ALSO
Algorithm::Diff
=head1 AUTHOR
Joe Schaefer, E<lt>joe+cpan@sunstarsys.comE<gt>
=head1 COPYRIGHT AND LICENSE
Copyright 2003 by Joe Schaefer
This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.
=cut