TimeEfficientLongestCommonSubsequenceImplementation.php in Zircon Profile 8.0

Namespace

SebastianBergmann\Diff\LCS

File

vendor/sebastian/diff/src/LCS/TimeEfficientLongestCommonSubsequenceImplementation.php

<?php

/*
 * This file is part of the Diff package.
 *
 * (c) Sebastian Bergmann <[e-mail]>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */
namespace SebastianBergmann\Diff\LCS;


/**
 * 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
 */
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);
  }

}

Classes

Name	Description
TimeEfficientImplementation	Time-efficient implementation of longest common subsequence calculation.