function _DiffEngine::_diag in Diff 6

Same name and namespace in other branches

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

1 call to _DiffEngine::_diag()

_DiffEngine::_compareseq in ./DiffEngine.php

File

./DiffEngine.php, line 258

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;
        }
        else {
          if (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,
  );
}