Julien Arlandis
unread,May 23, 2013, 9:17:11 AM5/23/13You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
Ceci est une tentative d'impl�mentation en javascript de l'algorithme
�crit par Olivier Miakinen en PHP. �a ne fonctionne pas, Olivier as tu
une id�e de ce qui cloche?
liste = [
{"Jid":"a", "refs":["d"]},
{"Jid":"b", "refs":["d","c"]},
{"Jid":"c", "refs":["d"]},
{"Jid":"d", "refs":[]},
{"Jid":"e", "refs":["d","c","f"]},
{"Jid":"f", "refs":["d","c"]},
{"Jid":"g", "refs":["d","c","f"]},
{"Jid":"h", "refs":["d"]},
{"Jid":"i", "refs":["d","a"]},
{"Jid":"j", "refs":[]},
{"Jid":"k", "refs":["j"]},
{"Jid":"l", "refs":["j","k"]}
];
isNotEmpty = function(tab)
{
for(i in tab){
if(tab[i] != undefined) return true;
}
return false;
}
construis_arbo = function(liste)
{
arbre = [];
arbre['']=[];
substitut = [];
while_liste:
while(isNotEmpty(liste))
{
for_liste:
for(i in liste)
{
refs = liste[i].refs;
while(refs.length)
{
ref = refs[refs.length - 1];
if(arbre[ref])
{
arbre[ref].push(liste[i].Jid);
arbre[liste[i].Jid] = [];
delete liste[i];
continue while_liste;
}
if(substitut[ref])
{
arbre[substitut[ref]].push( liste[i].Jid );
arbre[liste[i].Jid] = [];
delete liste[i];
continue while_liste;
}
if (liste[ref])
{
continue for_liste;
}
refs.pop();
if(!isNotEmpty(refs))
{
substitut[ref] = liste[i].Jid;
}
}
arbre[''].push(liste[i].Jid);
arbre[liste[i].Jid] = [];
delete liste[i];
continue while_liste;
}
for(i in liste)
{
refs.pop();
continue while_liste;
}
}
return arbre;
}
Voici le script php inititial :
$liste = array(
"a" => array("d"),
"b" => array("d","c"),
"c" => array("d"),
"d" => array(),
"e" => array("d","c","f"),
"f" => array("d","c"),
"g" => array("d","c","f"),
"h" => array("d"),
"i" => array("d","a"),
"j" => array(),
"k" => array("j"),
"l" => array("j","k")
);
function construis_arbo($liste)
{
$arbre = array("" => array());
$substitut = array();
while ($liste) {
foreach ($liste as $id => &$refs) {
// voyons un article non encore plac� dans l'arbre
while ($refs) {
// on regarde la derni�re r�f�rence de l'article
$ref = end($refs);
if (isset($arbre[$ref])) {
// l'article en r�f�rence est dans l'arbre :
// on peut placer le nouvel article.
$arbre[$ref][] = $id;
$arbre[$id] = array();
unset($liste[$id]);
continue 3; /* while ($liste) */
}
if (isset($substitut[$ref])) {
// l'article en r�f�rence n'est dans l'arbre car
// il n'�tait pas dans la liste, mais un autre
// article le remplace : on peut donc placer le
// nouvel article aussi.
$arbre[$substitut[$ref]][] = $id;
$arbre[$id] = array();
unset($liste[$id]);
continue 3; /* while ($liste) */
}
if (isset($liste[$ref])) {
// l'article en r�f�rence est encore � placer :
// voir un autre article, celui-ci sera trait�
// plus tard.
continue 2; /* foreach ($liste) */
}
// l'article en r�f�rence n'existe pas : on le
// supprime de la liste des r�f�rences.
array_pop($refs);
// si le premier article d'un fil de discussion
// n'existe pas, on lui choisit un substitut.
if (! $refs) {
$substitut[$ref] = $id;
}
}
// Cet article n'a pas (ou n'a plus) de r�f�rences : on le
// place � la racine de l'arbre
$arbre[""][] = $id;
$arbre[$id] = array();
unset($liste[$id]);
continue 2; /* while ($liste) */
}
// S'il n'y a pas de r�f�rences circulaires (a -> b -> a par
// exemple), $liste doit �tre vide. Sinon, on retire la derni�re
// r�f�rence du premier article, qui existe forc�ment puisque
// tous les articles non trait�s le sont � cause d'une r�f�rence
// non r�solue, et on repart pour un tour.
foreach ($liste as $id => &$refs) {
// Le fait d'utiliser foreach est une bidouille, en r�alit�
// on ne touche qu'au premier article avant de repartir au
// d�but.
array_pop($refs);
continue 2; /* while ($liste) */
}
}
return $arbre;
}