PHP diff with history and by keeping latest value saved in DB
===

I have to create a php diff system with an history of last 5 modifications, and displaying them by using color (like clear blue = oldest insertion, dark blue = most recent insertion)

My first idea was to keep the lastest value of the string in the database (the most safe from my point of view) and saving the modification in a database.

For example :

    $old = I want eat !
    $middle = I want to eat !
    $new= I really want to !

we will save "I really want to !" in the database, and we will save something like that into the database : 

    $new2middle = 1i(really)4d(eat)
    $middle2old = 2i(to)

So with the number we indicate the position of the string and we indicate with i if it's an insert of d if it's a delete.

To encode (generate the string 1i(really)4d(eat)) i don't have any problem. But the main problem is with that to produce a string like that :

    I <insert level="1">really</insert> want <insert level="2">to</insert> <delete level="1">eat</delete> !

I'm stuck because i have a lot of special case, like :

insert at begining :

    $old=!
    $middle=everybody !
    $new=Hi everybody !

with :

    $new2middle = 0i(hi)
    $middle2old = 0i(everybody)

The problem is that middle2old is based on string middle, and therefore in fact the position is changed. Of course i manage this case, but i have a lot of this kind of case and my code become very hard to compose, and more and more with mode history like that :

(sry is french example but word are word so ;-) )

    $old = "bien ?";
    $middle ="va bien ?";
    $new = "va bien toi ?";
    $verynew = "coucou va bien toi ? !";

with

    $verynew2new = 0i(coucou)5i(!)
    $new2middle = 2i(toi)
    $middle2old = 0i(va)

