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

   1 <?php
   2
   3 namespace Caxy\HtmlDiff;
   4
   5 class Preprocessor
   6 {
   7     public static function diffCommonPrefix($old, $new)
   8     {
   9         // Quick check for common null cases.
  10         if (strlen($old) == 0 || strlen($new) == 0 || substr($old, 0, 1) != substr($new, 0, 1)) {
  11             return 0;
  12         }
  13
  14         // Binary Search
  15         $pointerMin = 0;
  16         $pointerMax = min(strlen($old), strlen($new));
  17         $pointerMid = $pointerMax;
  18         $pointerStart = 0;
  19         while ($pointerMin < $pointerMid) {
  20             $cmp = substr_compare(
  21                 $old,
  22                 substr($new, $pointerStart, $pointerMid - $pointerStart),
  23                 $pointerStart,
  24                 $pointerMid - $pointerStart
  25             );
  26             if (0 === $cmp) {
  27                 $pointerMin = $pointerMid;
  28                 $pointerStart = $pointerMin;
  29             } else {
  30                 $pointerMax = $pointerMid;
  31             }
  32             $pointerMid = floor(($pointerMax - $pointerMin) / 2 + $pointerMin);
  33         }
  34         return $pointerMid;
  35     }
  36
  37     public static function diffCommonSuffix($old, $new)
  38     {
  39         // Quick check for common null cases.
  40         if (strlen($old) == 0 || strlen($new) == 0 || substr($old, strlen($old) - 1, 1) != substr($new, strlen($new) - 1, 1)) {
  41             return 0;
  42         }
  43
  44         // Binary Search
  45         $pointerMin = 0;
  46         $pointerMax = min(strlen($old), strlen($new));
  47         $pointerMid = $pointerMax;
  48         $pointerEnd = 0;
  49         $oldLen = strlen($old);
  50         $newLen = strlen($new);
  51         while ($pointerMin < $pointerMid) {
  52             if (substr($old, $oldLen - $pointerMid, $pointerMid - $pointerEnd) == substr($new, $newLen - $pointerMid, $pointerMid - $pointerEnd)) {
  53                 $pointerMin = $pointerMid;
  54                 $pointerEnd = $pointerMin;
  55             } else {
  56                 $pointerMax = $pointerMid;
  57             }
  58             $pointerMid = floor(($pointerMax - $pointerMin) / 2 + $pointerMin);
  59         }
  60         return $pointerMid;
  61     }
  62 }