Recréer un arbre à partir d'une liste.

Le 03/04/13 16:42, Julien Arlandis a écrit :

Bonjour,

Je suis en train de coder un client de news entièrement en Javascript, celui se connecte à usenet via le protocole HTTP-NNTP que je suis en train de spécifier.
Le prototype en cours de réalisation est accessible à cette adresse :

http://http://news.julien-arlandis.fr/ (Accès en écriture seulement sur
les groupes fr.test et nemo.test)

Le format d'échange de données entre le client et le serveur est le json.

Pour pouvoir gérer l'arborescence des messages en fonction des champs References, j'ai besoin d'un algorithme capable de transformer une liste d'articles contenant les articles référents (ici clé "ref"):

liste=[
{"id":"a", "ref":["d"]},
{"id":"b", "ref":["d","c"]},
{"id":"c", "ref":["d"]},
{"id":"d", "ref":[]},
{"id":"e", "ref":["d","c","f"]},
{"id":"f", "ref":["d","c"]},
{"id":"g", "ref":["d","c","f"]},
{"id":"h", "ref":["d"]},
{"id":"i", "ref":["d","a"]},
{"id":"j", "ref":[]},
{"id":"k", "ref":["j"]},
{"id":"l", "ref":["j","k"]},
]

en un objet json qui reflète la structure de l'arborescence des fichiers :

arbre={
"d":{
"a":{
"i":{}
},
"c":{
"f":{
"e":{},
"g":{}
},
"b":{}
},
"h":{}
},
"i":{
"j":{
"k":{}
}
}
}

Avez vous une idée sur la façon de procéder en javascript?

Personne n'a une idée sur la façon de procéder avec une fonction récursive?

FU2 : fr.comp.lang.javascript

Le 06/04/13 12:21, Julien Arlandis a écrit :

Le 03/04/13 16:42, Julien Arlandis a écrit :

Bonjour,

Je suis en train de coder un client de news entièrement en Javascript, celui se connecte à usenet via le protocole HTTP-NNTP que je suis en train de spécifier.
Le prototype en cours de réalisation est accessible à cette adresse :

http://http://news.julien-arlandis.fr/ (Accès en écriture seulement sur
les groupes fr.test et nemo.test)

Correction :

http://news.julien-arlandis.fr/

Le format d'échange de données entre le client et le serveur est le json.

Pour pouvoir gérer l'arborescence des messages en fonction des champs References, j'ai besoin d'un algorithme capable de transformer une liste d'articles contenant les articles référents (ici clé "ref"):

liste=[
{"id":"a", "ref":["d"]},
{"id":"b", "ref":["d","c"]},
{"id":"c", "ref":["d"]},
{"id":"d", "ref":[]},
{"id":"e", "ref":["d","c","f"]},
{"id":"f", "ref":["d","c"]},
{"id":"g", "ref":["d","c","f"]},
{"id":"h", "ref":["d"]},
{"id":"i", "ref":["d","a"]},
{"id":"j", "ref":[]},
{"id":"k", "ref":["j"]},
{"id":"l", "ref":["j","k"]},
]

en un objet json qui reflète la structure de l'arborescence des fichiers :

arbre={
"d":{
"a":{
"i":{}
},
"c":{
"f":{
"e":{},
"g":{}
},
"b":{}
},
"h":{}
},
"i":{
"j":{
"k":{}
}
}
}

Avez vous une idée sur la façon de procéder en javascript?

Personne n'a une idée sur la façon de procéder avec une fonction récursive?

FU2 : fr.comp.lang.javascript

Bonjour,

Le 03/04/2013 16:42, Julien Arlandis a écrit :

Je suis en train de coder un client de news entièrement en Javascript, celui se connecte [...]

