includes/diffengine/Engine/native.php
author Dan
Tue, 08 Apr 2008 20:08:35 -0400
changeset 522 fd46b1bf708e
parent 1 fe660c52c48f
child 1227 bdac73ed481e
permissions -rw-r--r--
Dramatically improved the page-rename UX and added a miniPrompt API that allows small pop-down prompts as opposed to prompt() or confirm().
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     1
<?php
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     2
/**
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     3
 * Class used internally by Diff to actually compute the diffs.  This class is
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     4
 * implemented using native PHP code.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     5
 *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     6
 * The algorithm used here is mostly lifted from the perl module
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     7
 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     8
 * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
     9
 *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    10
 * More ideas are taken from:
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    11
 * http://www.ics.uci.edu/~eppstein/161/960229.html
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    12
 *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    13
 * Some ideas (and a bit of code) are taken from analyze.c, of GNU
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    14
 * diffutils-2.7, which can be found at:
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    15
 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    16
 *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    17
 * Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    18
 * Geoffrey T. Dairiki <dairiki@dairiki.org>. The original PHP version of this
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    19
 * code was written by him, and is used/adapted with his permission.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    20
 *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    21
 * $Horde: framework/Text_Diff/Diff/Engine/native.php,v 1.3 2006/01/06 15:56:52 jan Exp $
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    22
 *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    23
 * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    24
 * @package Text_Diff
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    25
 *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    26
 * @access private
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    27
 */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    28
