diff.php

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