diff Text file difference utility.
---- Copyright 1987, 1989 by Donald C. Lindsay,
School of Computer Science, Carnegie Mellon University.
Copyright 1982 by Symbionics.
Use without fee is permitted when not for direct commercial
advantage, and when credit to the source is given. Other uses
require specific permission.
Converted from C to Java by Ian F. Darwin, http://www.darwinsys.com/, January, 1997.
Copyright 1997, Ian F. Darwin.
Conversion is NOT FULLY TESTED.
USAGE: diff oldfile newfile
This program assumes that "oldfile" and "newfile" are text files.
The program writes to stdout a description of the changes which would
transform "oldfile" into "newfile".
The printout is in the form of commands, each followed by a block of
text. The text is delimited by the commands, which are:
DELETE AT n
..deleted lines
INSERT BEFORE n
..inserted lines
n MOVED TO BEFORE n
..moved lines
n CHANGED FROM
..old lines
CHANGED TO
..newer lines
The line numbers all refer to the lines of the oldfile, as they are
numbered before any commands are applied.
The text lines are printed as-is, without indentation or prefixing. The
commands are printed in upper case, with a prefix of ">>>>", so that
they will stand out. Other schemes may be preferred.
Files which contain more than MAXLINECOUNT lines cannot be processed.
This can be fixed by changing "symbol" to a Vector.
The algorithm is taken from Communications of the ACM, Apr78 (21, 4, 264-),
"A Technique for Isolating Differences Between Files."
Ignoring I/O, and ignoring the symbol table, it should take O(N) time.
This implementation takes fixed space, plus O(U) space for the symbol
table (where U is the number of unique lines). Methods exist to change
the fixed space to O(N) space.
Note that this is not the only interesting file-difference algorithm. In
general, different algorithms draw different conclusions about the
changes that have been made to the oldfile. This algorithm is sometimes
"more right", particularly since it does not consider a block move to be
an insertion and a (separate) deletion. However, on some files it will be
"less right". This is a consequence of the fact that files may contain
many identical lines (particularly if they are program source). Each
algorithm resolves the ambiguity in its own way, and the resolution
is never guaranteed to be "right". However, it is often excellent.
This program is intended to be pedagogic. Specifically, this program was
the basis of the Literate Programming column which appeared in the
Communications of the ACM (CACM), in the June 1989 issue (32, 6,
740-755).
By "pedagogic", I do not mean that the program is gracefully worded, or
that it showcases language features or its algorithm. I also do not mean
that it is highly accessible to beginners, or that it is intended to be
read in full, or in a particular order. Rather, this program is an
example of one professional's style of keeping things organized and
maintainable.
The program would be better if the "print" variables were wrapped into
a struct. In general, grouping related variables in this way improves
documentation, and adds the ability to pass the group in argument lists.
This program is a de-engineered version of a program which uses less
memory and less time. The article points out that the "symbol" arrays
can be implemented as arrays of pointers to arrays, with dynamic
allocation of the subarrays. (In C, macros are very useful for hiding
the two-level accesses.) In Java, a Vector would be used. This allows an
extremely large value for MAXLINECOUNT, without dedicating fixed arrays.
(The "other" array can be allocated after the input phase, when the exact
sizes are known.) The only slow piece of code is the "strcmp" in the tree
descent: it can be speeded up by keeping a hash in the tree node, and
only using "strcmp" when two hashes happen to be equal.
Change Log
----------
1Jan97 Ian F. Darwin: first working rewrite in Java, based entirely on
D.C.Lindsay's reasonable C version.
Changed comments from /***************** to /**, shortened, added
whitespace, used tabs more, etc.
6jul89 D.C.Lindsay, CMU: fixed portability bug. Thanks, Gregg Wonderly.
Just changed "char ch" to "int ch".
Also added comment about way to improve code.
10jun89 D.C.Lindsay, CMU: posted version created.
Copyright notice changed to ACM style, and Dept. is now School.
ACM article referenced in docn.
26sep87 D.C.Lindsay, CMU: publication version created.
Condensed all 1982/83 change log entries.
Removed all command line options, and supporting code. This
simplified the input code (no case reduction etc). It also
simplified the symbol table, which was capable of remembering
offsets into files (instead of strings), and trusting (!) hash
values to be unique.
Removed dynamic allocation of arrays: now fixed static arrays.
Removed speed optimizations in symtab package.
Removed string compression/decompression code.
Recoded to Unix standards from old Lattice/MSDOS standards.
(This affected only the #include's and the IO.)
Some renaming of variables, and rewording of comments.
1982/83 D.C.Lindsay, Symbionics: created.