www.aleph1.co.uk Git - yaffs-website/blob - vendor/sebastian/diff/src/LCS/MemoryEfficientLongestCommonSubsequenceImplementation.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  * Memory-efficient implementation of longest common subsequence calculation.
  15  */
  16 class MemoryEfficientImplementation 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         $cFrom = \count($from);
  29         $cTo   = \count($to);
  30
  31         if ($cFrom === 0) {
  32             return array();
  33         }
  34
  35         if ($cFrom === 1) {
  36             if (\in_array($from[0], $to, true)) {
  37                 return array($from[0]);
  38             }
  39
  40             return array();
  41         }
  42
  43         $i         = (int) ($cFrom / 2);
  44         $fromStart = \array_slice($from, 0, $i);
  45         $fromEnd   = \array_slice($from, $i);
  46         $llB       = $this->length($fromStart, $to);
  47         $llE       = $this->length(\array_reverse($fromEnd), \array_reverse($to));
  48         $jMax      = 0;
  49         $max       = 0;
  50
  51         for ($j = 0; $j <= $cTo; $j++) {
  52             $m = $llB[$j] + $llE[$cTo - $j];
  53
  54             if ($m >= $max) {
  55                 $max  = $m;
  56                 $jMax = $j;
  57             }
  58         }
  59
  60         $toStart = \array_slice($to, 0, $jMax);
  61         $toEnd   = \array_slice($to, $jMax);
  62
  63         return \array_merge(
  64             $this->calculate($fromStart, $toStart),
  65             $this->calculate($fromEnd, $toEnd)
  66         );
  67     }
  68
  69     /**
  70      * @param array $from
  71      * @param array $to
  72      *
  73      * @return array
  74      */
  75     private function length(array $from, array $to)
  76     {
  77         $current = \array_fill(0, \count($to) + 1, 0);
  78         $cFrom   = \count($from);
  79         $cTo     = \count($to);
  80
  81         for ($i = 0; $i < $cFrom; $i++) {
  82             $prev = $current;
  83
  84             for ($j = 0; $j < $cTo; $j++) {
  85                 if ($from[$i] === $to[$j]) {
  86                     $current[$j + 1] = $prev[$j] + 1;
  87                 } else {
  88                     $current[$j + 1] = \max($current[$j], $prev[$j + 1]);
  89                 }
  90             }
  91         }
  92
  93         return $current;
  94     }
  95 }