class Text_Diff_Engine_native {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    29
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    30
    function diff($from_lines, $to_lines)
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    31
    {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    32
        array_walk($from_lines, array('Text_Diff', 'trimNewlines'));
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    33
        array_walk($to_lines, array('Text_Diff', 'trimNewlines'));
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    34
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    35
        $n_from = count($from_lines);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    36
        $n_to = count($to_lines);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    37
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    38
        $this->xchanged = $this->ychanged = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    39
        $this->xv = $this->yv = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    40
        $this->xind = $this->yind = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    41
        unset($this->seq);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    42
        unset($this->in_seq);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    43
        unset($this->lcs);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    44
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    45
        // Skip leading common lines.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    46
        for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    47
            if ($from_lines[$skip] !== $to_lines[$skip]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    48
                break;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    49
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    50
            $this->xchanged[$skip] = $this->ychanged[$skip] = false;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    51
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    52
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    53
        // Skip trailing common lines.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    54
        $xi = $n_from; $yi = $n_to;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    55
        for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    56
            if ($from_lines[$xi] !== $to_lines[$yi]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    57
                break;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    58
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    59
            $this->xchanged[$xi] = $this->ychanged[$yi] = false;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    60
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    61
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    62
        // Ignore lines which do not exist in both files.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    63
        for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    64
            $xhash[$from_lines[$xi]] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    65
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    66
        for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    67
            $line = $to_lines[$yi];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    68
            if (($this->ychanged[$yi] = empty($xhash[$line]))) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    69
                continue;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    70
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    71
            $yhash[$line] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    72
            $this->yv[] = $line;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    73
            $this->yind[] = $yi;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    74
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    75
        for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    76
            $line = $from_lines[$xi];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    77
            if (($this->xchanged[$xi] = empty($yhash[$line]))) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    78
                continue;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    79
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    80
            $this->xv[] = $line;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    81
            $this->xind[] = $xi;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    82
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    83
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    84
        // Find the LCS.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    85
        $this->_compareseq(0, count($this->xv), 0, count($this->yv));
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    86
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    87
        // Merge edits when possible.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    88
        $this->_shiftBoundaries($from_lines, $this->xchanged, $this->ychanged);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    89
        $this->_shiftBoundaries($to_lines, $this->ychanged, $this->xchanged);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    90
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    91
        // Compute the edit operations.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    92
        $edits = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    93
        $xi = $yi = 0;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    94
        while ($xi < $n_from || $yi < $n_to) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    95
            assert($yi < $n_to || $this->xchanged[$xi]);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    96
            assert($xi < $n_from || $this->ychanged[$yi]);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    97
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    98
            // Skip matching "snake".
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
    99
            $copy = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   100
            while ($xi < $n_from && $yi < $n_to
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   101
                   && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   102
                $copy[] = $from_lines[$xi++];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   103
                ++$yi;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   104
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   105
            if ($copy) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   106
                $edits[] = &new Text_Diff_Op_copy($copy);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   107
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   108
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   109
            // Find deletes & adds.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   110
            $delete = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   111
            while ($xi < $n_from && $this->xchanged[$xi]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   112
                $delete[] = $from_lines[$xi++];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   113
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   114
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   115
            $add = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   116
            while ($yi < $n_to && $this->ychanged[$yi]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   117
                $add[] = $to_lines[$yi++];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   118
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   119
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   120
            if ($delete && $add) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   121
                $edits[] = &new Text_Diff_Op_change($delete, $add);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   122
            } elseif ($delete) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   123
                $edits[] = &new Text_Diff_Op_delete($delete);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   124
            } elseif ($add) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   125
                $edits[] = &new Text_Diff_Op_add($add);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   126
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   127
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   128
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   129
        return $edits;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   130
    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   131
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   132
    /**
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   133
     * Divides the Largest Common Subsequence (LCS) of the sequences (XOFF,
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   134
     * XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   135
     * segments.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   136
     *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   137
     * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an array of
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   138
     * NCHUNKS+1 (X, Y) indexes giving the diving points between sub
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   139
     * sequences.  The first sub-sequence is contained in (X0, X1), (Y0, Y1),
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   140
     * the second in (X1, X2), (Y1, Y2) and so on.  Note that (X0, Y0) ==
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   141
     * (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   142
     *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   143
     * This function assumes that the first lines of the specified portions of
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   144
     * the two files do not match, and likewise that the last lines do not
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   145
     * match.  The caller must trim matching lines from the beginning and end
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   146
     * of the portions it is going to specify.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   147
     */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   148
    function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks)
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   149
    {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   150
        $flip = false;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   151
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   152
        if ($xlim - $xoff > $ylim - $yoff) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   153
            /* Things seems faster (I'm not sure I understand why) when the
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   154
             * shortest sequence is in X. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   155
            $flip = true;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   156
            list ($xoff, $xlim, $yoff, $ylim)
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   157
                = array($yoff, $ylim, $xoff, $xlim);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   158
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   159
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   160
        if ($flip) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   161
            for ($i = $ylim - 1; $i >= $yoff; $i--) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   162
                $ymatches[$this->xv[$i]][] = $i;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   163
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   164
        } else {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   165
            for ($i = $ylim - 1; $i >= $yoff; $i--) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   166
                $ymatches[$this->yv[$i]][] = $i;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   167
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   168
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   169
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   170
        $this->lcs = 0;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   171
        $this->seq[0]= $yoff - 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   172
        $this->in_seq = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   173
        $ymids[0] = array();
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   174
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   175
        $numer = $xlim - $xoff + $nchunks - 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   176
        $x = $xoff;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   177
        for ($chunk = 0; $chunk < $nchunks; $chunk++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   178
            if ($chunk > 0) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   179
                for ($i = 0; $i <= $this->lcs; $i++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   180
                    $ymids[$i][$chunk - 1] = $this->seq[$i];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   181
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   182
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   183
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   184
            $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   185
            for (; $x < $x1; $x++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   186
                $line = $flip ? $this->yv[$x] : $this->xv[$x];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   187
                if (empty($ymatches[$line])) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   188
                    continue;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   189
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   190
                $matches = $ymatches[$line];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   191
                foreach ($matches as $y) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   192
                    if (empty($this->in_seq[$y])) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   193
                        $k = $this->_lcsPos($y);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   194
                        assert($k > 0);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   195
                        $ymids[$k] = $ymids[$k - 1];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   196
                        break;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   197
                    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   198
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   199
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   200
                while (list($junk, $y) = each($matches)) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   201
                    if ($y > $this->seq[$k - 1]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   202
                        assert($y < $this->seq[$k]);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   203
                        /* Optimization: this is a common case: next match is
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   204
                         * just replacing previous match. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   205
                        $this->in_seq[$this->seq[$k]] = false;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   206
                        $this->seq[$k] = $y;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   207
                        $this->in_seq[$y] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   208
                    } elseif (empty($this->in_seq[$y])) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   209
                        $k = $this->_lcsPos($y);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   210
                        assert($k > 0);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   211
                        $ymids[$k] = $ymids[$k - 1];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   212
                    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   213
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   214
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   215
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   216
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   217
        $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   218
        $ymid = $ymids[$this->lcs];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   219
        for ($n = 0; $n < $nchunks - 1; $n++) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   220
            $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   221
            $y1 = $ymid[$n] + 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   222
            $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   223
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   224
        $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   225
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   226
        return array($this->lcs, $seps);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   227
    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   228
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   229
    function _lcsPos($ypos)
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   230
    {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   231
        $end = $this->lcs;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   232
        if ($end == 0 || $ypos > $this->seq[$end]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   233
            $this->seq[++$this->lcs] = $ypos;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   234
            $this->in_seq[$ypos] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   235
            return $this->lcs;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   236
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   237
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   238
        $beg = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   239
        while ($beg < $end) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   240
            $mid = (int)(($beg + $end) / 2);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   241
            if ($ypos > $this->seq[$mid]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   242
                $beg = $mid + 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   243
            } else {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   244
                $end = $mid;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   245
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   246
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   247
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   248
        assert($ypos != $this->seq[$end]);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   249
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   250
        $this->in_seq[$this->seq[$end]] = false;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   251
        $this->seq[$end] = $ypos;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   252
        $this->in_seq[$ypos] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   253
        return $end;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   254
    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   255
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   256
    /**
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   257
     * Finds LCS of two sequences.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   258
     *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   259
     * The results are recorded in the vectors $this->{x,y}changed[], by
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   260
     * storing a 1 in the element for each line that is an insertion or
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   261
     * deletion (ie. is not in the LCS).
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   262
     *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   263
     * The subsequence of file 0 is (XOFF, XLIM) and likewise for file 1.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   264
     *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   265
     * Note that XLIM, YLIM are exclusive bounds.  All line numbers are
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   266
     * origin-0 and discarded lines are not counted.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   267
     */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   268
    function _compareseq ($xoff, $xlim, $yoff, $ylim)
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   269
    {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   270
        /* Slide down the bottom initial diagonal. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   271
        while ($xoff < $xlim && $yoff < $ylim
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   272
               && $this->xv[$xoff] == $this->yv[$yoff]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   273
            ++$xoff;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   274
            ++$yoff;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   275
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   276
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   277
        /* Slide up the top initial diagonal. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   278
        while ($xlim > $xoff && $ylim > $yoff
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   279
               && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   280
            --$xlim;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   281
            --$ylim;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   282
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   283
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   284
        if ($xoff == $xlim || $yoff == $ylim) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   285
            $lcs = 0;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   286
        } else {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   287
            /* This is ad hoc but seems to work well.  $nchunks =
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   288
             * sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); $nchunks =
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   289
             * max(2,min(8,(int)$nchunks)); */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   290
            $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   291
            list($lcs, $seps)
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   292
                = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   293
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   294
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   295
        if ($lcs == 0) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   296
            /* X and Y sequences have no common subsequence: mark all
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   297
             * changed. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   298
            while ($yoff < $ylim) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   299
                $this->ychanged[$this->yind[$yoff++]] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   300
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   301
            while ($xoff < $xlim) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   302
                $this->xchanged[$this->xind[$xoff++]] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   303
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   304
        } else {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   305
            /* Use the partitions to split this problem into subproblems. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   306
            reset($seps);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   307
            $pt1 = $seps[0];
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   308
            while ($pt2 = next($seps)) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   309
                $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   310
                $pt1 = $pt2;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   311
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   312
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   313
    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   314
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   315
    /**
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   316
     * Adjusts inserts/deletes of identical lines to join changes as much as
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   317
     * possible.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   318
     *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   319
     * We do something when a run of changed lines include a line at one end
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   320
     * and has an excluded, identical line at the other.  We are free to
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   321
     * choose which identical line is included.  `compareseq' usually chooses
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   322
     * the one at the beginning, but usually it is cleaner to consider the
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   323
     * following identical line to be the "change".
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   324
     *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   325
     * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   326
     */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   327
    function _shiftBoundaries($lines, &$changed, $other_changed)
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   328
    {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   329
        $i = 0;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   330
        $j = 0;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   331
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   332
        assert('count($lines) == count($changed)');
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   333
        $len = count($lines);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   334
        $other_len = count($other_changed);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   335
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   336
        while (1) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   337
            /* Scan forward to find the beginning of another run of
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   338
             * changes. Also keep track of the corresponding point in the
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   339
             * other file.
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   340
             *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   341
             * Throughout this code, $i and $j are adjusted together so that
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   342
             * the first $i elements of $changed and the first $j elements of
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   343
             * $other_changed both contain the same number of zeros (unchanged
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   344
             * lines).
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   345
             *
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   346
             * Furthermore, $j is always kept so that $j == $other_len or
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   347
             * $other_changed[$j] == false. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   348
            while ($j < $other_len && $other_changed[$j]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   349
                $j++;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   350
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   351
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   352
            while ($i < $len && ! $changed[$i]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   353
                assert('$j < $other_len && ! $other_changed[$j]');
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   354
                $i++; $j++;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   355
                while ($j < $other_len && $other_changed[$j]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   356
                    $j++;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   357
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   358
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   359
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   360
            if ($i == $len) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   361
                break;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   362
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   363
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   364
            $start = $i;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   365
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   366
            /* Find the end of this run of changes. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   367
            while (++$i < $len && $changed[$i]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   368
                continue;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   369
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   370
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   371
            do {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   372
                /* Record the length of this run of changes, so that we can
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   373
                 * later determine whether the run has grown. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   374
                $runlength = $i - $start;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   375
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   376
                /* Move the changed region back, so long as the previous
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   377
                 * unchanged line matches the last changed one.  This merges
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   378
                 * with previous changed regions. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   379
                while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   380
                    $changed[--$start] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   381
                    $changed[--$i] = false;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   382
                    while ($start > 0 && $changed[$start - 1]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   383
                        $start--;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   384
                    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   385
                    assert('$j > 0');
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   386
                    while ($other_changed[--$j]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   387
                        continue;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   388
                    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   389
                    assert('$j >= 0 && !$other_changed[$j]');
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   390
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   391
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   392
                /* Set CORRESPONDING to the end of the changed run, at the
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   393
                 * last point where it corresponds to a changed run in the
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   394
                 * other file. CORRESPONDING == LEN means no such point has
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   395
                 * been found. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   396
                $corresponding = $j < $other_len ? $i : $len;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   397
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   398
                /* Move the changed region forward, so long as the first
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   399
                 * changed line matches the following unchanged one.  This
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   400
                 * merges with following changed regions.  Do this second, so
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   401
                 * that if there are no merges, the changed region is moved
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   402
                 * forward as far as possible. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   403
                while ($i < $len && $lines[$start] == $lines[$i]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   404
                    $changed[$start++] = false;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   405
                    $changed[$i++] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   406
                    while ($i < $len && $changed[$i]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   407
                        $i++;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   408
                    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   409
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   410
                    assert('$j < $other_len && ! $other_changed[$j]');
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   411
                    $j++;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   412
                    if ($j < $other_len && $other_changed[$j]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   413
                        $corresponding = $i;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   414
                        while ($j < $other_len && $other_changed[$j]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   415
                            $j++;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   416
                        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   417
                    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   418
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   419
            } while ($runlength != $i - $start);
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   420
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   421
            /* If possible, move the fully-merged run of changes back to a
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   422
             * corresponding run in the other file. */
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   423
            while ($corresponding < $i) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   424
                $changed[--$start] = 1;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   425
                $changed[--$i] = 0;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   426
                assert('$j > 0');
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   427
                while ($other_changed[--$j]) {
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   428
                    continue;
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   429
                }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   430
                assert('$j >= 0 && !$other_changed[$j]');
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   431
            }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   432
        }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   433
    }
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   434
fe660c52c48f Adding /includes
dan@scribus.fuhry.local.fuhry.local
parents:
diff changeset
   435
}