| 1 | .\" Automatically generated by Pod::Man v1.34, Pod::Parser v1.13 |
| 2 | .\" |
| 3 | .\" Standard preamble: |
| 4 | .\" ======================================================================== |
| 5 | .de Sh \" Subsection heading |
| 6 | .br |
| 7 | .if t .Sp |
| 8 | .ne 5 |
| 9 | .PP |
| 10 | \fB\\$1\fR |
| 11 | .PP |
| 12 | .. |
| 13 | .de Sp \" Vertical space (when we can't use .PP) |
| 14 | .if t .sp .5v |
| 15 | .if n .sp |
| 16 | .. |
| 17 | .de Vb \" Begin verbatim text |
| 18 | .ft CW |
| 19 | .nf |
| 20 | .ne \\$1 |
| 21 | .. |
| 22 | .de Ve \" End verbatim text |
| 23 | .ft R |
| 24 | .fi |
| 25 | .. |
| 26 | .\" Set up some character translations and predefined strings. \*(-- will |
| 27 | .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left |
| 28 | .\" double quote, and \*(R" will give a right double quote. | will give a |
| 29 | .\" real vertical bar. \*(C+ will give a nicer C++. Capital omega is used to |
| 30 | .\" do unbreakable dashes and therefore won't be available. \*(C` and \*(C' |
| 31 | .\" expand to `' in nroff, nothing in troff, for use with C<>. |
| 32 | .tr \(*W-|\(bv\*(Tr |
| 33 | .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' |
| 34 | .ie n \{\ |
| 35 | . ds -- \(*W- |
| 36 | . ds PI pi |
| 37 | . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch |
| 38 | . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch |
| 39 | . ds L" "" |
| 40 | . ds R" "" |
| 41 | . ds C` "" |
| 42 | . ds C' "" |
| 43 | 'br\} |
| 44 | .el\{\ |
| 45 | . ds -- \|\(em\| |
| 46 | . ds PI \(*p |
| 47 | . ds L" `` |
| 48 | . ds R" '' |
| 49 | 'br\} |
| 50 | .\" |
| 51 | .\" If the F register is turned on, we'll generate index entries on stderr for |
| 52 | .\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index |
| 53 | .\" entries marked with X<> in POD. Of course, you'll have to process the |
| 54 | .\" output yourself in some meaningful fashion. |
| 55 | .if \nF \{\ |
| 56 | . de IX |
| 57 | . tm Index:\\$1\t\\n%\t"\\$2" |
| 58 | .. |
| 59 | . nr % 0 |
| 60 | . rr F |
| 61 | .\} |
| 62 | .\" |
| 63 | .\" For nroff, turn off justification. Always turn off hyphenation; it makes |
| 64 | .\" way too many mistakes in technical documents. |
| 65 | .hy 0 |
| 66 | .if n .na |
| 67 | .\" |
| 68 | .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). |
| 69 | .\" Fear. Run. Save yourself. No user-serviceable parts. |
| 70 | . \" fudge factors for nroff and troff |
| 71 | .if n \{\ |
| 72 | . ds #H 0 |
| 73 | . ds #V .8m |
| 74 | . ds #F .3m |
| 75 | . ds #[ \f1 |
| 76 | . ds #] \fP |
| 77 | .\} |
| 78 | .if t \{\ |
| 79 | . ds #H ((1u-(\\\\n(.fu%2u))*.13m) |
| 80 | . ds #V .6m |
| 81 | . ds #F 0 |
| 82 | . ds #[ \& |
| 83 | . ds #] \& |
| 84 | .\} |
| 85 | . \" simple accents for nroff and troff |
| 86 | .if n \{\ |
| 87 | . ds ' \& |
| 88 | . ds ` \& |
| 89 | . ds ^ \& |
| 90 | . ds , \& |
| 91 | . ds ~ ~ |
| 92 | . ds / |
| 93 | .\} |
| 94 | .if t \{\ |
| 95 | . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" |
| 96 | . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' |
| 97 | . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' |
| 98 | . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' |
| 99 | . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' |
| 100 | . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' |
| 101 | .\} |
| 102 | . \" troff and (daisy-wheel) nroff accents |
| 103 | .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' |
| 104 | .ds 8 \h'\*(#H'\(*b\h'-\*(#H' |
| 105 | .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] |
| 106 | .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' |
| 107 | .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' |
| 108 | .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] |
| 109 | .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] |
| 110 | .ds ae a\h'-(\w'a'u*4/10)'e |
| 111 | .ds Ae A\h'-(\w'A'u*4/10)'E |
| 112 | . \" corrections for vroff |
| 113 | .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' |
| 114 | .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' |
| 115 | . \" for low resolution devices (crt and lpr) |
| 116 | .if \n(.H>23 .if \n(.V>19 \ |
| 117 | \{\ |
| 118 | . ds : e |
| 119 | . ds 8 ss |
| 120 | . ds o a |
| 121 | . ds d- d\h'-1'\(ga |
| 122 | . ds D- D\h'-1'\(hy |
| 123 | . ds th \o'bp' |
| 124 | . ds Th \o'LP' |
| 125 | . ds ae ae |
| 126 | . ds Ae AE |
| 127 | .\} |
| 128 | .rm #[ #] #H #V #F C |
| 129 | .\" ======================================================================== |
| 130 | .\" |
| 131 | .IX Title "Algorithm::Diff 3" |
| 132 | .TH Algorithm::Diff 3 "2002-03-24" "perl v5.8.0" "User Contributed Perl Documentation" |
| 133 | .SH "NAME" |
| 134 | Algorithm::Diff \- Compute `intelligent' differences between two files / lists |
| 135 | .SH "SYNOPSIS" |
| 136 | .IX Header "SYNOPSIS" |
| 137 | .Vb 2 |
| 138 | \& use Algorithm::Diff qw(diff sdiff LCS traverse_sequences |
| 139 | \& traverse_balanced); |
| 140 | .Ve |
| 141 | .PP |
| 142 | .Vb 1 |
| 143 | \& @lcs = LCS( \e@seq1, \e@seq2 ); |
| 144 | .Ve |
| 145 | .PP |
| 146 | .Vb 1 |
| 147 | \& @lcs = LCS( \e@seq1, \e@seq2, $key_generation_function ); |
| 148 | .Ve |
| 149 | .PP |
| 150 | .Vb 1 |
| 151 | \& $lcsref = LCS( \e@seq1, \e@seq2 ); |
| 152 | .Ve |
| 153 | .PP |
| 154 | .Vb 1 |
| 155 | \& $lcsref = LCS( \e@seq1, \e@seq2, $key_generation_function ); |
| 156 | .Ve |
| 157 | .PP |
| 158 | .Vb 1 |
| 159 | \& @diffs = diff( \e@seq1, \e@seq2 ); |
| 160 | .Ve |
| 161 | .PP |
| 162 | .Vb 1 |
| 163 | \& @diffs = diff( \e@seq1, \e@seq2, $key_generation_function ); |
| 164 | .Ve |
| 165 | .PP |
| 166 | .Vb 1 |
| 167 | \& @sdiffs = sdiff( \e@seq1, \e@seq2 ); |
| 168 | .Ve |
| 169 | .PP |
| 170 | .Vb 1 |
| 171 | \& @sdiffs = sdiff( \e@seq1, \e@seq2, $key_generation_function ); |
| 172 | .Ve |
| 173 | .PP |
| 174 | .Vb 5 |
| 175 | \& traverse_sequences( \e@seq1, \e@seq2, |
| 176 | \& { MATCH => $callback, |
| 177 | \& DISCARD_A => $callback, |
| 178 | \& DISCARD_B => $callback, |
| 179 | \& } ); |
| 180 | .Ve |
| 181 | .PP |
| 182 | .Vb 6 |
| 183 | \& traverse_sequences( \e@seq1, \e@seq2, |
| 184 | \& { MATCH => $callback, |
| 185 | \& DISCARD_A => $callback, |
| 186 | \& DISCARD_B => $callback, |
| 187 | \& }, |
| 188 | \& $key_generation_function ); |
| 189 | .Ve |
| 190 | .PP |
| 191 | .Vb 6 |
| 192 | \& traverse_balanced( \e@seq1, \e@seq2, |
| 193 | \& { MATCH => $callback, |
| 194 | \& DISCARD_A => $callback, |
| 195 | \& DISCARD_B => $callback, |
| 196 | \& CHANGE => $callback, |
| 197 | \& } ); |
| 198 | .Ve |
| 199 | .SH "INTRODUCTION" |
| 200 | .IX Header "INTRODUCTION" |
| 201 | (by Mark-Jason Dominus) |
| 202 | .PP |
| 203 | I once read an article written by the authors of \f(CW\*(C`diff\*(C'\fR; they said |
| 204 | that they hard worked very hard on the algorithm until they found the |
| 205 | right one. |
| 206 | .PP |
| 207 | I think what they ended up using (and I hope someone will correct me, |
| 208 | because I am not very confident about this) was the `longest common |
| 209 | subsequence' method. in the \s-1LCS\s0 problem, you have two sequences of |
| 210 | items: |
| 211 | .PP |
| 212 | .Vb 1 |
| 213 | \& a b c d f g h j q z |
| 214 | .Ve |
| 215 | .PP |
| 216 | .Vb 1 |
| 217 | \& a b c d e f g i j k r x y z |
| 218 | .Ve |
| 219 | .PP |
| 220 | and you want to find the longest sequence of items that is present in |
| 221 | both original sequences in the same order. That is, you want to find |
| 222 | a new sequence \fIS\fR which can be obtained from the first sequence by |
| 223 | deleting some items, and from the secend sequence by deleting other |
| 224 | items. You also want \fIS\fR to be as long as possible. In this case |
| 225 | \&\fIS\fR is |
| 226 | .PP |
| 227 | .Vb 1 |
| 228 | \& a b c d f g j z |
| 229 | .Ve |
| 230 | .PP |
| 231 | From there it's only a small step to get diff-like output: |
| 232 | .PP |
| 233 | .Vb 2 |
| 234 | \& e h i k q r x y |
| 235 | \& + - + + - + + + |
| 236 | .Ve |
| 237 | .PP |
| 238 | This module solves the \s-1LCS\s0 problem. It also includes a canned |
| 239 | function to generate \f(CW\*(C`diff\*(C'\fR\-like output. |
| 240 | .PP |
| 241 | It might seem from the example above that the \s-1LCS\s0 of two sequences is |
| 242 | always pretty obvious, but that's not always the case, especially when |
| 243 | the two sequences have many repeated elements. For example, consider |
| 244 | .PP |
| 245 | .Vb 2 |
| 246 | \& a x b y c z p d q |
| 247 | \& a b c a x b y c z |
| 248 | .Ve |
| 249 | .PP |
| 250 | A naive approach might start by matching up the \f(CW\*(C`a\*(C'\fR and \f(CW\*(C`b\*(C'\fR that |
| 251 | appear at the beginning of each sequence, like this: |
| 252 | .PP |
| 253 | .Vb 2 |
| 254 | \& a x b y c z p d q |
| 255 | \& a b c a b y c z |
| 256 | .Ve |
| 257 | .PP |
| 258 | This finds the common subsequence \f(CW\*(C`a b c z\*(C'\fR. But actually, the \s-1LCS\s0 |
| 259 | is \f(CW\*(C`a x b y c z\*(C'\fR: |
| 260 | .PP |
| 261 | .Vb 2 |
| 262 | \& a x b y c z p d q |
| 263 | \& a b c a x b y c z |
| 264 | .Ve |
| 265 | .SH "USAGE" |
| 266 | .IX Header "USAGE" |
| 267 | This module provides three exportable functions, which we'll deal with in |
| 268 | ascending order of difficulty: \f(CW\*(C`LCS\*(C'\fR, |
| 269 | \&\f(CW\*(C`diff\*(C'\fR, \f(CW\*(C`sdiff\*(C'\fR, \f(CW\*(C`traverse_sequences\*(C'\fR, and \f(CW\*(C`traverse_balanced\*(C'\fR. |
| 270 | .ie n .Sh """LCS""" |
| 271 | .el .Sh "\f(CWLCS\fP" |
| 272 | .IX Subsection "LCS" |
| 273 | Given references to two lists of items, \s-1LCS\s0 returns an array containing their |
| 274 | longest common subsequence. In scalar context, it returns a reference to |
| 275 | such a list. |
| 276 | .PP |
| 277 | .Vb 2 |
| 278 | \& @lcs = LCS( \e@seq1, \e@seq2 ); |
| 279 | \& $lcsref = LCS( \e@seq1, \e@seq2 ); |
| 280 | .Ve |
| 281 | .PP |
| 282 | \&\f(CW\*(C`LCS\*(C'\fR may be passed an optional third parameter; this is a \s-1CODE\s0 |
| 283 | reference to a key generation function. See \*(L"\s-1KEY\s0 \s-1GENERATION\s0 \s-1FUNCTIONS\s0\*(R". |
| 284 | .PP |
| 285 | .Vb 2 |
| 286 | \& @lcs = LCS( \e@seq1, \e@seq2, $keyGen ); |
| 287 | \& $lcsref = LCS( \e@seq1, \e@seq2, $keyGen ); |
| 288 | .Ve |
| 289 | .PP |
| 290 | Additional parameters, if any, will be passed to the key generation |
| 291 | routine. |
| 292 | .ie n .Sh """diff""" |
| 293 | .el .Sh "\f(CWdiff\fP" |
| 294 | .IX Subsection "diff" |
| 295 | .Vb 2 |
| 296 | \& @diffs = diff( \e@seq1, \e@seq2 ); |
| 297 | \& $diffs_ref = diff( \e@seq1, \e@seq2 ); |
| 298 | .Ve |
| 299 | .PP |
| 300 | \&\f(CW\*(C`diff\*(C'\fR computes the smallest set of additions and deletions necessary |
| 301 | to turn the first sequence into the second, and returns a description |
| 302 | of these changes. The description is a list of \fIhunks\fR; each hunk |
| 303 | represents a contiguous section of items which should be added, |
| 304 | deleted, or replaced. The return value of \f(CW\*(C`diff\*(C'\fR is a list of |
| 305 | hunks, or, in scalar context, a reference to such a list. |
| 306 | .PP |
| 307 | Here is an example: The diff of the following two sequences: |
| 308 | .PP |
| 309 | .Vb 2 |
| 310 | \& a b c e h j l m n p |
| 311 | \& b c d e f j k l m r s t |
| 312 | .Ve |
| 313 | .PP |
| 314 | Result: |
| 315 | .PP |
| 316 | .Vb 2 |
| 317 | \& [ |
| 318 | \& [ [ '-', 0, 'a' ] ], |
| 319 | .Ve |
| 320 | .PP |
| 321 | .Vb 1 |
| 322 | \& [ [ '+', 2, 'd' ] ], |
| 323 | .Ve |
| 324 | .PP |
| 325 | .Vb 2 |
| 326 | \& [ [ '-', 4, 'h' ] , |
| 327 | \& [ '+', 4, 'f' ] ], |
| 328 | .Ve |
| 329 | .PP |
| 330 | .Vb 1 |
| 331 | \& [ [ '+', 6, 'k' ] ], |
| 332 | .Ve |
| 333 | .PP |
| 334 | .Vb 7 |
| 335 | \& [ [ '-', 8, 'n' ], |
| 336 | \& [ '-', 9, 'p' ], |
| 337 | \& [ '+', 9, 'r' ], |
| 338 | \& [ '+', 10, 's' ], |
| 339 | \& [ '+', 11, 't' ], |
| 340 | \& ] |
| 341 | \& ] |
| 342 | .Ve |
| 343 | .PP |
| 344 | There are five hunks here. The first hunk says that the \f(CW\*(C`a\*(C'\fR at |
| 345 | position 0 of the first sequence should be deleted (\f(CW\*(C`\-\*(C'\fR). The second |
| 346 | hunk says that the \f(CW\*(C`d\*(C'\fR at position 2 of the second sequence should |
| 347 | be inserted (\f(CW\*(C`+\*(C'\fR). The third hunk says that the \f(CW\*(C`h\*(C'\fR at position 4 |
| 348 | of the first sequence should be removed and replaced with the \f(CW\*(C`f\*(C'\fR |
| 349 | from position 4 of the second sequence. The other two hunks similarly. |
| 350 | .PP |
| 351 | \&\f(CW\*(C`diff\*(C'\fR may be passed an optional third parameter; this is a \s-1CODE\s0 |
| 352 | reference to a key generation function. See \*(L"\s-1KEY\s0 \s-1GENERATION\s0 \s-1FUNCTIONS\s0\*(R". |
| 353 | .PP |
| 354 | Additional parameters, if any, will be passed to the key generation |
| 355 | routine. |
| 356 | .ie n .Sh """sdiff""" |
| 357 | .el .Sh "\f(CWsdiff\fP" |
| 358 | .IX Subsection "sdiff" |
| 359 | .Vb 2 |
| 360 | \& @sdiffs = sdiff( \e@seq1, \e@seq2 ); |
| 361 | \& $sdiffs_ref = sdiff( \e@seq1, \e@seq2 ); |
| 362 | .Ve |
| 363 | .PP |
| 364 | \&\f(CW\*(C`sdiff\*(C'\fR computes all necessary components to show two sequences |
| 365 | and their minimized differences side by side, just like the |
| 366 | Unix-utility \fIsdiff\fR does: |
| 367 | .PP |
| 368 | .Vb 4 |
| 369 | \& same same |
| 370 | \& before | after |
| 371 | \& old < - |
| 372 | \& - > new |
| 373 | .Ve |
| 374 | .PP |
| 375 | It returns a list of array refs, each pointing to an array of |
| 376 | display instructions. In scalar context it returns a reference |
| 377 | to such a list. |
| 378 | .PP |
| 379 | Display instructions consist of three elements: A modifier indicator |
| 380 | (\f(CW\*(C`+\*(C'\fR: Element added, \f(CW\*(C`\-\*(C'\fR: Element removed, \f(CW\*(C`u\*(C'\fR: Element unmodified, |
| 381 | \&\f(CW\*(C`c\*(C'\fR: Element changed) and the value of the old and new elements, to |
| 382 | be displayed side by side. |
| 383 | .PP |
| 384 | An \f(CW\*(C`sdiff\*(C'\fR of the following two sequences: |
| 385 | .PP |
| 386 | .Vb 2 |
| 387 | \& a b c e h j l m n p |
| 388 | \& b c d e f j k l m r s t |
| 389 | .Ve |
| 390 | .PP |
| 391 | results in |
| 392 | .PP |
| 393 | [ [ '\-', 'a', '' ], |
| 394 | [ 'u', 'b', 'b' ], |
| 395 | [ 'u', 'c', 'c' ], |
| 396 | [ '+', '', 'd' ], |
| 397 | [ 'u', 'e', 'e' ], |
| 398 | [ 'c', 'h', 'f' ], |
| 399 | [ 'u', 'j', 'j' ], |
| 400 | [ '+', '', 'k' ], |
| 401 | [ 'u', 'l', 'l' ], |
| 402 | [ 'u', 'm', 'm' ], |
| 403 | [ 'c', 'n', 'r' ], |
| 404 | [ 'c', 'p', 's' ], |
| 405 | [ '+', '', 't' ] ] |
| 406 | .PP |
| 407 | \&\f(CW\*(C`sdiff\*(C'\fR may be passed an optional third parameter; this is a \s-1CODE\s0 |
| 408 | reference to a key generation function. See \*(L"\s-1KEY\s0 \s-1GENERATION\s0 \s-1FUNCTIONS\s0\*(R". |
| 409 | .PP |
| 410 | Additional parameters, if any, will be passed to the key generation |
| 411 | routine. |
| 412 | .ie n .Sh """traverse_sequences""" |
| 413 | .el .Sh "\f(CWtraverse_sequences\fP" |
| 414 | .IX Subsection "traverse_sequences" |
| 415 | \&\f(CW\*(C`traverse_sequences\*(C'\fR is the most general facility provided by this |
| 416 | module; \f(CW\*(C`diff\*(C'\fR and \f(CW\*(C`LCS\*(C'\fR are implemented as calls to it. |
| 417 | .PP |
| 418 | Imagine that there are two arrows. Arrow A points to an element of sequence A, |
| 419 | and arrow B points to an element of the sequence B. Initially, the arrows |
| 420 | point to the first elements of the respective sequences. \f(CW\*(C`traverse_sequences\*(C'\fR |
| 421 | will advance the arrows through the sequences one element at a time, calling an |
| 422 | appropriate user-specified callback function before each advance. It |
| 423 | willadvance the arrows in such a way that if there are equal elements \f(CW$A[$i]\fR |
| 424 | and \f(CW$B[$j]\fR which are equal and which are part of the \s-1LCS\s0, there will be |
| 425 | some moment during the execution of \f(CW\*(C`traverse_sequences\*(C'\fR when arrow A is |
| 426 | pointing to \f(CW$A[$i]\fR and arrow B is pointing to \f(CW$B[$j]\fR. When this happens, |
| 427 | \&\f(CW\*(C`traverse_sequences\*(C'\fR will call the \f(CW\*(C`MATCH\*(C'\fR callback function and then it will |
| 428 | advance both arrows. |
| 429 | .PP |
| 430 | Otherwise, one of the arrows is pointing to an element of its sequence that is |
| 431 | not part of the \s-1LCS\s0. \f(CW\*(C`traverse_sequences\*(C'\fR will advance that arrow and will |
| 432 | call the \f(CW\*(C`DISCARD_A\*(C'\fR or the \f(CW\*(C`DISCARD_B\*(C'\fR callback, depending on which arrow it |
| 433 | advanced. If both arrows point to elements that are not part of the \s-1LCS\s0, then |
| 434 | \&\f(CW\*(C`traverse_sequences\*(C'\fR will advance one of them and call the appropriate |
| 435 | callback, but it is not specified which it will call. |
| 436 | .PP |
| 437 | The arguments to \f(CW\*(C`traverse_sequences\*(C'\fR are the two sequences to traverse, and a |
| 438 | hash which specifies the callback functions, like this: |
| 439 | .PP |
| 440 | .Vb 5 |
| 441 | \& traverse_sequences( \e@seq1, \e@seq2, |
| 442 | \& { MATCH => $callback_1, |
| 443 | \& DISCARD_A => $callback_2, |
| 444 | \& DISCARD_B => $callback_3, |
| 445 | \& } ); |
| 446 | .Ve |
| 447 | .PP |
| 448 | Callbacks for \s-1MATCH\s0, \s-1DISCARD_A\s0, and \s-1DISCARD_B\s0 are invoked with at least the |
| 449 | indices of the two arrows as their arguments. They are not expected to return |
| 450 | any values. If a callback is omitted from the table, it is not called. |
| 451 | .PP |
| 452 | Callbacks for A_FINISHED and B_FINISHED are invoked with at least the |
| 453 | corresponding index in A or B. |
| 454 | .PP |
| 455 | If arrow A reaches the end of its sequence, before arrow B does, |
| 456 | \&\f(CW\*(C`traverse_sequences\*(C'\fR will call the \f(CW\*(C`A_FINISHED\*(C'\fR callback when it advances |
| 457 | arrow B, if there is such a function; if not it will call \f(CW\*(C`DISCARD_B\*(C'\fR instead. |
| 458 | Similarly if arrow B finishes first. \f(CW\*(C`traverse_sequences\*(C'\fR returns when both |
| 459 | arrows are at the ends of their respective sequences. It returns true on |
| 460 | success and false on failure. At present there is no way to fail. |
| 461 | .PP |
| 462 | \&\f(CW\*(C`traverse_sequences\*(C'\fR may be passed an optional fourth parameter; this is a |
| 463 | \&\s-1CODE\s0 reference to a key generation function. See \*(L"\s-1KEY\s0 \s-1GENERATION\s0 \s-1FUNCTIONS\s0\*(R". |
| 464 | .PP |
| 465 | Additional parameters, if any, will be passed to the key generation function. |
| 466 | .ie n .Sh """traverse_balanced""" |
| 467 | .el .Sh "\f(CWtraverse_balanced\fP" |
| 468 | .IX Subsection "traverse_balanced" |
| 469 | \&\f(CW\*(C`traverse_balanced\*(C'\fR is an alternative to \f(CW\*(C`traverse_sequences\*(C'\fR. It |
| 470 | uses a different algorithm to iterate through the entries in the |
| 471 | computed \s-1LCS\s0. Instead of sticking to one side and showing element changes |
| 472 | as insertions and deletions only, it will jump back and forth between |
| 473 | the two sequences and report \fIchanges\fR occurring as deletions on one |
| 474 | side followed immediatly by an insertion on the other side. |
| 475 | .PP |
| 476 | In addition to the |
| 477 | \&\f(CW\*(C`DISCARD_A\*(C'\fR, |
| 478 | \&\f(CW\*(C`DISCARD_B\*(C'\fR, and |
| 479 | \&\f(CW\*(C`MATCH\*(C'\fR |
| 480 | callbacks supported by \f(CW\*(C`traverse_sequences\*(C'\fR, \f(CW\*(C`traverse_balanced\*(C'\fR supports |
| 481 | a \f(CW\*(C`CHANGE\*(C'\fR callback indicating that one element got \f(CW\*(C`replaced\*(C'\fR by another: |
| 482 | .PP |
| 483 | .Vb 6 |
| 484 | \& traverse_sequences( \e@seq1, \e@seq2, |
| 485 | \& { MATCH => $callback_1, |
| 486 | \& DISCARD_A => $callback_2, |
| 487 | \& DISCARD_B => $callback_3, |
| 488 | \& CHANGE => $callback_4, |
| 489 | \& } ); |
| 490 | .Ve |
| 491 | .PP |
| 492 | If no \f(CW\*(C`CHANGE\*(C'\fR callback is specified, \f(CW\*(C`traverse_balanced\*(C'\fR |
| 493 | will map \f(CW\*(C`CHANGE\*(C'\fR events to \f(CW\*(C`DISCARD_A\*(C'\fR and \f(CW\*(C`DISCARD_B\*(C'\fR actions, |
| 494 | therefore resulting in a similar behaviour as \f(CW\*(C`traverse_sequences\*(C'\fR |
| 495 | with different order of events. |
| 496 | .PP |
| 497 | \&\f(CW\*(C`traverse_balanced\*(C'\fR might be a bit slower than \f(CW\*(C`traverse_sequences\*(C'\fR, |
| 498 | noticable only while processing huge amounts of data. |
| 499 | .PP |
| 500 | The \f(CW\*(C`sdiff\*(C'\fR function of this module |
| 501 | is implemented as call to \f(CW\*(C`traverse_balanced\*(C'\fR. |
| 502 | .SH "KEY GENERATION FUNCTIONS" |
| 503 | .IX Header "KEY GENERATION FUNCTIONS" |
| 504 | \&\f(CW\*(C`diff\*(C'\fR, \f(CW\*(C`LCS\*(C'\fR, and \f(CW\*(C`traverse_sequences\*(C'\fR accept an optional last parameter. |
| 505 | This is a \s-1CODE\s0 reference to a key generating (hashing) function that should |
| 506 | return a string that uniquely identifies a given element. It should be the |
| 507 | case that if two elements are to be considered equal, their keys should be the |
| 508 | same (and the other way around). If no key generation function is provided, |
| 509 | the key will be the element as a string. |
| 510 | .PP |
| 511 | By default, comparisons will use \*(L"eq\*(R" and elements will be turned into keys |
| 512 | using the default stringizing operator '""'. |
| 513 | .PP |
| 514 | Where this is important is when you're comparing something other than strings. |
| 515 | If it is the case that you have multiple different objects that should be |
| 516 | considered to be equal, you should supply a key generation function. Otherwise, |
| 517 | you have to make sure that your arrays contain unique references. |
| 518 | .PP |
| 519 | For instance, consider this example: |
| 520 | .PP |
| 521 | .Vb 1 |
| 522 | \& package Person; |
| 523 | .Ve |
| 524 | .PP |
| 525 | .Vb 5 |
| 526 | \& sub new |
| 527 | \& { |
| 528 | \& my $package = shift; |
| 529 | \& return bless { name => '', ssn => '', @_ }, $package; |
| 530 | \& } |
| 531 | .Ve |
| 532 | .PP |
| 533 | .Vb 5 |
| 534 | \& sub clone |
| 535 | \& { |
| 536 | \& my $old = shift; |
| 537 | \& my $new = bless { %$old }, ref($old); |
| 538 | \& } |
| 539 | .Ve |
| 540 | .PP |
| 541 | .Vb 4 |
| 542 | \& sub hash |
| 543 | \& { |
| 544 | \& return shift()->{'ssn'}; |
| 545 | \& } |
| 546 | .Ve |
| 547 | .PP |
| 548 | .Vb 5 |
| 549 | \& my $person1 = Person->new( name => 'Joe', ssn => '123-45-6789' ); |
| 550 | \& my $person2 = Person->new( name => 'Mary', ssn => '123-47-0000' ); |
| 551 | \& my $person3 = Person->new( name => 'Pete', ssn => '999-45-2222' ); |
| 552 | \& my $person4 = Person->new( name => 'Peggy', ssn => '123-45-9999' ); |
| 553 | \& my $person5 = Person->new( name => 'Frank', ssn => '000-45-9999' ); |
| 554 | .Ve |
| 555 | .PP |
| 556 | If you did this: |
| 557 | .PP |
| 558 | .Vb 3 |
| 559 | \& my $array1 = [ $person1, $person2, $person4 ]; |
| 560 | \& my $array2 = [ $person1, $person3, $person4, $person5 ]; |
| 561 | \& Algorithm::Diff::diff( $array1, $array2 ); |
| 562 | .Ve |
| 563 | .PP |
| 564 | everything would work out \s-1OK\s0 (each of the objects would be converted |
| 565 | into a string like \*(L"Person=HASH(0x82425b0)\*(R" for comparison). |
| 566 | .PP |
| 567 | But if you did this: |
| 568 | .PP |
| 569 | .Vb 3 |
| 570 | \& my $array1 = [ $person1, $person2, $person4 ]; |
| 571 | \& my $array2 = [ $person1, $person3, $person4->clone(), $person5 ]; |
| 572 | \& Algorithm::Diff::diff( $array1, $array2 ); |
| 573 | .Ve |
| 574 | .PP |
| 575 | $person4 and \f(CW$person4\fR\->\fIclone()\fR (which have the same name and \s-1SSN\s0) |
| 576 | would be seen as different objects. If you wanted them to be considered |
| 577 | equivalent, you would have to pass in a key generation function: |
| 578 | .PP |
| 579 | .Vb 3 |
| 580 | \& my $array1 = [ $person1, $person2, $person4 ]; |
| 581 | \& my $array2 = [ $person1, $person3, $person4->clone(), $person5 ]; |
| 582 | \& Algorithm::Diff::diff( $array1, $array2, \e&Person::hash ); |
| 583 | .Ve |
| 584 | .PP |
| 585 | This would use the 'ssn' field in each Person as a comparison key, and |
| 586 | so would consider \f(CW$person4\fR and \f(CW$person4\fR\->\fIclone()\fR as equal. |
| 587 | .PP |
| 588 | You may also pass additional parameters to the key generation function |
| 589 | if you wish. |
| 590 | .SH "AUTHOR" |
| 591 | .IX Header "AUTHOR" |
| 592 | This version by Ned Konz, perl@bike\-nomad.com |
| 593 | .SH "LICENSE" |
| 594 | .IX Header "LICENSE" |
| 595 | Copyright (c) 2000\-2002 Ned Konz. All rights reserved. |
| 596 | This program is free software; |
| 597 | you can redistribute it and/or modify it under the same terms |
| 598 | as Perl itself. |
| 599 | .SH "CREDITS" |
| 600 | .IX Header "CREDITS" |
| 601 | Versions through 0.59 (and much of this documentation) were written by: |
| 602 | .PP |
| 603 | Mark-Jason Dominus, mjd\-perl\-diff@plover.com |
| 604 | .PP |
| 605 | This version borrows the documentation and names of the routines |
| 606 | from Mark\-Jason's, but has all new code in Diff.pm. |
| 607 | .PP |
| 608 | This code was adapted from the Smalltalk code of |
| 609 | Mario Wolczko <mario@wolczko.com>, which is available at |
| 610 | ftp://st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st |
| 611 | .PP |
| 612 | \&\f(CW\*(C`sdiff\*(C'\fR and \f(CW\*(C`traverse_balanced\*(C'\fR were written by Mike Schilli |
| 613 | <m@perlmeister.com>. |
| 614 | .PP |
| 615 | The algorithm is that described in |
| 616 | \&\fIA Fast Algorithm for Computing Longest Common Subsequences\fR, |
| 617 | \&\s-1CACM\s0, vol.20, no.5, pp.350\-353, May 1977, with a few |
| 618 | minor improvements to improve the speed. |