You are here

class TimeEfficientImplementation 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

Time-efficient implementation of longest common subsequence calculation.

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

Hierarchy

Expanded class hierarchy of TimeEfficientImplementation

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
View source
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

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