Tes lignes sont trop longues. :-(

Le format d'échange de données entre le client et le serveur est le json.

Pour pouvoir gérer l'arborescence des messages en fonction des champs References, j'ai besoin [...]

liste=[
{"id":"a", "ref":["d"]},
{"id":"b", "ref":["d","c"]},
{"id":"c", "ref":["d"]},
{"id":"d", "ref":[]},
{"id":"e", "ref":["d","c","f"]},
{"id":"f", "ref":["d","c"]},
{"id":"g", "ref":["d","c","f"]},
{"id":"h", "ref":["d"]},
{"id":"i", "ref":["d","a"]},
{"id":"j", "ref":[]},
{"id":"k", "ref":["j"]},
{"id":"l", "ref":["j","k"]},
]

Tu as choisi le cas hyper simple où toutes les listes de références sont
parfaites, sans trous ni boucles.

Le cas avec trous, tu le rencontreras certainement car c'est prévu dans
la norme. Par exemple, la ligne avec "id":"g" pourrait très bien avoir
"ref":["d","f"] au lieu de "ref":["d","c","f"].

Le cas avec boucles, tu ne devrais pas en rencontrer, mais il faut le
prévoir pour éviter qu'un petit malin n'en émette exprès pour faire
buguer ton programme.

en un objet json qui reflète la structure de l'arborescence des fichiers :

arbre={
"d":{
"a":{
"i":{}
},
"c":{
"f":{
"e":{},
"g":{}
},
"b":{}
},
"h":{}
},
"i":{
"j":{
"k":{}
}
}
}

Je suis en train de mettre au point un algorithme. La version zéro,
qui gère les trous mais pas les boucles, a donné ceci :

arbre={
"d":{
"a":{
"i":{}
},
"c":{
"b":{}
"f":{
"e":{},
"g":{}
},
},
"h":{}
},
"j":{
"k":{
"l":{}
}
}
}

Outre les "j", "k", "l" à la fin au lieu de "i", "j", "k", que je crois
être une simple coquille de ta part, la seule différence est qu'il met
"b" avant "f", dans l'ordre où ils se trouvaient dans 'liste' (que je
suppose être l'ordre chronologique puisque tu voulais que les articles
soient facilement triés par date).

Avez vous une idée sur la façon de procéder en javascript?

Je ne me lance pas dans du JavaScript, je vais tenter de décrire un
algorithme. J'espère que mes conventions seront assez claires. Ah, je
précise avant de commencer que je nomme refs ce que tu appelais ref
dans une ligne de 'liste', car c'est potentiellement un tableau de
plusieurs références. J'appelle ref un élément de refs.

arbre <- []
boucle_1: tant que liste n'est pas vide {
element <- premier élément de liste
boucle_2: tant que element.refs n'est pas vide {
ref <- dernier élément de element.refs
si ref est dans arbre {
ajouter element.id sous ref dans arbre
supprimer la ligne element de liste
revenir au début de boucle_1
}
si ref n'est pas dans liste {
supprimer le dernier élément de element.refs
revenir au début de boucle_2
}
s'il reste d'autres éléments dans liste {
element <- élément suivant de liste
revenir au début de boucle_2
}
SI ON ARRIVE ICI, IL Y A UNE BOUCLE !
À TRAITER.
}
ajouter element.id à la racine dans arbre
supprimer la ligne element de liste
revenir au début de boucle_1
}

J'ai une idée.

Le 07/04/2013 00:04, j'écrivais :

SI ON ARRIVE ICI, IL Y A UNE BOUCLE !
À TRAITER.

À cet endroit, faire :

