diff.php

   1 <?php
   2 /////////////////////////////////////////////////
   3 // PukiWiki - Yet another WikiWikiWeb clone.
   4 //
   5 // $Id: diff.php,v 1.7 2003/06/11 00:00:51 arino 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                         {
  54                                 $text = htmlspecialchars($text);
  55                                 if (trim($text) == '')
  56                                 {
  57                                         $text = '&nbsp;';
  58                                 }
  59                                 $do_update_diff_table .= "<{$tags[$key]} class=\"style_{$tags[$key]}\">$text</{$tags[$key]}>";
  60                         }
  61                         $do_update_diff_table .= '</tr>'."\n";
  62                 }
  63                 $do_update_diff_table .= '</table>'."\n";
  64         }
  65
  66         $body = '';
  67         foreach ($arr as $_obj)
  68         {
  69                 if ($_obj->get('left') != '-' and $_obj->get('right') != '-')
  70                 {
  71                         $body .= $_obj->text();
  72                 }
  73         }
  74
  75         $auto = 1;
  76
  77         return array(rtrim($body)."\n",$auto);
  78 }
  79
  80 /*
  81 line_diff¥¯¥é¥¹
  82
  83 °Ê²¼¤Î¾ðÊó¤ò»²¹Í¤Ë¤·¤ÆºîÀ®¤·¤Þ¤·¤¿¡£
  84
  85 S. Wu, <A HREF="http://www.cs.arizona.edu/people/gene/vita.html">
  86 E. Myers,</A> U. Manber, and W. Miller,
  87 <A HREF="http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps">
  88 "An O(NP) Sequence Comparison Algorithm,"</A>
  89 Information Processing Letters 35, 6 (1990), 317-323.
  90
  91 */
  92
  93 class line_diff
  94 {
  95         var $arr1,$arr2,$m,$n,$pos,$key,$plus,$minus,$equal,$reverse;
  96
  97         function line_diff($plus='+',$minus='-',$equal=' ')
  98         {
  99                 $this->plus = $plus;
 100                 $this->minus = $minus;
 101                 $this->equal = $equal;
 102         }
 103         function arr_compare($key,$arr1,$arr2)
 104         {
 105                 $this->key = $key;
 106                 $this->arr1 = $arr1;
 107                 $this->arr2 = $arr2;
 108                 $this->compare();
 109                 $arr = $this->toArray();
 110                 return $arr;
 111         }
 112         function set_str($key,$str1,$str2)
 113         {
 114                 $this->key = $key;
 115                 $this->arr1 = array();
 116                 $this->arr2 = array();
 117                 $str1 = preg_replace("/\r/",'',$str1);
 118                 $str2 = preg_replace("/\r/",'',$str2);
 119                 foreach (explode("\n",$str1) as $line)
 120                 {
 121                         $this->arr1[] = new DiffLine($line);
 122                 }
 123                 foreach (explode("\n",$str2) as $line)
 124                 {
 125                         $this->arr2[] = new DiffLine($line);
 126                 }
 127         }
 128         function str_compare($str1,$str2)
 129         {
 130                 $this->set_str('diff',$str1,$str2);
 131                 $this->compare();
 132
 133                 $str = '';
 134                 foreach ($this->toArray() as $obj)
 135                 {
 136                         $str .= $obj->get('diff').$obj->text();
 137                 }
 138                 return $str;
 139         }
 140         function compare()
 141         {
 142                 $this->m = count($this->arr1);
 143                 $this->n = count($this->arr2);
 144
 145                 if ($this->m == 0 or $this->n == 0) // no need compare.
 146                 {
 147                         $this->result = array(array('x'=>0,'y'=>0));
 148                         return;
 149                 }
 150
 151                 // sentinel
 152                 array_unshift($this->arr1,new DiffLine(''));
 153                 $this->m++;
 154                 array_unshift($this->arr2,new DiffLine(''));
 155                 $this->n++;
 156
 157                 $this->reverse = ($this->n < $this->m);
 158                 if ($this->reverse) // swap
 159                 {
 160                         $tmp = $this->m; $this->m = $this->n; $this->n = $tmp;
 161                         $tmp = $this->arr1; $this->arr1 = $this->arr2; $this->arr2 = $tmp;
 162                         unset($tmp);
 163                 }
 164
 165                 $delta = $this->n - $this->m; // must be >=0;
 166
 167                 $fp = array();
 168                 $this->path = array();
 169
 170                 for ($p = -($this->m + 1); $p <= ($this->n + 1); $p++)
 171                 {
 172                         $fp[$p] = -1;
 173                         $this->path[$p] = array();
 174                 }
 175
 176                 for ($p = 0;; $p++)
 177                 {
 178                         for ($k = -$p; $k <= $delta - 1; $k++)
 179                         {
 180                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 181                         }
 182                         for ($k = $delta + $p; $k >= $delta + 1; $k--)
 183                         {
 184                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 185                         }
 186                         $fp[$delta] = $this->snake($delta, $fp[$delta - 1], $fp[$delta + 1]);
 187                         if ($fp[$delta] >= $this->n)
 188                         {
 189                                 $this->pos = $this->path[$delta]; // ·ÐÏ©¤ò·èÄê
 190                                 return;
 191                         }
 192                 }
 193         }
 194         function snake($k, $y1, $y2)
 195         {
 196                 if ($y1 >= $y2)
 197                 {
 198                         $_k = $k - 1;
 199                         $y = $y1 + 1;
 200                 }
 201                 else
 202                 {
 203                         $_k = $k + 1;
 204                         $y = $y2;
 205                 }
 206                 $this->path[$k] = $this->path[$_k];// ¤³¤³¤Þ¤Ç¤Î·ÐÏ©¤ò¥³¥Ô¡¼
 207                 $x = $y - $k;
 208                 while ((($x + 1) < $this->m) and (($y + 1) < $this->n)
 209                         and $this->arr1[$x + 1]->compare($this->arr2[$y + 1]))
 210                 {
 211                         $x++; $y++;
 212                         $this->path[$k][] = array('x'=>$x,'y'=>$y); // ·ÐÏ©¤òÄÉ²Ã
 213                 }
 214                 return $y;
 215         }
 216         function toArray()
 217         {
 218                 $arr = array();
 219                 if ($this->reverse) //¸ÈÂ©¤Ê¡Ä
 220                 {
 221                         $_x = 'y'; $_y = 'x'; $_m = $this->n; $arr1 =& $this->arr2; $arr2 =& $this->arr1;
 222                 }
 223                 else
 224                 {
 225                         $_x = 'x'; $_y = 'y'; $_m = $this->m; $arr1 =& $this->arr1; $arr2 =& $this->arr2;
 226                 }
 227
 228                 $x = $y = 1;
 229                 $this->add_count = $this->delete_count = 0;
 230                 $this->pos[] = array('x'=>$this->m,'y'=>$this->n); // sentinel
 231                 foreach ($this->pos as $pos)
 232                 {
 233                         $this->delete_count += ($pos[$_x] - $x);
 234                         $this->add_count += ($pos[$_y] - $y);
 235
 236                         while ($pos[$_x] > $x)
 237                         {
 238                                 $arr1[$x]->set($this->key,$this->minus);
 239                                 $arr[] = $arr1[$x++];
 240                         }
 241
 242                         while ($pos[$_y] > $y)
 243                         {
 244                                 $arr2[$y]->set($this->key,$this->plus);
 245                                 $arr[] =  $arr2[$y++];
 246                         }
 247
 248                         if ($x < $_m)
 249                         {
 250                                 $arr1[$x]->merge($arr2[$y]);
 251                                 $arr1[$x]->set($this->key,$this->equal);
 252                                 $arr[] = $arr1[$x];
 253                         }
 254                         $x++; $y++;
 255                 }
 256                 return $arr;
 257         }
 258 }
 259
 260 class DiffLine
 261 {
 262         var $text;
 263         var $status;
 264
 265         function DiffLine($text)
 266         {
 267                 $this->text = "$text\n";
 268                 $this->status = array();
 269         }
 270         function compare($obj)
 271         {
 272                 return $this->text == $obj->text;
 273         }
 274         function set($key,$status)
 275         {
 276                 $this->status[$key] = $status;
 277         }
 278         function get($key)
 279         {
 280                 return array_key_exists($key,$this->status) ? $this->status[$key] : '';
 281         }
 282         function merge($obj)
 283         {
 284                 $this->status += $obj->status;
 285         }
 286         function text()
 287         {
 288                 return $this->text;
 289         }
 290 }
 291 ?>