includes/diffengine/Engine/native.php
author Dan
Sun, 22 Mar 2009 00:55:06 -0400
changeset 885 a86a69394a95
parent 1 fe660c52c48f
child 1227 bdac73ed481e
permissions -rw-r--r--
Major revamp to sidebar editor. Some behavioral changes as well as being based on jQuery UI Sortables. Creation interface remains the same, but better strings merged in from stable.
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
}