element <- premier élément de liste
supprimer dernier élément de element.refs (qui n'est pas vide)
revenir au début de boucle_1 (ou de boucle_2, c'est pareil)

Cordialement,
--
Olivier Miakinen

Le 07/04/13 00:04, Olivier Miakinen a écrit :

Bonjour,

Le 03/04/2013 16:42, Julien Arlandis a écrit :

Je suis en train de coder un client de news entièrement en Javascript, celui se connecte [...]

Tes lignes sont trop longues. :-(

Le format d'échange de données entre le client et le serveur est le json.

Pour pouvoir gérer l'arborescence des messages en fonction des champs References, j'ai besoin [...]

liste=[
{"id":"a", "ref":["d"]},
{"id":"b", "ref":["d","c"]},
{"id":"c", "ref":["d"]},
{"id":"d", "ref":[]},
{"id":"e", "ref":["d","c","f"]},
{"id":"f", "ref":["d","c"]},
{"id":"g", "ref":["d","c","f"]},
{"id":"h", "ref":["d"]},
{"id":"i", "ref":["d","a"]},
{"id":"j", "ref":[]},
{"id":"k", "ref":["j"]},
{"id":"l", "ref":["j","k"]},
]

Tu as choisi le cas hyper simple où toutes les listes de références sont
parfaites, sans trous ni boucles.

Le cas avec trous, tu le rencontreras certainement car c'est prévu dans
la norme. Par exemple, la ligne avec "id":"g" pourrait très bien avoir
"ref":["d","f"] au lieu de "ref":["d","c","f"].

Le cas avec boucles, tu ne devrais pas en rencontrer, mais il faut le
prévoir pour éviter qu'un petit malin n'en émette exprès pour faire
buguer ton programme.

Oui j'y ai pensé, tu as une idée sur la façon de les détecter ?

en un objet json qui reflète la structure de l'arborescence des fichiers :

arbre={
"d":{
"a":{
"i":{}
},
"c":{
"f":{
"e":{},
"g":{}
},
"b":{}
},
"h":{}
},
"i":{
"j":{
"k":{}
}
}
}

Je suis en train de mettre au point un algorithme. La version zéro,
qui gère les trous mais pas les boucles, a donné ceci :

arbre={
"d":{
"a":{
"i":{}
},
"c":{
"b":{}
"f":{
"e":{},
"g":{}
},
},
"h":{}
},
"j":{
"k":{
"l":{}
}
}
}

Bien! Tu l'as écrit en quel langage?

Outre les "j", "k", "l" à la fin au lieu de "i", "j", "k", que je crois
être une simple coquille de ta part, la seule différence est qu'il met
"b" avant "f", dans l'ordre où ils se trouvaient dans 'liste' (que je
suppose être l'ordre chronologique puisque tu voulais que les articles
soient facilement triés par date).

Avez vous une idée sur la façon de procéder en javascript?

Je ne me lance pas dans du JavaScript, je vais tenter de décrire un
algorithme. J'espère que mes conventions seront assez claires. Ah, je
précise avant de commencer que je nomme refs ce que tu appelais ref
dans une ligne de 'liste', car c'est potentiellement un tableau de
plusieurs références. J'appelle ref un élément de refs.

arbre <- []
boucle_1: tant que liste n'est pas vide {
element <- premier élément de liste
boucle_2: tant que element.refs n'est pas vide {
ref <- dernier élément de element.refs
si ref est dans arbre {
ajouter element.id sous ref dans arbre
supprimer la ligne element de liste
revenir au début de boucle_1
}
si ref n'est pas dans liste {
supprimer le dernier élément de element.refs
revenir au début de boucle_2
}
s'il reste d'autres éléments dans liste {
element <- élément suivant de liste
revenir au début de boucle_2
}
SI ON ARRIVE ICI, IL Y A UNE BOUCLE !
À TRAITER.
}
ajouter element.id à la racine dans arbre
supprimer la ligne element de liste
revenir au début de boucle_1
}

Je l'analyserai demain à tête reposée, tu as calculé comment augmente le
temps de calcul quand on multiplie par k le nombre d'éléments de la liste?

Sinon j'ai pas mal avancé : http://news.julien-arlandis.fr/

Le 07/04/2013 01:00, Julien Arlandis a écrit :

Je suis en train de mettre au point un algorithme. La version zéro,
qui gère les trous mais pas les boucles, a donné ceci :

[...]

Je précide qu'il gère aussi les cas où un article de référence est
manquant. Quant aux boucles, cf. mon article de minuit dix, ça les
résoud en mettant le premier article (le plus ancien) avant l'autre.

Par exemple, avec :
{"id":"e", "ref":["d","c","f"]},
si l'article f manque, l'article e sera mis sous c ;
si l'article c manque aussi, il sera mis sous d ;
si l'article d manque aussi, il sera mis sous la racine.

Inconvénient : si l'article initial est absent, tous ceux qui en
dérivent directement sont mis sous la racine, contrairement à ce
que fait Thunderbird. Pour améliorer ça, il faudrait traiter à part
le cas de la première référence.

Bien! Tu l'as écrit en quel langage?

En langage naturel, avec vérification « à la mimine » sur un bout de
papier.

[...]

Je l'analyserai demain à tête reposée, tu as calculé comment augmente le
temps de calcul quand on multiplie par k le nombre d'éléments de la liste?

Si tous les articles sont présents, et dans l'ordre chronologique,
alors l'algo est en O(n) : les articles seront placés les uns
après les autres dans l'arbre, dans l'ordre où ils seront lus.

