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

TimeEfficientLongestCommonSubsequenceImplementation.php (2273B)

      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  * Time-efficient implementation of longest common subsequence calculation.
     15  *
     16  * @package    Diff
     17  * @author     Sebastian Bergmann <sebastian@phpunit.de>
     18  * @author     Kore Nordmann <mail@kore-nordmann.de>
     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 TimeEfficientImplementation 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         $common     = array();
     35         $fromLength = count($from);
     36         $toLength   = count($to);
     37         $width      = $fromLength + 1;
     38         $matrix     = new \SplFixedArray($width * ($toLength + 1));
     39 
     40         for ($i = 0; $i <= $fromLength; ++$i) {
     41             $matrix[$i] = 0;
     42         }
     43 
     44         for ($j = 0; $j <= $toLength; ++$j) {
     45             $matrix[$j * $width] = 0;
     46         }
     47 
     48         for ($i = 1; $i <= $fromLength; ++$i) {
     49             for ($j = 1; $j <= $toLength; ++$j) {
     50                 $o = ($j * $width) + $i;
     51                 $matrix[$o] = max(
     52                     $matrix[$o - 1],
     53                     $matrix[$o - $width],
     54                     $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0
     55                 );
     56             }
     57         }
     58 
     59         $i = $fromLength;
     60         $j = $toLength;
     61 
     62         while ($i > 0 && $j > 0) {
     63             if ($from[$i-1] === $to[$j-1]) {
     64                 $common[] = $from[$i-1];
     65                 --$i;
     66                 --$j;
     67             } else {
     68                 $o = ($j * $width) + $i;
     69                 if ($matrix[$o - $width] > $matrix[$o - 1]) {
     70                     --$j;
     71                 } else {
     72                     --$i;
     73                 }
     74             }
     75         }
     76 
     77         return array_reverse($common);
     78     }
     79 }