<?
/**
  Implementation of a GNU diff alike function from scratch.
  This file contains functions needed by both diff and patch
  Copyright (C) 2003  Nils Knappmeier <nk@knappi.org>

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License
  as published by the Free Software Foundation; either version 2
  of the License, or (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

  http://www.gnu.org/licenses/gpl.html

  
  Revision: $Revision: 1.3 $
  
 **/


/*
 * Convert texts into arrays such that the newlines are conserved
 */
function splitWithNL($text) {
    $array = split("\n", $text);
    for ($i=0; $i<count($array); $i++) {
	$array[$i]=$array[$i]."\n";
    }
    if ($array[count($array)-1]=="\n") {
	array_pop($array);
    } else {
	$array[count($array)-1]=$array[count($array)-1].
	    "\\ No newline at end of file\n";
    }
    return $array;
}

?>
<?
/**
  Implementation of a GNU diff alike function from scratch.
  Copyright (C) 2003  Nils Knappmeier <nk@knappi.org>

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License
  as published by the Free Software Foundation; either version 2
  of the License, or (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

  http://www.gnu.org/licenses/gpl.html

  
  Revision: $Revision: 1.12 $
  
 **/


$DiffFunction='php_Diff';



/**
 * Checks, if there is a line number-entry in $r_array for $line,
 * that is behind $where.
 * $where will be assigned the line-number, if true
 **/
function nextOccurence($line, &$r_array, $where) {
    $tmp = $r_array[$line];
    if (!$tmp) return FALSE;
    foreach($tmp as $nr) {
	if ($where<=$nr) {
	    $where = $nr;
	    return $nr;
	}
    }
    return FALSE;
}


/**
 * Compute the manhatten distance of two points
 **/
function dist($a,$b) {
    $d1=$b[1]-$a[1];
    $d2=$b[2]-$a[2];
    return $d2+$d1;
}


/*
 * Computes the difference between two string linewise. 
 * The output is the same format
 * as the GNU diff command without any parameters.
 * Note: Since GNU diff starts counting with 1, and arrays start counting with
 * 0, you have to subtract one from each line number to get the real one.
 */