À chaque fois qu'un article aura comme dernière référence un
article qui n'existe pas, il faudra le temps de vérifier que, dans
les articles non encore traités il n'y en a aucun avec cet id.
Je suppose que ça doit être assez rapide en base de données ?

En revanche, les trous dans la liste de références ne gênent pas
puisque, sauf absence de la dernière référence, on ne tient pas
compte des autres.

Avec ton jeu de douze données non complètement triées, j'ai fait
dix-sept tours de boucles au lieu de douze, traitant les lignes
dans l'ordre suivant -- je mets l'id entre parenthèses à chaque
fois qu'il est examiné mais non transféré dans l'arbre :
(a) (b) (c) d a (b) c b (e) f e g h i j k l

Sinon j'ai pas mal avancé : http://news.julien-arlandis.fr/

Ok, je verrai ça plus tard.

[cancel+repost]

Le 07/04/2013 01:00, Julien Arlandis a écrit :

Je suis en train de mettre au point un algorithme. La version zéro,
qui gère les trous mais pas les boucles, a donné ceci :

[...]

Je précise qu'il gère aussi les cas où un article de référence est
manquant. Quant aux boucles, cf. mon article de minuit dix, ça les
résout en mettant le premier article (le plus ancien) avant l'autre.

Par exemple, avec :
{"id":"e", "ref":["d","c","f"]},
si l'article f manque, l'article e sera mis sous c ;
si l'article c manque aussi, il sera mis sous d ;
si l'article d manque aussi, il sera mis sous la racine.

Inconvénient : si l'article initial est absent, tous ceux qui en
dérivent _directement_ sont mis sous la racine, contrairement à ce
que fait Thunderbird. Pour améliorer ça, il faudrait traiter à part
le cas de la première référence.

Bien! Tu l'as écrit en quel langage?

En langage naturel, avec vérification « à la mimine » sur un bout de
papier.

[...]

Je l'analyserai demain à tête reposée, tu as calculé comment augmente le
temps de calcul quand on multiplie par k le nombre d'éléments de la liste?

Si tous les articles sont présents, et dans l'ordre chronologique,
alors l'algo est en O(n) : les articles seront placés les uns
après les autres dans l'arbre, dans l'ordre où ils seront lus.

À chaque fois qu'un article aura comme dernière référence un
article qui n'existe pas, il faudra le temps de vérifier que, dans
les articles non encore traités il n'y en a aucun avec cet id.
Je suppose que ça doit être assez rapide en base de données ?

En revanche, les trous dans la liste de références ne gênent pas
puisque, sauf absence de la dernière référence, on ne tient pas
compte des autres.

Avec ton jeu de douze données non complètement triées, j'ai fait
dix-sept tours de boucles au lieu de douze, traitant les lignes
dans l'ordre suivant -- je mets l'id entre parenthèses à chaque
fois qu'il est examiné mais non transféré dans l'arbre :
(a) (b) (c) d a (b) c b (e) f e g h i j k l

Sinon j'ai pas mal avancé : http://news.julien-arlandis.fr/

Ok, je verrai ça plus tard.

Le 07/04/2013 02:25, Olivier Miakinen a écrit :

Bien! Tu l'as écrit en quel langage?

En langage naturel, avec vérification « à la mimine » sur un bout de
papier.

