lib/diff.php

   1 <?php
   2 /////////////////////////////////////////////////
   3 // PukiWiki - Yet another WikiWikiWeb clone.
   4 //
   5 // $Id: diff.php,v 1.2 2004/10/07 14:34:55 henoheno Exp $
   6 //
   7 //¾×ÆÍ»þ¤ËÂÐ±þÉ½¤ò½Ð¤¹
   8 define('DIFF_SHOW_TABLE',TRUE);
   9
  10 // º¹Ê¬¤ÎºîÀ®
  11 function do_diff($strlines1, $strlines2)
  12 {
  13         $obj = new line_diff();
  14         $str = $obj->str_compare($strlines1, $strlines2);
  15         return $str;
  16 }
  17
  18 // º¹Ê¬¤ÎºîÀ®(¹¹¿·¤Î¾×ÆÍ)
  19 function do_update_diff($pagestr, $poststr, $original)
  20 {
  21         $obj = new line_diff();
  22
  23         $obj->set_str('left', $original, $pagestr);
  24         $obj->compare();
  25         $diff1 = $obj->toArray();
  26
  27         $obj->set_str('right', $original, $poststr);
  28         $obj->compare();
  29         $diff2 = $obj->toArray();
  30
  31         $arr = $obj->arr_compare('all', $diff1, $diff2);
  32
  33         if (DIFF_SHOW_TABLE)
  34         {
  35                 global $do_update_diff_table;
  36
  37                 $do_update_diff_table = <<<EOD
  38 <p>l : between backup data and stored page data.<br />
  39  r : between backup data and your post data.</p>
  40 <table class="style_table">
  41  <tr>
  42   <th>l</th>
  43   <th>r</th>
  44   <th>text</th>
  45  </tr>
  46 EOD;
  47                 $tags = array('th', 'th', 'td');
  48                 foreach ($arr as $_obj)
  49                 {
  50                         $do_update_diff_table .= '<tr>';
  51                         $params = array($_obj->get('left'), $_obj->get('right'), $_obj->text());
  52                         foreach ($params as $key=>$text) {
  53                                 $text = htmlspecialchars($text);
  54                                 if (trim($text) == '') $text = '&nbsp;';
  55                                 $do_update_diff_table .= "<{$tags[$key]} class=\"style_{$tags[$key]}\">$text</{$tags[$key]}>";
  56                         }
  57                         $do_update_diff_table .= '</tr>'."\n";
  58                 }
  59                 $do_update_diff_table .= '</table>'."\n";
  60         }
  61
  62         $body = '';
  63         foreach ($arr as $_obj) {
  64                 if ($_obj->get('left') != '-' && $_obj->get('right') != '-')
  65                         $body .= $_obj->text();
  66         }
  67
  68         $auto = 1;
  69
  70         return array(rtrim($body) . "\n", $auto);
  71 }
  72
  73 /*
  74 line_diff¥¯¥é¥¹
  75
  76 °Ê²¼¤Î¾ðÊó¤ò»²¹Í¤Ë¤·¤ÆºîÀ®¤·¤Þ¤·¤¿¡£
  77
  78 S. Wu, <A HREF="http://www.cs.arizona.edu/people/gene/vita.html">
  79 E. Myers,</A> U. Manber, and W. Miller,
  80 <A HREF="http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps">
  81 "An O(NP) Sequence Comparison Algorithm,"</A>
  82 Information Processing Letters 35, 6 (1990), 317-323.
  83
  84 */
  85
  86 class line_diff
  87 {
  88         var $arr1, $arr2, $m, $n, $pos, $key, $plus, $minus, $equal, $reverse;
  89
  90         function line_diff($plus = '+', $minus = '-', $equal = ' ')
  91         {
  92                 $this->plus  = $plus;
  93                 $this->minus = $minus;
  94                 $this->equal = $equal;
  95         }
  96
  97         function arr_compare($key, $arr1, $arr2)
  98         {
  99                 $this->key  = $key;
 100                 $this->arr1 = $arr1;
 101                 $this->arr2 = $arr2;
 102                 $this->compare();
 103                 $arr = $this->toArray();
 104                 return $arr;
 105         }
 106
 107         function set_str($key, $str1, $str2)
 108         {
 109                 $this->key  = $key;
 110                 $this->arr1 = array();
 111                 $this->arr2 = array();
 112                 $str1 = preg_replace("/\r/",'',$str1);
 113                 $str2 = preg_replace("/\r/",'',$str2);
 114                 foreach (explode("\n", $str1) as $line) {
 115                         $this->arr1[] = new DiffLine($line);
 116                 }
 117                 foreach (explode("\n", $str2) as $line) {
 118                         $this->arr2[] = new DiffLine($line);
 119                 }
 120         }
 121
 122         function str_compare($str1, $str2)
 123         {
 124                 $this->set_str('diff', $str1, $str2);
 125                 $this->compare();
 126
 127                 $str = '';
 128                 foreach ($this->toArray() as $obj) {
 129                         $str .= $obj->get('diff') . $obj->text();
 130                 }
 131                 return $str;
 132         }
 133
 134         function compare()
 135         {
 136                 $this->m = count($this->arr1);
 137                 $this->n = count($this->arr2);
 138
 139                 if ($this->m == 0 || $this->n == 0) { // no need compare.
 140                         $this->result = array(array('x'=>0, 'y'=>0));
 141                         return;
 142                 }
 143
 144                 // sentinel
 145                 array_unshift($this->arr1, new DiffLine(''));
 146                 $this->m++;
 147                 array_unshift($this->arr2, new DiffLine(''));
 148                 $this->n++;
 149
 150                 $this->reverse = ($this->n < $this->m);
 151                 if ($this->reverse) {
 152                         // Swap
 153                         $tmp = $this->m; $this->m = $this->n; $this->n = $tmp;
 154                         $tmp = $this->arr1; $this->arr1 = $this->arr2; $this->arr2 = $tmp;
 155                         unset($tmp);
 156                 }
 157
 158                 $delta = $this->n - $this->m; // Must be >=0;
 159
 160                 $fp = array();
 161                 $this->path = array();
 162
 163                 for ($p = -($this->m + 1); $p <= ($this->n + 1); $p++) {
 164                         $fp[$p] = -1;
 165                         $this->path[$p] = array();
 166                 }
 167
 168                 for ($p = 0;; $p++) {
 169                         for ($k = -$p; $k <= $delta - 1; $k++) {
 170                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 171                         }
 172                         for ($k = $delta + $p; $k >= $delta + 1; $k--) {
 173                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 174                         }
 175                         $fp[$delta] = $this->snake($delta, $fp[$delta - 1], $fp[$delta + 1]);
 176                         if ($fp[$delta] >= $this->n) {
 177                                 $this->pos = $this->path[$delta]; // ·ÐÏ©¤ò·èÄê
 178                                 return;
 179                         }
 180                 }
 181         }
 182
 183         function snake($k, $y1, $y2)
 184         {
 185                 if ($y1 >= $y2) {
 186                         $_k = $k - 1;
 187                         $y = $y1 + 1;
 188                 } else {
 189                         $_k = $k + 1;
 190                         $y = $y2;
 191                 }
 192                 $this->path[$k] = $this->path[$_k];// ¤³¤³¤Þ¤Ç¤Î·ÐÏ©¤ò¥³¥Ô¡¼
 193                 $x = $y - $k;
 194                 while ((($x + 1) < $this->m) && (($y + 1) < $this->n)
 195                         and $this->arr1[$x + 1]->compare($this->arr2[$y + 1]))
 196                 {
 197                         ++$x; ++$y;
 198                         $this->path[$k][] = array('x'=>$x, 'y'=>$y); // ·ÐÏ©¤òÄÉ²Ã
 199                 }
 200                 return $y;
 201         }
 202
 203         function toArray()
 204         {
 205                 $arr = array();
 206                 if ($this->reverse) { //¸ÈÂ©¤Ê¡Ä
 207                         $_x = 'y'; $_y = 'x'; $_m = $this->n; $arr1 =& $this->arr2; $arr2 =& $this->arr1;
 208                 } else {
 209                         $_x = 'x'; $_y = 'y'; $_m = $this->m; $arr1 =& $this->arr1; $arr2 =& $this->arr2;
 210                 }
 211
 212                 $x = $y = 1;
 213                 $this->add_count = $this->delete_count = 0;
 214                 $this->pos[] = array('x'=>$this->m, 'y'=>$this->n); // Sentinel
 215                 foreach ($this->pos as $pos) {
 216                         $this->delete_count += ($pos[$_x] - $x);
 217                         $this->add_count    += ($pos[$_y] - $y);
 218
 219                         while ($pos[$_x] > $x) {
 220                                 $arr1[$x]->set($this->key, $this->minus);
 221                                 $arr[] = $arr1[$x++];
 222                         }
 223
 224                         while ($pos[$_y] > $y) {
 225                                 $arr2[$y]->set($this->key, $this->plus);
 226                                 $arr[] =  $arr2[$y++];
 227                         }
 228
 229                         if ($x < $_m) {
 230                                 $arr1[$x]->merge($arr2[$y]);
 231                                 $arr1[$x]->set($this->key, $this->equal);
 232                                 $arr[] = $arr1[$x];
 233                         }
 234                         ++$x; ++$y;
 235                 }
 236                 return $arr;
 237         }
 238 }
 239
 240 class DiffLine
 241 {
 242         var $text;
 243         var $status;
 244
 245         function DiffLine($text)
 246         {
 247                 $this->text   = "$text\n";
 248                 $this->status = array();
 249         }
 250
 251         function compare($obj)
 252         {
 253                 return $this->text == $obj->text;
 254         }
 255
 256         function set($key, $status)
 257         {
 258                 $this->status[$key] = $status;
 259         }
 260
 261         function get($key)
 262         {
 263                 return isset($this->status[$key]) ? $this->status[$key] : '';
 264         }
 265
 266         function merge($obj)
 267         {
 268                 $this->status += $obj->status;
 269         }
 270
 271         function text()
 272         {
 273                 return $this->text;
 274         }
 275 }
 276 ?>