protected static function PHPUnit_Util_Diff::longestCommonSubsequence

Calculates the longest common subsequence of two arrays.

Parameters

array $from:

array $to:

Return value

array

1 call to PHPUnit_Util_Diff::longestCommonSubsequence()

File

drupal/core/vendor/phpunit/phpunit/PHPUnit/Util/Diff.php, line 246

Class

PHPUnit_Util_Diff
Diff implementation.

Code

protected static function longestCommonSubsequence(array $from, array $to) {
  $common = array();
  $matrix = array();
  $fromLength = count($from);
  $toLength = count($to);
  for ($i = 0; $i <= $fromLength; ++$i) {
    $matrix[$i][0] = 0;
  }
  for ($j = 0; $j <= $toLength; ++$j) {
    $matrix[0][$j] = 0;
  }
  for ($i = 1; $i <= $fromLength; ++$i) {
    for ($j = 1; $j <= $toLength; ++$j) {
      $matrix[$i][$j] = max($matrix[$i - 1][$j], $matrix[$i][$j - 1], $from[$i - 1] === $to[$j - 1] ? $matrix[$i - 1][$j - 1] + 1 : 0);
    }
  }
  $i = $fromLength;
  $j = $toLength;
  while ($i > 0 && $j > 0) {
    if ($from[$i - 1] === $to[$j - 1]) {
      array_unshift($common, $from[$i - 1]);
      --$i;
      --$j;
    }
    else {
      if ($matrix[$i][$j - 1] > $matrix[$i - 1][$j]) {
        --$j;
      }
      else {
        --$i;
      }
    }
  }
  return $common;
}