Si tu me donnes les éléments de syntaxe de JavaScript permettant de
gérer les listes (obtenir le premier élément, le dernier, le suivant,
etc.) et les arbres (trouver un n½ud par son id, créer un n½ud en
dessous d'un autre, ou en dessous de la racine), alors je peux essayer
de récrire l'algo de façon à ce que ça ressemble plus à du JavaScript.

Olivier Miakinen <om+news@miakinen.net> a écrit :

Le 07/04/2013 02:25, Olivier Miakinen a écrit :

Bien! Tu l'as écrit en quel langage?

En langage naturel, avec vérification « à la mimine » sur un bout de
papier.

Si tu me donnes les éléments de syntaxe de JavaScript permettant de
gérer les listes (obtenir le premier élément, le dernier, le suivant,
etc.) et les arbres (trouver un nœud par son id, créer un nœud en
dessous d'un autre, ou en dessous de la racine), alors je peux essayer
de récrire l'algo de façon à ce que ça ressemble plus à du JavaScript.

json {"code":"200","body":
[
{"MessageID":"slrnklul68.eg5.kevin@slackwall.local.tux","References":["515e7e0a$0$1987$426a74cc@news.free.fr","515e878d$0$3738$426a74cc@news.free.fr","515eaa48$0$2291$426a34cc@news.free.fr","slrnkltvck.ed8.kevin@slackwall.local.tux","slrnkltmfi.lp5.tth@hangartistique.cispeo.fr"],"ID":"618"},

{"MessageID":"20130405212819.b4682ec7.ekimol@equidure.it","References":[],"ID":"567"},

{"MessageID":"slrnklu43u.esp.hugolino@Deborah.Rock-n-Roll.org","References":["515e7e0a$0$1987$426a74cc@news.free.fr","515e878d$0$3738$426a74cc@news.free.fr","slrnkltgl1.ed8.kevin@slackwall.local.tux"],"ID":"406"},

{"MessageID":"515ef745ebf6a@news.julien-arlandis.fr","References":[],"ID":"239"},

{"MessageID":"515ef6f271429@news.julien-arlandis.fr","References":["515e7e0a$0$1987$426a74cc@news.free.fr","515e878d$0$3738$426a74cc@news.free.fr","515eaa48$0$2291$426a34cc@news.free.fr","slrnkltvck.ed8.kevin@slackwall.local.tux","slrnkltmfi.lp5.tth@hangartistique.cispeo.fr"],"ID":"237"},

{"MessageID":"slrnkltmfi.lp5.tth@hangartistique.cispeo.fr","References":["515e7e0a$0$1987$426a74cc@news.free.fr","515e878d$0$3738$426a74cc@news.free.fr","515eaa48$0$2291$426a34cc@news.free.fr","slrnkltvck.ed8.kevin@slackwall.local.tux"],"ID":"42"},

{"MessageID":"slrnkltvck.ed8.kevin@slackwall.local.tux","References":["515e7e0a$0$1987$426a74cc@news.free.fr","515e878d$0$3738$426a74cc@news.free.fr","515eaa48$0$2291$426a34cc@news.free.fr"],"ID":"32"}
]
};


liste = json.body;
arbre = Array();
children = Array();

// On récupère les root
for(i in liste)
{
refs = liste[i].References;
parent = true;

for(j in liste)
{
if(i == j) continue;
for(k in refs)
{
if(refs[k] == liste[j].MessageID)
{
parent = false;
break;
}
}
}
if(parent)
{
arbre.push(i);
}
else
{
children.push(i);
}
}

En partant des données json de base, j'ai rapidement écrit un algo pour récupérer les orphelins (dans arbre) et les premiers enfants (dans children). Je sais pas si ça peut t'aider pour la syntaxe...

Bonne nuit.

--
Pour lire ce message avec Nemo : http://news.julien-arlandis.fr/?MessageIDQ60c0f46c0f9@news.julien-arlandis.fr

Le 07/04/2013 02:42, Julien Arlandis a écrit :

En partant des données json de base, j'ai rapidement écrit un algo pour [...]

Tes lignes sont toujours trop longues. Tant que tu n'as pas résolu le
problème du wordwrap, tu ne voudrais pas insérer des sauts de ligne
à la main ?


Ton exemple avec javascript et json ne me suffit pas pour savoir comment
écrire le programme, alors je le fais en PHP.

Expurgée de ses lignes de commentaires, la fonction qui construit
l'arborescence est étonnamment courte bien qu'elle traite tous les
cas, même pathologiques (boucles de références) :

=============================================================== function construis_arbo($liste)
{
$arbre = array("" => array());

while ($liste) {
foreach ($liste as $id => &$refs) {
while ($refs) {
$ref = end($refs);
if (isset($arbre[$ref])) {
$arbre[$ref][] = $id;
$arbre[$id] = array();
unset($liste[$id]);
continue 3; /* while ($liste) */
}
if (isset($liste[$ref])) {
continue 2; /* foreach ($liste) */
}
array_pop($refs);
}
$arbre[""][] = $id;
$arbre[$id] = array();
unset($liste[$id]);
}
foreach ($liste as $id => &$refs) {
array_pop($refs);
continue 2; /* while ($liste) */
}
}

return $arbre;
}
===============================================================
Je vais envoyer deux articles répondant à celui-ci, l'un contenant
le programme PHP complet (algo + tests) et l'autre le résultat des
tests.