001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.tools;
003
004//// Taken from http://www.bmsi.com/java/#diff
005
006// http://www.bmsi.com/java/DiffPrint.java could also be useful
007
008/*
009 * $Log: Diff.java,v $
010 * Revision 1.15  2013/04/01 16:27:31  stuart
011 * Fix DiffPrint unified format with test cases.
012 * Begin porting some diff-2.7 features.
013 *
014 * Revision 1.14  2010/03/03 21:21:25  stuart
015 * Test new direct equivalence API
016 *
017 * Revision 1.13  2009/12/07 17:43:17  stuart
018 * Compute equivMax for int[] ctor
019 *
020 * Revision 1.12  2009/12/07 17:34:46  stuart
021 * Ctor with int[].
022 *
023 * Revision 1.11  2009/11/15 01:11:54  stuart
024 * Diff doesn't need to be generic
025 *
026 * Revision 1.10  2009/11/15 00:54:03  stuart
027 * Update to Java 5 containers
028 *
029 * Revision 1.7  2009/01/19 03:05:26  stuart
030 * Fix StackOverflow bug with heuristic on reported by Jimmy Han.
031 *
032 * Revision 1.6  2003/03/06 22:51:32  stuart
033 * Convert to CVS
034 *
035 * Revision 1.5  2002/07/19  19:14:40  stuart
036 * fix reverseScript, make change ctor public, update docs
037 *
038 * Revision 1.4  2002/04/09  17:53:39  stuart
039 * More flexible interface for diff() function.
040 *
041 * Revision 1.3  2000/03/03 21:58:03  stuart
042 * move discard_confusing_lines and shift_boundaries to class file_data
043 *
044 * Revision 1.2  2000/03/02  16:37:38  stuart
045 * Add GPL and copyright
046 *
047 */
048
049import java.util.HashMap;
050import java.util.Map;
051
052/** A class to compare vectors of objects.  The result of comparison
053    is a list of <code>change</code> objects which form an
054    edit script.  The objects compared are traditionally lines
055    of text from two files.  Comparison options such as "ignore
056    whitespace" are implemented by modifying the <code>equals</code>
057    and <code>hashcode</code> methods for the objects compared.
058<p>
059   The basic algorithm is described in: <br>
060   "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
061   Algorithmica Vol. 1 No. 2, 1986, p 251.
062<p>
063   This class outputs different results from GNU diff 1.15 on some
064   inputs.  Our results are actually better (smaller change list, smaller
065   total size of changes), but it would be nice to know why.  Perhaps
066   there is a memory overwrite bug in GNU diff 1.15.
067
068  @author Stuart D. Gathman, translated from GNU diff 1.15
069    Copyright (C) 2000  Business Management Systems, Inc.
070<p>
071    This program is free software; you can redistribute it and/or modify
072    it under the terms of the GNU General Public License as published by
073    the Free Software Foundation; either version 1, or (at your option)
074    any later version.
075<p>
076    This program is distributed in the hope that it will be useful,
077    but WITHOUT ANY WARRANTY; without even the implied warranty of
078    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
079    GNU General Public License for more details.
080<p>
081    You should have received a copy of the <a href=COPYING.txt>
082    GNU General Public License</a>
083    along with this program; if not, write to the Free Software
084    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
085 */
086public class Diff {
087
088    /** Prepare to find differences between two arrays.  Each element of
089      the arrays is translated to an "equivalence number" based on
090      the result of <code>equals</code>.  The original Object arrays
091      are no longer needed for computing the differences.  They will
092      be needed again later to print the results of the comparison as
093      an edit script, if desired.
094     * @param a first array
095     * @param b second array
096     */
097    public Diff(Object[] a, Object[] b) {
098        Map<Object, Integer> h = new HashMap<>(a.length + b.length);
099        filevec = new FileData[] {new FileData(a, h), new FileData(b, h)};
100    }
101
102    /** 1 more than the maximum equivalence value used for this or its
103     sibling file. */
104    private int equivMax = 1;
105
106    /* Vectors being compared. */
107    private int[] xvec;
108    private int[] yvec;
109    private int[] fdiag;      /* Vector, indexed by diagonal, containing
110                   the X coordinate of the point furthest
111                   along the given diagonal in the forward
112                   search of the edit matrix. */
113    private int[] bdiag;      /* Vector, indexed by diagonal, containing
114                   the X coordinate of the point furthest
115                   along the given diagonal in the backward
116                   search of the edit matrix. */
117    private int fdiagoff;
118    private int bdiagoff;
119    private final FileData[] filevec;
120    private int cost;
121
122    /**
123     * Find the midpoint of the shortest edit script for a specified
124     * portion of the two files.
125     * <p>
126     * We scan from the beginnings of the files, and simultaneously from the ends,
127     * doing a breadth-first search through the space of edit-sequence.
128     * When the two searches meet, we have found the midpoint of the shortest
129     * edit sequence.
130     * <p>
131     * The value returned is the number of the diagonal on which the midpoint lies.
132     * The diagonal number equals the number of inserted lines minus the number
133     * of deleted lines (counting only lines before the midpoint).
134     * The edit cost is stored into COST; this is the total number of
135     * lines inserted or deleted (counting only lines before the midpoint).
136     * <p>
137     * This function assumes that the first lines of the specified portions
138     * of the two files do not match, and likewise that the last lines do not
139     * match.  The caller must trim matching lines from the beginning and end
140     * of the portions it is going to specify.
141     * <p>
142     * Note that if we return the "wrong" diagonal value, or if
143     * the value of bdiag at that diagonal is "wrong",
144     * the worst this can do is cause suboptimal diff output.
145     * It cannot cause incorrect diff output.
146     * @param xoff xoff
147     * @param xlim xlim
148     * @param yoff yoff
149     * @param ylim ylim
150     * @return midpoint of the shortest edit script
151     */
152    private int diag(int xoff, int xlim, int yoff, int ylim) {
153        final int[] fd = fdiag; // Give the compiler a chance.
154        final int[] bd = bdiag; // Additional help for the compiler.
155        final int[] xv = xvec;      // Still more help for the compiler.
156        final int[] yv = yvec;      // And more and more . . .
157        final int dmin = xoff - ylim;   // Minimum valid diagonal.
158        final int dmax = xlim - yoff;   // Maximum valid diagonal.
159        final int fmid = xoff - yoff;   // Center diagonal of top-down search.
160        final int bmid = xlim - ylim;   // Center diagonal of bottom-up search.
161        // Limits of top-down search.
162        int fmin = fmid;
163        int fmax = fmid;
164        // Limits of bottom-up search.
165        int bmin = bmid;
166        int bmax = bmid;
167        // True if southeast corner is on an odd diagonal with respect to the northwest.
168        final boolean odd = (fmid - bmid & 1) != 0;
169
170        fd[fdiagoff + fmid] = xoff;
171        bd[bdiagoff + bmid] = xlim;
172
173        for (int c = 1;; ++c) {
174            int d;          /* Active diagonal. */
175
176            /* Extend the top-down search by an edit step in each diagonal. */
177            if (fmin > dmin) {
178                fd[fdiagoff + --fmin - 1] = -1;
179            } else {
180                ++fmin;
181            }
182            if (fmax < dmax) {
183                fd[fdiagoff + ++fmax + 1] = -1;
184            } else {
185                --fmax;
186            }
187            for (d = fmax; d >= fmin; d -= 2) {
188                int x;
189                int y;
190                int tlo = fd[fdiagoff + d - 1];
191                int thi = fd[fdiagoff + d + 1];
192
193                if (tlo >= thi) {
194                    x = tlo + 1;
195                } else {
196                    x = thi;
197                }
198                y = x - d;
199                while (x < xlim && y < ylim && xv[x] == yv[y]) {
200                    ++x; ++y;
201                }
202                fd[fdiagoff + d] = x;
203                if (odd && bmin <= d && d <= bmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) {
204                    cost = 2 * c - 1;
205                    return d;
206                }
207            }
208
209            /* Similar extend the bottom-up search. */
210            if (bmin > dmin) {
211                bd[bdiagoff + --bmin - 1] = Integer.MAX_VALUE;
212            } else {
213                ++bmin;
214            }
215            if (bmax < dmax) {
216                bd[bdiagoff + ++bmax + 1] = Integer.MAX_VALUE;
217            } else {
218                --bmax;
219            }
220            for (d = bmax; d >= bmin; d -= 2) {
221                int x;
222                int y;
223                final int tlo = bd[bdiagoff + d - 1];
224                final int thi = bd[bdiagoff + d + 1];
225
226                if (tlo < thi) {
227                    x = tlo;
228                } else {
229                    x = thi - 1;
230                }
231                y = x - d;
232                while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1]) {
233                    --x; --y;
234                }
235                bd[bdiagoff + d] = x;
236                if (!odd && fmin <= d && d <= fmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) {
237                    cost = 2 * c;
238                    return d;
239                }
240            }
241        }
242    }
243
244    /**
245     * Compare in detail contiguous subsequences of the two files
246     * which are known, as a whole, to match each other.
247     * <p>
248     * The results are recorded in the vectors filevec[N].changed_flag, by
249     * storing a 1 in the element for each line that is an insertion or deletion.
250     * <p>
251     * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
252     * <p>
253     * Note that XLIM, YLIM are exclusive bounds.
254     * All line numbers are origin-0 and discarded lines are not counted.
255     * @param xoff xoff
256     * @param xlim xlim
257     * @param yoff yoff
258     * @param ylim ylim
259     */
260    private void compareseq(int xoff, int xlim, int yoff, int ylim) {
261        /* Slide down the bottom initial diagonal. */
262        while (xoff < xlim && yoff < ylim && xvec[xoff] == yvec[yoff]) {
263            ++xoff; ++yoff;
264        }
265        /* Slide up the top initial diagonal. */
266        while (xlim > xoff && ylim > yoff && xvec[xlim - 1] == yvec[ylim - 1]) {
267            --xlim; --ylim;
268        }
269
270        /* Handle simple cases. */
271        if (xoff == xlim) {
272            while (yoff < ylim) {
273                filevec[1].changedFlag[1+filevec[1].realindexes[yoff++]] = true;
274            }
275        } else if (yoff == ylim) {
276            while (xoff < xlim) {
277                filevec[0].changedFlag[1+filevec[0].realindexes[xoff++]] = true;
278            }
279        } else {
280            /* Find a point of correspondence in the middle of the files.  */
281
282            int d = diag(xoff, xlim, yoff, ylim);
283            int c = cost;
284            int b = bdiag[bdiagoff + d];
285
286            if (c == 1)
287                /* This should be impossible, because it implies that
288                   one of the two subsequences is empty,
289                   and that case was handled above without calling `diag'.
290                   Let's verify that this is true.  */
291                throw new IllegalArgumentException("Empty subsequence");
292            else {
293                /* Use that point to split this problem into two subproblems.  */
294                compareseq(xoff, b, yoff, b - d);
295                /* This used to use f instead of b,
296                   but that is incorrect!
297                   It is not necessarily the case that diagonal d
298                   has a snake from b to f.  */
299                compareseq(b, xlim, b - d, ylim);
300            }
301        }
302    }
303
304    /** Discard lines from one file that have no matches in the other file.
305     */
306    private void discardConfusingLines() {
307        filevec[0].discardConfusingLines(filevec[1]);
308        filevec[1].discardConfusingLines(filevec[0]);
309    }
310
311    /**
312     * Adjust inserts/deletes of blank lines to join changes as much as possible.
313     */
314    private void shiftBoundaries() {
315        filevec[0].shiftBoundaries(filevec[1]);
316        filevec[1].shiftBoundaries(filevec[0]);
317    }
318
319    /**
320     * Script builder.
321     * @since 10600 (functional interface)
322     */
323    @FunctionalInterface
324    public interface ScriptBuilder {
325        /**
326         * Scan the tables of which lines are inserted and deleted, producing an edit script.
327         * @param changed0 true for lines in first file which do not match 2nd
328         * @param len0 number of lines in first file
329         * @param changed1 true for lines in 2nd file which do not match 1st
330         * @param len1 number of lines in 2nd file
331         * @return a linked list of changes - or null
332         * @since 10600 (renamed)
333         */
334        Change buildScript(
335                boolean[] changed0, int len0,
336                boolean[] changed1, int len1
337        );
338    }
339
340    /**
341     * Scan the tables of which lines are inserted and deleted, producing an edit script in reverse order.
342     */
343    static class ReverseScript implements ScriptBuilder {
344        @Override
345        public Change buildScript(
346                final boolean[] changed0, int len0,
347                final boolean[] changed1, int len1) {
348            Change script = null;
349            int i0 = 0, i1 = 0;
350            while (i0 < len0 || i1 < len1) {
351                if (changed0[1+i0] || changed1[1+i1]) {
352                    int line0 = i0;
353                    int line1 = i1;
354
355                    /* Find # lines changed here in each file.  */
356                    while (changed0[1+i0]) {
357                        ++i0;
358                    }
359                    while (changed1[1+i1]) {
360                        ++i1;
361                    }
362
363                    /* Record this change.  */
364                    script = new Change(line0, line1, i0 - line0, i1 - line1, script);
365                }
366
367                /* We have reached lines in the two files that match each other.  */
368                i0++; i1++;
369            }
370
371            return script;
372        }
373    }
374
375    static class ForwardScript implements ScriptBuilder {
376        /** Scan the tables of which lines are inserted and deleted,
377            producing an edit script in forward order.  */
378        @Override
379        public Change buildScript(
380                final boolean[] changed0, int len0,
381                final boolean[] changed1, int len1) {
382            Change script = null;
383            int i0 = len0, i1 = len1;
384
385            while (i0 >= 0 || i1 >= 0) {
386                if (changed0[i0] || changed1[i1]) {
387                    int line0 = i0;
388                    int line1 = i1;
389
390                    /* Find # lines changed here in each file.  */
391                    while (changed0[i0]) {
392                        --i0;
393                    }
394                    while (changed1[i1]) {
395                        --i1;
396                    }
397
398                    /* Record this change.  */
399                    script = new Change(i0, i1, line0 - i0, line1 - i1, script);
400                }
401
402                /* We have reached lines in the two files that match each other.  */
403                i0--; i1--;
404            }
405
406            return script;
407        }
408    }
409
410    /** Standard Forward ScriptBuilder. */
411    public static final ScriptBuilder forwardScript = new ForwardScript();
412    /** Standard Reverse ScriptBuilder. */
413    public static final ScriptBuilder reverseScript = new ReverseScript();
414
415    /**
416     * Report the differences of two files. DEPTH is the current directory depth.
417     * @param reverse if {@code true} use {@link #reverseScript} else use {@link #forwardScript}
418     * @return the differences of two files
419     */
420    public final Change diff2(final boolean reverse) {
421        return diff(reverse ? reverseScript : forwardScript);
422    }
423
424    /**
425     * Get the results of comparison as an edit script.  The script
426     * is described by a list of changes.  The standard ScriptBuilder
427     * implementations provide for forward and reverse edit scripts.
428     * Alternate implementations could, for instance, list common elements
429     * instead of differences.
430     * @param bld an object to build the script from change flags
431     * @return the head of a list of changes
432     */
433    public Change diff(final ScriptBuilder bld) {
434
435        // Some lines are obviously insertions or deletions because they don't match anything.
436        // Detect them now, and avoid even thinking about them in the main comparison algorithm.
437        discardConfusingLines();
438
439        // Now do the main comparison algorithm, considering just the undiscarded lines.
440        xvec = filevec[0].undiscarded;
441        yvec = filevec[1].undiscarded;
442
443        int diags = filevec[0].nondiscardedLines + filevec[1].nondiscardedLines + 3;
444        fdiag = new int[diags];
445        fdiagoff = filevec[1].nondiscardedLines + 1;
446        bdiag = new int[diags];
447        bdiagoff = filevec[1].nondiscardedLines + 1;
448
449        compareseq(0, filevec[0].nondiscardedLines,
450                   0, filevec[1].nondiscardedLines);
451        fdiag = null;
452        bdiag = null;
453
454        // Modify the results slightly to make them prettier in cases where that can validly be done.
455        shiftBoundaries();
456
457        // Get the results of comparison in the form of a chain of `struct change's -- an edit script.
458        return bld.buildScript(
459                filevec[0].changedFlag,
460                filevec[0].bufferedLines,
461                filevec[1].changedFlag,
462                filevec[1].bufferedLines
463        );
464    }
465
466    /** The result of comparison is an "edit script": a chain of change objects.
467     Each change represents one place where some lines are deleted
468     and some are inserted.
469
470     LINE0 and LINE1 are the first affected lines in the two files (origin 0).
471     DELETED is the number of lines deleted here from file 0.
472     INSERTED is the number of lines inserted here in file 1.
473
474     If DELETED is 0 then LINE0 is the number of the line before
475     which the insertion was done; vice versa for INSERTED and LINE1.  */
476
477    public static class Change {
478        /** Previous or next edit command. */
479        public Change link;
480        /** # lines of file 1 changed here.  */
481        public final int inserted;
482        /** # lines of file 0 changed here.  */
483        public final int deleted;
484        /** Line number of 1st deleted line.  */
485        public final int line0;
486        /** Line number of 1st inserted line.  */
487        public final int line1;
488
489        /**
490         * Cons an additional entry onto the front of an edit script OLD.
491         * LINE0 and LINE1 are the first affected lines in the two files (origin 0).
492         * DELETED is the number of lines deleted here from file 0.
493         * INSERTED is the number of lines inserted here in file 1.
494         * <p>
495         * If DELETED is 0 then LINE0 is the number of the line before
496         * which the insertion was done; vice versa for INSERTED and LINE1.
497         * @param line0 first affected lines in the two files (origin 0)
498         * @param line1 first affected lines in the two files (origin 0)
499         * @param deleted the number of lines deleted here from file 0
500         * @param inserted the number of lines inserted here in file 1
501         * @param old edit script
502         */
503        public Change(int line0, int line1, int deleted, int inserted, Change old) {
504            this.line0 = line0;
505            this.line1 = line1;
506            this.inserted = inserted;
507            this.deleted = deleted;
508            this.link = old;
509        }
510
511        /**
512         * Returns the number of insertions and deletions of this change as well as
513         * (recursively) the changes linked via {@link #link}.
514         * @return recursive number of insertions and deletions
515         */
516        public int getTotalNumberOfChanges() {
517            return inserted + deleted + (link != null ? link.getTotalNumberOfChanges() : 0);
518        }
519
520        @Override
521        public String toString() {
522            String s = String.format("%d -%d +%d %d", line0, deleted, inserted, line1);
523            return (link != null) ? s + '\n' + link : s;
524        }
525    }
526
527    /**
528     * Data on one input file being compared.
529     */
530    class FileData {
531
532        /** Allocate changed array for the results of comparison.  */
533        void clear() {
534            // Allocate a flag for each line of each file, saying whether that line is an insertion or deletion.
535            // Allocate an extra element, always zero, at each end of each vector.
536            changedFlag = new boolean[bufferedLines + 2];
537        }
538
539        /**
540         * Return equiv_count[I] as the number of lines in this file that fall in equivalence class I.
541         * @return the array of equivalence class counts.
542         */
543        int[] equivCount() {
544            int[] equivCount = new int[equivMax];
545            for (int i = 0; i < bufferedLines; ++i) {
546                ++equivCount[equivs[i]];
547            }
548            return equivCount;
549        }
550
551        /**
552         * Discard lines that have no matches in another file.
553         * <p>
554         * A line which is discarded will not be considered by the actual comparison algorithm;
555         * it will be as if that line were not in the file.
556         * The file's `realindexes' table maps virtual line numbers
557         * (which don't count the discarded lines) into real line numbers;
558         * this is how the actual comparison algorithm produces results
559         * that are comprehensible when the discarded lines are counted.
560         * <p>
561         * When we discard a line, we also mark it as a deletion or insertion so that it will be printed in the output.
562         * @param f the other file
563         */
564        void discardConfusingLines(FileData f) {
565            clear();
566            // Set up table of which lines are going to be discarded.
567            final byte[] discarded = discardable(f.equivCount());
568
569            // Don't really discard the provisional lines except when they occur in a run of discardables,
570            // with nonprovisionals at the beginning and end.
571            filterDiscards(discarded);
572
573            // Actually discard the lines.
574            discard(discarded);
575        }
576
577        /**
578         * Mark to be discarded each line that matches no line of another file.
579         * If a line matches many lines, mark it as provisionally discardable.
580         * @param counts The count of each equivalence number for the other file.
581         * @return 0=nondiscardable, 1=discardable or 2=provisionally discardable for each line
582         * @see #equivCount()
583         */
584        private byte[] discardable(final int... counts) {
585            final int end = bufferedLines;
586            final byte[] discards = new byte[end];
587            final int[] equivs = this.equivs;
588            int many = 5;
589            int tem = end / 64;
590
591            /* Multiply MANY by approximate square root of number of lines.
592               That is the threshold for provisionally discardable lines.  */
593            while ((tem = tem >> 2) > 0) {
594                many *= 2;
595            }
596
597            for (int i = 0; i < end; i++) {
598                int nmatch;
599                if (equivs[i] == 0) {
600                    continue;
601                }
602                nmatch = counts[equivs[i]];
603                if (nmatch == 0) {
604                    discards[i] = 1;
605                } else if (nmatch > many) {
606                    discards[i] = 2;
607                }
608            }
609            return discards;
610        }
611
612        /**
613         * Don't really discard the provisional lines except when they occur
614         * in a run of discardables, with nonprovisionals at the beginning and end.
615         * @param discards discards
616         */
617        private void filterDiscards(final byte[] discards) {
618            final int end = bufferedLines;
619
620            for (int i = 0; i < end; i++) {
621                /* Cancel provisional discards not in middle of run of discards.  */
622                if (discards[i] == 2) {
623                    discards[i] = 0;
624                } else if (discards[i] != 0) {
625                    /* We have found a nonprovisional discard.  */
626                    int j;
627                    int length;
628                    int provisional = 0;
629
630                    /* Find end of this run of discardable lines.
631                       Count how many are provisionally discardable.  */
632                    for (j = i; j < end; j++) {
633                        if (discards[j] == 0) {
634                            break;
635                        }
636                        if (discards[j] == 2) {
637                            ++provisional;
638                        }
639                    }
640
641                    /* Cancel provisional discards at end, and shrink the run.  */
642                    while (j > i && discards[j - 1] == 2) {
643                        discards[--j] = 0; --provisional;
644                    }
645
646                    /* Now we have the length of a run of discardable lines
647                       whose first and last are not provisional.  */
648                    length = j - i;
649
650                    /* If 1/4 of the lines in the run are provisional,
651                       cancel discarding of all provisional lines in the run.  */
652                    if (provisional * 4 > length) {
653                        while (j > i)
654                            if (discards[--j] == 2) {
655                                discards[j] = 0;
656                            }
657                    } else {
658                        int consec;
659                        int minimum = 1;
660                        int tem = length / 4;
661
662                        /* MINIMUM is approximate square root of LENGTH/4.
663                           A subrun of two or more provisionals can stand
664                           when LENGTH is at least 16.
665                           A subrun of 4 or more can stand when LENGTH >= 64.  */
666                        while ((tem = tem >> 2) > 0) {
667                            minimum *= 2;
668                        }
669                        minimum++;
670
671                        /* Cancel any subrun of MINIMUM or more provisionals
672                           within the larger run.  */
673                        for (j = 0, consec = 0; j < length; j++) {
674                            if (discards[i + j] != 2) {
675                                consec = 0;
676                            } else if (minimum == ++consec) {
677                                /* Back up to start of subrun, to cancel it all.  */
678                                j -= consec;
679                            } else if (minimum < consec) {
680                                discards[i + j] = 0;
681                            }
682                        }
683
684                        /* Scan from beginning of run
685                           until we find 3 or more nonprovisionals in a row
686                           or until the first nonprovisional at least 8 lines in.
687                           Until that point, cancel any provisionals.  */
688                        for (j = 0, consec = 0; j < length; j++) {
689                            if (j >= 8 && discards[i + j] == 1) {
690                                break;
691                            }
692                            if (discards[i + j] == 2) {
693                                consec = 0; discards[i + j] = 0;
694                            } else if (discards[i + j] == 0) {
695                                consec = 0;
696                            } else {
697                                consec++;
698                            }
699                            if (consec == 3) {
700                                break;
701                            }
702                        }
703
704                        /* I advances to the last line of the run.  */
705                        i += length - 1;
706
707                        /* Same thing, from end.  */
708                        for (j = 0, consec = 0; j < length; j++) {
709                            if (j >= 8 && discards[i - j] == 1) {
710                                break;
711                            }
712                            if (discards[i - j] == 2) {
713                                consec = 0; discards[i - j] = 0;
714                            } else if (discards[i - j] == 0) {
715                                consec = 0;
716                            } else {
717                                consec++;
718                            }
719                            if (consec == 3) {
720                                break;
721                            }
722                        }
723                    }
724                }
725            }
726        }
727
728        /** Actually discard the lines.
729            @param discards flags lines to be discarded
730         */
731        private void discard(final byte[] discards) {
732            final int end = bufferedLines;
733            int j = 0;
734            for (int i = 0; i < end; ++i) {
735                if (discards[i] == 0) {
736                    undiscarded[j] = equivs[i];
737                    realindexes[j++] = i;
738                } else {
739                    changedFlag[1+i] = true;
740                }
741            }
742            nondiscardedLines = j;
743        }
744
745        FileData(int length) {
746            bufferedLines = length;
747            equivs = new int[length];
748            undiscarded = new int[bufferedLines];
749            realindexes = new int[bufferedLines];
750        }
751
752        FileData(Object[] data, Map<Object, Integer> h) {
753            this(data.length);
754            // FIXME: diff 2.7 removes common prefix and common suffix
755            for (int i = 0; i < data.length; ++i) {
756                Integer ir = h.get(data[i]);
757                if (ir == null) {
758                    equivs[i] = equivMax++;
759                    h.put(data[i], equivs[i]);
760                } else {
761                    equivs[i] = ir;
762                }
763            }
764        }
765
766        /**
767         * Adjust inserts/deletes of blank lines to join changes as much as possible.
768         * <p>
769         * We do something when a run of changed lines include a blank line at one end and have an excluded blank line at the other.
770         * We are free to choose which blank line is included.
771         * `compareseq' always chooses the one at the beginning, but usually it is cleaner to consider the following blank line
772         * to be the "change". The only exception is if the preceding blank line would join this change to other changes.
773         * @param f the file being compared against
774         */
775        void shiftBoundaries(FileData f) {
776            final boolean[] changed = changedFlag;
777            final boolean[] otherChanged = f.changedFlag;
778            int i = 0;
779            int j = 0;
780            int iEnd = bufferedLines;
781            int preceding = -1;
782            int otherPreceding = -1;
783
784            for (;;) {
785                int start, end, otherStart;
786
787                /* Scan forwards to find beginning of another run of changes.
788                   Also keep track of the corresponding point in the other file.  */
789
790                while (i < iEnd && !changed[1+i]) {
791                    while (otherChanged[1+j++]) {
792                        /* Non-corresponding lines in the other file
793                           will count as the preceding batch of changes.  */
794                        otherPreceding = j;
795                    }
796                    i++;
797                }
798
799                if (i == iEnd) {
800                    break;
801                }
802
803                start = i;
804                otherStart = j;
805
806                boolean loop = true;
807                while (loop) {
808                    /* Now find the end of this run of changes.  */
809
810                    while (i < iEnd && changed[1+i]) {
811                        i++;
812                    }
813                    end = i;
814
815                    /* If the first changed line matches the following unchanged one,
816                       and this run does not follow right after a previous run,
817                       and there are no lines deleted from the other file here,
818                       then classify the first changed line as unchanged
819                       and the following line as changed in its place.  */
820
821                    /* You might ask, how could this run follow right after another?
822                       Only because the previous run was shifted here.  */
823
824                    if (end != iEnd && equivs[start] == equivs[end] && !otherChanged[1+j]
825                         && !((preceding >= 0 && start == preceding) || (otherPreceding >= 0 && otherStart == otherPreceding))) {
826                        changed[1+end] = true;
827                        changed[1+start++] = false;
828                        ++i;
829                        /* Since one line-that-matches is now before this run
830                           instead of after, we must advance in the other file
831                           to keep in synch.  */
832                        ++j;
833                    } else {
834                        loop = false;
835                    }
836                }
837
838                preceding = i;
839                otherPreceding = j;
840            }
841        }
842
843        /** Number of elements (lines) in this file. */
844        private final int bufferedLines;
845
846        /** Vector, indexed by line number, containing an equivalence code for each line.
847         * It is this vector that is actually compared with that of another file to generate differences. */
848        private final int[] equivs;
849
850        /** Vector, like the previous one except that the elements for discarded lines have been squeezed out. */
851        private final int[] undiscarded;
852
853        /** Vector mapping virtual line numbers (not counting discarded lines) to real ones (counting those lines).
854         * Both are origin-0.  */
855        private final int[] realindexes;
856
857        /** Total number of nondiscarded lines. */
858        private int nondiscardedLines;
859
860        /** Array, indexed by real origin-1 line number, containing true for a line that is an insertion or a deletion.
861           The results of comparison are stored here. */
862        private boolean[] changedFlag;
863    }
864}