1Algorithm::Diff(3) User Contributed Perl Documentation Algorithm::Diff(3)
2
6 Algorithm::Diff - Compute `intelligent' differences between two files /
7 lists
8
10 require Algorithm::Diff;
11 # This example produces traditional 'diff' output:
13 my $diff = Algorithm::Diff->new( \@seq1, \@seq2 );
15 $diff->Base( 1 ); # Return line numbers, not indices
17 while( $diff->Next() ) {
18 next if $diff->Same();
19 my $sep = '';
20 if( ! $diff->Items(2) ) {
21 printf "%d,%dd%d\n",
22 $diff->Get(qw( Min1 Max1 Max2 ));
23 } elsif( ! $diff->Items(1) ) {
24 printf "%da%d,%d\n",
25 $diff->Get(qw( Max1 Min2 Max2 ));
26 } else {
27 $sep = "---\n";
28 printf "%d,%dc%d,%d\n",
29 $diff->Get(qw( Min1 Max1 Min2 Max2 ));
30 }
31 print "< $_" for $diff->Items(1);
32 print $sep;
33 print "> $_" for $diff->Items(2);
34 }
35 # Alternate interfaces:
38 use Algorithm::Diff qw(
40 LCS LCS_length LCSidx
41 diff sdiff compact_diff
42 traverse_sequences traverse_balanced );
43 @lcs = LCS( \@seq1, \@seq2 );
45 $lcsref = LCS( \@seq1, \@seq2 );
46 $count = LCS_length( \@seq1, \@seq2 );
47 ( $seq1idxref, $seq2idxref ) = LCSidx( \@seq1, \@seq2 );
49 # Complicated interfaces:
52 @diffs = diff( \@seq1, \@seq2 );
54 @sdiffs = sdiff( \@seq1, \@seq2 );
56 @cdiffs = compact_diff( \@seq1, \@seq2 );
58 traverse_sequences(
60 \@seq1,
61 \@seq2,
62 { MATCH => \&callback1,
63 DISCARD_A => \&callback2,
64 DISCARD_B => \&callback3,
65 },
66 \&key_generator,
67 @extra_args,
68 );
69 traverse_balanced(
71 \@seq1,
72 \@seq2,
73 { MATCH => \&callback1,
74 DISCARD_A => \&callback2,
75 DISCARD_B => \&callback3,
76 CHANGE => \&callback4,
77 },
78 \&key_generator,
79 @extra_args,
80 );
81
83 (by Mark-Jason Dominus)
84 I once read an article written by the authors of "diff"; they said that
86 they worked very hard on the algorithm until they found the right one.
87 I think what they ended up using (and I hope someone will correct me,
89 because I am not very confident about this) was the `longest common
90 subsequence' method. In the LCS problem, you have two sequences of
91 items:
92 a b c d f g h j q z
94 a b c d e f g i j k r x y z
96 and you want to find the longest sequence of items that is present in
98 both original sequences in the same order. That is, you want to find a
99 new sequence S which can be obtained from the first sequence by
100 deleting some items, and from the second sequence by deleting other
101 items. You also want S to be as long as possible. In this case S is
102 a b c d f g j z
104 From there it's only a small step to get diff-like output:
106 e h i k q r x y
108 + - + + - + + +
109 This module solves the LCS problem. It also includes a canned function
111 to generate "diff"-like output.
112 It might seem from the example above that the LCS of two sequences is
114 always pretty obvious, but that's not always the case, especially when
115 the two sequences have many repeated elements. For example, consider
116 a x b y c z p d q
118 a b c a x b y c z
119 A naive approach might start by matching up the "a" and "b" that appear
121 at the beginning of each sequence, like this:
122 a x b y c z p d q
124 a b c a b y c z
125 This finds the common subsequence "a b c z". But actually, the LCS is
127 "a x b y c z":
128 a x b y c z p d q
130 a b c a x b y c z
131 or
133 a x b y c z p d q
135 a b c a x b y c z
136
138 (See also the README file and several example scripts include with this
139 module.)
140 This module now provides an object-oriented interface that uses less
142 memory and is easier to use than most of the previous procedural
143 interfaces. It also still provides several exportable functions.
144 We'll deal with these in ascending order of difficulty: "LCS",
145 "LCS_length", "LCSidx", OO interface, "prepare", "diff", "sdiff",
146 "traverse_sequences", and "traverse_balanced".
147 "LCS"
149 Given references to two lists of items, LCS returns an array containing
150 their longest common subsequence. In scalar context, it returns a
151 reference to such a list.
152 @lcs = LCS( \@seq1, \@seq2 );
154 $lcsref = LCS( \@seq1, \@seq2 );
155 "LCS" may be passed an optional third parameter; this is a CODE
157 reference to a key generation function. See "KEY GENERATION
158 FUNCTIONS".
159 @lcs = LCS( \@seq1, \@seq2, \&keyGen, @args );
161 $lcsref = LCS( \@seq1, \@seq2, \&keyGen, @args );
162 Additional parameters, if any, will be passed to the key generation
164 routine.
165 "LCS_length"
167 This is just like "LCS" except it only returns the length of the
168 longest common subsequence. This provides a performance gain of about
169 9% compared to "LCS".
170 "LCSidx"
172 Like "LCS" except it returns references to two arrays. The first array
173 contains the indices into @seq1 where the LCS items are located. The
174 second array contains the indices into @seq2 where the LCS items are
175 located.
176 Therefore, the following three lists will contain the same values:
178 my( $idx1, $idx2 ) = LCSidx( \@seq1, \@seq2 );
180 my @list1 = @seq1[ @$idx1 ];
181 my @list2 = @seq2[ @$idx2 ];
182 my @list3 = LCS( \@seq1, \@seq2 );
183 "new"
185 $diff = Algorithm::Diffs->new( \@seq1, \@seq2 );
186 $diff = Algorithm::Diffs->new( \@seq1, \@seq2, \%opts );
187 "new" computes the smallest set of additions and deletions necessary to
189 turn the first sequence into the second and compactly records them in
190 the object.
191 You use the object to iterate over hunks, where each hunk represents a
193 contiguous section of items which should be added, deleted, replaced,
194 or left unchanged.
195 The following summary of all of the methods looks a lot like Perl
197 code but some of the symbols have different meanings:
198 [ ] Encloses optional arguments
200 : Is followed by the default value for an optional argument
201 | Separates alternate return results
202 Method summary:
204 $obj = Algorithm::Diff->new( \@seq1, \@seq2, [ \%opts ] );
206 $pos = $obj->Next( [ $count : 1 ] );
207 $revPos = $obj->Prev( [ $count : 1 ] );
208 $obj = $obj->Reset( [ $pos : 0 ] );
209 $copy = $obj->Copy( [ $pos, [ $newBase ] ] );
210 $oldBase = $obj->Base( [ $newBase ] );
211 Note that all of the following methods "die" if used on an object
213 that is "reset" (not currently pointing at any hunk).
214 $bits = $obj->Diff( );
216 @items|$cnt = $obj->Same( );
217 @items|$cnt = $obj->Items( $seqNum );
218 @idxs |$cnt = $obj->Range( $seqNum, [ $base ] );
219 $minIdx = $obj->Min( $seqNum, [ $base ] );
220 $maxIdx = $obj->Max( $seqNum, [ $base ] );
221 @values = $obj->Get( @names );
222 Passing in "undef" for an optional argument is always treated the
224 same as if no argument were passed in.
225 "Next"
227 $pos = $diff->Next(); # Move forward 1 hunk
229 $pos = $diff->Next( 2 ); # Move forward 2 hunks
230 $pos = $diff->Next(-5); # Move backward 5 hunks
231 "Next" moves the object to point at the next hunk. The object
233 starts out "reset", which means it isn't pointing at any hunk. If
234 the object is reset, then "Next()" moves to the first hunk.
235 "Next" returns a true value iff the move didn't go past the last
237 hunk. So Next(0) will return true iff the object is not reset.
238 Actually, "Next" returns the object's new position, which is a
240 number between 1 and the number of hunks (inclusive), or returns a
241 false value.
242 "Prev"
244 "Prev($N)" is almost identical to "Next(-$N)"; it moves to the $Nth
246 previous hunk. On a 'reset' object, "Prev()" [and "Next(-1)"] move
247 to the last hunk.
248 The position returned by "Prev" is relative to the end of the
250 hunks; -1 for the last hunk, -2 for the second-to-last, etc.
251 "Reset"
253 $diff->Reset(); # Reset the object's position
255 $diff->Reset($pos); # Move to the specified hunk
256 $diff->Reset(1); # Move to the first hunk
257 $diff->Reset(-1); # Move to the last hunk
258 "Reset" returns the object, so, for example, you could use
260 "$diff->Reset()->Next(-1)" to get the number of hunks.
261 "Copy"
263 $copy = $diff->Copy( $newPos, $newBase );
265 "Copy" returns a copy of the object. The copy and the original
267 object share most of their data, so making copies takes very little
268 memory. The copy maintains its own position (separate from the
269 original), which is the main purpose of copies. It also maintains
270 its own base.
271 By default, the copy's position starts out the same as the original
273 object's position. But "Copy" takes an optional first argument to
274 set the new position, so the following three snippets are
275 equivalent:
276 $copy = $diff->Copy($pos);
278 $copy = $diff->Copy();
280 $copy->Reset($pos);
281 $copy = $diff->Copy()->Reset($pos);
283 "Copy" takes an optional second argument to set the base for the
285 copy. If you wish to change the base of the copy but leave the
286 position the same as in the original, here are two equivalent ways:
287 $copy = $diff->Copy();
289 $copy->Base( 0 );
290 $copy = $diff->Copy(undef,0);
292 Here are two equivalent way to get a "reset" copy:
294 $copy = $diff->Copy(0);
296 $copy = $diff->Copy()->Reset();
298 "Diff"
300 $bits = $obj->Diff();
302 "Diff" returns a true value iff the current hunk contains items
304 that are different between the two sequences. It actually returns
305 one of the follow 4 values:
306 3 "3==(1|2)". This hunk contains items from @seq1 and the items
308 from @seq2 that should replace them. Both sequence 1 and 2
309 contain changed items so both the 1 and 2 bits are set.
310 2 This hunk only contains items from @seq2 that should be
312 inserted (not items from @seq1). Only sequence 2 contains
313 changed items so only the 2 bit is set.
314 1 This hunk only contains items from @seq1 that should be deleted
316 (not items from @seq2). Only sequence 1 contains changed items
317 so only the 1 bit is set.
318 0 This means that the items in this hunk are the same in both
320 sequences. Neither sequence 1 nor 2 contain changed items so
321 neither the 1 nor the 2 bits are set.
322 "Same"
324 "Same" returns a true value iff the current hunk contains items
326 that are the same in both sequences. It actually returns the list
327 of items if they are the same or an empty list if they aren't. In
328 a scalar context, it returns the size of the list.
329 "Items"
331 $count = $diff->Items(2);
333 @items = $diff->Items($seqNum);
334 "Items" returns the (number of) items from the specified sequence
336 that are part of the current hunk.
337 If the current hunk contains only insertions, then
339 "$diff->Items(1)" will return an empty list (0 in a scalar
340 context). If the current hunk contains only deletions, then
341 "$diff->Items(2)" will return an empty list (0 in a scalar
342 context).
343 If the hunk contains replacements, then both "$diff->Items(1)" and
345 "$diff->Items(2)" will return different, non-empty lists.
346 Otherwise, the hunk contains identical items and all of the
348 following will return the same lists:
349 @items = $diff->Items(1);
351 @items = $diff->Items(2);
352 @items = $diff->Same();
353 "Range"
355 $count = $diff->Range( $seqNum );
357 @indices = $diff->Range( $seqNum );
358 @indices = $diff->Range( $seqNum, $base );
359 "Range" is like "Items" except that it returns a list of indices to
361 the items rather than the items themselves. By default, the index
362 of the first item (in each sequence) is 0 but this can be changed
363 by calling the "Base" method. So, by default, the following two
364 snippets return the same lists:
365 @list = $diff->Items(2);
367 @list = @seq2[ $diff->Range(2) ];
368 You can also specify the base to use as the second argument. So
370 the following two snippets always return the same lists:
371 @list = $diff->Items(1);
373 @list = @seq1[ $diff->Range(1,0) ];
374 "Base"
376 $curBase = $diff->Base();
378 $oldBase = $diff->Base($newBase);
379 "Base" sets and/or returns the current base (usually 0 or 1) that
381 is used when you request range information. The base defaults to 0
382 so that range information is returned as array indices. You can
383 set the base to 1 if you want to report traditional line numbers
384 instead.
385 "Min"
387 $min1 = $diff->Min(1);
389 $min = $diff->Min( $seqNum, $base );
390 "Min" returns the first value that "Range" would return (given the
392 same arguments) or returns "undef" if "Range" would return an empty
393 list.
394 "Max"
396 "Max" returns the last value that "Range" would return or "undef".
398 "Get"
400 ( $n, $x, $r ) = $diff->Get(qw( min1 max1 range1 ));
402 @values = $diff->Get(qw( 0min2 1max2 range2 same base ));
403 "Get" returns one or more scalar values. You pass in a list of the
405 names of the values you want returned. Each name must match one of
406 the following regexes:
407 /^(-?\d+)?(min|max)[12]$/i
409 /^(range[12]|same|diff|base)$/i
410 The 1 or 2 after a name says which sequence you want the
412 information for (and where allowed, it is required). The optional
413 number before "min" or "max" is the base to use. So the following
414 equalities hold:
415 $diff->Get('min1') == $diff->Min(1)
417 $diff->Get('0min2') == $diff->Min(2,0)
418 Using "Get" in a scalar context when you've passed in more than one
420 name is a fatal error ("die" is called).
421 "prepare"
423 Given a reference to a list of items, "prepare" returns a reference to
424 a hash which can be used when comparing this sequence to other
425 sequences with "LCS" or "LCS_length".
426 $prep = prepare( \@seq1 );
428 for $i ( 0 .. 10_000 )
429 {
430 @lcs = LCS( $prep, $seq[$i] );
431 # do something useful with @lcs
432 }
433 "prepare" may be passed an optional third parameter; this is a CODE
435 reference to a key generation function. See "KEY GENERATION
436 FUNCTIONS".
437 $prep = prepare( \@seq1, \&keyGen );
439 for $i ( 0 .. 10_000 )
440 {
441 @lcs = LCS( $seq[$i], $prep, \&keyGen );
442 # do something useful with @lcs
443 }
444 Using "prepare" provides a performance gain of about 50% when calling
446 LCS many times compared with not preparing.
447 "diff"
449 @diffs = diff( \@seq1, \@seq2 );
450 $diffs_ref = diff( \@seq1, \@seq2 );
451 "diff" computes the smallest set of additions and deletions necessary
453 to turn the first sequence into the second, and returns a description
454 of these changes. The description is a list of hunks; each hunk
455 represents a contiguous section of items which should be added,
456 deleted, or replaced. (Hunks containing unchanged items are not
457 included.)
458 The return value of "diff" is a list of hunks, or, in scalar context, a
460 reference to such a list. If there are no differences, the list will
461 be empty.
462 Here is an example. Calling "diff" for the following two sequences:
464 a b c e h j l m n p
466 b c d e f j k l m r s t
467 would produce the following list:
469 (
471 [ [ '-', 0, 'a' ] ],
472 [ [ '+', 2, 'd' ] ],
474 [ [ '-', 4, 'h' ],
476 [ '+', 4, 'f' ] ],
477 [ [ '+', 6, 'k' ] ],
479 [ [ '-', 8, 'n' ],
481 [ '-', 9, 'p' ],
482 [ '+', 9, 'r' ],
483 [ '+', 10, 's' ],
484 [ '+', 11, 't' ] ],
485 )
486 There are five hunks here. The first hunk says that the "a" at
488 position 0 of the first sequence should be deleted ("-"). The second
489 hunk says that the "d" at position 2 of the second sequence should be
490 inserted ("+"). The third hunk says that the "h" at position 4 of the
491 first sequence should be removed and replaced with the "f" from
492 position 4 of the second sequence. And so on.
493 "diff" may be passed an optional third parameter; this is a CODE
495 reference to a key generation function. See "KEY GENERATION
496 FUNCTIONS".
497 Additional parameters, if any, will be passed to the key generation
499 routine.
500 "sdiff"
502 @sdiffs = sdiff( \@seq1, \@seq2 );
503 $sdiffs_ref = sdiff( \@seq1, \@seq2 );
504 "sdiff" computes all necessary components to show two sequences and
506 their minimized differences side by side, just like the Unix-utility
507 sdiff does:
508 same same
510 before | after
511 old < -
512 - > new
513 It returns a list of array refs, each pointing to an array of display
515 instructions. In scalar context it returns a reference to such a list.
516 If there are no differences, the list will have one entry per item,
517 each indicating that the item was unchanged.
518 Display instructions consist of three elements: A modifier indicator
520 ("+": Element added, "-": Element removed, "u": Element unmodified,
521 "c": Element changed) and the value of the old and new elements, to be
522 displayed side-by-side.
523 An "sdiff" of the following two sequences:
525 a b c e h j l m n p
527 b c d e f j k l m r s t
528 results in
530 ( [ '-', 'a', '' ],
532 [ 'u', 'b', 'b' ],
533 [ 'u', 'c', 'c' ],
534 [ '+', '', 'd' ],
535 [ 'u', 'e', 'e' ],
536 [ 'c', 'h', 'f' ],
537 [ 'u', 'j', 'j' ],
538 [ '+', '', 'k' ],
539 [ 'u', 'l', 'l' ],
540 [ 'u', 'm', 'm' ],
541 [ 'c', 'n', 'r' ],
542 [ 'c', 'p', 's' ],
543 [ '+', '', 't' ],
544 )
545 "sdiff" may be passed an optional third parameter; this is a CODE
547 reference to a key generation function. See "KEY GENERATION
548 FUNCTIONS".
549 Additional parameters, if any, will be passed to the key generation
551 routine.
552 "compact_diff"
554 "compact_diff" is much like "sdiff" except it returns a much more
555 compact description consisting of just one flat list of indices. An
556 example helps explain the format:
557 my @a = qw( a b c e h j l m n p );
559 my @b = qw( b c d e f j k l m r s t );
560 @cdiff = compact_diff( \@a, \@b );
561 # Returns:
562 # @a @b @a @b
563 # start start values values
564 ( 0, 0, # =
565 0, 0, # a !
566 1, 0, # b c = b c
567 3, 2, # ! d
568 3, 3, # e = e
569 4, 4, # f ! h
570 5, 5, # j = j
571 6, 6, # ! k
572 6, 7, # l m = l m
573 8, 9, # n p ! r s t
574 10, 12, #
575 );
576 The 0th, 2nd, 4th, etc. entries are all indices into @seq1 (@a in the
578 above example) indicating where a hunk begins. The 1st, 3rd, 5th, etc.
579 entries are all indices into @seq2 (@b in the above example) indicating
580 where the same hunk begins.
581 So each pair of indices (except the last pair) describes where a hunk
583 begins (in each sequence). Since each hunk must end at the item just
584 before the item that starts the next hunk, the next pair of indices can
585 be used to determine where the hunk ends.
586 So, the first 4 entries (0..3) describe the first hunk. Entries 0 and
588 1 describe where the first hunk begins (and so are always both 0).
589 Entries 2 and 3 describe where the next hunk begins, so subtracting 1
590 from each tells us where the first hunk ends. That is, the first hunk
591 contains items $diff[0] through "$diff[2] - 1" of the first sequence
592 and contains items $diff[1] through "$diff[3] - 1" of the second
593 sequence.
594 In other words, the first hunk consists of the following two lists of
596 items:
597 # 1st pair 2nd pair
599 # of indices of indices
600 @list1 = @a[ $cdiff[0] .. $cdiff[2]-1 ];
601 @list2 = @b[ $cdiff[1] .. $cdiff[3]-1 ];
602 # Hunk start Hunk end
603 Note that the hunks will always alternate between those that are part
605 of the LCS (those that contain unchanged items) and those that contain
606 changes. This means that all we need to be told is whether the first
607 hunk is a 'same' or 'diff' hunk and we can determine which of the other
608 hunks contain 'same' items or 'diff' items.
609 By convention, we always make the first hunk contain unchanged items.
611 So the 1st, 3rd, 5th, etc. hunks (all odd-numbered hunks if you start
612 counting from 1) all contain unchanged items. And the 2nd, 4th, 6th,
613 etc. hunks (all even-numbered hunks if you start counting from 1) all
614 contain changed items.
615 Since @a and @b don't begin with the same value, the first hunk in our
617 example is empty (otherwise we'd violate the above convention). Note
618 that the first 4 index values in our example are all zero. Plug these
619 values into our previous code block and we get:
620 @hunk1a = @a[ 0 .. 0-1 ];
622 @hunk1b = @b[ 0 .. 0-1 ];
623 And "0..-1" returns the empty list.
625 Move down one pair of indices (2..5) and we get the offset ranges for
627 the second hunk, which contains changed items.
628 Since @diff[2..5] contains (0,0,1,0) in our example, the second hunk
630 consists of these two lists of items:
631 @hunk2a = @a[ $cdiff[2] .. $cdiff[4]-1 ];
633 @hunk2b = @b[ $cdiff[3] .. $cdiff[5]-1 ];
634 # or
635 @hunk2a = @a[ 0 .. 1-1 ];
636 @hunk2b = @b[ 0 .. 0-1 ];
637 # or
638 @hunk2a = @a[ 0 .. 0 ];
639 @hunk2b = @b[ 0 .. -1 ];
640 # or
641 @hunk2a = ( 'a' );
642 @hunk2b = ( );
643 That is, we would delete item 0 ('a') from @a.
645 Since @diff[4..7] contains (1,0,3,2) in our example, the third hunk
647 consists of these two lists of items:
648 @hunk3a = @a[ $cdiff[4] .. $cdiff[6]-1 ];
650 @hunk3a = @b[ $cdiff[5] .. $cdiff[7]-1 ];
651 # or
652 @hunk3a = @a[ 1 .. 3-1 ];
653 @hunk3a = @b[ 0 .. 2-1 ];
654 # or
655 @hunk3a = @a[ 1 .. 2 ];
656 @hunk3a = @b[ 0 .. 1 ];
657 # or
658 @hunk3a = qw( b c );
659 @hunk3a = qw( b c );
660 Note that this third hunk contains unchanged items as our convention
662 demands.
663 You can continue this process until you reach the last two indices,
665 which will always be the number of items in each sequence. This is
666 required so that subtracting one from each will give you the indices to
667 the last items in each sequence.
668 "traverse_sequences"
670 "traverse_sequences" used to be the most general facility provided by
671 this module (the new OO interface is more powerful and much easier to
672 use).
673 Imagine that there are two arrows. Arrow A points to an element of
675 sequence A, and arrow B points to an element of the sequence B.
676 Initially, the arrows point to the first elements of the respective
677 sequences. "traverse_sequences" will advance the arrows through the
678 sequences one element at a time, calling an appropriate user-specified
679 callback function before each advance. It will advance the arrows in
680 such a way that if there are equal elements $A[$i] and $B[$j] which are
681 equal and which are part of the LCS, there will be some moment during
682 the execution of "traverse_sequences" when arrow A is pointing to
683 $A[$i] and arrow B is pointing to $B[$j]. When this happens,
684 "traverse_sequences" will call the "MATCH" callback function and then
685 it will advance both arrows.
686 Otherwise, one of the arrows is pointing to an element of its sequence
688 that is not part of the LCS. "traverse_sequences" will advance that
689 arrow and will call the "DISCARD_A" or the "DISCARD_B" callback,
690 depending on which arrow it advanced. If both arrows point to elements
691 that are not part of the LCS, then "traverse_sequences" will advance
692 one of them and call the appropriate callback, but it is not specified
693 which it will call.
694 The arguments to "traverse_sequences" are the two sequences to
696 traverse, and a hash which specifies the callback functions, like this:
697 traverse_sequences(
699 \@seq1, \@seq2,
700 { MATCH => $callback_1,
701 DISCARD_A => $callback_2,
702 DISCARD_B => $callback_3,
703 }
704 );
705 Callbacks for MATCH, DISCARD_A, and DISCARD_B are invoked with at least
707 the indices of the two arrows as their arguments. They are not
708 expected to return any values. If a callback is omitted from the
709 table, it is not called.
710 Callbacks for A_FINISHED and B_FINISHED are invoked with at least the
712 corresponding index in A or B.
713 If arrow A reaches the end of its sequence, before arrow B does,
715 "traverse_sequences" will call the "A_FINISHED" callback when it
716 advances arrow B, if there is such a function; if not it will call
717 "DISCARD_B" instead. Similarly if arrow B finishes first.
718 "traverse_sequences" returns when both arrows are at the ends of their
719 respective sequences. It returns true on success and false on failure.
720 At present there is no way to fail.
721 "traverse_sequences" may be passed an optional fourth parameter; this
723 is a CODE reference to a key generation function. See "KEY GENERATION
724 FUNCTIONS".
725 Additional parameters, if any, will be passed to the key generation
727 function.
728 If you want to pass additional parameters to your callbacks, but don't
730 need a custom key generation function, you can get the default by
731 passing undef:
732 traverse_sequences(
734 \@seq1, \@seq2,
735 { MATCH => $callback_1,
736 DISCARD_A => $callback_2,
737 DISCARD_B => $callback_3,
738 },
739 undef, # default key-gen
740 $myArgument1,
741 $myArgument2,
742 $myArgument3,
743 );
744 "traverse_sequences" does not have a useful return value; you are
746 expected to plug in the appropriate behavior with the callback
747 functions.
748 "traverse_balanced"
750 "traverse_balanced" is an alternative to "traverse_sequences". It uses
751 a different algorithm to iterate through the entries in the computed
752 LCS. Instead of sticking to one side and showing element changes as
753 insertions and deletions only, it will jump back and forth between the
754 two sequences and report changes occurring as deletions on one side
755 followed immediately by an insertion on the other side.
756 In addition to the "DISCARD_A", "DISCARD_B", and "MATCH" callbacks
758 supported by "traverse_sequences", "traverse_balanced" supports a
759 "CHANGE" callback indicating that one element got "replaced" by
760 another:
761 traverse_balanced(
763 \@seq1, \@seq2,
764 { MATCH => $callback_1,
765 DISCARD_A => $callback_2,
766 DISCARD_B => $callback_3,
767 CHANGE => $callback_4,
768 }
769 );
770 If no "CHANGE" callback is specified, "traverse_balanced" will map
772 "CHANGE" events to "DISCARD_A" and "DISCARD_B" actions, therefore
773 resulting in a similar behaviour as "traverse_sequences" with different
774 order of events.
775 "traverse_balanced" might be a bit slower than "traverse_sequences",
777 noticeable only while processing huge amounts of data.
778 The "sdiff" function of this module is implemented as call to
780 "traverse_balanced".
781 "traverse_balanced" does not have a useful return value; you are
783 expected to plug in the appropriate behavior with the callback
784 functions.
785
787 Most of the functions accept an optional extra parameter. This is a
788 CODE reference to a key generating (hashing) function that should
789 return a string that uniquely identifies a given element. It should be
790 the case that if two elements are to be considered equal, their keys
791 should be the same (and the other way around). If no key generation
792 function is provided, the key will be the element as a string.
793 By default, comparisons will use "eq" and elements will be turned into
795 keys using the default stringizing operator '""'.
796 Where this is important is when you're comparing something other than
798 strings. If it is the case that you have multiple different objects
799 that should be considered to be equal, you should supply a key
800 generation function. Otherwise, you have to make sure that your arrays
801 contain unique references.
802 For instance, consider this example:
804 package Person;
806 sub new
808 {
809 my $package = shift;
810 return bless { name => '', ssn => '', @_ }, $package;
811 }
812 sub clone
814 {
815 my $old = shift;
816 my $new = bless { %$old }, ref($old);
817 }
818 sub hash
820 {
821 return shift()->{'ssn'};
822 }
823 my $person1 = Person->new( name => 'Joe', ssn => '123-45-6789' );
825 my $person2 = Person->new( name => 'Mary', ssn => '123-47-0000' );
826 my $person3 = Person->new( name => 'Pete', ssn => '999-45-2222' );
827 my $person4 = Person->new( name => 'Peggy', ssn => '123-45-9999' );
828 my $person5 = Person->new( name => 'Frank', ssn => '000-45-9999' );
829 If you did this:
831 my $array1 = [ $person1, $person2, $person4 ];
833 my $array2 = [ $person1, $person3, $person4, $person5 ];
834 Algorithm::Diff::diff( $array1, $array2 );
835 everything would work out OK (each of the objects would be converted
837 into a string like "Person=HASH(0x82425b0)" for comparison).
838 But if you did this:
840 my $array1 = [ $person1, $person2, $person4 ];
842 my $array2 = [ $person1, $person3, $person4->clone(), $person5 ];
843 Algorithm::Diff::diff( $array1, $array2 );
844 $person4 and $person4->clone() (which have the same name and SSN) would
846 be seen as different objects. If you wanted them to be considered
847 equivalent, you would have to pass in a key generation function:
848 my $array1 = [ $person1, $person2, $person4 ];
850 my $array2 = [ $person1, $person3, $person4->clone(), $person5 ];
851 Algorithm::Diff::diff( $array1, $array2, \&Person::hash );
852 This would use the 'ssn' field in each Person as a comparison key, and
854 so would consider $person4 and $person4->clone() as equal.
855 You may also pass additional parameters to the key generation function
857 if you wish.
858
860 If you pass these routines a non-reference and they expect a reference,
861 they will die with a message.
862
864 This version released by Tye McQueen (http://perlmonks.org/?node=tye).
865
867 Parts Copyright (c) 2000-2004 Ned Konz. All rights reserved. Parts by
868 Tye McQueen.
869 This program is free software; you can redistribute it and/or modify it
871 under the same terms as Perl.
872
874 Mark-Jason still maintains a mailing list. To join a low-volume
875 mailing list for announcements related to diff and Algorithm::Diff,
876 send an empty mail message to mjd-perl-diff-request@plover.com.
877
879 Versions through 0.59 (and much of this documentation) were written by:
880 Mark-Jason Dominus, mjd-perl-diff@plover.com
882 This version borrows some documentation and routine names from Mark-
884 Jason's, but Diff.pm's code was completely replaced.
885 This code was adapted from the Smalltalk code of Mario Wolczko
887 <mario@wolczko.com>, which is available at
888 ftp://st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st
889 "sdiff" and "traverse_balanced" were written by Mike Schilli
891 <m@perlmeister.com>.
892 The algorithm is that described in A Fast Algorithm for Computing
894 Longest Common Subsequences, CACM, vol.20, no.5, pp.350-353, May 1977,
895 with a few minor improvements to improve the speed.
896 Much work was done by Ned Konz (perl@bike-nomad.com).
898 The OO interface and some other changes are by Tye McQueen.
900
902 Hey! The above document had some coding errors, which are explained
903 below:
904 Around line 989:
906 You can't have =items (as at line 1021) unless the first thing
907 after the =over is an =item
908 Around line 1108:
910 Expected text after =item, not a number
911 Around line 1114:
913 Expected text after =item, not a number
914 Around line 1120:
916 Expected text after =item, not a number
917perl v5.26.3 2014-11-26 Algorithm::Diff(3)