File Coverage

blib/lib/Algorithm/Diff/Any.pm
Criterion Covered Total %
statement 40 41 97.5
branch 5 6 83.3
condition 3 3 100.0
subroutine 19 19 100.0
pod 13 13 100.0
total 80 82 97.5


line stmt bran cond sub pod time code
1             # Algorithm::Diff::Any
2             # An interface that automagically selects the XS or Pure Perl port of
3             # the diff algorithm (Algorithm::Diff or Algorithm::Diff::XS)
4             #
5             # $Id: Any.pm 10595 2009-12-23 00:29:52Z FREQUENCY@cpan.org $
6              
7             package Algorithm::Diff::Any;
8              
9 4     4   84917 use strict;
  4         9  
  4         155  
10 4     4   31 use warnings;
  4         8  
  4         117  
11 4     4   24 use Carp ();
  4         6  
  4         84  
12              
13 4     4   22 use Exporter 'import';
  4         6  
  4         565  
14             our @EXPORT_OK = qw(
15             prepare
16             LCS
17             LCSidx
18             LCS_length
19             diff
20             sdiff
21             compact_diff
22             traverse_sequences
23             traverse_balanced
24             );
25              
26             =head1 NAME
27              
28             Algorithm::Diff::Any - Perl module to find differences between files
29              
30             =head1 VERSION
31              
32             Version 1.001 ($Id: Any.pm 10595 2009-12-23 00:29:52Z FREQUENCY@cpan.org $)
33              
34             =cut
35              
36             our $VERSION = '1.001';
37             $VERSION = eval $VERSION;
38              
39             our $DRIVER = 'PP';
40              
41             # Try to load the XS version first
42             eval {
43             require Algorithm::Diff::XS;
44             $DRIVER = 'XS';
45              
46             # Import external subroutines here
47 4     4   22 no strict 'refs';
  4         7  
  4         308  
48             for my $func (@EXPORT_OK) {
49             *{$func} = \&{'Algorithm::Diff::XS::' . $func};
50             }
51             };
52              
53             # Fall back on the Perl version
54             if ($@) {
55             require Algorithm::Diff;
56              
57             # Import external subroutines here
58 4     4   19 no strict 'refs';
  4         9  
  4         2754  
59             for my $func (@EXPORT_OK) {
60             *{$func} = \&{'Algorithm::Diff::' . $func};
61             }
62             }
63              
64             =head1 DESCRIPTION
65              
66             This is a simple module to select the best available implementation of the
67             standard C algorithm, which works by effectively trying to solve the
68             Longest Common Subsequence (LCS) problem. This algorithm is described in:
69             I, CACM, vol.20,
70             no.5, pp.350-353, May 1977.
71              
72             However, it is algorithmically rather complicated to solve the LCS problem;
73             for arbitrary sequences, it is an NP-hard problem. Simply comparing two
74             strings together of lengths I and I is B. Consequently, this
75             means the algorithm necessarily has some tight loops, which, for a dynamic
76             language like Perl, can be slow.
77              
78             In order to speed up processing, a fast (C/XS-based) implementation of the
79             algorithm's core loop was implemented. It can confer a noticable performance
80             advantage (benchmarks show a 54x speedup for the C routine).
81              
82             =head1 SYNOPSIS
83              
84             use Algorithm::Diff::Any;
85              
86             my $diff = Algorithm::Diff::Any->new(\@seq1, \@seq2);
87              
88             For complete usage details, see the Object-Oriented interface description
89             for the L module.
90              
91             =head1 PURPOSE
92              
93             The intent of this module is to provide single simple interface to the two
94             (presumably) compatible implementations of this module, namely,
95             L and L.
96              
97             If, for some reason, you need to determine what version of the module is
98             actually being included by C, then:
99              
100             print 'Backend type: ', $Algorithm::Diff::Any::DRIVER, "\n";
101              
102             In order to force use of one or the other, simply load the appropriate module:
103              
104             use Algorithm::Diff::XS;
105             my $diff = Algorithm::Diff::XS->new();
106             # or
107             use Algorithm::Diff;
108             my $diff = Algorithm::Diff->new();
109              
110             =head1 COMPATIBILITY
111              
112             This module was tested under Perl 5.10.1, using Debian Linux. However, because
113             it's Pure Perl and doesn't do anything too obscure, it should be compatible
114             with any version of Perl that supports its prerequisite modules.
115              
116             If you encounter any problems on a different version or architecture, please
117             contact the maintainer.
118              
119             =head1 EXPORTABLE FUNCTIONS
120              
121             The following functions are available for import into your namespace:
122              
123             =over
124              
125             =item * prepare
126              
127             =item * LCS
128              
129             =item * LCSidx
130              
131             =item * LCS_length
132              
133             =item * diff
134              
135             =item * sdiff
136              
137             =item * compact_diff
138              
139             =item * traverse_sequences
140              
141             =item * traverse_balanced
142              
143             =back
144              
145             For full documentation, see the relevant functional descriptions in the Pure
146             Perl implementation, L.
147              
148             =cut
149              
150             =head1 METHODS
151              
152             =head2 new
153              
154             Algorithm::Diff::Any->new( \@seq1, \@seq2, \%opts );
155              
156             Creates a C object, based upon either the optimized
157             C/XS version of the algorithm, L, or falls back to
158             the Pure Perl implementation, L.
159              
160             Example code:
161              
162             my $diff = Algorithm::Diff::Any->new( \@seq1, \@seq2 );
163             # or with options
164             my $diff = Algorithm::Diff::Any->new( \@seq1, \@seq2, \%opts );
165              
166             This method will return an appropriate B object or
167             throw an exception on error.
168              
169             =cut
170              
171             # Wrappers around the actual methods
172             sub new {
173 15     15 1 12582 my ($class, $seq1, $seq2, $opts) = @_;
174              
175 15 100       140 Carp::croak('You must call this as a class method') if ref($class);
176              
177 14 100 100     383 Carp::croak('You must provide two sequences to compare as array refs')
178             unless (ref($seq1) eq 'ARRAY' && ref($seq2) eq 'ARRAY');
179              
180 12         18 my $self = {
181             };
182              
183 12 50       48 if ($DRIVER eq 'XS') {
184 12         70 $self->{backend} = Algorithm::Diff::XS->new($seq1, $seq2, $opts);
185             }
186             else {
187 0         0 $self->{backend} = Algorithm::Diff->new($seq1, $seq2, $opts);
188             }
189              
190 12         1665 bless($self, $class);
191 12         29 return $self;
192             }
193              
194             =head2 Next
195              
196             $diff->Next( $count )
197              
198             See L for method documentation.
199              
200             =cut
201              
202             sub Next {
203 194     194 1 23229 shift->{backend}->Next(@_);
204             }
205              
206             =head2 Prev
207              
208             $diff->Prev( $count )
209              
210             See L for method documentation.
211              
212             =cut
213              
214             sub Prev {
215 109     109 1 14305 shift->{backend}->Prev(@_);
216             }
217              
218             =head2 Reset
219              
220             $diff->Reset( $pos )
221              
222             See L for method documentation.
223              
224             =cut
225              
226             sub Reset {
227 55     55 1 7287 my $self = shift;
228 55         173 $self->{backend}->Reset(@_);
229 55         506 return $self;
230             }
231              
232             =head2 Copy
233              
234             $diff->Copy( $pos, $newBase )
235              
236             See L for method documentation.
237              
238             =cut
239              
240             sub Copy {
241 54     54 1 2518 shift->{backend}->Copy(@_);
242             }
243              
244             =head2 Base
245              
246             $diff->Base( $newBase )
247              
248             See L for method documentation.
249              
250             =cut
251              
252             sub Base {
253 76     76 1 8887 shift->{backend}->Base(@_);
254             }
255              
256             =head2 Diff
257              
258             $diff->Diff( )
259              
260             See L for method documentation.
261              
262             =cut
263              
264             sub Diff {
265 71     71 1 4134 shift->{backend}->Diff(@_);
266             }
267              
268             =head2 Same
269              
270             See L for method documentation.
271              
272             Code example:
273              
274             $diff->Same( )
275              
276             =cut
277              
278             sub Same {
279 146     146 1 24356 shift->{backend}->Same(@_);
280             }
281              
282             =head2 Items
283              
284             $diff->Items( $seqNum )
285              
286             See L for method documentation.
287              
288             =cut
289              
290             sub Items {
291 155     155 1 18324 shift->{backend}->Items(@_);
292             }
293              
294             =head2 Range
295              
296             $diff->Range( $seqNum, $base )
297              
298             See L for method documentation.
299              
300             =cut
301              
302             sub Range {
303 245     245 1 34464 shift->{backend}->Range(@_);
304             }
305              
306             =head2 Min
307              
308             $diff->Min( $seqNum, $base )
309              
310             See L for method documentation.
311              
312             =cut
313              
314             sub Min {
315 31     31 1 12484 shift->{backend}->Min(@_);
316             }
317              
318             =head2 Max
319              
320             $diff->Max( $seqNum, $base )
321              
322             See L for method documentation.
323              
324             =cut
325              
326             sub Max {
327 31     31 1 12710 shift->{backend}->Max(@_);
328             }
329              
330             =head2 Get
331              
332             $diff->Get( @names )
333              
334             See L for method documentation.
335              
336             =cut
337              
338             sub Get {
339 61     61 1 6728 shift->{backend}->Get(@_);
340             }
341              
342             =head1 AUTHOR
343              
344             Jonathan Yu Ejawnsy@cpan.orgE
345              
346             =head2 CONTRIBUTORS
347              
348             Your name here ;-)
349              
350             =head1 ACKNOWLEDGEMENTS
351              
352             =over
353              
354             =item *
355              
356             Many thanks go to the primary authors and maintainers of the Pure Perl
357             implementation of this algorithm, notably:
358              
359             =over
360              
361             =item * Mark-Jason Dominus
362              
363             =item * Ned Konz
364              
365             =item * Tye McQueen
366              
367             =back
368              
369             =item *
370              
371             Thanks to Audrey Tang , author of L,
372             for recognizing the value of Joe Schaefer's
373             work on L
374              
375             =item *
376              
377             Neither the Pure Perl nor C/XS-based implementations of this module would
378             have been possible without the work of James W. Hunt (Stanford University)
379             and Thomas G. Szymanski (Princeton University), authors of the often-cited
380             paper for computing longest common subsequences.
381              
382             In their abstract, they claim that a running time of B can be
383             expected, with a worst-case time of B for two subsequences of
384             length I.
385              
386             =back
387              
388             =head1 SUPPORT
389              
390             You can find documentation for this module with the perldoc command.
391              
392             perldoc Algorithm::Diff::Any
393              
394             You can also look for information at:
395              
396             =over
397              
398             =item * AnnoCPAN: Annotated CPAN documentation
399              
400             L
401              
402             =item * CPAN Ratings
403              
404             L
405              
406             =item * Search CPAN
407              
408             L
409              
410             =item * CPAN Request Tracker
411              
412             L
413              
414             =item * CPAN Testing Service (Kwalitee Tests)
415              
416             L
417              
418             =item * CPAN Testers Platform Compatibility Matrix
419              
420             L
421              
422             =back
423              
424             =head1 REPOSITORY
425              
426             You can access the most recent development version of this module at:
427              
428             L
429              
430             If you are a CPAN developer and would like to make modifications to the code
431             base, please contact Adam Kennedy Eadamk@cpan.orgE, the repository
432             administrator. I only ask that you contact me first to discuss the changes you
433             wish to make to the distribution.
434              
435             =head1 FEEDBACK
436              
437             Please send relevant comments, rotten tomatoes and suggestions directly to the
438             maintainer noted above.
439              
440             If you have a bug report or feature request, please file them on the CPAN
441             Request Tracker at L. If you are able to submit your bug
442             report in the form of failing unit tests, you are B encouraged to do
443             so.
444              
445             =head1 SEE ALSO
446              
447             L, the classic reference implementation for finding the
448             differences between two chunks of text in Perl. It is based on the algorithm
449             described in I,
450             CACM, vol.20, no.5, pp.350-353, May 1977.
451              
452             L, the C/XS optimized version of Algorithm::Diff, which
453             will be used automatically if available.
454              
455             =head1 CAVEATS
456              
457             =head2 KNOWN BUGS
458              
459             There are no known bugs as of this release.
460              
461             =head2 LIMITATIONS
462              
463             =over
464              
465             =item *
466              
467             It is not currently known whether L (Pure Perl version)
468             and L (C/XS implementation) produce the same output.
469             The algorithms may not be equivalent (source code-wise) so they may produce
470             different output under some as-yet-undiscovered conditions.
471              
472             =item *
473              
474             Any potential performance gains will be limited by those features implemented
475             by L. As of time of writing, this is limited to the
476             C subroutine.
477              
478             =back
479              
480             =head1 QUALITY ASSURANCE METRICS
481              
482             =head2 TEST COVERAGE
483              
484             -------------------------- ------ ------ ------ ------ ------ ------
485             File stmt bran cond sub pod total
486             -------------------------- ------ ------ ------ ------ ------ ------
487             lib/Algorithm/Diff/Any.pm 100.0 100.0 100.0 100.0 100.0 100.0
488             Total 100.0 100.0 100.0 100.0 100.0 100.0
489              
490             =head1 LICENSE
491              
492             Copyright (C) 2009 by Jonathan Yu
493              
494             This package is distributed under the same terms as Perl itself. Please
495             see the F file included in this distribution for full details of
496             these terms.
497              
498             =head1 DISCLAIMER OF WARRANTY
499              
500             This software is provided by the copyright holders and contributors
501             "AS IS" and ANY EXPRESS OR IMPLIED WARRANTIES, including, but not
502             limited to, the IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
503             A PARTICULAR PURPOSE ARE DISCLAIMED.
504              
505             In no event shall the copyright owner or contributors be liable for
506             any direct, indirect, incidental, special, exemplary or consequential
507             damages (including, but not limited to, procurement of substitute
508             goods or services; loss of use, data or profits; or business
509             interruption) however caused and on any theory of liability, whether
510             in contract, strict liability or tort (including negligence or
511             otherwise) arising in any way out of the use of this software, even if
512             advised of the possibility of such damage.
513              
514             =cut
515              
516             1;