git.stricted.de - GitHub/WoltLab/WCF.git/blob

   1 <?php declare(strict_types=1);
   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 namespace SebastianBergmann\Diff;
  11
  12 use function array_fill;
  13 use function array_merge;
  14 use function array_reverse;
  15 use function array_slice;
  16 use function count;
  17 use function in_array;
  18 use function max;
  19
  20 final class MemoryEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator
  21 {
  22     /**
  23      * @inheritDoc
  24      */
  25     public function calculate(array $from, array $to): array
  26     {
  27         $cFrom = count($from);
  28         $cTo   = count($to);
  29
  30         if ($cFrom === 0) {
  31             return [];
  32         }
  33
  34         if ($cFrom === 1) {
  35             if (in_array($from[0], $to, true)) {
  36                 return [$from[0]];
  37             }
  38
  39             return [];
  40         }
  41
  42         $i         = (int) ($cFrom / 2);
  43         $fromStart = array_slice($from, 0, $i);
  44         $fromEnd   = array_slice($from, $i);
  45         $llB       = $this->length($fromStart, $to);
  46         $llE       = $this->length(array_reverse($fromEnd), array_reverse($to));
  47         $jMax      = 0;
  48         $max       = 0;
  49
  50         for ($j = 0; $j <= $cTo; $j++) {
  51             $m = $llB[$j] + $llE[$cTo - $j];
  52
  53             if ($m >= $max) {
  54                 $max  = $m;
  55                 $jMax = $j;
  56             }
  57         }
  58
  59         $toStart = array_slice($to, 0, $jMax);
  60         $toEnd   = array_slice($to, $jMax);
  61
  62         return array_merge(
  63             $this->calculate($fromStart, $toStart),
  64             $this->calculate($fromEnd, $toEnd)
  65         );
  66     }
  67
  68     private function length(array $from, array $to): array
  69     {
  70         $current = array_fill(0, count($to) + 1, 0);
  71         $cFrom   = count($from);
  72         $cTo     = count($to);
  73
  74         for ($i = 0; $i < $cFrom; $i++) {
  75             $prev = $current;
  76
  77             for ($j = 0; $j < $cTo; $j++) {
  78                 if ($from[$i] === $to[$j]) {
  79                     $current[$j + 1] = $prev[$j] + 1;
  80                 } else {
  81                     // don't use max() to avoid function call overhead
  82                     if ($current[$j] > $prev[$j + 1]) {
  83                         $current[$j + 1] = $current[$j];
  84                     } else {
  85                         $current[$j + 1] = $prev[$j + 1];
  86                     }
  87                 }
  88             }
  89         }
  90
  91         return $current;
  92     }
  93 }