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::Diff->new( \@seq1, \@seq2 );
186 $diff = Algorithm::Diff->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 code
197 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 that
213 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 same
224 as if no argument were passed in.
225 "Next"
227 $pos = $diff->Next(); # Move forward 1 hunk
228 $pos = $diff->Next( 2 ); # Move forward 2 hunks
229 $pos = $diff->Next(-5); # Move backward 5 hunks
230 "Next" moves the object to point at the next hunk. The object
232 starts out "reset", which means it isn't pointing at any hunk. If
233 the object is reset, then Next() moves to the first hunk.
234 "Next" returns a true value iff the move didn't go past the last
236 hunk. So Next(0) will return true iff the object is not reset.
237 Actually, "Next" returns the object's new position, which is a
239 number between 1 and the number of hunks (inclusive), or returns a
240 false value.
241 "Prev"
243 Prev($N) is almost identical to Next(-$N); it moves to the $Nth
244 previous hunk. On a 'reset' object, Prev() [and Next(-1)] move to
245 the last hunk.
246 The position returned by "Prev" is relative to the end of the
248 hunks; -1 for the last hunk, -2 for the second-to-last, etc.
249 "Reset"
251 $diff->Reset(); # Reset the object's position
252 $diff->Reset($pos); # Move to the specified hunk
253 $diff->Reset(1); # Move to the first hunk
254 $diff->Reset(-1); # Move to the last hunk
255 "Reset" returns the object, so, for example, you could use
257 "$diff->Reset()->Next(-1)" to get the number of hunks.
258 "Copy"
260 $copy = $diff->Copy( $newPos, $newBase );
261 "Copy" returns a copy of the object. The copy and the original
263 object share most of their data, so making copies takes very little
264 memory. The copy maintains its own position (separate from the
265 original), which is the main purpose of copies. It also maintains
266 its own base.
267 By default, the copy's position starts out the same as the original
269 object's position. But "Copy" takes an optional first argument to
270 set the new position, so the following three snippets are
271 equivalent:
272 $copy = $diff->Copy($pos);
274 $copy = $diff->Copy();
276 $copy->Reset($pos);
277 $copy = $diff->Copy()->Reset($pos);
279 "Copy" takes an optional second argument to set the base for the
281 copy. If you wish to change the base of the copy but leave the
282 position the same as in the original, here are two equivalent ways:
283 $copy = $diff->Copy();
285 $copy->Base( 0 );
286 $copy = $diff->Copy(undef,0);
288 Here are two equivalent way to get a "reset" copy:
290 $copy = $diff->Copy(0);
292 $copy = $diff->Copy()->Reset();
294 "Diff"
296 $bits = $obj->Diff();
297 "Diff" returns a true value iff the current hunk contains items
299 that are different between the two sequences. It actually returns
300 one of the follow 4 values:
301 3 "3==(1|2)". This hunk contains items from @seq1 and the items
303 from @seq2 that should replace them. Both sequence 1 and 2
304 contain changed items so both the 1 and 2 bits are set.
305 2 This hunk only contains items from @seq2 that should be
307 inserted (not items from @seq1). Only sequence 2 contains
308 changed items so only the 2 bit is set.
309 1 This hunk only contains items from @seq1 that should be deleted
311 (not items from @seq2). Only sequence 1 contains changed items
312 so only the 1 bit is set.
313 0 This means that the items in this hunk are the same in both
315 sequences. Neither sequence 1 nor 2 contain changed items so
316 neither the 1 nor the 2 bits are set.
317 "Same"
319 "Same" returns a true value iff the current hunk contains items
320 that are the same in both sequences. It actually returns the list
321 of items if they are the same or an empty list if they aren't. In
322 a scalar context, it returns the size of the list.
323 "Items"
325 $count = $diff->Items(2);
326 @items = $diff->Items($seqNum);
327 "Items" returns the (number of) items from the specified sequence
329 that are part of the current hunk.
330 If the current hunk contains only insertions, then
332 "$diff->Items(1)" will return an empty list (0 in a scalar
333 context). If the current hunk contains only deletions, then
334 "$diff->Items(2)" will return an empty list (0 in a scalar
335 context).
336 If the hunk contains replacements, then both "$diff->Items(1)" and
338 "$diff->Items(2)" will return different, non-empty lists.
339 Otherwise, the hunk contains identical items and all of the
341 following will return the same lists:
342 @items = $diff->Items(1);
344 @items = $diff->Items(2);
345 @items = $diff->Same();
346 "Range"
348 $count = $diff->Range( $seqNum );
349 @indices = $diff->Range( $seqNum );
350 @indices = $diff->Range( $seqNum, $base );
351 "Range" is like "Items" except that it returns a list of indices to
353 the items rather than the items themselves. By default, the index
354 of the first item (in each sequence) is 0 but this can be changed
355 by calling the "Base" method. So, by default, the following two
356 snippets return the same lists:
357 @list = $diff->Items(2);
359 @list = @seq2[ $diff->Range(2) ];
360 You can also specify the base to use as the second argument. So
362 the following two snippets always return the same lists:
363 @list = $diff->Items(1);
365 @list = @seq1[ $diff->Range(1,0) ];
366 "Base"
368 $curBase = $diff->Base();
369 $oldBase = $diff->Base($newBase);
370 "Base" sets and/or returns the current base (usually 0 or 1) that
372 is used when you request range information. The base defaults to 0
373 so that range information is returned as array indices. You can
374 set the base to 1 if you want to report traditional line numbers
375 instead.
376 "Min"
378 $min1 = $diff->Min(1);
379 $min = $diff->Min( $seqNum, $base );
380 "Min" returns the first value that "Range" would return (given the
382 same arguments) or returns "undef" if "Range" would return an empty
383 list.
384 "Max"
386 "Max" returns the last value that "Range" would return or "undef".
387 "Get"
389 ( $n, $x, $r ) = $diff->Get(qw( min1 max1 range1 ));
390 @values = $diff->Get(qw( 0min2 1max2 range2 same base ));
391 "Get" returns one or more scalar values. You pass in a list of the
393 names of the values you want returned. Each name must match one of
394 the following regexes:
395 /^(-?\d+)?(min|max)[12]$/i
397 /^(range[12]|same|diff|base)$/i
398 The 1 or 2 after a name says which sequence you want the
400 information for (and where allowed, it is required). The optional
401 number before "min" or "max" is the base to use. So the following
402 equalities hold:
403 $diff->Get('min1') == $diff->Min(1)
405 $diff->Get('0min2') == $diff->Min(2,0)
406 Using "Get" in a scalar context when you've passed in more than one
408 name is a fatal error ("die" is called).
409 "prepare"
411 Given a reference to a list of items, "prepare" returns a reference to
412 a hash which can be used when comparing this sequence to other
413 sequences with "LCS" or "LCS_length".
414 $prep = prepare( \@seq1 );
416 for $i ( 0 .. 10_000 )
417 {
418 @lcs = LCS( $prep, $seq[$i] );
419 # do something useful with @lcs
420 }
421 "prepare" may be passed an optional third parameter; this is a CODE
423 reference to a key generation function. See "KEY GENERATION
424 FUNCTIONS".
425 $prep = prepare( \@seq1, \&keyGen );
427 for $i ( 0 .. 10_000 )
428 {
429 @lcs = LCS( $seq[$i], $prep, \&keyGen );
430 # do something useful with @lcs
431 }
432 Using "prepare" provides a performance gain of about 50% when calling
434 LCS many times compared with not preparing.
435 "diff"
437 @diffs = diff( \@seq1, \@seq2 );
438 $diffs_ref = diff( \@seq1, \@seq2 );
439 "diff" computes the smallest set of additions and deletions necessary
441 to turn the first sequence into the second, and returns a description
442 of these changes. The description is a list of hunks; each hunk
443 represents a contiguous section of items which should be added,
444 deleted, or replaced. (Hunks containing unchanged items are not
445 included.)
446 The return value of "diff" is a list of hunks, or, in scalar context, a
448 reference to such a list. If there are no differences, the list will
449 be empty.
450 Here is an example. Calling "diff" for the following two sequences:
452 a b c e h j l m n p
454 b c d e f j k l m r s t
455 would produce the following list:
457 (
459 [ [ '-', 0, 'a' ] ],
460 [ [ '+', 2, 'd' ] ],
462 [ [ '-', 4, 'h' ],
464 [ '+', 4, 'f' ] ],
465 [ [ '+', 6, 'k' ] ],
467 [ [ '-', 8, 'n' ],
469 [ '-', 9, 'p' ],
470 [ '+', 9, 'r' ],
471 [ '+', 10, 's' ],
472 [ '+', 11, 't' ] ],
473 )
474 There are five hunks here. The first hunk says that the "a" at
476 position 0 of the first sequence should be deleted ("-"). The second
477 hunk says that the "d" at position 2 of the second sequence should be
478 inserted ("+"). The third hunk says that the "h" at position 4 of the
479 first sequence should be removed and replaced with the "f" from
480 position 4 of the second sequence. And so on.
481 "diff" may be passed an optional third parameter; this is a CODE
483 reference to a key generation function. See "KEY GENERATION
484 FUNCTIONS".
485 Additional parameters, if any, will be passed to the key generation
487 routine.
488 "sdiff"
490 @sdiffs = sdiff( \@seq1, \@seq2 );
491 $sdiffs_ref = sdiff( \@seq1, \@seq2 );
492 "sdiff" computes all necessary components to show two sequences and
494 their minimized differences side by side, just like the Unix-utility
495 sdiff does:
496 same same
498 before | after
499 old < -
500 - > new
501 It returns a list of array refs, each pointing to an array of display
503 instructions. In scalar context it returns a reference to such a list.
504 If there are no differences, the list will have one entry per item,
505 each indicating that the item was unchanged.
506 Display instructions consist of three elements: A modifier indicator
508 ("+": Element added, "-": Element removed, "u": Element unmodified,
509 "c": Element changed) and the value of the old and new elements, to be
510 displayed side-by-side.
511 An "sdiff" of the following two sequences:
513 a b c e h j l m n p
515 b c d e f j k l m r s t
516 results in
518 ( [ '-', 'a', '' ],
520 [ 'u', 'b', 'b' ],
521 [ 'u', 'c', 'c' ],
522 [ '+', '', 'd' ],
523 [ 'u', 'e', 'e' ],
524 [ 'c', 'h', 'f' ],
525 [ 'u', 'j', 'j' ],
526 [ '+', '', 'k' ],
527 [ 'u', 'l', 'l' ],
528 [ 'u', 'm', 'm' ],
529 [ 'c', 'n', 'r' ],
530 [ 'c', 'p', 's' ],
531 [ '+', '', 't' ],
532 )
533 "sdiff" may be passed an optional third parameter; this is a CODE
535 reference to a key generation function. See "KEY GENERATION
536 FUNCTIONS".
537 Additional parameters, if any, will be passed to the key generation
539 routine.
540 "compact_diff"
542 "compact_diff" is much like "sdiff" except it returns a much more
543 compact description consisting of just one flat list of indices. An
544 example helps explain the format:
545 my @a = qw( a b c e h j l m n p );
547 my @b = qw( b c d e f j k l m r s t );
548 @cdiff = compact_diff( \@a, \@b );
549 # Returns:
550 # @a @b @a @b
551 # start start values values
552 ( 0, 0, # =
553 0, 0, # a !
554 1, 0, # b c = b c
555 3, 2, # ! d
556 3, 3, # e = e
557 4, 4, # f ! h
558 5, 5, # j = j
559 6, 6, # ! k
560 6, 7, # l m = l m
561 8, 9, # n p ! r s t
562 10, 12, #
563 );
564 The 0th, 2nd, 4th, etc. entries are all indices into @seq1 (@a in the
566 above example) indicating where a hunk begins. The 1st, 3rd, 5th, etc.
567 entries are all indices into @seq2 (@b in the above example) indicating
568 where the same hunk begins.
569 So each pair of indices (except the last pair) describes where a hunk
571 begins (in each sequence). Since each hunk must end at the item just
572 before the item that starts the next hunk, the next pair of indices can
573 be used to determine where the hunk ends.
574 So, the first 4 entries (0..3) describe the first hunk. Entries 0 and
576 1 describe where the first hunk begins (and so are always both 0).
577 Entries 2 and 3 describe where the next hunk begins, so subtracting 1
578 from each tells us where the first hunk ends. That is, the first hunk
579 contains items $diff[0] through "$diff[2] - 1" of the first sequence
580 and contains items $diff[1] through "$diff[3] - 1" of the second
581 sequence.
582 In other words, the first hunk consists of the following two lists of
584 items:
585 # 1st pair 2nd pair
587 # of indices of indices
588 @list1 = @a[ $cdiff[0] .. $cdiff[2]-1 ];
589 @list2 = @b[ $cdiff[1] .. $cdiff[3]-1 ];
590 # Hunk start Hunk end
591 Note that the hunks will always alternate between those that are part
593 of the LCS (those that contain unchanged items) and those that contain
594 changes. This means that all we need to be told is whether the first
595 hunk is a 'same' or 'diff' hunk and we can determine which of the other
596 hunks contain 'same' items or 'diff' items.
597 By convention, we always make the first hunk contain unchanged items.
599 So the 1st, 3rd, 5th, etc. hunks (all odd-numbered hunks if you start
600 counting from 1) all contain unchanged items. And the 2nd, 4th, 6th,
601 etc. hunks (all even-numbered hunks if you start counting from 1) all
602 contain changed items.
603 Since @a and @b don't begin with the same value, the first hunk in our
605 example is empty (otherwise we'd violate the above convention). Note
606 that the first 4 index values in our example are all zero. Plug these
607 values into our previous code block and we get:
608 @hunk1a = @a[ 0 .. 0-1 ];
610 @hunk1b = @b[ 0 .. 0-1 ];
611 And "0..-1" returns the empty list.
613 Move down one pair of indices (2..5) and we get the offset ranges for
615 the second hunk, which contains changed items.
616 Since @diff[2..5] contains (0,0,1,0) in our example, the second hunk
618 consists of these two lists of items:
619 @hunk2a = @a[ $cdiff[2] .. $cdiff[4]-1 ];
621 @hunk2b = @b[ $cdiff[3] .. $cdiff[5]-1 ];
622 # or
623 @hunk2a = @a[ 0 .. 1-1 ];
624 @hunk2b = @b[ 0 .. 0-1 ];
625 # or
626 @hunk2a = @a[ 0 .. 0 ];
627 @hunk2b = @b[ 0 .. -1 ];
628 # or
629 @hunk2a = ( 'a' );
630 @hunk2b = ( );
631 That is, we would delete item 0 ('a') from @a.
633 Since @diff[4..7] contains (1,0,3,2) in our example, the third hunk
635 consists of these two lists of items:
636 @hunk3a = @a[ $cdiff[4] .. $cdiff[6]-1 ];
638 @hunk3a = @b[ $cdiff[5] .. $cdiff[7]-1 ];
639 # or
640 @hunk3a = @a[ 1 .. 3-1 ];
641 @hunk3a = @b[ 0 .. 2-1 ];
642 # or
643 @hunk3a = @a[ 1 .. 2 ];
644 @hunk3a = @b[ 0 .. 1 ];
645 # or
646 @hunk3a = qw( b c );
647 @hunk3a = qw( b c );
648 Note that this third hunk contains unchanged items as our convention
650 demands.
651 You can continue this process until you reach the last two indices,
653 which will always be the number of items in each sequence. This is
654 required so that subtracting one from each will give you the indices to
655 the last items in each sequence.
656 "traverse_sequences"
658 "traverse_sequences" used to be the most general facility provided by
659 this module (the new OO interface is more powerful and much easier to
660 use).
661 Imagine that there are two arrows. Arrow A points to an element of
663 sequence A, and arrow B points to an element of the sequence B.
664 Initially, the arrows point to the first elements of the respective
665 sequences. "traverse_sequences" will advance the arrows through the
666 sequences one element at a time, calling an appropriate user-specified
667 callback function before each advance. It will advance the arrows in
668 such a way that if there are equal elements $A[$i] and $B[$j] which are
669 equal and which are part of the LCS, there will be some moment during
670 the execution of "traverse_sequences" when arrow A is pointing to
671 $A[$i] and arrow B is pointing to $B[$j]. When this happens,
672 "traverse_sequences" will call the "MATCH" callback function and then
673 it will advance both arrows.
674 Otherwise, one of the arrows is pointing to an element of its sequence
676 that is not part of the LCS. "traverse_sequences" will advance that
677 arrow and will call the "DISCARD_A" or the "DISCARD_B" callback,
678 depending on which arrow it advanced. If both arrows point to elements
679 that are not part of the LCS, then "traverse_sequences" will advance
680 one of them and call the appropriate callback, but it is not specified
681 which it will call.
682 The arguments to "traverse_sequences" are the two sequences to
684 traverse, and a hash which specifies the callback functions, like this:
685 traverse_sequences(
687 \@seq1, \@seq2,
688 { MATCH => $callback_1,
689 DISCARD_A => $callback_2,
690 DISCARD_B => $callback_3,
691 }
692 );
693 Callbacks for MATCH, DISCARD_A, and DISCARD_B are invoked with at least
695 the indices of the two arrows as their arguments. They are not
696 expected to return any values. If a callback is omitted from the
697 table, it is not called.
698 Callbacks for A_FINISHED and B_FINISHED are invoked with at least the
700 corresponding index in A or B.
701 If arrow A reaches the end of its sequence, before arrow B does,
703 "traverse_sequences" will call the "A_FINISHED" callback when it
704 advances arrow B, if there is such a function; if not it will call
705 "DISCARD_B" instead. Similarly if arrow B finishes first.
706 "traverse_sequences" returns when both arrows are at the ends of their
707 respective sequences. It returns true on success and false on failure.
708 At present there is no way to fail.
709 "traverse_sequences" may be passed an optional fourth parameter; this
711 is a CODE reference to a key generation function. See "KEY GENERATION
712 FUNCTIONS".
713 Additional parameters, if any, will be passed to the key generation
715 function.
716 If you want to pass additional parameters to your callbacks, but don't
718 need a custom key generation function, you can get the default by
719 passing undef:
720 traverse_sequences(
722 \@seq1, \@seq2,
723 { MATCH => $callback_1,
724 DISCARD_A => $callback_2,
725 DISCARD_B => $callback_3,
726 },
727 undef, # default key-gen
728 $myArgument1,
729 $myArgument2,
730 $myArgument3,
731 );
732 "traverse_sequences" does not have a useful return value; you are
734 expected to plug in the appropriate behavior with the callback
735 functions.
736 "traverse_balanced"
738 "traverse_balanced" is an alternative to "traverse_sequences". It uses
739 a different algorithm to iterate through the entries in the computed
740 LCS. Instead of sticking to one side and showing element changes as
741 insertions and deletions only, it will jump back and forth between the
742 two sequences and report changes occurring as deletions on one side
743 followed immediately by an insertion on the other side.
744 In addition to the "DISCARD_A", "DISCARD_B", and "MATCH" callbacks
746 supported by "traverse_sequences", "traverse_balanced" supports a
747 "CHANGE" callback indicating that one element got "replaced" by
748 another:
749 traverse_balanced(
751 \@seq1, \@seq2,
752 { MATCH => $callback_1,
753 DISCARD_A => $callback_2,
754 DISCARD_B => $callback_3,
755 CHANGE => $callback_4,
756 }
757 );
758 If no "CHANGE" callback is specified, "traverse_balanced" will map
760 "CHANGE" events to "DISCARD_A" and "DISCARD_B" actions, therefore
761 resulting in a similar behaviour as "traverse_sequences" with different
762 order of events.
763 "traverse_balanced" might be a bit slower than "traverse_sequences",
765 noticeable only while processing huge amounts of data.
766 The "sdiff" function of this module is implemented as call to
768 "traverse_balanced".
769 "traverse_balanced" does not have a useful return value; you are
771 expected to plug in the appropriate behavior with the callback
772 functions.
773
775 Most of the functions accept an optional extra parameter. This is a
776 CODE reference to a key generating (hashing) function that should
777 return a string that uniquely identifies a given element. It should be
778 the case that if two elements are to be considered equal, their keys
779 should be the same (and the other way around). If no key generation
780 function is provided, the key will be the element as a string.
781 By default, comparisons will use "eq" and elements will be turned into
783 keys using the default stringizing operator '""'.
784 Where this is important is when you're comparing something other than
786 strings. If it is the case that you have multiple different objects
787 that should be considered to be equal, you should supply a key
788 generation function. Otherwise, you have to make sure that your arrays
789 contain unique references.
790 For instance, consider this example:
792 package Person;
794 sub new
796 {
797 my $package = shift;
798 return bless { name => '', ssn => '', @_ }, $package;
799 }
800 sub clone
802 {
803 my $old = shift;
804 my $new = bless { %$old }, ref($old);
805 }
806 sub hash
808 {
809 return shift()->{'ssn'};
810 }
811 my $person1 = Person->new( name => 'Joe', ssn => '123-45-6789' );
813 my $person2 = Person->new( name => 'Mary', ssn => '123-47-0000' );
814 my $person3 = Person->new( name => 'Pete', ssn => '999-45-2222' );
815 my $person4 = Person->new( name => 'Peggy', ssn => '123-45-9999' );
816 my $person5 = Person->new( name => 'Frank', ssn => '000-45-9999' );
817 If you did this:
819 my $array1 = [ $person1, $person2, $person4 ];
821 my $array2 = [ $person1, $person3, $person4, $person5 ];
822 Algorithm::Diff::diff( $array1, $array2 );
823 everything would work out OK (each of the objects would be converted
825 into a string like "Person=HASH(0x82425b0)" for comparison).
826 But if you did this:
828 my $array1 = [ $person1, $person2, $person4 ];
830 my $array2 = [ $person1, $person3, $person4->clone(), $person5 ];
831 Algorithm::Diff::diff( $array1, $array2 );
832 $person4 and $person4->clone() (which have the same name and SSN) would
834 be seen as different objects. If you wanted them to be considered
835 equivalent, you would have to pass in a key generation function:
836 my $array1 = [ $person1, $person2, $person4 ];
838 my $array2 = [ $person1, $person3, $person4->clone(), $person5 ];
839 Algorithm::Diff::diff( $array1, $array2, \&Person::hash );
840 This would use the 'ssn' field in each Person as a comparison key, and
842 so would consider $person4 and $person4->clone() as equal.
843 You may also pass additional parameters to the key generation function
845 if you wish.
846
848 If you pass these routines a non-reference and they expect a reference,
849 they will die with a message.
850
852 This version released by Tye McQueen (http://perlmonks.org/?node=tye).
853
855 Parts Copyright (c) 2000-2004 Ned Konz. All rights reserved. Parts by
856 Tye McQueen.
857 This program is free software; you can redistribute it and/or modify it
859 under the same terms as Perl.
860
862 Mark-Jason still maintains a mailing list. To join a low-volume
863 mailing list for announcements related to diff and Algorithm::Diff,
864 send an empty mail message to mjd-perl-diff-request@plover.com.
865
867 Versions through 0.59 (and much of this documentation) were written by:
868 Mark-Jason Dominus
870 This version borrows some documentation and routine names from Mark-
872 Jason's, but Diff.pm's code was completely replaced.
873 This code was adapted from the Smalltalk code of Mario Wolczko
875 <mario@wolczko.com>, which is available at
876 ftp://st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st
877 "sdiff" and "traverse_balanced" were written by Mike Schilli
879 <m@perlmeister.com>.
880 The algorithm is that described in A Fast Algorithm for Computing
882 Longest Common Subsequences, CACM, vol.20, no.5, pp.350-353, May 1977,
883 with a few minor improvements to improve the speed.
884 Much work was done by Ned Konz (perl@bike-nomad.com).
886 The OO interface and some other changes are by Tye McQueen.
888perl v5.38.0 2023-07-20 Algorithm::Diff(3)