yaffs.net Git - yaffs-website/blob - vendor/sebastian/diff/src/LCS/MemoryEfficientLongestCommonSubsequenceImplementation.php

   1 <?php
   2 /*
   3  * This file is part of the Diff package.
   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         } elseif ($cFrom == 1) {
  34             if (in_array($from[0], $to)) {
  35                 return array($from[0]);
  36             } else {
  37                 return array();
  38             }
  39         } else {
  40             $i         = intval($cFrom / 2);
  41             $fromStart = array_slice($from, 0, $i);
  42             $fromEnd   = array_slice($from, $i);
  43             $llB       = $this->length($fromStart, $to);
  44             $llE       = $this->length(array_reverse($fromEnd), array_reverse($to));
  45             $jMax      = 0;
  46             $max       = 0;
  47
  48             for ($j = 0; $j <= $cTo; $j++) {
  49                 $m = $llB[$j] + $llE[$cTo - $j];
  50
  51                 if ($m >= $max) {
  52                     $max  = $m;
  53                     $jMax = $j;
  54                 }
  55             }
  56
  57             $toStart = array_slice($to, 0, $jMax);
  58             $toEnd   = array_slice($to, $jMax);
  59
  60             return array_merge(
  61                 $this->calculate($fromStart, $toStart),
  62                 $this->calculate($fromEnd, $toEnd)
  63             );
  64         }
  65     }
  66
  67     /**
  68      * @param array $from
  69      * @param array $to
  70      *
  71      * @return array
  72      */
  73     private function length(array $from, array $to)
  74     {
  75         $current = array_fill(0, count($to) + 1, 0);
  76         $cFrom   = count($from);
  77         $cTo     = count($to);
  78
  79         for ($i = 0; $i < $cFrom; $i++) {
  80             $prev = $current;
  81
  82             for ($j = 0; $j < $cTo; $j++) {
  83                 if ($from[$i] == $to[$j]) {
  84                     $current[$j + 1] = $prev[$j] + 1;
  85                 } else {
  86                     $current[$j + 1] = max($current[$j], $prev[$j + 1]);
  87                 }
  88             }
  89         }
  90
  91         return $current;
  92     }
  93 }