public function MemoryEfficientImplementation::calculate in Zircon Profile 8

Same name and namespace in other branches

1. 8.0 vendor/sebastian/diff/src/LCS/MemoryEfficientLongestCommonSubsequenceImplementation.php \SebastianBergmann\Diff\LCS\MemoryEfficientImplementation::calculate()

Calculates the longest common subsequence of two arrays.

Parameters

array $from:

array $to:

Return value

array

Overrides LongestCommonSubsequence::calculate

File

vendor/sebastian/diff/src/LCS/MemoryEfficientLongestCommonSubsequenceImplementation.php, line 32

Class

MemoryEfficientImplementation

Memory-efficient implementation of longest common subsequence calculation.

Namespace

SebastianBergmann\Diff\LCS

Code

public function calculate(array $from, array $to) {
  $cFrom = count($from);
  $cTo = count($to);
  if ($cFrom == 0) {
    return array();
  }
  elseif ($cFrom == 1) {
    if (in_array($from[0], $to)) {
      return array(
        $from[0],
      );
    }
    else {
      return array();
    }
  }
  else {
    $i = intval($cFrom / 2);
    $fromStart = array_slice($from, 0, $i);
    $fromEnd = array_slice($from, $i);
    $llB = $this
      ->length($fromStart, $to);
    $llE = $this
      ->length(array_reverse($fromEnd), array_reverse($to));
    $jMax = 0;
    $max = 0;
    for ($j = 0; $j <= $cTo; $j++) {
      $m = $llB[$j] + $llE[$cTo - $j];
      if ($m >= $max) {
        $max = $m;
        $jMax = $j;
      }
    }
    $toStart = array_slice($to, 0, $jMax);
    $toEnd = array_slice($to, $jMax);
    return array_merge($this
      ->calculate($fromStart, $toStart), $this
      ->calculate($fromEnd, $toEnd));
  }
}