with become very hard to mange (verynew insert at end and begining of the phrase, and therefore we need to increase the position but just from one because "coucou" is before "toi" but "!" is after "toi" so we just only to increase from 1.

I try to search a lib but what i found is :
 * no history
 * retrieve from the original text which is not what i want 
 * no encoding (need encoding in order to save place in databse)

So if i post this here, is to find answer about :
 * is my way to do is adapted ? it exist a better idea ? 
 * do you know a lib which can do that ? (need utf-8 compatibility)


Thanks.

Here is my code, if you are courageous :
commented in french, sorry !

	<!DOCTYPE html>
	<html>
		<head>
			<meta charset="utf-8" />
			<link rel="stylesheet" href="style.css" />
		</head>

		<body>



	<?php

	/* Paul's Simple Diff Algorithm v 0.1
	(C) Paul Butler 2007 <http://www.paulbutler.org/>
	May be used and distributed under the zlib/libpng license.
	This code is intended for learning purposes; it was written with short
	code taking priority over performance. It could be used in a practical
	application, but there are a few ways it could be optimized.
	Given two arrays, the function diff will return an array of the changes.
	I won't describe the format of the array, but it will be obvious
	if you use print_r() on the result of a diff on some test data.
	htmlDiff is a wrapper for the diff command, it takes two strings and
	returns the differences in HTML. The tags used are <ins> and <del>,
	which can easily be styled with CSS. */	



	/*
	function diff($old, $new){
			$matrix = array();
			$maxlen = 0;
			foreach($old as $oindex => $ovalue){
				$nkeys = array_keys($new, $ovalue);
				foreach($nkeys as $nindex){
					$matrix[$oindex][$nindex] = isset($matrix[$oindex - 1][$nindex - 1]) ? $matrix[$oindex - 1][$nindex - 1] + 1 : 1;
					
					if($matrix[$oindex][$nindex] > $maxlen){
						$maxlen = $matrix[$oindex][$nindex];
						$omax = $oindex + 1 - $maxlen;
						$nmax = $nindex + 1 - $maxlen;
					}

				}

			}

			
			if($maxlen == 0)
				return array(array('d'=>$old, 'i'=>$new));
		   

			return array_merge(diff(array_slice($old, 0, $omax), array_slice($new, 0, $nmax)),array_slice($new, $nmax, $maxlen),diff(array_slice($old, $omax + $maxlen), array_slice($new, $nmax + $maxlen)));

	//            echo "array_merge(diff(" .implode(' ',array_slice($old, 0, $omax)). " , " . implode(' ',array_slice($new, 0, $nmax)).")," . implode(' ',array_slice($new, $nmax, $maxlen)).",diff(".implode(' ',array_slice($old, $omax + $maxlen)).", ".implode(' ', array_slice($new, $nmax + $maxlen))."))";

		}

	*/

	function diff($old, $new){
			$matrix = array();
			$maxlen = 0;
			foreach($old as $oindex => $ovalue){
				$ovalue = preg_replace("/<.?insert[^>]*>/", "", $ovalue);
				$ovalue = preg_replace("/<.?delete[^>]*>/", "", $ovalue);
				$ovalue = preg_replace("/<.?modif[^>]*>/", "", $ovalue);
				$ovalue = preg_replace("/<.?av[^>]*>/", "", $ovalue);
				$ovalue = preg_replace("/<.?ap[^>]*>/", "", $ovalue);
				$nkeys = array_keys($new, $ovalue);
				foreach($nkeys as $nindex){
					$matrix[$oindex][$nindex] = isset($matrix[$oindex - 1][$nindex - 1]) ? $matrix[$oindex - 1][$nindex - 1] + 1 : 1;
					
					if($matrix[$oindex][$nindex] > $maxlen){
						$maxlen = $matrix[$oindex][$nindex];
						$omax = $oindex + 1 - $maxlen;
						$nmax = $nindex + 1 - $maxlen;
					}

				}

			}

			
			if($maxlen == 0)
				return array(array('d'=>$old, 'i'=>$new));
		   

			return array_merge(diff(array_slice($old, 0, $omax), array_slice($new, 0, $nmax)),array_slice($new, $nmax, $maxlen),diff(array_slice($old, $omax + $maxlen), array_slice($new, $nmax + $maxlen)));

	//            echo "array_merge(diff(" .implode(' ',array_slice($old, 0, $omax)). " , " . implode(' ',array_slice($new, 0, $nmax)).")," . implode(' ',array_slice($new, $nmax, $maxlen)).",diff(".implode(' ',array_slice($old, $omax + $maxlen)).", ".implode(' ', array_slice($new, $nmax + $maxlen))."))";

		}

	function htmlDiff($old, $new){

			$ret = '';
			$diff = diff(explode(' ', $old), explode(' ', $new));
			foreach($diff as $k){
				
				if(is_array($k))
					$ret .= (!empty($k['d'])?"<del>".implode(' ',$k['d'])."</del> " : '') . (!empty($k['i'])?"<ins>".implode(' ',$k['i'])."</ins> ":
				''); 
				else 
					$ret .= $k . ' ';
			}

			return $ret;
		}



	/*
		Cette fonction produit une chaine suivant le format : 
		(\d+)(d\([^()]*\))?(i\([^()]*\))?
		example : 
		$old = Salut je suis français
		$new = Bonjour je suis chinois
		produit : 
		0d(Salut)i(Bonjour)3d(français)i(chinois)
		la position est relative à la chaine FINALE (CORRIGE)

		diff renvoie un array avec soit une chaine = pas de modif, soit un array avec la valeur a delete (d) ou/et la valeur à insert (i)
	*/
	function encodeHtmlDiff($old, $new){

			$diff = diff(explode(' ', $old), explode(' ', $new));
			$modif2save = "";
			$pos = 0;

			foreach($diff as $k){
				if(is_array($k)) {
					if (!empty($k['d']) || !empty($k['i'])) // il y a suppression ou insertion, on écrit la pos
						$modif2save .= "$pos";
					if (!empty($k['d'])) {
						$modif2save .= "d(" . implode(' ',$k['d']) . ")"; // on écrit la mot a delete. On increm pas car le mot supprimé sera absent
																		  // de la chaine finale, donc il faut pas avancé !
					}
					if (!empty($k['i'])) {
						$modif2save .= "i(" . implode(' ',$k['i']) . ")"; // on écrit le mot à insert, et on avance
						$pos += sizeof($k['i']);
					}
						
				}
				else { 
					$pos++; // peu importe le mot, on avance
				}
			}
		
			return $modif2save;
	}


	/**
		Transforme original suivant la valeur encode
		Exemple : 
		$original = Bonjour je suis chinois
		$encode = 0d(Salut)i(Bonjour)3d(français)i(chinois)
		produit : 
		<del>Salut</del><ins>Bonjour</ins> je suis <del>français</del><ins>chinois</ins> 

		Plus niveau est élevé, plus la couleur sera claire
	*/

	function decodeHtmlDiff($original, $encode) {

		echo $encode . "<br />";
		static $niveau = 0;
		$niveau++;
		static $positionPrec = "";
		static $decalageInsert = 0;
		static $decalageInsertFirst = 0;
		
		$original = str_replace("<delete niveau=", "<delete_niveau=", $original);
		$original = str_replace("<insert niveau=", "<insert_niveau=", $original);
		$original = str_replace("<modif niveau=", "<modif_niveau=", $original);

		$newString = explode(" ",$original); /* chaine à modifier */

		preg_match_all('/(\d+)(d\([^()]*\))?(i\([^()]*\))?/', $encode, $data, PREG_SET_ORDER);

		$data = array_reverse($data); // on reverse le tableau, car les insertions/suppression vont modifier la taille de la chaine finale.
									  // obligé donc de partir de la fin.


		foreach($data as $val) {
			/* on recupère la position et la chaine à inserer */
			$pos = $val[1];
			$toInsert = "";
			$flag = 0;
			if (isset($val[2]) && $val[2] != "" && $val[2][0] == 'd' && isset($val[3]) && $val[3] != "" && $val[3][0] == 'i') {
				$toInsert .= "<modif_niveau=\"$niveau\"><av>".substr($val[2], 2, strlen($val[2])-3)."</av> <ap>".substr($val[3], 2, strlen($val[3])-3)."</ap></modif> ";
			}
			else if (isset($val[2]) && $val[2] != "" && $val[2][0] == 'd') {
				$toInsert .= "<delete_niveau=\"$niveau\">".substr($val[2], 2, strlen($val[2])-3)."</delete> ";
				$flag = -1;
			}
			else if (isset($val[3]) && $val[3] != "" && $val[3][0] == 'i') {
				$toInsert .= " <insert_niveau=\"$niveau\">".substr($val[3], 2, strlen($val[3])-3)."</insert>";
				$flag = 1;
			}
			
			if ($flag == -1) { // juste une suppression
				if (isset ($newString[$pos]))
					array_splice ($newString, $pos, 1, explode(" ",$toInsert . $newString[$pos]) );
				else
					array_push($newString, $toInsert);

			} else if ($flag == 0) { // une suppression et une insertion
				array_splice ($newString, $pos, sizeof(explode(" ", $val[3])), explode(" ",$toInsert) );
			}else { // une insertion
				echo "$positionPrec == $pos";
				if ($positionPrec == "") {
					$positionPrec = $pos;
					$decalageInsertFirst += sizeof(array_filter(explode(" ", $val[3])));
				}
				else if ($positionPrec <= $pos) {
					$decalageInsert += sizeof(array_filter(explode(" ", $val[3]))) + $decalageInsertFirst;
					$positionPrec = $pos;
					$decalageInsertFirst = 0;
					
				}
				else {
					$decalageInsert = 0;
					$positionPrec = $pos;
				}
				echo " donc : $decalageInsert<br />";
				array_splice ($newString, $pos+$decalageInsert, sizeof(array_filter(explode(" ", $val[3]))), array_filter(explode(" ", $toInsert)));

			}

		} 

		$precedenteImbrication = $imbrication;
		$imbrication++;
		
		foreach ($newString as $key=>$val) {
			$newString[$key] = str_replace("<delete_niveau=", "<delete niveau=", $newString[$key]);
			$newString[$key] = str_replace("<insert_niveau=", "<insert niveau=", $newString[$key]);
			$newString[$key] = str_replace("<modif_niveau=", "<modif niveau=", $newString[$key]);

		}

		return implode(" ", $newString);

	}




	$old = "Le fossa (Cryptoprocta ferox), aussi appelé cryptoprocte féroce et unique représentant actuel du genre Cryptoprocta, est une espèce de mammifère féliforme de la famille des Eupleridae, endémique de Madagascar. Il est le plus gros mammifère carnivore de l'île et est parfois comparé à un petit puma. Les adultes mesurent 70 à 80 cm de long du museau à la base de la queue, et pèsent de 5,5 à 8,6 kg, les mâles étant plus lourds que les femelles. Ses griffes semi-rétractiles permettent au fossa de grimper et de descendre des arbres la tête en avant, et l'animal peut aussi sauter d'arbre en arbre. Le fossa est un représentant très particulier dans sa famille, ses organes génitaux partageant certains caractères avec les félins et les hyènes.

	Le fossa a une aire de répartition répandue sur Madagascar, mais les densités de peuplement sont généralement faibles. Il vit uniquement en habitat forestier, et chasse activement la nuit comme le jour. Plus de la moitié de son régime alimentaire se compose de lémuriens, les primates également endémiques de l'île ; les autres proies connues sont représentées par des tenrecs, des rongeurs, des lézards, des oiseaux et divers autres animaux. L'accouplement a habituellement lieu dans des arbres, sur des branches horizontales, et peut durer plusieurs heures. La portée compte un à six petits, qui naissent aveugles et sans dents. Les jeunes sont sevrés au bout de quatre mois et demi, et sont indépendants au bout d'un an. Ils atteignent la maturité sexuelle à l'âge de deux ans, et la longévité mesurée en captivité est de vingt ans.

	Sa classification a été sujette à débats, l'animal partageant des traits avec les félins, d'autres suggérant une relation étroite avec les viverridés. Sa position phylogénétique, avec celles des autres carnivores malgaches, a influencé les hypothèses sur le nombre de colonisations de l'île par les mammifères carnivores. Les études génétiques ayant montré que le fossa et tous les autres carnivores de Madagascar étant plus proches entre eux, formant le clade qu'est la famille des Eupleridae, on sait aujourd'hui que les carnivores ont colonisé l'île en une seule arrivée, remontant à 18 ou 20 millions d'années. Le fossa est considéré comme « vulnérable » par l'Union internationale pour la conservation de la nature, ses effectifs sont jugés en déclin et principalement menacés par la destruction de l'habitat. Il est généralement craint par le peuple malgache et est souvent protégé par son tabou, nommé fady.";



	$new = "Le fossa (Cryptoprocta ferox), aussi appelé cryptoprocte et un unique représentant actuel du genre Cryptoprocta, est une espèce de mammifère féliforme de la famille des Eupleridae, endémique de Madagascar. Il est le plus gros mammifère carnivore de l'île et est parfois comparé à un petit puma. Ils mesurent 70 à 80 cm de long du museau à la base de la queue, et pèsent de 5,5 à 8,6 kg, les mâles étant plus lourds que les femelles. Ses griffes semi-rétractiles permettent au fossa de grimper et de descendre des arbres la tête en avant, et l'animal peut aussi sauter d'arbre en arbre. Le fossa est un représentant très particulier dans sa famille, ses organes génitaux partageant certains caractères avec les félins et les hyènes.

	Le fossa a une aire de répartition répandue sur Grenoble, mais les densités de peuplement sont généralement faibles. Il vit uniquement en habitat forestier, et chasse activement la nuit comme le jour. Plus de la moitié de son régime alimentaire se compose de lémuriens, les primates également endémiques de l'île ; les autres proies connues sont représentées par des tenrecs, des rongeurs, des lézards, des oiseaux et divers autres animaux. L'accouplement a habituellement lieu dans des arbres, sur des branches horizontales, et peut durer plusieurs heures. La portée compte un à six petits, qui naissent aveugles et sans dents. Les jeunes sont sevrés au bout de quatre mois et demi, et sont indépendants au bout d'un an. Ils atteignent la maturité sexuelle à l'âge de deux ans, et la longévité mesurée en captivité est de vingt ans.

	Sa classification a été sujette à débats, l'animal féroce partageant des traits avec les félins, d'autres suggérant une relation étroite avec les viverridés. Sa position phylogénétique, avec celles des autres carnivores malgaches, a influencé les hypothèses sur le nombre de colonisations de l'île par les mammifères carnivores. Les études génétiques ayant montré que le fossa et tous les autres carnivores de Madagascar étant plus proches entre eux, formant le clade qu'est la famille des Eupleridae, on sait aujourd'hui que les carnivores ont colonisé l'île en une seule arrivée, remontant à 18 ou 20 millions d'années. Le fossa  est considéré comme un très grand « vulnérable » par l'Union internationale pour la conservation de la nature, ses effectifs sont jugés en déclin et principalement menacés par la destruction de l'habitat. Il est généralement craint par le peuple malgache et est souvent protégé par son tabou, nommé fady!";



	$old = "Bonjour je suis un français et j'aime les tartes aux pommes ! et toi ?";
	$middle = "Bonjour je suis un chinois et j'aime pas les tartes aux pommes !!! et";
	$new = "Salut je m'apelle Sébastien et j'aime beaucoup les tartes aux poires !!!";
	$verynew = "Salut je m'apelle Nicolas et j'aime beaucoup les tartes aux poires !!!";



	//$old = "Salut toi ça va bien ?";
	//$middle ="Salut toi ça va";
	//$new = "Salut toi ";
	//$verynew = "Salut";



	/* tests insertions */

	$old = "bien ?";
	$middle ="va bien ?";
	$new = "va bien toi ?";
	$verynew = "coucou va bien toi ? !";

	//$old = "bien ?";
	//$middle ="va bien ?";
	//$new = "ça va bien ?";
	//$verynew = "Salut toi ça va bien ?";

	//$old = "Salut";
	//$middle ="Salut toi ça";
	//$new = "Salut toi ça va";
	//$verynew = "Salut toi ça va bien ?";

	//$old = "bien ?";
	//$middle ="Salut bien ?";
	//$new = "Salut va bien ?";
	//$verynew = "Salut ça va bien ?";



	echo "old=$old<br />middle=$middle<br />new=$new<br />verynew=$verynew<br /><hr />";

	// 1er modif, on a accès a old et à middle (le new)
	$middle2old = encodeHtmlDiff($old, $middle);

	// 2eme modif, on a accès à middle et à new
	$new2middle = encodeHtmlDiff($middle, $new);
	//echo decodeHtmlDiff(decodeHtmlDiff($new, $new2middle), $middle2old);

	// 3eme modif, on a acces a new et a verynew
	$verynew2new = encodeHtmlDiff($new, $verynew);


	echo decodeHtmlDiff(decodeHtmlDiff(decodeHtmlDiff($verynew, $verynew2new), $new2middle), $middle2old);


	echo "<hr />";

	?>

		</body>
	</html>
