Skip to content

Instantly share code, notes, and snippets.

@hoehrmann
Created October 25, 2013 17:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hoehrmann/7158853 to your computer and use it in GitHub Desktop.
Save hoehrmann/7158853 to your computer and use it in GitHub Desktop.
Takes the output of Algorithm::Diff::compact_diff and turns it into what Algorithm::Diff::sdiff would have returned. This may be useful in conjunction with Algorithm::Diff::XS which speeds up compact_diff considerably but not sdiff.
#!perl -w
use Modern::Perl;
use Algorithm::Diff::XS;
use Test::More;
use Data::Random qw/rand_chars/;
sub compact_diff_to_sdiff {
my ($a, $b, @cdiff) = @_;
my @temp;
my $add = sub {
my ($op, $ax, $bx, $count) = @_;
push @temp, [$op,
defined $ax ? $ax + $_ : $ax,
defined $bx ? $bx + $_ : $bx] for 0 .. $count - 1;
};
for (my $ix = 0; $ix < @cdiff - 2; $ix += 2) {
my ($a_from, $b_from, $a2_from, $b2_from) =
@cdiff[ $ix .. $ix + 3 ];
my $a_length = ($a2_from - 1) - $a_from + 1;
my $b_length = ($b2_from - 1) - $b_from + 1;
if ($ix & 2) {
# modified
if ($a_from == $a2_from) {
# addition
$add->('+', undef, $b_from, $b_length);
} elsif ($b_from == $b2_from) {
# removal
$add->('-', $a_from, undef, $a_length);
} else {
# change
if ($a_length < $b_length) {
$add->('c', $a_from, $b_from, $a_length);
$add->('+', undef, $b_from + $a_length, $b_length - $a_length);
} elsif ($a_length > $b_length) {
$add->('c', $a_from, $b_from, $b_length);
$add->('-', $a_from + $b_length, undef, $a_length - $b_length);
} else {
$add->('c', $a_from, $b_from, $a_length);
}
}
} else {
# unchanged
$add->('u', $a_from, $b_from, $a_length);
}
}
$_->[1] = defined $_->[1] ? $a->[$_->[1]] : '' for @temp;
$_->[2] = defined $_->[2] ? $b->[$_->[2]] : '' for @temp;
@temp;
}
for (0 .. 1000) {
my @x = rand_chars(set => 'all', min => 0, max => 26);
my @y = rand_chars(set => 'all', min => 0, max => 26);
my @cdiff = Algorithm::Diff::XS::compact_diff(\@x, \@y);
my @sdiff = compact_diff_to_sdiff(\@x, \@y, @cdiff);
my @sdiff_orig = Algorithm::Diff::XS::sdiff(\@x, \@y);
is_deeply(\@sdiff, \@sdiff_orig,
'compact_diff_to_sdiff(compact_diff(...)) == sdiff(...)');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment