function _DiffEngine::_diag in Diff 6.2

Same name and namespace in other branches

1. 5.2 DiffEngine.php \_DiffEngine::_diag()
2. 5 DiffEngine.php \_DiffEngine::_diag()
3. 6 DiffEngine.php \_DiffEngine::_diag()
4. 7.3 DiffEngine.php \_DiffEngine::_diag()
5. 7.2 DiffEngine.php \_DiffEngine::_diag()

Divide the Largest Common Subsequence (LCS) of the sequences [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally sized segments.

Returns (LCS, PTS). LCS is the length of the LCS. PTS is an array of NCHUNKS+1 (X, Y) indexes giving the diving points between sub sequences. The first sub-sequence is contained in [X0, X1), [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note that (X0, Y0) == (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).

This function assumes that the first lines of the specified portions of the two files do not match, and likewise that the last lines do not match. The caller must trim matching lines from the beginning and end of the portions it is going to specify.

1 call to _DiffEngine::_diag()

_DiffEngine::_compareseq in ./DiffEngine.php

Find LCS of two sequences.

File

./DiffEngine.php, line 267

A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)

Class

_DiffEngine

Class used internally by Diff to actually compute the diffs.

Code

function _diag($xoff, $xlim, $yoff, $ylim, $nchunks) {
  $flip = FALSE;
  if ($xlim - $xoff > $ylim - $yoff) {

    // Things seems faster (I'm not sure I understand why)
    // when the shortest sequence in X.
    $flip = TRUE;
    list($xoff, $xlim, $yoff, $ylim) = array(
      $yoff,
      $ylim,
      $xoff,
      $xlim,
    );
  }
  if ($flip) {
    for ($i = $ylim - 1; $i >= $yoff; $i--) {
      $ymatches[$this->xv[$i]][] = $i;
    }
  }
  else {
    for ($i = $ylim - 1; $i >= $yoff; $i--) {
      $ymatches[$this->yv[$i]][] = $i;
    }
  }
  $this->lcs = 0;
  $this->seq[0] = $yoff - 1;
  $this->in_seq = array();
  $ymids[0] = array();
  $numer = $xlim - $xoff + $nchunks - 1;
  $x = $xoff;
  for ($chunk = 0; $chunk < $nchunks; $chunk++) {
    if ($chunk > 0) {
      for ($i = 0; $i <= $this->lcs; $i++) {
        $ymids[$i][$chunk - 1] = $this->seq[$i];
      }
    }
    $x1 = $xoff + (int) (($numer + ($xlim - $xoff) * $chunk) / $nchunks);
    for (; $x < $x1; $x++) {
      $line = $flip ? $this->yv[$x] : $this->xv[$x];
      if (empty($ymatches[$line])) {
        continue;
      }
      $matches = $ymatches[$line];
      reset($matches);
      while (list($junk, $y) = each($matches)) {
        if (empty($this->in_seq[$y])) {
          $k = $this
            ->_lcs_pos($y);
          USE_ASSERTS && assert($k > 0);
          $ymids[$k] = $ymids[$k - 1];
          break;
        }
      }
      while (list($junk, $y) = each($matches)) {
        if ($y > $this->seq[$k - 1]) {
          USE_ASSERTS && assert($y < $this->seq[$k]);

          // Optimization: this is a common case:
          // next match is just replacing previous match.
          $this->in_seq[$this->seq[$k]] = FALSE;
          $this->seq[$k] = $y;
          $this->in_seq[$y] = 1;
        }
        elseif (empty($this->in_seq[$y])) {
          $k = $this
            ->_lcs_pos($y);
          USE_ASSERTS && assert($k > 0);
          $ymids[$k] = $ymids[$k - 1];
        }
      }
    }
  }
  $seps[] = $flip ? array(
    $yoff,
    $xoff,
  ) : array(
    $xoff,
    $yoff,
  );
  $ymid = $ymids[$this->lcs];
  for ($n = 0; $n < $nchunks - 1; $n++) {
    $x1 = $xoff + (int) (($numer + ($xlim - $xoff) * $n) / $nchunks);
    $y1 = $ymid[$n] + 1;
    $seps[] = $flip ? array(
      $y1,
      $x1,
    ) : array(
      $x1,
      $y1,
    );
  }
  $seps[] = $flip ? array(
    $ylim,
    $xlim,
  ) : array(
    $xlim,
    $ylim,
  );
  return array(
    $this->lcs,
    $seps,
  );
}