gluon-web-remote

Web remote Administration for big size of gluon routers
git clone git://archive.git.mtrnord.blog/MTRNord/gluon-web-remote.git
Log | Files | Refs | README

MemoryEfficientLongestCommonSubsequenceImplementation.php (2804B)

      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  * @package    Diff
     17  * @author     Sebastian Bergmann <sebastian@phpunit.de>
     18  * @author     Denes Lados <lados.denes@gmail.com>
     19  * @copyright  Sebastian Bergmann <sebastian@phpunit.de>
     20  * @license    http://www.opensource.org/licenses/BSD-3-Clause  The BSD 3-Clause License
     21  * @link       http://www.github.com/sebastianbergmann/diff
     22  */
     23 class MemoryEfficientImplementation implements LongestCommonSubsequence
     24 {
     25     /**
     26      * Calculates the longest common subsequence of two arrays.
     27      *
     28      * @param  array $from
     29      * @param  array $to
     30      * @return array
     31      */
     32     public function calculate(array $from, array $to)
     33     {
     34         $cFrom = count($from);
     35         $cTo   = count($to);
     36 
     37         if ($cFrom == 0) {
     38             return array();
     39         } elseif ($cFrom == 1) {
     40             if (in_array($from[0], $to)) {
     41                 return array($from[0]);
     42             } else {
     43                 return array();
     44             }
     45         } else {
     46             $i         = intval($cFrom / 2);
     47             $fromStart = array_slice($from, 0, $i);
     48             $fromEnd   = array_slice($from, $i);
     49             $llB       = $this->length($fromStart, $to);
     50             $llE       = $this->length(array_reverse($fromEnd), array_reverse($to));
     51             $jMax      = 0;
     52             $max       = 0;
     53 
     54             for ($j = 0; $j <= $cTo; $j++) {
     55                 $m = $llB[$j] + $llE[$cTo - $j];
     56 
     57                 if ($m >= $max) {
     58                     $max  = $m;
     59                     $jMax = $j;
     60                 }
     61             }
     62 
     63             $toStart = array_slice($to, 0, $jMax);
     64             $toEnd   = array_slice($to, $jMax);
     65 
     66             return array_merge(
     67                 $this->calculate($fromStart, $toStart),
     68                 $this->calculate($fromEnd, $toEnd)
     69             );
     70         }
     71     }
     72 
     73     /**
     74      * @param array $from
     75      * @param array $to
     76      * @return array
     77      */
     78     private function length(array $from, array $to)
     79     {
     80         $current = array_fill(0, count($to) + 1, 0);
     81         $cFrom   = count($from);
     82         $cTo     = count($to);
     83 
     84         for ($i = 0; $i < $cFrom; $i++) {
     85             $prev = $current;
     86 
     87             for ($j = 0; $j < $cTo; $j++) {
     88                 if ($from[$i] == $to[$j]) {
     89                     $current[$j + 1] = $prev[$j] + 1;
     90                 } else {
     91                     $current[$j + 1] = max($current[$j], $prev[$j + 1]);
     92                 }
     93             }
     94         }
     95 
     96         return $current;
     97     }
     98 }