www.aleph1.co.uk Git - yaffs-website/blob - vendor/sebastian/diff/src/LCS/TimeEfficientLongestCommonSubsequenceImplementation.php

   1 <?php
   2 /*
   3  * This file is part of sebastian/diff.
   4  *
   5  * (c) Sebastian Bergmann <sebastian@phpunit.de>
   6  *
   7  * For the full copyright and license information, please view the LICENSE
   8  * file that was distributed with this source code.
   9  */
  10
  11 namespace SebastianBergmann\Diff\LCS;
  12
  13 /**
  14  * Time-efficient implementation of longest common subsequence calculation.
  15  */
  16 class TimeEfficientImplementation implements LongestCommonSubsequence
  17 {
  18     /**
  19      * Calculates the longest common subsequence of two arrays.
  20      *
  21      * @param array $from
  22      * @param array $to
  23      *
  24      * @return array
  25      */
  26     public function calculate(array $from, array $to)
  27     {
  28         $common     = array();
  29         $fromLength = \count($from);
  30         $toLength   = \count($to);
  31         $width      = $fromLength + 1;
  32         $matrix     = new \SplFixedArray($width * ($toLength + 1));
  33
  34         for ($i = 0; $i <= $fromLength; ++$i) {
  35             $matrix[$i] = 0;
  36         }
  37
  38         for ($j = 0; $j <= $toLength; ++$j) {
  39             $matrix[$j * $width] = 0;
  40         }
  41
  42         for ($i = 1; $i <= $fromLength; ++$i) {
  43             for ($j = 1; $j <= $toLength; ++$j) {
  44                 $o          = ($j * $width) + $i;
  45                 $matrix[$o] = \max(
  46                     $matrix[$o - 1],
  47                     $matrix[$o - $width],
  48                     $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0
  49                 );
  50             }
  51         }
  52
  53         $i = $fromLength;
  54         $j = $toLength;
  55
  56         while ($i > 0 && $j > 0) {
  57             if ($from[$i - 1] === $to[$j - 1]) {
  58                 $common[] = $from[$i - 1];
  59                 --$i;
  60                 --$j;
  61             } else {
  62                 $o = ($j * $width) + $i;
  63
  64                 if ($matrix[$o - $width] > $matrix[$o - 1]) {
  65                     --$j;
  66                 } else {
  67                     --$i;
  68                 }
  69             }
  70         }
  71
  72         return \array_reverse($common);
  73     }
  74 }