X-Git-Url: http://git.cyclocoop.org/?p=velocampus%2Fweb%2Fwww.git;a=blobdiff_plain;f=www%2Fecrire%2Finc%2Fdiff.php;fp=www%2Fecrire%2Finc%2Fdiff.php;h=b7c1abff2918d7ecf26568b11e1b11fb018b947f;hp=0000000000000000000000000000000000000000;hb=80b4d3e85f78d402ed2e73f8f5d1bf4c19962eed;hpb=aaf970bf4cdaf76689ecc10609048e18d073820c diff --git a/www/ecrire/inc/diff.php b/www/ecrire/inc/diff.php new file mode 100644 index 0000000..b7c1abf --- /dev/null +++ b/www/ecrire/inc/diff.php @@ -0,0 +1,403 @@ + $c) { + for ($len = $max_len; $len > 0; $len--) { + if ($paths_ymin[$len] < $y) { + $paths_ymin[$len + 1] = $y; + $paths[$len + 1] = $paths[$len]; + $paths[$len + 1][$y] = $c; + break; + } + } + if ($len == 0) { + $paths_ymin[1] = $y; + $paths[1] = array($y => $c); + } + if ($len + 1 > $max_len) $max_len = $len + 1; + } + return $paths[$max_len]; +} + +// Version normale : les deux chaines n'ont pas ete traitees au prealable +// par la fonction d'appariement +// http://doc.spip.org/@lcs +function lcs($s, $t) { + $n = count($s); + $p = count($t); + if (!$n || !$p) return array(0 => array(), 1 => array()); + $paths = array(); + $paths_ymin = array(); + $max_len = 0; + $s_pos = $t_pos = array(); + + // Insertion des points + foreach ($t as $y => $c) $t_pos[trim($c)][] = $y; + + foreach ($s as $x => $c) { + $c = trim($c); + if (!isset($t_pos[$c])) continue; + krsort($t_pos[$c]); + foreach ($t_pos[$c] as $y) { + for ($len = $max_len; $len > 0; $len--) { + if ($paths_ymin[$len] < $y) { + $paths_ymin[$len + 1] = $y; + // On construit le resultat sous forme de chaine d'abord, + // car les tableaux de PHP sont dispendieux en taille memoire + $paths[$len + 1] = $paths[$len]." $x,$y"; + break; + } + } + if ($len + 1 > $max_len) $max_len = $len + 1; + if ($len == 0) { + $paths_ymin[1] = $y; + $paths[1] = "$x,$y"; + } + } + } + if ($paths[$max_len]) { + $path = explode(" ", $paths[$max_len]); + $u = $v = array(); + foreach ($path as $p) { + list($x, $y) = explode(",", $p); + $u[$x] = $y; + $v[$y] = $x; + } + return array($u, $v); + } + return array(0 => array(), 1 => array()); +} + +// +// Generation de diff a plusieurs etages +// + +// http://doc.spip.org/@Diff +class Diff { + var $diff; + var $fuzzy; + +// http://doc.spip.org/@Diff + function Diff($diff) { + $this->diff = $diff; + $this->fuzzy = true; + } + +// http://doc.spip.org/@comparer + function comparer($new, $old) { + $paras = $this->diff->segmenter($new); + $paras_old = $this->diff->segmenter($old); + if ($this->diff->fuzzy()) { + list($trans_rev, $trans) = apparier_paras($paras_old, $paras); + $lcs = lcs_opt($trans); + $lcs_rev = array_flip($lcs); + } + else { + list($trans_rev, $trans) = lcs($paras_old, $paras); + $lcs = $trans; + $lcs_rev = $trans_rev; + } + + reset($paras_old); + reset($paras); + reset($lcs); + unset($i_old); + $fin_old = false; + foreach ($paras as $i => $p) { + if (!isset($trans[$i])) { + // Paragraphe ajoute + $this->diff->ajouter($p); + continue; + } + $j = $trans[$i]; + if (!isset($lcs[$i])) { + // Paragraphe deplace + $this->diff->deplacer($p, $paras_old[$j]); + continue; + } + if (!$fin_old) { + // Paragraphes supprimes jusqu'au paragraphe courant + if (!isset($i_old)) { + list($i_old, $p_old) = each($paras_old); + if (!$p_old) $fin_old = true; + } + while (!$fin_old && $i_old < $j) { + if (!isset($trans_rev[$i_old])) { + $this->diff->supprimer($p_old); + } + unset($i_old); + list($i_old, $p_old) = each($paras_old); + if (!$p_old) $fin_old = true; + } + } + // Paragraphe n'ayant pas change de place + $this->diff->comparer($p, $paras_old[$j]); + } + // Paragraphes supprimes a la fin du texte + if (!$fin_old) { + if (!isset($i_old)) { + list($i_old, $p_old) = each($paras_old); + if (!strlen($p_old)) $fin_old = true; + } + while (!$fin_old) { + if (!isset($trans_rev[$i_old])) { + $this->diff->supprimer($p_old); + } + list($i_old, $p_old) = each($paras_old); + if (!$p_old) $fin_old = true; + } + } + if (isset($i_old)) { + if (!isset($trans_rev[$i_old])) { + $this->diff->supprimer($p_old); + } + } + return $this->diff->resultat(); + } +} + +// http://doc.spip.org/@DiffTexte +class DiffTexte { + var $r; + +// http://doc.spip.org/@DiffTexte + function DiffTexte() { + $this->r = ""; + } + +// http://doc.spip.org/@_diff + function _diff($p, $p_old) { + $diff = new Diff(new DiffPara); + return $diff->comparer($p, $p_old); + } + +// http://doc.spip.org/@fuzzy + function fuzzy() { + return true; + } +// http://doc.spip.org/@segmenter + function segmenter($texte) { + return separer_paras($texte); + } + + // NB : rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies" +// http://doc.spip.org/@ajouter + function ajouter($p) { + $p = trim($p); + $this->r .= "\n\n\n