Recréer un arbre à partir d'une liste

[Julien Arlandis]

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;
}

[Olivier Miakinen]

Post by Julien Arlandis
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?

Il est tard et je n'ai pas le temps de regarder en détail. Voici juste
un truc qui m'a sauté aux yeux, sauf que je ne suis pas expert en
JavaScript alors je ne sais pas comment corriger même si je suppose
que c'est incorrect.

Post by Julien Arlandis
[...]
for(i in liste)
{
refs = liste[i].refs;
[...]
refs.pop();

Je parierais bien que le refs.pop() agit sur une copie locale de
liste[i].refs au lieu de modifier le contenu de liste.

Post by Julien Arlandis
[...]
for(i in liste)
{
refs.pop();

Et là c'est encore pire : refs n'est même pas assigné.

Post by Julien Arlandis
[...]
foreach ($liste as $id => &$refs) {

Note le « & » : copie par référence et non par valeur.

Post by Julien Arlandis
[...]
array_pop($refs);

C'est donc array_pop($liste[$id]) et pas d'une copie.

Post by Julien Arlandis
[...]
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);

Idem.