function php_Diff($text1, $text2) {
    
    
    $array1 = splitWithNL($text1);
    $array2 = splitWithNL($text2);

    /* Build up array with the line as key and a list of line numbers as value */
    
    foreach($array1 as $nr => $line) {
	$r_array1[$line][] = $nr;
    }
    foreach($array2 as $nr => $line) {
	$r_array2[$line][] = $nr;
    }


    $result="";

  
    $a[1]=0;  /* counter for array1 */
    $a[2]=0;  /* counter for array2 */
    $actions=Array();
    while($a[1]<sizeof($array1) && $a[2]<sizeof($array2)) {
 #       print "$a[1]:$a[2]\n";
	if ($array1[$a[1]]==$array2[$a[2]]) {
	    $a[1]++;
	    $a[2]++;
	    $actions[]=copy;
	} else {
	    /*
	     * $tmp1/2 is the next line in $array1/2 that equals
	     * $array2/1[$a2/1+1];
	     */ 


	    $best[1]=count($array1);
	    $best[2]=count($array2);
	    $scan=$a;
	    
	    
#	    echo "distBest = ".dist($a, $best)."\n";
#	    echo "distScan = ".dist($a, $scan)."\n";
	    while(dist($a, $scan)<dist($a, $best)) {
#		echo "A    $a[1]:$a[2]\t";
#		echo "Scan $scan[1]:$scan[2]  ";
		$tmp[1]=nextOccurence($array2[$scan[2]], $r_array1, $scan[1]);
		$tmp[2]=$scan[2];
		if ($tmp[1] && dist($a, $tmp) < dist($a,$best)) $best=$tmp; 
#		echo "Tmp1 $tmp[1]:$tmp[2]\t";;
	    
		$tmp[1]=$scan[1];
		$tmp[2]=nextOccurence($array1[$scan[1]], $r_array2, $scan[2]);
		if ($tmp[2] && dist($a, $tmp) < dist($a,$best)) $best=$tmp; 
#		echo "Tmp2 $tmp[1]:$tmp[2]\t";

		
#		echo "Best $best[1]:$best[2]\n";
		$scan[1]++;
		$scan[2]++;
	    }
	
	    for($i=$a[1]; $i<$best[1]; $i++) {
		$actions[]=del;
	    }
	    
	    for($i=$a[2]; $i<$best[2]; $i++) {
		$actions[]=add;
	    }
	
	    $a=$best;
	}	       
    }

    # Here, we may still not be at the bottom left corner.
    # So we have to get there. (This case happens, when we just append something to the page)	
    for($i=$a[1]; $i<sizeof($array1); $i++) {
	$actions[]=del;
    }
    
    for($i=$a[2]; $i<sizeof($array2); $i++) {
	$actions[]=add;
    }

    $actions[]=finish;
    
    

    
    /* Now follow the way back and report connected (unequal) pieces */
    $x=$xold=0;
    $y=$yold=0;
    $realAction=""; /* the current action */
    foreach($actions as $action) {

	if ($action==del) {
	    if ($realAction=="" || $realAction=="d") {
		$realAction="d";
	    } else {
		$realAction="c";
	    }
	    $x++;
	}
	if ($action==add) {
	    if ($realAction=="" || $realAction=="a") {
		$realAction="a";
	    } else {
		$realAction="c";
	    }
	    $y++;
	}
	if ($action==copy || $action==finish) { 
	    /* Prepare header for diff entry */
	    if ($xold+1 == $x) {
		$xstr=$x;
	    } else {
		$xstr=($xold+1).",$x";
	    }
	    if ($yold+1 == $y) {
		$ystr=$y;
	    } else {
		$ystr=($yold+1).",$y";
	    }

	    /* "Print" entry to result */
	    if ($realAction=="a") {
		$result.= ($x)."a$ystr\n";
		for($i=$yold; $i<$y;$i++) {
		    $result.= "> ".$array2[$i];
		}
	    } else if ($realAction=="d") {
		$result.= ($xstr)."d".($y)."\n";
		for($i=$xold; $i<$x;$i++) {
		    $result.= "< ".$array1[$i];
		}
	    } else if ($realAction=="c") {
		$result.= "$xstr$realAction$ystr\n";
		for($i=$xold; $i<$x;$i++) {
		    $result.= "< ".$array1[$i];
		}
		$result.= "---\n";
		for($i=$yold; $i<$y;$i++) {
		    $result.= "> ".$array2[$i];
		}
	    }
	    $x++; $y++;
	    $realAction="";
	    $xold=$x;
	    $yold=$y;

	}
    }
    return $result;
}

/* 
   File history:

   $Log: phpdiff.php,v $
   Revision 1.12  2004/03/25 23:21:13  nknapp
   Bugfix: Early stopping algorithm when appending file.

   Revision 1.11  2004/03/07 11:57:09  nknapp
   Removed include(difflib)

   Revision 1.10  2004/03/07 11:08:53  nknapp
   Removed some debug statements

   Revision 1.9  2004/03/07 10:48:26  nknapp
   Implemented greedy

   Revision 1.8  2004/03/04 09:57:25  nknapp
   For 0.6.9

   Revision 1.7  2004/02/22 18:03:42  nknapp
   New algorithm

   Revision 1.6  2004/02/14 09:09:39  nknapp
   Spawn of some variations

   Revision 1.5  2004/02/13 23:13:28  nknapp
   Externalized difflib.php

   Revision 1.4  2004/02/13 22:21:02  nknapp
   Removed "Algorithm described"

   Revision 1.3  2004/02/13 22:18:30  nknapp
   Splitted diff and patch into two files. Improved makefile

   Revision 1.2  2004/02/13 21:18:45  nknapp
   Minor change

   Revision 1.1  2004/02/13 21:16:02  nknapp
   First checkin

   
   vim:sw=4:ai:cin:sts=4:
*/
?>