www.aleph1.co.uk Git - yaffs-website/blob - vendor/caxy/php-htmldiff/lib/Caxy/HtmlDiff/LcsService.php

   1 <?php
   2
   3 namespace Caxy\HtmlDiff;
   4
   5 use Caxy\HtmlDiff\Strategy\EqualMatchStrategy;
   6 use Caxy\HtmlDiff\Strategy\MatchStrategyInterface;
   7
   8 class LcsService
   9 {
  10     /**
  11      * @var MatchStrategyInterface
  12      */
  13     protected $matchStrategy;
  14
  15     /**
  16      * LcsService constructor.
  17      *
  18      * @param MatchStrategyInterface $matchStrategy
  19      */
  20     public function __construct(MatchStrategyInterface $matchStrategy = null)
  21     {
  22         if (null === $matchStrategy) {
  23             $matchStrategy = new EqualMatchStrategy();
  24         }
  25
  26         $this->matchStrategy = $matchStrategy;
  27     }
  28
  29     /**
  30      * @param array $a
  31      * @param array $b
  32      *
  33      * @return array
  34      */
  35     public function longestCommonSubsequence(array $a, array $b)
  36     {
  37         $c = array();
  38
  39         $m = count($a);
  40         $n = count($b);
  41
  42         for ($i = 0; $i <= $m; $i++) {
  43             $c[$i][0] = 0;
  44         }
  45
  46         for ($j = 0; $j <= $n; $j++) {
  47             $c[0][$j] = 0;
  48         }
  49
  50         for ($i = 1; $i <= $m; $i++) {
  51             for ($j = 1; $j <= $n; $j++) {
  52                 if ($this->matchStrategy->isMatch($a[$i - 1], $b[$j - 1])) {
  53                     $c[$i][$j] = 1 + (isset($c[$i - 1][$j - 1]) ? $c[$i - 1][$j - 1] : 0);
  54                 } else {
  55                     $c[$i][$j] = max(
  56                         isset($c[$i][$j - 1]) ? $c[$i][$j - 1] : 0,
  57                         isset($c[$i - 1][$j]) ? $c[$i - 1][$j] : 0
  58                     );
  59                 }
  60             }
  61         }
  62
  63         $lcs = array_pad(array(), $m + 1, 0);
  64         $this->compileMatches($c, $a, $b, $m, $n, $lcs);
  65
  66         return $lcs;
  67     }
  68
  69     /**
  70      * @param $c
  71      * @param $a
  72      * @param $b
  73      * @param $i
  74      * @param $j
  75      * @param $matches
  76      */
  77     protected function compileMatches($c, $a, $b, $i, $j, &$matches)
  78     {
  79         if ($i > 0 && $j > 0 && $this->matchStrategy->isMatch($a[$i - 1], $b[$j - 1])) {
  80             $this->compileMatches($c, $a, $b, $i - 1, $j - 1, $matches);
  81             $matches[$i] = $j;
  82         } elseif ($j > 0 && ($i === 0 || $c[$i][$j - 1] >= $c[$i - 1][$j])) {
  83             $this->compileMatches($c, $a, $b, $i, $j - 1, $matches);
  84         } elseif ($i > 0 && ($j === 0 || $c[$i][$j - 1] < $c[$i - 1][$j])) {
  85             $this->compileMatches($c, $a, $b, $i - 1, $j, $matches);
  86         }
  87     }
  88 }