DiffEngine::_diag

protected DiffEngine::_diag($xoff, $xlim, $yoff, $ylim, $nchunks)

protected 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);
          $this::USE_ASSERTS && assert($k > 0);
          $ymids[$k] = $ymids[$k - 1];
          break;
        }
      }
      while (list($junk, $y) = each($matches)) {
        if ($y > $this->seq[$k - 1]) {
          $this::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);
          $this::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);
}