<?
/**
  Implementation of a GNU diff alike function from scratch.
  Copyright (C) 2003  Nils Knappmeier <nk@knappi.org>

  Permission is hereby granted, free of charge, to any person obtaining 
  a copy of this software and associated documentation files (the 
  "Software"), to deal in the Software without restriction, including 
  without limitation the rights to use, copy, modify, merge, publish, 
  distribute, sublicense, and/or sell copies of the Software, and to 
  permit persons to whom the Software is furnished to do so, subject to 
  the following conditions:

  The above copyright notice and this permission notice shall be 
  included in all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 
  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 
  BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 
  ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 
  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 
  SOFTWARE.

  Revision: $Revision: 1.9 $
  
 **/


/*
 * 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) {
#    echo "<pre>";
    $array1 = splitWithNL($text1);
    $array2 = splitWithNL($text2);

    $result="";
    /* Build matching matrix (i.e. the cost for a diagonal edge) */
#    for ($y=0; $y<count($array2); $y++) {
#	for ($x=0; $x<count($array1); $x++) {
#    if ($array1[$x] == $array2[$y]) {
#		$match[$x][$y]=0;
#	    } else {
#		$match[$x][$y]=1;
#	    }
#	    /* 0=unvisited, 1=right, 2=down, 3=diag */
#	    $from[$x][$y] = 0;
#	}
#   }

    /*
     * Do a BFS with collapsing zero-edges to one point
     * It's tricky, but it's much easier to do the BFS i
     * from the right bottom to the top left.
     */
    $queueX = array(count($array1));
    $queueY = array(count($array2));
    $firstX = end($queueX);
    $firstY = end($queueY);
    do {
	$x=array_shift($queueX);
	$y=array_shift($queueY);
#	echo 'Size of queue: '.count($queueX).':'.count($queueY).' Taking:'.$x.':'.$y."\n";
	if (add_succ($x,$y,$queueX,$queueY,$array1,$array2,$from)) break;
    } while($x>0 || $y>0 );
    /* Now follow the way back and report connected (unequal) pieces */
    $x=$xold=0;
    $y=$yold=0;
    $action="";

#    print_r($from);
    
    do {
	$direction=$from[$x][$y];
#	echo "$direction\n";
	if ($direction==1) {
	    if ($action=="" || $action=="d") {
		$action="d";
	    } else {
		$action="c";
	    }
	    $x++;
	}
	if ($direction==2) {
	    if ($action=="" || $action=="a") {
		$action="a";
	    } else {
		$action="c";
	    }
	    $y++;
	}
	if ($direction==3 || $direction=="") { 
	    /* Prepare header for change 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 ($action=="a") {
		$result.= ($x)."a$ystr\n";
		for($i=$yold; $i<$y;$i++) {
		    $result.= "> ".$array2[$i];
		}
	    } else if ($action=="d") {
		$result.= ($xstr)."d".($y)."\n";
		for($i=$xold; $i<$x;$i++) {
		    $result.= "< ".$array1[$i];
		}
	    } else if ($action=="c") {
		$result.= "$xstr$action$ystr\n";
		for($i=$xold; $i<$x;$i++) {
		    $result.= "< ".$array1[$i];
		}
		$result.= "---\n";
		for($i=$yold; $i<$y;$i++) {
		    $result.= "> ".$array2[$i];
		}
	    }
	    $x++; $y++;
	    $action="";
	    $xold=$x;
	    $yold=$y;

	}
    } while($direction!="");

#   echo $result;
#    echo "</pre>";
#    exit;
    return $result;
}

function add_succ($x,$y, &$queueX, &$queueY, &$array1, &$array2, &$from) {

    

    /** Go diognally until there is no edge, then backwards and add all the successors **/
    $xscan=$x;
    $yscan=$y;
    while ($array1[$xscan-1] == $array2[$yscan-1]) { #if ($match[$x-1][$y-1]==0) 
	if ($xscan<=0 && $yscan<=0) {
	    return true;
	} else if ($from[$xscan-1][$yscan-1]==0) {
	    $from[$xscan-1][$yscan-1]=3;
	    $xscan--;
	    $yscan--;
	} else {
	    break;
	}
    }
    
#    while ($xscan<=$x && $yscan<=$y) {

	if ($yscan>0 && $from[$xscan][$y-1]==0) {
	   $from[$xscan][$yscan-1]=2;
	    $queueX[]=$xscan;
	    $queueY[]=$yscan-1;
	}
	if ($xscan>0 && $from[$xscan-1][$yscan]==0) {
	    $from[$xscan-1][$yscan]=1;
	    $queueX[]=$xscan-1;
	    $queueY[]=$yscan;
	}
#	$yscan++;
#	$xscan++;
#    }
    return false;
}


/* 
   File history:

   $Log: phpdiffnm.php,v $
   Revision 1.9  2004/12/16 14:05:08  nknapp
   Changed the license statements to MIT-license in all files

   Revision 1.8  2004/09/22 19:04:22  nknapp
   ...

   Revision 1.7  2004/03/04 10:07:28  nknapp
   Ready for pmwiki-0.6.9 now

   Revision 1.6  2004/03/04 09:57:25  nknapp
   For 0.6.9

   Revision 1.5  2004/02/24 08:02:40  nknapp
   ...

   Revision 1.4  2004/02/14 14:30:30  nknapp
   Bugfix in add_succ

   Revision 1.3  2004/02/14 13:45:50  nknapp
   Replaced recursion in add_suc by iteration

   Revision 1.2  2004/02/14 10:41:34  nknapp
   Some memory optimizations

   Revision 1.1  2004/02/13 23:56:33  nknapp
   n*m space version

   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:
*/
?>
