class TimeEfficientImplementation in Zircon Profile 8

Time-efficient implementation of longest common subsequence calculation.

@package Diff @author Sebastian Bergmann <[e-mail]> @author Kore Nordmann <[e-mail]> @copyright Sebastian Bergmann <[e-mail]> @license http://www.opensource.org/licenses/BSD-3-Clause The BSD 3-Clause License @link http://www.github.com/sebastianbergmann/diff

Hierarchy

• class \SebastianBergmann\Diff\LCS\TimeEfficientImplementation implements LongestCommonSubsequence

2 files declare their use of TimeEfficientImplementation

Differ.php in vendor/sebastian/diff/src/Differ.php

DifferTest.php in vendor/sebastian/diff/tests/DifferTest.php

File

vendor/sebastian/diff/src/LCS/TimeEfficientLongestCommonSubsequenceImplementation.php, line 23

Namespace

SebastianBergmann\Diff\LCS

class TimeEfficientImplementation implements LongestCommonSubsequence {

  /**
   * Calculates the longest common subsequence of two arrays.
   *
   * @param  array $from
   * @param  array $to
   * @return array
   */
  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);
  }

}

Members

Name	Modifiers	Type	Description	Overrides
TimeEfficientImplementation::calculate	public	function	Calculates the longest common subsequence of two arrays. Overrides LongestCommonSubsequence::calculate