Class Diff


  • public class Diff
    extends Object
    A class to compare vectors of objects. The result of comparison is a list of change objects which form an edit script. The objects compared are traditionally lines of text from two files. Comparison options such as "ignore whitespace" are implemented by modifying the equals and hashcode methods for the objects compared.

    The basic algorithm is described in:
    "An O(ND) Difference Algorithm and its Variations", Eugene Myers, Algorithmica Vol. 1 No. 2, 1986, p 251.

    This class outputs different results from GNU diff 1.15 on some inputs. Our results are actually better (smaller change list, smaller total size of changes), but it would be nice to know why. Perhaps there is a memory overwrite bug in GNU diff 1.15.

    • Constructor Detail

      • Diff

        public Diff​(Object[] a,
                    Object[] b)
        Prepare to find differences between two arrays. Each element of the arrays is translated to an "equivalence number" based on the result of equals. The original Object arrays are no longer needed for computing the differences. They will be needed again later to print the results of the comparison as an edit script, if desired.
        Parameters:
        a - first array
        b - second array
    • Method Detail

      • diag

        private int diag​(int xoff,
                         int xlim,
                         int yoff,
                         int ylim)
        Find the midpoint of the shortest edit script for a specified portion of the two files. We scan from the beginnings of the files, and simultaneously from the ends, doing a breadth-first search through the space of edit-sequence. When the two searches meet, we have found the midpoint of the shortest edit sequence. The value returned is the number of the diagonal on which the midpoint lies. The diagonal number equals the number of inserted lines minus the number of deleted lines (counting only lines before the midpoint). The edit cost is stored into COST; this is the total number of lines inserted or deleted (counting only lines before the midpoint). This function assumes that the first lines of the specified portions of the two files do not match, and likewise that the last lines do not match. The caller must trim matching lines from the beginning and end of the portions it is going to specify. Note that if we return the "wrong" diagonal value, or if the value of bdiag at that diagonal is "wrong", the worst this can do is cause suboptimal diff output. It cannot cause incorrect diff output.
        Parameters:
        xoff - xoff
        xlim - xlim
        yoff - yoff
        ylim - ylim
        Returns:
        midpoint of the shortest edit script
      • compareseq

        private void compareseq​(int xoff,
                                int xlim,
                                int yoff,
                                int ylim)
        Compare in detail contiguous subsequences of the two files which are known, as a whole, to match each other. The results are recorded in the vectors filevec[N].changed_flag, by storing a 1 in the element for each line that is an insertion or deletion. The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. Note that XLIM, YLIM are exclusive bounds. All line numbers are origin-0 and discarded lines are not counted.
        Parameters:
        xoff - xoff
        xlim - xlim
        yoff - yoff
        ylim - ylim
      • discardConfusingLines

        private void discardConfusingLines()
        Discard lines from one file that have no matches in the other file.
      • shiftBoundaries

        private void shiftBoundaries()
        Adjust inserts/deletes of blank lines to join changes as much as possible.
      • diff2

        public final Diff.Change diff2​(boolean reverse)
        Report the differences of two files. DEPTH is the current directory depth.
        Parameters:
        reverse - if true use reverseScript else use forwardScript
        Returns:
        the differences of two files
      • diff

        public Diff.Change diff​(Diff.ScriptBuilder bld)
        Get the results of comparison as an edit script. The script is described by a list of changes. The standard ScriptBuilder implementations provide for forward and reverse edit scripts. Alternate implementations could, for instance, list common elements instead of differences.
        Parameters:
        bld - an object to build the script from change flags
        Returns:
        the head of a list of changes