1 4 6 import java.io.*; 7 8 9 class fileInfo { 10 11 static final int MAXLINECOUNT = 20000; 12 13 DataInputStream file; 14 public int maxLine; 15 node symbol[]; 16 int other[]; 17 18 19 20 23 fileInfo( String filename ) { 24 symbol = new node [ MAXLINECOUNT+2 ]; 25 other = null; try { 27 file = new DataInputStream( 28 new FileInputStream( filename)); 29 } catch (IOException e) { 30 System.err.println("Diff can't read file " + 31 filename ); 32 System.err.println("Error Exception was:" + e ); 33 System.exit(1); 34 } 35 } 36 void alloc() { 38 other = new int[symbol.length + 2]; 39 } 40 }; 41 42 157 public class Diff { 158 159 160 final int UNREAL=Integer.MAX_VALUE; 161 162 163 fileInfo oldinfo, newinfo; 164 165 175 int blocklen[]; 176 177 183 public static void main(String argstrings[]) 184 { 185 if ( argstrings.length != 2 ) { 186 System.err.println("Usage: diff oldfile newfile" ); 187 System.exit(1); 188 } 189 Diff d = new Diff(); 190 d.doDiff(argstrings[0], argstrings[1]); 191 return; 192 } 193 194 195 Diff() { 196 } 197 198 199 public void doDiff(String oldFile, String newFile) { 200 println( ">>>> Difference of file \"" + oldFile + 201 "\" and file \"" + newFile + "\".\n"); 202 oldinfo = new fileInfo(oldFile); 203 newinfo = new fileInfo(newFile); 204 205 try { 206 inputscan( oldinfo ); 207 inputscan( newinfo ); 208 } catch (IOException e) { 209 System.err.println("Read error: " + e); 210 } 211 212 214 blocklen = new int[ (oldinfo.maxLine>newinfo.maxLine? 215 oldinfo.maxLine : newinfo.maxLine) + 2 ]; 216 oldinfo.alloc(); 217 newinfo.alloc(); 218 219 220 transform(); 221 printout(); 222 } 223 224 229 void inputscan( fileInfo pinfo ) throws IOException 230 { 231 String linebuffer; 232 233 pinfo.maxLine = 0; 234 while ((linebuffer = pinfo.file.readLine()) != null) { 235 storeline( linebuffer, pinfo ); 236 } 237 } 238 239 245 void storeline( String linebuffer, fileInfo pinfo ) 246 { 247 int linenum = ++pinfo.maxLine; 248 if ( linenum > fileInfo.MAXLINECOUNT ) { 249 System.err.println( "MAXLINECOUNT exceeded, must stop." ); 250 System.exit(1); 251 } 252 pinfo.symbol[ linenum ] = 253 node.addSymbol( linebuffer, pinfo == oldinfo, linenum ); 254 } 255 256 263 void transform() 264 { 265 int oldline, newline; 266 int oldmax = oldinfo.maxLine + 2; 267 int newmax = newinfo.maxLine + 2; 268 269 for (oldline=0; oldline < oldmax; oldline++ ) 270 oldinfo.other[oldline]= -1; 271 for (newline=0; newline < newmax; newline++ ) 272 newinfo.other[newline]= -1; 273 274 scanunique(); 275 scanafter(); 276 scanbefore(); 277 scanblocks(); 278 } 279 280 288 void scanunique() 289 { 290 int oldline, newline; 291 node psymbol; 292 293 for( newline = 1; newline <= newinfo.maxLine; newline++ ) { 294 psymbol = newinfo.symbol[ newline ]; 295 if ( psymbol.symbolIsUnique()) { oldline = psymbol.linenum; 297 newinfo.other[ newline ] = oldline; oldinfo.other[ oldline ] = newline; 299 } 300 } 301 newinfo.other[ 0 ] = 0; 302 oldinfo.other[ 0 ] = 0; 303 newinfo.other[ newinfo.maxLine + 1 ] = oldinfo.maxLine + 1; 304 oldinfo.other[ oldinfo.maxLine + 1 ] = newinfo.maxLine + 1; 305 } 306 307 317 void scanafter() 318 { 319 int oldline, newline; 320 321 for( newline = 0; newline <= newinfo.maxLine; newline++ ) { 322 oldline = newinfo.other[ newline ]; 323 if ( oldline >= 0 ) { 324 for(;;) { 325 if ( ++oldline > oldinfo.maxLine ) break; 326 if ( oldinfo.other[ oldline ] >= 0 ) break; 327 if ( ++newline > newinfo.maxLine ) break; 328 if ( newinfo.other[ newline ] >= 0 ) break; 329 330 332 333 if ( newinfo.symbol[ newline ] != 334 oldinfo.symbol[ oldline ] ) break; 336 newinfo.other[newline] = oldline; oldinfo.other[oldline] = newline; 338 } 339 } 340 } 341 } 342 343 348 void scanbefore() 349 { 350 int oldline, newline; 351 352 for( newline = newinfo.maxLine + 1; newline > 0; newline-- ) { 353 oldline = newinfo.other[ newline ]; 354 if ( oldline >= 0 ) { 355 for(;;) { 356 if ( --oldline <= 0 ) break; 357 if ( oldinfo.other[ oldline ] >= 0 ) break; 358 if ( --newline <= 0 ) break; 359 if ( newinfo.other[ newline ] >= 0 ) break; 360 361 363 364 if ( newinfo.symbol[ newline ] != 365 oldinfo.symbol[ oldline ] ) break; 367 newinfo.other[newline] = oldline; oldinfo.other[oldline] = newline; 369 } 370 } 371 } 372 } 373 374 379 void scanblocks() 380 { 381 int oldline, newline; 382 int oldfront = 0; int newlast = -1; 385 for( oldline = 1; oldline <= oldinfo.maxLine; oldline++ ) 386 blocklen[ oldline ] = 0; 387 blocklen[ oldinfo.maxLine + 1 ] = UNREAL; 389 for( oldline = 1; oldline <= oldinfo.maxLine; oldline++ ) { 390 newline = oldinfo.other[ oldline ]; 391 if ( newline < 0 ) oldfront = 0; 392 else{ 393 if ( oldfront == 0 ) oldfront = oldline; 394 if ( newline != (newlast+1)) oldfront = oldline; 395 ++blocklen[ oldfront ]; 396 } 397 newlast = newline; 398 } 399 } 400 401 402 public static final int 405 idle = 0, delete = 1, insert = 2, movenew = 3, moveold = 4, 406 same = 5, change = 6; 407 int printstatus; 408 boolean anyprinted; 409 int printoldline, printnewline; 411 415 void printout() 416 { 417 printstatus = idle; 418 anyprinted = false; 419 for( printoldline = printnewline = 1; ; ) { 420 if ( printoldline > oldinfo.maxLine ) { newconsume(); break;} 421 if ( printnewline > newinfo.maxLine ) { oldconsume(); break;} 422 if ( newinfo.other[ printnewline ] < 0 ) { 423 if ( oldinfo.other[ printoldline ] < 0 ) 424 showchange(); 425 else 426 showinsert(); 427 } 428 else if ( oldinfo.other[ printoldline ] < 0 ) 429 showdelete(); 430 else if ( blocklen[ printoldline ] < 0 ) 431 skipold(); 432 else if ( oldinfo.other[ printoldline ] == printnewline ) 433 showsame(); 434 else 435 showmove(); 436 } 437 if ( anyprinted == true ) println( ">>>> End of differences." ); 438 else println( ">>>> Files are identical." ); 439 } 440 441 445 void newconsume() 446 { 447 for(;;) { 448 if ( printnewline > newinfo.maxLine ) 449 break; 450 if ( newinfo.other[ printnewline ] < 0 ) showinsert(); 451 else showmove(); 452 } 453 } 454 455 460 void oldconsume() 461 { 462 for(;;) { 463 if ( printoldline > oldinfo.maxLine ) 464 break; 465 printnewline = oldinfo.other[ printoldline ]; 466 if ( printnewline < 0 ) showdelete(); 467 else if ( blocklen[ printoldline ] < 0 ) skipold(); 468 else showmove(); 469 } 470 } 471 472 476 void showdelete() 477 { 478 if ( printstatus != delete ) 479 println( ">>>> DELETE AT " + printoldline); 480 printstatus = delete; 481 oldinfo.symbol[ printoldline ].showSymbol(); 482 anyprinted = true; 483 printoldline++; 484 } 485 486 490 void showinsert() 491 { 492 if ( printstatus == change ) println( ">>>> CHANGED TO" ); 493 else if ( printstatus != insert ) 494 println( ">>>> INSERT BEFORE " + printoldline ); 495 printstatus = insert; 496 newinfo.symbol[ printnewline ].showSymbol(); 497 anyprinted = true; 498 printnewline++; 499 } 500 501 506 void showchange() 507 { 508 if ( printstatus != change ) 509 println( ">>>> " + printoldline + " CHANGED FROM"); 510 printstatus = change; 511 oldinfo.symbol[ printoldline ].showSymbol(); 512 anyprinted = true; 513 printoldline++; 514 } 515 516 522 void skipold() 523 { 524 printstatus = idle; 525 for(;;) { 526 if ( ++printoldline > oldinfo.maxLine ) 527 break; 528 if ( oldinfo.other[ printoldline ] < 0 ) 529 break; 530 if ( blocklen[ printoldline ]!=0) 531 break; 532 } 533 } 534 535 541 void skipnew() 542 { 543 int oldline; 544 printstatus = idle; 545 for(;;) { 546 if ( ++printnewline > newinfo.maxLine ) 547 break; 548 oldline = newinfo.other[ printnewline ]; 549 if ( oldline < 0 ) 550 break; 551 if ( blocklen[ oldline ] != 0) 552 break; 553 } 554 } 555 556 561 void showsame() 562 { 563 int count; 564 printstatus = idle; 565 if ( newinfo.other[ printnewline ] != printoldline ) { 566 System.err.println("BUG IN LINE REFERENCING"); 567 System.exit(1); 568 } 569 count = blocklen[ printoldline ]; 570 printoldline += count; 571 printnewline += count; 572 } 573 574 579 void showmove() 580 { 581 int oldblock = blocklen[ printoldline ]; 582 int newother = newinfo.other[ printnewline ]; 583 int newblock = blocklen[ newother ]; 584 585 if ( newblock < 0 ) skipnew(); else if ( oldblock >= newblock ) { blocklen[newother] = -1; println( ">>>> " + newother + 589 " THRU " + (newother + newblock - 1) + 590 " MOVED TO BEFORE " + printoldline ); 591 for( ; newblock > 0; newblock--, printnewline++ ) 592 newinfo.symbol[ printnewline ].showSymbol(); 593 anyprinted = true; 594 printstatus = idle; 595 596 } else 597 skipold(); 598 } 599 600 601 public void println(String s) { 602 System.out.println(s); 603 } 604 }; 606 611 class node{ 612 node pleft, pright; 613 int linenum; 614 615 static final int freshnode = 0, 616 oldonce = 1, newonce = 2, bothonce = 3, other = 4; 617 618 int linestate; 619 String line; 620 621 static node panchor = null; 622 623 627 node( String pline) 628 { 629 pleft = pright = null; 630 linestate = freshnode; 631 632 line = pline; 633 } 634 635 640 static node matchsymbol( String pline ) 641 { 642 int comparison; 643 node pnode = panchor; 644 if ( panchor == null ) return panchor = new node( pline); 645 for(;;) { 646 comparison = pnode.line.compareTo(pline); 647 if ( comparison == 0 ) return pnode; 648 649 if ( comparison < 0 ) { 650 if ( pnode.pleft == null ) { 651 pnode.pleft = new node( pline); 652 return pnode.pleft; 653 } 654 pnode = pnode.pleft; 655 } 656 if ( comparison > 0 ) { 657 if ( pnode.pright == null ) { 658 pnode.pright = new node( pline); 659 return pnode.pright; 660 } 661 pnode = pnode.pright; 662 } 663 } 664 665 } 666 667 672 static node addSymbol( String pline, boolean inoldfile, int linenum ) 673 { 674 node pnode; 675 pnode = matchsymbol( pline ); 676 if ( pnode.linestate == freshnode ) { 677 pnode.linestate = inoldfile ? oldonce : newonce; 678 } else { 679 if (( pnode.linestate == oldonce && !inoldfile ) || 680 ( pnode.linestate == newonce && inoldfile )) 681 pnode.linestate = bothonce; 682 else pnode.linestate = other; 683 } 684 if (inoldfile) pnode.linenum = linenum; 685 return pnode; 686 } 687 688 694 boolean symbolIsUnique() 695 { 696 return (linestate == bothonce ); 697 } 698 699 702 void showSymbol() 703 { 704 System.out.println(line); 705 } 706 } 707 | Popular Tags |