public function TimeEfficientImplementation::calculate in Zircon Profile 8

Same name and namespace in other branches

1. 8.0 vendor/sebastian/diff/src/LCS/TimeEfficientLongestCommonSubsequenceImplementation.php \SebastianBergmann\Diff\LCS\TimeEfficientImplementation::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/TimeEfficientLongestCommonSubsequenceImplementation.php, line 32

Class

TimeEfficientImplementation

Time-efficient implementation of longest common subsequence calculation.

Namespace

SebastianBergmann\Diff\LCS

Code

public function calculate(array $from, array $to) {
  $common = array();
  $fromLength = count($from);
  $toLength = count($to);
  $width = $fromLength + 1;
  $matrix = new \SplFixedArray($width * ($toLength + 1));
  for ($i = 0; $i <= $fromLength; ++$i) {
    $matrix[$i] = 0;
  }
  for ($j = 0; $j <= $toLength; ++$j) {
    $matrix[$j * $width] = 0;
  }
  for ($i = 1; $i <= $fromLength; ++$i) {
    for ($j = 1; $j <= $toLength; ++$j) {
      $o = $j * $width + $i;
      $matrix[$o] = max($matrix[$o - 1], $matrix[$o - $width], $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0);
    }
  }
  $i = $fromLength;
  $j = $toLength;
  while ($i > 0 && $j > 0) {
    if ($from[$i - 1] === $to[$j - 1]) {
      $common[] = $from[$i - 1];
      --$i;
      --$j;
    }
    else {
      $o = $j * $width + $i;
      if ($matrix[$o - $width] > $matrix[$o - 1]) {
        --$j;
      }
      else {
        --$i;
      }
    }
  }
  return array_reverse($common);
}