diff.java

JSPWiki,100%Java开发的一套完整WIKI程序

         @see equivCount()
         @param counts The count of each equivalence number for the other file.
         @return 0=nondiscardable, 1=discardable or 2=provisionally discardable
         for each line
         */

        private byte[] discardable(final int[] counts) {
            final int end = buffered_lines;
            final byte[] discards = new byte[end];
            final int[] equivs = this.equivs;
            int many = 5;
            int tem = end / 64;

            /* Multiply MANY by approximate square root of number of lines.
           That is the threshold for provisionally discardable lines.  */
            while ((tem = tem >> 2) > 0)
                many *= 2;

            for (int i = 0; i < end; i++) {
                int nmatch;
                if (equivs[i] == 0)
                    continue;
                nmatch = counts[equivs[i]];
                if (nmatch == 0)
                    discards[i] = 1;
                else if (nmatch > many)
                    discards[i] = 2;
            }
            return discards;
        }

        /** Don't really discard the provisional lines except when they occur
         in a run of discardables, with nonprovisionals at the beginning
         and end.  */

        private void filterDiscards(final byte[] discards) {
            final int end = buffered_lines;

            for (int i = 0; i < end; i++) {
                /* Cancel provisional discards not in middle of run of discards.  */
                if (discards[i] == 2)
                    discards[i] = 0;
                else if (discards[i] != 0) {
                    /* We have found a nonprovisional discard.  */
                    int j;
                    int length;
                    int provisional = 0;

                    /* Find end of this run of discardable lines.
                       Count how many are provisionally discardable.  */
                    for (j = i; j < end; j++) {
                        if (discards[j] == 0)
                            break;
                        if (discards[j] == 2)
                            ++provisional;
                    }

                    /* Cancel provisional discards at end, and shrink the run.  */
                    while (j > i && discards[j - 1] == 2) {
                        discards[--j] = 0;
                        --provisional;
                    }

                    /* Now we have the length of a run of discardable lines
                       whose first and last are not provisional.  */
                    length = j - i;

                    /* If 1/4 of the lines in the run are provisional,
                       cancel discarding of all provisional lines in the run.  */
                    if (provisional * 4 > length) {
                        while (j > i)
                            if (discards[--j] == 2)
                                discards[j] = 0;
                    } else {
                        int consec;
                        int minimum = 1;
                        int tem = length / 4;

                        /* MINIMUM is approximate square root of LENGTH/4.
                           A subrun of two or more provisionals can stand
                           when LENGTH is at least 16.
                           A subrun of 4 or more can stand when LENGTH >= 64.  */
                        while ((tem = tem >> 2) > 0)
                            minimum *= 2;
                        minimum++;

                        /* Cancel any subrun of MINIMUM or more provisionals
                           within the larger run.  */
                        for (j = 0, consec = 0; j < length; j++)
                            if (discards[i + j] != 2)
                                consec = 0;
                            else if (minimum == ++consec)
                            /* Back up to start of subrun, to cancel it all.  */
                                j -= consec;
                            else if (minimum < consec)
                                discards[i + j] = 0;

                        /* Scan from beginning of run
                           until we find 3 or more nonprovisionals in a row
                           or until the first nonprovisional at least 8 lines in.
                           Until that point, cancel any provisionals.  */
                        for (j = 0, consec = 0; j < length; j++) {
                            if (j >= 8 && discards[i + j] == 1)
                                break;
                            if (discards[i + j] == 2) {
                                consec = 0;
                                discards[i + j] = 0;
                            } else if (discards[i + j] == 0)
                                consec = 0;
                            else
                                consec++;
                            if (consec == 3)
                                break;
                        }

                        /* I advances to the last line of the run.  */
                        i += length - 1;

                        /* Same thing, from end.  */
                        for (j = 0, consec = 0; j < length; j++) {
                            if (j >= 8 && discards[i - j] == 1)
                                break;
                            if (discards[i - j] == 2) {
                                consec = 0;
                                discards[i - j] = 0;
                            } else if (discards[i - j] == 0)
                                consec = 0;
                            else
                                consec++;
                            if (consec == 3)
                                break;
                        }
                    }
                }
            }
        }

        /** Actually discard the lines.
         @param discards flags lines to be discarded
         */
        private void discard(final byte[] discards) {
            final int end = buffered_lines;
            int j = 0;
            for (int i = 0; i < end; ++i)
                if (no_discards || discards[i] == 0) {
                    undiscarded[j] = equivs[i];
                    realindexes[j++] = i;
                } else
                    changed_flag[1 + i] = true;
            nondiscarded_lines = j;
        }

        file_data(Object[] data, Hashtable h) {
            buffered_lines = data.length;

            equivs = new int[buffered_lines];
            undiscarded = new int[buffered_lines];
            realindexes = new int[buffered_lines];

            for (int i = 0; i < data.length; ++i) {
                Integer ir = (Integer) h.get(data[i]);
                if (ir == null)
                    h.put(data[i], new Integer(equivs[i] = equiv_max++));
                else
                    equivs[i] = ir.intValue();
            }
        }

        /** Adjust inserts/deletes of blank lines to join changes
         as much as possible.

         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.
         We are free to choose which blank line is included.
         `compareseq' always chooses the one at the beginning,
         but usually it is cleaner to consider the following blank line
         to be the "change".  The only exception is if the preceding blank line
         would join this change to other changes.
         @param f the file being compared against
         */

        void shift_boundaries(file_data f) {
            final boolean[] changed = changed_flag;
            final boolean[] other_changed = f.changed_flag;
            int i = 0;
            int j = 0;
            int i_end = buffered_lines;
            int preceding = -1;
            int other_preceding = -1;

            for (; ;) {
                int start, end, other_start;

                /* Scan forwards to find beginning of another run of changes.
                   Also keep track of the corresponding point in the other file.  */

                while (i < i_end && !changed[1 + i]) {
                    while (other_changed[1 + j++])
                            /* Non-corresponding lines in the other file
                               will count as the preceding batch of changes.  */
                        other_preceding = j;
                    i++;
                }

                if (i == i_end)
                    break;

                start = i;
                other_start = j;

                for (; ;) {
                    /* Now find the end of this run of changes.  */

                    while (i < i_end && changed[1 + i]) i++;
                    end = i;

                    /* If the first changed line matches the following unchanged one,
                   and this run does not follow right after a previous run,
                   and there are no lines deleted from the other file here,
                   then classify the first changed line as unchanged
                   and the following line as changed in its place.  */

                    /* You might ask, how could this run follow right after another?
                   Only because the previous run was shifted here.  */

                    if (end != i_end
                            && equivs[start] == equivs[end]
                            && !other_changed[1 + j]
                            && end != i_end
                            && !((preceding >= 0 && start == preceding)
                            || (other_preceding >= 0
                            && other_start == other_preceding))) {
                        changed[1 + end++] = true;
                        changed[1 + start++] = false;
                        ++i;
                        /* Since one line-that-matches is now before this run
                           instead of after, we must advance in the other file
                           to keep in synch.  */
                        ++j;
                    } else
                        break;
                }

                preceding = i;
                other_preceding = j;
            }
        }

        /** Number of elements (lines) in this file. */
        final int buffered_lines;

        /** Vector, indexed by line number, containing an equivalence code for
         each line.  It is this vector that is actually compared with that
         of another file to generate differences. */
        private final int[] equivs;

        /** Vector, like the previous one except that
         the elements for discarded lines have been squeezed out.  */
        final int[] undiscarded;

        /** Vector mapping virtual line numbers (not counting discarded lines)
         to real ones (counting those lines).  Both are origin-0.  */
        final int[] realindexes;

        /** Total number of nondiscarded lines. */
        int nondiscarded_lines;

        /** Array, indexed by real origin-1 line number,
         containing true for a line that is an insertion or a deletion.
         The results of comparison are stored here.  */
        boolean[] changed_flag;

    }
}