Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Recréer un arbre à partir d'une liste.
5 views
Skip to first unread message
julienarlandis
Apr 3, 2013, 10:42:14 AM4/3/13
to
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?
Autre question, en json si la clé d'un objet possède des caractères spéciaux comme le -, comment peut aux éléments de la structure?
Exemple : si j'ai toto = {"message-id":"xxx"}
Je ne pourrais pas faire toto.message-id (confusion avec l'opérateur de soustraction).
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?
Autre question, en json si la clé d'un objet possède des caractères spéciaux comme le -, comment peut aux éléments de la structure?
Exemple : si j'ai toto = {"message-id":"xxx"}
Je ne pourrais pas faire toto.message-id (confusion avec l'opérateur de soustraction).
Julien Arlandis
Apr 6, 2013, 6:21:02 AM4/6/13
to
Le 03/04/13 16:42, Julien Arlandis a écrit :
Personne n'a une idée sur la façon de procéder avec une fonction récursive?
FU2 : fr.comp.lang.javascript
FU2 : fr.comp.lang.javascript
Julien Arlandis
Apr 6, 2013, 6:22:42 AM4/6/13
to
Le 06/04/13 12:21, Julien Arlandis a écrit :
http://news.julien-arlandis.fr/
> 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 :
>> 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)
http://news.julien-arlandis.fr/
Olivier Miakinen
Apr 6, 2013, 6:04:45 PM4/6/13
to
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 [...]
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":{}
"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
}
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.
>
>
> 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
> 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"]},
> ]
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":{}
> }
> }
> }
qui gère les trous mais pas les boucles, a donné ceci :
arbre={
"d":{
"a":{
"i":{}
},
"c":{
"f":{
"e":{},
"g":{}
},
},
"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?
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
}
Olivier Miakinen
Apr 6, 2013, 6:10:09 PM4/6/13
to
J'ai une idée.
Le 07/04/2013 00:04, j'écrivais :
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/2013 00:04, j'écrivais :
> SI ON ARRIVE ICI, IL Y A UNE BOUCLE !
> À TRAITER.
À cet endroit, faire :
> À TRAITER.
element <- premier élément de liste
revenir au début de boucle_1 (ou de boucle_2, c'est pareil)
Cordialement,
--
Olivier Miakinen
Julien Arlandis
Apr 6, 2013, 7:00:10 PM4/6/13
to
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 [...]
>>
>> Pour pouvoir g�rer l'arborescence des messages en fonction des champs References, j'ai besoin [...]
> la norme. Par exemple, la ligne avec "id":"g" pourrait tr�s bien avoir
> 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 :
> qui g�re les trous mais pas les boucles, a donn� ceci :
> 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
> 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
> }
> ajouter element.id � la racine dans arbre
> }
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/
> 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.
> Tes lignes sont trop longues. :-(
>
>>
>> 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
>> 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"]},
>> ]
>
> 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
>
> Le cas avec boucles, tu ne devrais pas en rencontrer, mais il faut le
> 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,
>> arbre={
>> "d":{
>> "a":{
>> "i":{}
>> },
>> "c":{
>> "f":{
>> "e":{},
>> "g":{}
>> },
>> "b":{}
>> },
>> "h":{}
>> },
>> "i":{
>> "j":{
>> "k":{}
>> }
>> }
>> }
>
> 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?
> 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
> arbre <- []
> boucle_1: tant que liste n'est pas vide {
> 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
> ajouter element.id sous ref dans arbre
> supprimer la ligne element de liste
> }
> si ref n'est pas dans liste {
> supprimer le dernier �l�ment de element.refs
> si ref n'est pas dans liste {
> 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.
> SI ON ARRIVE ICI, IL Y A UNE BOUCLE !
> }
> 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/
Olivier Miakinen
Apr 6, 2013, 8:22:11 PM4/6/13
to
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 :
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.
>>
>> 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.
Olivier Miakinen
Apr 6, 2013, 8:25:32 PM4/6/13
to
[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
Par exemple, avec :
Le 07/04/2013 01:00, Julien Arlandis a écrit :
>>
>> 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
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
Olivier Miakinen
Apr 6, 2013, 8:29:21 PM4/6/13
to
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
>
>> Bien! Tu l'as écrit en quel langage?
>
> En langage naturel, avec vérification « à la mimine » sur un bout de
> papier.
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.
Julien Arlandis
Apr 6, 2013, 8:42:28 PM4/6/13
to
Olivier Miakinen <om+...@miakinen.net> a écrit :
json =
{"code":"200","body":
[
{"MessageID":"slrnklul68...@slackwall.local.tux","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@news.free.fr","slrnkltvck...@slackwall.local.tux","slrnkltmf...@hangartistique.cispeo.fr"],"ID":"618"},
{"MessageID":"20130405212819....@equidure.it","References":[],"ID":"567"},
{"MessageID":"slrnklu43u....@Deborah.Rock-n-Roll.org","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","slrnkltgl1...@slackwall.local.tux"],"ID":"406"},
{"MessageID":"515ef7...@news.julien-arlandis.fr","References":[],"ID":"239"},
{"MessageID":"515ef6...@news.julien-arlandis.fr","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@news.free.fr","slrnkltvck...@slackwall.local.tux","slrnkltmf...@hangartistique.cispeo.fr"],"ID":"237"},
{"MessageID":"slrnkltmf...@hangartistique.cispeo.fr","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@news.free.fr","slrnkltvck...@slackwall.local.tux"],"ID":"42"},
{"MessageID":"slrnkltvck...@slackwall.local.tux","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@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/?MessageID=5160c0...@news.julien-arlandis.fr
{"code":"200","body":
[
{"MessageID":"slrnklul68...@slackwall.local.tux","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@news.free.fr","slrnkltvck...@slackwall.local.tux","slrnkltmf...@hangartistique.cispeo.fr"],"ID":"618"},
{"MessageID":"20130405212819....@equidure.it","References":[],"ID":"567"},
{"MessageID":"slrnklu43u....@Deborah.Rock-n-Roll.org","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","slrnkltgl1...@slackwall.local.tux"],"ID":"406"},
{"MessageID":"515ef7...@news.julien-arlandis.fr","References":[],"ID":"239"},
{"MessageID":"515ef6...@news.julien-arlandis.fr","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@news.free.fr","slrnkltvck...@slackwall.local.tux","slrnkltmf...@hangartistique.cispeo.fr"],"ID":"237"},
{"MessageID":"slrnkltmf...@hangartistique.cispeo.fr","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@news.free.fr","slrnkltvck...@slackwall.local.tux"],"ID":"42"},
{"MessageID":"slrnkltvck...@slackwall.local.tux","References":["515e7e0a$0$1987$426a...@news.free.fr","515e878d$0$3738$426a...@news.free.fr","515eaa48$0$2291$426a...@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/?MessageID=5160c0...@news.julien-arlandis.fr
Olivier Miakinen
Apr 7, 2013, 10:39:37 AM4/7/13
to
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.
>
> 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.
Olivier Miakinen
Apr 7, 2013, 10:44:51 AM4/7/13
to
Le 07/04/2013 16:39, Olivier Miakinen a �crit :
function construis_arbo($liste)
{
$arbre = array("" => 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
// article plac�
// voir un autre article, celui-ci sera trait�
// plus tard.
// de la liste des r�f�rences
array_pop($refs);
}
// Cet article n'a pas (ou n'a plus) de r�f�rences : on le
// place � la racine de l'arbre
// 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.
// on ne touche qu'au premier article avant de repartir au
// d�but.
{
foreach ($liste as $id => $refs) {
printf("$id => [%s]\n", implode(",", $refs));
}
}
function affiche_arbo($arbre, $refid, $indent)
{
foreach ($arbre[$refid] as $id) {
printf("%s%s\n", $indent, $id);
affiche_arbo($arbre, $id, $indent . " ");
}
}
$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")
);
echo "==========================\n";
echo "liste normale\n";
affiche_liste($liste);
$arbre = construis_arbo($liste);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste tronqu�e\n";
$lis = $liste; /* liste tronqu�e */
unset($lis["k"]);
unset($lis["d"]);
affiche_liste($lis);
$arbre = construis_arbo($lis);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste m�lang�e\n";
$lesti = array(); /* liste m�lang�e */
$keys = array_keys($liste);
shuffle($keys);
foreach ($keys as $key) {
$lesti[$key] = $liste[$key];
}
affiche_liste($lesti);
$arbre = construis_arbo($lesti);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste invers�e\n";
$etsil = array_reverse($liste); /* liste invers�e */
affiche_liste($etsil);
$arbre = construis_arbo($etsil);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste avec boucle\n";
$lislislis = $liste;
$lislislis["xyz"] = array("yzx", "zxy");
$lislislis["yzx"] = array("zxy", "xyz");
$lislislis["zxy"] = array("xyz", "yzx");
affiche_liste($lislislis);
$arbre = construis_arbo($lislislis);
affiche_arbo($arbre, "", "");
echo "==========================\n";
?>
>
> 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.
<?php
> 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.
function construis_arbo($liste)
{
$arbre = array("" => array());
while ($liste) {
foreach ($liste as $id => &$refs) {
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 :
if (isset($arbre[$ref])) {
// article plac�
$arbre[$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 :
$arbre[$id] = array();
unset($liste[$id]);
continue 3; /* while ($liste) */
}
if (isset($liste[$ref])) {
// 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);
}
// 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]);
}
// S'il n'y a pas de r�f�rences circulaires (a -> b -> a par
$arbre[$id] = array();
unset($liste[$id]);
}
// 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;
}
function affiche_liste($liste)
continue 2; /* while ($liste) */
}
}
return $arbre;
}
{
foreach ($liste as $id => $refs) {
printf("$id => [%s]\n", implode(",", $refs));
}
}
function affiche_arbo($arbre, $refid, $indent)
{
foreach ($arbre[$refid] as $id) {
printf("%s%s\n", $indent, $id);
affiche_arbo($arbre, $id, $indent . " ");
}
}
$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")
);
echo "==========================\n";
echo "liste normale\n";
affiche_liste($liste);
$arbre = construis_arbo($liste);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste tronqu�e\n";
$lis = $liste; /* liste tronqu�e */
unset($lis["k"]);
unset($lis["d"]);
affiche_liste($lis);
$arbre = construis_arbo($lis);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste m�lang�e\n";
$lesti = array(); /* liste m�lang�e */
$keys = array_keys($liste);
shuffle($keys);
foreach ($keys as $key) {
$lesti[$key] = $liste[$key];
}
affiche_liste($lesti);
$arbre = construis_arbo($lesti);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste invers�e\n";
$etsil = array_reverse($liste); /* liste invers�e */
affiche_liste($etsil);
$arbre = construis_arbo($etsil);
affiche_arbo($arbre, "", "");
echo "==========================\n";
echo "liste avec boucle\n";
$lislislis = $liste;
$lislislis["xyz"] = array("yzx", "zxy");
$lislislis["yzx"] = array("zxy", "xyz");
$lislislis["zxy"] = array("xyz", "yzx");
affiche_liste($lislislis);
$arbre = construis_arbo($lislislis);
affiche_arbo($arbre, "", "");
echo "==========================\n";
?>
Olivier Miakinen
Apr 7, 2013, 10:46:30 AM4/7/13
to
Le 07/04/2013 16:39, Olivier Miakinen a écrit :
>
> 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.
==========================
liste normale
a => [d]
b => [d,c]
c => [d]
d => []
e => [d,c,f]
f => [d,c]
g => [d,c,f]
h => [d]
i => [d,a]
j => []
k => [j]
l => [j,k]
d
h
a
i
c
b
f
e
g
j
k
l
==========================
liste tronquée
a => [d]
b => [d,c]
c => [d]
e => [d,c,f]
f => [d,c]
g => [d,c,f]
h => [d]
i => [d,a]
j => []
l => [j,k]
a
i
c
f
e
g
b
h
j
l
==========================
liste mélangée
b => [d,c]
j => []
g => [d,c,f]
a => [d]
f => [d,c]
h => [d]
c => [d]
d => []
e => [d,c,f]
i => [d,a]
k => [j]
l => [j,k]
j
k
l
d
a
i
h
c
b
f
g
e
==========================
liste inversée
l => [j,k]
k => [j]
j => []
i => [d,a]
h => [d]
g => [d,c,f]
f => [d,c]
e => [d,c,f]
d => []
c => [d]
b => [d,c]
a => [d]
j
k
l
d
c
f
g
e
b
h
a
i
==========================
liste avec boucle
a => [d]
b => [d,c]
c => [d]
d => []
e => [d,c,f]
f => [d,c]
g => [d,c,f]
h => [d]
i => [d,a]
j => []
k => [j]
l => [j,k]
xyz => [yzx,zxy]
yzx => [zxy,xyz]
zxy => [xyz,yzx]
d
h
a
i
c
b
f
e
g
j
k
l
xyz
yzx
zxy
==========================
>
> 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.
==========================
liste normale
a => [d]
b => [d,c]
c => [d]
d => []
e => [d,c,f]
f => [d,c]
g => [d,c,f]
h => [d]
i => [d,a]
j => []
k => [j]
l => [j,k]
d
h
a
i
c
b
f
e
g
j
k
l
==========================
liste tronquée
a => [d]
b => [d,c]
c => [d]
e => [d,c,f]
f => [d,c]
g => [d,c,f]
h => [d]
i => [d,a]
j => []
l => [j,k]
a
i
c
f
e
g
b
h
j
l
==========================
liste mélangée
b => [d,c]
j => []
g => [d,c,f]
a => [d]
f => [d,c]
h => [d]
c => [d]
d => []
e => [d,c,f]
i => [d,a]
k => [j]
l => [j,k]
j
k
l
d
a
i
h
c
b
f
g
e
==========================
liste inversée
l => [j,k]
k => [j]
j => []
i => [d,a]
h => [d]
g => [d,c,f]
f => [d,c]
e => [d,c,f]
d => []
c => [d]
b => [d,c]
a => [d]
j
k
l
d
c
f
g
e
b
h
a
i
==========================
liste avec boucle
a => [d]
b => [d,c]
c => [d]
d => []
e => [d,c,f]
f => [d,c]
g => [d,c,f]
h => [d]
i => [d,a]
j => []
k => [j]
l => [j,k]
xyz => [yzx,zxy]
yzx => [zxy,xyz]
zxy => [xyz,yzx]
d
h
a
i
c
b
f
e
g
j
k
l
xyz
yzx
zxy
==========================
Julien Arlandis
Apr 7, 2013, 11:49:41 AM4/7/13
to
Le 07/04/13 16:39, Olivier Miakinen a écrit :
> 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 [...]
Merci pour ce travail remarquable.
> 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 ?
J'ai retiré le wordwrap car ça créait plus de problèmes qu'autre chose,
d'autant plus que sur thunderbird le retour à la ligne est automatique à
la lecture, sauf pour les citations mais dans ce cas les retours
chariots peuvent être replacés manuellement.
Mon problème, c'est qu'à chaque foi que l'article est cité de nouveaux
retours chariots sont créés et à la fin l'article devient illisible.
Pour résoudre ce problème je suppose qu'il ne faudrait jamais appliquer
le wordwrap sur les lignes qui commencent par un chevron?
Un autre problème lié à la citation, c'est que ça coupe le contenu des
balises contenant du code à interpréter (BBcode, latex ou autre).
Donc si les lignes trop longues reviennent à la ligne automatiquement à
la lecture et si la personne qui répond peut elle rajouter les retours
lignes là où ça l'arrange, quel est le problème ? De plus, en HTML la
longueur de la ligne est automatique car elle dépend de la taille de la
fenêtre du navigateur qui dépend de la taille de l'écran. Bref pas
facile de faire un compromis.
> 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) :
> 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.
>
> 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 [...]
Merci pour ce travail remarquable.
> 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 ?
J'ai retiré le wordwrap car ça créait plus de problèmes qu'autre chose,
d'autant plus que sur thunderbird le retour à la ligne est automatique à
la lecture, sauf pour les citations mais dans ce cas les retours
chariots peuvent être replacés manuellement.
Mon problème, c'est qu'à chaque foi que l'article est cité de nouveaux
retours chariots sont créés et à la fin l'article devient illisible.
Pour résoudre ce problème je suppose qu'il ne faudrait jamais appliquer
le wordwrap sur les lignes qui commencent par un chevron?
Un autre problème lié à la citation, c'est que ça coupe le contenu des
balises contenant du code à interpréter (BBcode, latex ou autre).
Donc si les lignes trop longues reviennent à la ligne automatiquement à
la lecture et si la personne qui répond peut elle rajouter les retours
lignes là où ça l'arrange, quel est le problème ? De plus, en HTML la
longueur de la ligne est automatique car elle dépend de la taille de la
fenêtre du navigateur qui dépend de la taille de l'écran. Bref pas
facile de faire un compromis.
> Ton exemple avec javascript et json ne me suffit pas pour savoir comment
>
> 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;
> }
> ================================================================
Joli, je vais de ce pas coder ça en Javascript, je te tiens au courant.
> ================================================================
> 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.
>
Olivier Miakinen
Apr 8, 2013, 6:19:14 AM4/8/13
to
Le 07/04/2013 17:49, Julien Arlandis a écrit :
>
>> 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 ?
>
> J'ai retiré le wordwrap car ça créait plus de problèmes qu'autre chose,
Ça ne pourra fonctionner correctement que quand tu l'implémenteras
>
>> 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 ?
>
> J'ai retiré le wordwrap car ça créait plus de problèmes qu'autre chose,
dans l'éditeur et non pas après coup. Au fait, est-ce seulement
possible ? Qu'est-ce que tu utilises pour la rédaction du contenu
des articles ?
> d'autant plus que sur thunderbird le retour à la ligne est automatique à
> la lecture, sauf pour les citations mais dans ce cas les retours
> chariots peuvent être replacés manuellement.
j'ai plonké pendant plusieurs mois un contributeur pourtant intéressant
sur fciwa et quelques autres groupes pour cette seule raison. À chaque
fois que je tentais de lui répondre je me retrouvais avec des lignes de
3 km à redécouper, et je n'avais vraiment pas envie de perdre mon temps
à ça.
> Mon problème, c'est qu'à chaque fois que l'article est cité de nouveaux
> retours chariots sont créés et à la fin l'article devient illisible.
Comme je le disais, il ne faut pas reproduire ce bug d'Outlook Express !
> Pour résoudre ce problème je suppose qu'il ne faudrait jamais appliquer
> le wordwrap sur les lignes qui commencent par un chevron?
> Un autre problème lié à la citation, c'est que ça coupe le contenu des
> balises contenant du code à interpréter (BBcode, latex ou autre).
quitte à envoyer autre chose que du text/plain, pourquoi ne pas passer
à HTML ? Ce ne serait pas plus approprié ? Certes, ça ne passera pas
sur la hiérarchie fr.*, mais le BBcode et le latex non plus ne sont pas
les bienvenus, et je suppose donc que tu créeras une autre hiérarchie
où ils sont autorisés, non ?... (Rassure-moi !)
> Donc si les lignes trop longues reviennent à la ligne automatiquement à
> la lecture et si la personne qui répond peut elle rajouter les retours
> lignes là où ça l'arrange, quel est le problème ?
reformater l'article qu'il reçoit avant d'y répondre. C'est très
pénible.
Pour l'émetteur soucieux de bonne typographie : il insèrera de toute
façon des sauts de ligne, ne serait-ce que pour que la coupure ne
se fasse pas avant un « : » ou au milieu de « 20 h 30 ». S'il les
insère un tout petit peu trop loin par rapport à l'affichage de ceux
qui vont le lire, par exemple au bout de 90 caractères au lieu de
80, cela reproduira à l'affichage le bug d'Outlook Express : une
alternance de lignes longues et de lignes courtes.
> De plus, en HTML la
> longueur de la ligne est automatique car elle dépend de la taille de la
> fenêtre du navigateur qui dépend de la taille de l'écran. Bref pas
> facile de faire un compromis.
de le proposer. Je parle des lecteurs, bien sûr. Pour le rédacteur, il
faut que la coupure se fasse à la bonne longueur au moment où il rédige.
Et donc je repose ma question : est-ce possible et vois-tu comment le
faire ?
>> Ton exemple avec javascript et json ne me suffit pas pour savoir comment
>> écrire le programme, alors je le fais en PHP.
>>
J'ai trouvé comment traiter le cas où c'est le premier article qui
manque. Je n'ai pas encore testé, mais il suffit de rajouter une
dizaine de lignes dans mon code, sans rien changer d'autre. Dès
que j'ai le temps, je les écris ici (à moins que tu ne préfères
attendre que j'aie testé d'abord, et alors ce ne sera pas avant
cette nuit).
Cordialement,
--
Olivier Miakinen
Julien Arlandis
Apr 8, 2013, 12:56:58 PM4/8/13
to
Le 08/04/13 12:19, Olivier Miakinen a écrit :
non plus, y a t-il seulement un webmail qui le propose? Comment le
problème est il contourné dans ce cas ?
>> d'autant plus que sur thunderbird le retour à la ligne est automatique à
>> la lecture, sauf pour les citations mais dans ce cas les retours
>> chariots peuvent être replacés manuellement.
>
> Certes, mais c'est vachement pénible. Moi qui ne plonke que rarement,
> j'ai plonké pendant plusieurs mois un contributeur pourtant intéressant
> sur fciwa et quelques autres groupes pour cette seule raison. À chaque
> fois que je tentais de lui répondre je me retrouvais avec des lignes de
> 3 km à redécouper, et je n'avais vraiment pas envie de perdre mon temps
> à ça.
En fait je ne comprends toujours pas l'intérêt de couper une phrase en
insérant un retour chariot en plein milieu alors même que l'affichage
est parfaitement géré par le client sans cet artifice. Encore que si les
retours chariots automatiques étaient différents des retours chariots
manuels je pourrais décider de les ignorer côté HTML, mais dans l'état
actuel je suis obligé pour formater mon texte de remplacer tous les \n
par des <br>.
Pour faciliter le travail de celui qui va répondre on dénature la
syntaxe même de la phrase, laquelle n'exige un retour à la ligne qu'à la
fin de celle ci, et pas là où on devine que le lecteur l'attend.
Pourtant il existe une solution, regarde ce message :
http://news.julien-arlandis.fr/?MessageID=5162ed...@news.julien-arlandis.fr
Le message est à la fois lisible et tu peux y répondre sans soucis car
par défaut le texte d'un textarea ne déborde pas mais ne rajoute pas de
retours chariots pour autant. Le problème ne se pose donc pas. Pourquoi
ne pas avoir implémenté ce mécanisme dans les lecteurs de news tout
simplement ?
>> Mon problème, c'est qu'à chaque fois que l'article est cité de nouveaux
>> retours chariots sont créés et à la fin l'article devient illisible.
>
> Comme je le disais, il ne faut pas reproduire ce bug d'Outlook Express !
>
>> Pour résoudre ce problème je suppose qu'il ne faudrait jamais appliquer
>> le wordwrap sur les lignes qui commencent par un chevron?
>
> Tout simplement, oui.
>
>> Un autre problème lié à la citation, c'est que ça coupe le contenu des
>> balises contenant du code à interpréter (BBcode, latex ou autre).
>
> Ah oui, j'ai vu sur fr.test que tu faisais des tests avec latex. Mais
> quitte à envoyer autre chose que du text/plain, pourquoi ne pas passer
> à HTML ? Ce ne serait pas plus approprié ? Certes, ça ne passera pas
> sur la hiérarchie fr.*, mais le BBcode et le latex non plus ne sont pas
> les bienvenus, et je suppose donc que tu créeras une autre hiérarchie
> où ils sont autorisés, non ?... (Rassure-moi !)
Y aura une autre hiérarchie 100% compatible JNTP, ce n'est pas tout car
toutes les évolutions du protocole ne seront pas compatibles avec NNTP,
pour assurer l'intéropérabilité des deux protocoles elles ne seront pas
activées pour l'usage des hiérarchies communes. Néanmoins, je compte
développer une nouvelle hiérarchie Nemo qui appliquera le protocole JNTP
à 100%, elle ne pourra donc pas être relayée sur NNTP pour des raisons
de sécurité, car j'ai prévu que le nouvel identifiant (le JID) soit un
hash de l'ensemle des entêtes obligatoires et non modifiables de
l'article. Tout article dont le hash n'est pas valide sera
automatiquement éjecté et par le client et par le serveur. J'ai
également prévu un champ pour signer numériquement l'article, l'idée est
simple : chaque utilisateur génère une phrase secrète qu'il stocke dans
son client. Lors de la rédaction d'un article, il réalise avant
d'expédier l'article les opérations suivantes :
MyHash = SHA1(From + Subject + Body + Newsgroups + SHA1(From + Subject
+ Body + Newsgroups + phrase_secrete))
Dans l'article il rajoute l'entête :
Signature: MyHash
Pour prouver son identité lors de la suppression ou de la modification
de son message, l'auteur devra fournir la clé
SHA1(From + Subject + Body + Newsgroups + phrase_secrete)
Si le hash de cette clé concaténée au message est identique à MyHash
c'est qu'il est l'auteur de l'article.
Chose nouvelle également, le JID sera de cette forme
SHA1(enêtes+body)@domaine_du_serveur_de_news_emetteur
Les serveurs devront avoir un certificat numérique valable et devront
signer tous les articles émis par leurs abonnés. Toutes ces règles ne
seront pas optionnelles, elles devront être appliquées.
>> Donc si les lignes trop longues reviennent à la ligne automatiquement à
>> la lecture et si la personne qui répond peut elle rajouter les retours
>> lignes là où ça l'arrange, quel est le problème ?
>
> Pour le destinataire : ce n'est pas à lui de passer du temps à
> reformater l'article qu'il reçoit avant d'y répondre. C'est très
> pénible.
>
> Pour l'émetteur soucieux de bonne typographie : il insèrera de toute
> façon des sauts de ligne, ne serait-ce que pour que la coupure ne
> se fasse pas avant un « : » ou au milieu de « 20 h 30 ». S'il les
> insère un tout petit peu trop loin par rapport à l'affichage de ceux
> qui vont le lire, par exemple au bout de 90 caractères au lieu de
> 80, cela reproduira à l'affichage le bug d'Outlook Express : une
> alternance de lignes longues et de lignes courtes.
Su un navigateur, la typographie se gère à l'affichage et pas à la
rédaction, c'est ce qui assure la compatibilité de lecture sur
différents médias.
>> De plus, en HTML la
>> longueur de la ligne est automatique car elle dépend de la taille de la
>> fenêtre du navigateur qui dépend de la taille de l'écran. Bref pas
>> facile de faire un compromis.
>
> Ça, ce sera le rôle de l'infâme format flowed le jour où tu décideras
> de le proposer. Je parle des lecteurs, bien sûr. Pour le rédacteur, il
> faut que la coupure se fasse à la bonne longueur au moment où il rédige.
> Et donc je repose ma question : est-ce possible et vois-tu comment le
> faire ?
Je ne comprends toujours pas ce qu'est ce format=flowed, que fait il
exactement, à quoi sert il, à qui est il destiné?
>>> Ton exemple avec javascript et json ne me suffit pas pour savoir comment
>>> écrire le programme, alors je le fais en PHP.
>>>
>>> [...]
>
> J'ai trouvé comment traiter le cas où c'est le premier article qui
> manque. Je n'ai pas encore testé, mais il suffit de rajouter une
> dizaine de lignes dans mon code, sans rien changer d'autre. Dès
> que j'ai le temps, je les écris ici (à moins que tu ne préfères
> attendre que j'aie testé d'abord, et alors ce ne sera pas avant
> cette nuit).
Pas de soucis, je n'ai pas encore eu le temps d'implémenter ton algo en
javascript, mais les choses avancent ...
Crosspost sur fr.comp.securite et retour sur fr.comp.lang.javascript
> Le 07/04/2013 17:49, Julien Arlandis a écrit :
>>
>>> 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 ?
>>
>> J'ai retiré le wordwrap car ça créait plus de problèmes qu'autre chose,
>
> Ça ne pourra fonctionner correctement que quand tu l'implémenteras
> dans l'éditeur et non pas après coup. Au fait, est-ce seulement
> possible ? Qu'est-ce que tu utilises pour la rédaction du contenu
> des articles ?
Un simple textarea, j'ai vérifié que google groups ne l'implémente pas
>>
>>> 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 ?
>>
>> J'ai retiré le wordwrap car ça créait plus de problèmes qu'autre chose,
>
> Ça ne pourra fonctionner correctement que quand tu l'implémenteras
> dans l'éditeur et non pas après coup. Au fait, est-ce seulement
> possible ? Qu'est-ce que tu utilises pour la rédaction du contenu
> des articles ?
non plus, y a t-il seulement un webmail qui le propose? Comment le
problème est il contourné dans ce cas ?
>> d'autant plus que sur thunderbird le retour à la ligne est automatique à
>> la lecture, sauf pour les citations mais dans ce cas les retours
>> chariots peuvent être replacés manuellement.
>
> Certes, mais c'est vachement pénible. Moi qui ne plonke que rarement,
> j'ai plonké pendant plusieurs mois un contributeur pourtant intéressant
> sur fciwa et quelques autres groupes pour cette seule raison. À chaque
> fois que je tentais de lui répondre je me retrouvais avec des lignes de
> 3 km à redécouper, et je n'avais vraiment pas envie de perdre mon temps
> à ça.
insérant un retour chariot en plein milieu alors même que l'affichage
est parfaitement géré par le client sans cet artifice. Encore que si les
retours chariots automatiques étaient différents des retours chariots
manuels je pourrais décider de les ignorer côté HTML, mais dans l'état
actuel je suis obligé pour formater mon texte de remplacer tous les \n
par des <br>.
Pour faciliter le travail de celui qui va répondre on dénature la
syntaxe même de la phrase, laquelle n'exige un retour à la ligne qu'à la
fin de celle ci, et pas là où on devine que le lecteur l'attend.
Pourtant il existe une solution, regarde ce message :
http://news.julien-arlandis.fr/?MessageID=5162ed...@news.julien-arlandis.fr
Le message est à la fois lisible et tu peux y répondre sans soucis car
par défaut le texte d'un textarea ne déborde pas mais ne rajoute pas de
retours chariots pour autant. Le problème ne se pose donc pas. Pourquoi
ne pas avoir implémenté ce mécanisme dans les lecteurs de news tout
simplement ?
>> Mon problème, c'est qu'à chaque fois que l'article est cité de nouveaux
>> retours chariots sont créés et à la fin l'article devient illisible.
>
> Comme je le disais, il ne faut pas reproduire ce bug d'Outlook Express !
>
>> Pour résoudre ce problème je suppose qu'il ne faudrait jamais appliquer
>> le wordwrap sur les lignes qui commencent par un chevron?
>
> Tout simplement, oui.
>
>> Un autre problème lié à la citation, c'est que ça coupe le contenu des
>> balises contenant du code à interpréter (BBcode, latex ou autre).
>
> Ah oui, j'ai vu sur fr.test que tu faisais des tests avec latex. Mais
> quitte à envoyer autre chose que du text/plain, pourquoi ne pas passer
> à HTML ? Ce ne serait pas plus approprié ? Certes, ça ne passera pas
> sur la hiérarchie fr.*, mais le BBcode et le latex non plus ne sont pas
> les bienvenus, et je suppose donc que tu créeras une autre hiérarchie
> où ils sont autorisés, non ?... (Rassure-moi !)
toutes les évolutions du protocole ne seront pas compatibles avec NNTP,
pour assurer l'intéropérabilité des deux protocoles elles ne seront pas
activées pour l'usage des hiérarchies communes. Néanmoins, je compte
développer une nouvelle hiérarchie Nemo qui appliquera le protocole JNTP
à 100%, elle ne pourra donc pas être relayée sur NNTP pour des raisons
de sécurité, car j'ai prévu que le nouvel identifiant (le JID) soit un
hash de l'ensemle des entêtes obligatoires et non modifiables de
l'article. Tout article dont le hash n'est pas valide sera
automatiquement éjecté et par le client et par le serveur. J'ai
également prévu un champ pour signer numériquement l'article, l'idée est
simple : chaque utilisateur génère une phrase secrète qu'il stocke dans
son client. Lors de la rédaction d'un article, il réalise avant
d'expédier l'article les opérations suivantes :
MyHash = SHA1(From + Subject + Body + Newsgroups + SHA1(From + Subject
+ Body + Newsgroups + phrase_secrete))
Dans l'article il rajoute l'entête :
Signature: MyHash
Pour prouver son identité lors de la suppression ou de la modification
de son message, l'auteur devra fournir la clé
SHA1(From + Subject + Body + Newsgroups + phrase_secrete)
Si le hash de cette clé concaténée au message est identique à MyHash
c'est qu'il est l'auteur de l'article.
Chose nouvelle également, le JID sera de cette forme
SHA1(enêtes+body)@domaine_du_serveur_de_news_emetteur
Les serveurs devront avoir un certificat numérique valable et devront
signer tous les articles émis par leurs abonnés. Toutes ces règles ne
seront pas optionnelles, elles devront être appliquées.
>> Donc si les lignes trop longues reviennent à la ligne automatiquement à
>> la lecture et si la personne qui répond peut elle rajouter les retours
>> lignes là où ça l'arrange, quel est le problème ?
>
> Pour le destinataire : ce n'est pas à lui de passer du temps à
> reformater l'article qu'il reçoit avant d'y répondre. C'est très
> pénible.
>
> Pour l'émetteur soucieux de bonne typographie : il insèrera de toute
> façon des sauts de ligne, ne serait-ce que pour que la coupure ne
> se fasse pas avant un « : » ou au milieu de « 20 h 30 ». S'il les
> insère un tout petit peu trop loin par rapport à l'affichage de ceux
> qui vont le lire, par exemple au bout de 90 caractères au lieu de
> 80, cela reproduira à l'affichage le bug d'Outlook Express : une
> alternance de lignes longues et de lignes courtes.
rédaction, c'est ce qui assure la compatibilité de lecture sur
différents médias.
>> De plus, en HTML la
>> longueur de la ligne est automatique car elle dépend de la taille de la
>> fenêtre du navigateur qui dépend de la taille de l'écran. Bref pas
>> facile de faire un compromis.
>
> Ça, ce sera le rôle de l'infâme format flowed le jour où tu décideras
> de le proposer. Je parle des lecteurs, bien sûr. Pour le rédacteur, il
> faut que la coupure se fasse à la bonne longueur au moment où il rédige.
> Et donc je repose ma question : est-ce possible et vois-tu comment le
> faire ?
exactement, à quoi sert il, à qui est il destiné?
>>> Ton exemple avec javascript et json ne me suffit pas pour savoir comment
>>> écrire le programme, alors je le fais en PHP.
>>>
>>> [...]
>
> J'ai trouvé comment traiter le cas où c'est le premier article qui
> manque. Je n'ai pas encore testé, mais il suffit de rajouter une
> dizaine de lignes dans mon code, sans rien changer d'autre. Dès
> que j'ai le temps, je les écris ici (à moins que tu ne préfères
> attendre que j'aie testé d'abord, et alors ce ne sera pas avant
> cette nuit).
javascript, mais les choses avancent ...
Crosspost sur fr.comp.securite et retour sur fr.comp.lang.javascript
Julien Arlandis
Apr 8, 2013, 1:21:48 PM4/8/13
to
Le 08/04/13 12:19, Olivier Miakinen a écrit :
> Ah oui, j'ai vu sur fr.test que tu faisais des tests avec latex. Mais
> quitte à envoyer autre chose que du text/plain, pourquoi ne pas passer
> à HTML ?
On ne peut pas permettre à un utilisateur d'injecter du HTML, c'est la
> quitte à envoyer autre chose que du text/plain, pourquoi ne pas passer
> à HTML ?
porte ouverte aux failles XSS. Il faut nécessairement passer par un
langage de balisage léger dont on contrôle la transition vers HTML.
> Ça, ce sera le rôle de l'infâme format flowed le jour où tu décideras
> de le proposer. Je parle des lecteurs, bien sûr. Pour le rédacteur, il
> faut que la coupure se fasse à la bonne longueur au moment où il rédige.
> Et donc je repose ma question : est-ce possible et vois-tu comment le
> faire ?
que le wordwrap n'est pas adapté au HTML. Le problème ne se pose pas
entre navigateurs mais entre navigateur et client de news. M'est avis
que la solution doit aussi s'adapter...
Julien Arlandis
Apr 8, 2013, 1:22:16 PM4/8/13
to
Le 08/04/13 19:21, Julien Arlandis a écrit :
Que le client de news doit aussi s'adapter, pardon.
SAM
Apr 8, 2013, 1:29:53 PM4/8/13
to
Le 08/04/13 18:56, Julien Arlandis a écrit :
> Le message est à la fois lisible
Ha! Non! J'y comprends rien à ce message !
C'est en quelle langue ?
Je sais pas trop à quoi sert ce Nemo ?
Et qui donne des messages le lendemain de leur envoi (et en anglishe,
les dates des NG fr)
Cordialement,
--
Stéphane Moriaux avec/with iMac-intel 27" & Mac OS X 10.6.8
> Pourtant il existe une solution, regarde ce message :
> http://news.julien-arlandis.fr/?MessageID=5162ed...@news.julien-arlandis.fr
Joli.
> http://news.julien-arlandis.fr/?MessageID=5162ed...@news.julien-arlandis.fr
> Le message est à la fois lisible
C'est en quelle langue ?
Je sais pas trop à quoi sert ce Nemo ?
Et qui donne des messages le lendemain de leur envoi (et en anglishe,
les dates des NG fr)
Cordialement,
--
Stéphane Moriaux avec/with iMac-intel 27" & Mac OS X 10.6.8
Olivier Miakinen
Apr 8, 2013, 8:01:35 PM4/8/13
to
Salut !
On est de plus en plus HS sur fclj. À défaut d'une meilleure idée, je
fais suivre vers fr.comp.usenet.serveurs
Le 08/04/2013 18:56, Julien Arlandis a écrit :
>>
>> Ça ne pourra fonctionner correctement que quand tu l'implémenteras
>> dans l'éditeur et non pas après coup. Au fait, est-ce seulement
>> possible ? Qu'est-ce que tu utilises pour la rédaction du contenu
>> des articles ?
>
> Un simple textarea, j'ai vérifié que google groups ne l'implémente pas
> non plus,
C'est l'une des tares rédhibitoires de Google groupes en tant que
nouvelleur. Certes, ce n'est pas la seule.
> y a t-il seulement un webmail qui le propose?
D'habitude je fuis les webmails, mais je viens d'essayer celui de
GalacSys. Il propose par configuration de choisir la taille de la
zone de saisie (nombre de lignes et nombre de colonnes, par défaut
24 lignes de 78 colonnes), et il fait le wordwrap en conséquence.
Si j'insère des sauts de ligne, il en tient compte. Il semble donc
que celui-ci le propose.
> En fait je ne comprends toujours pas l'intérêt de couper une phrase en
> insérant un retour chariot en plein milieu alors même que l'affichage
> est parfaitement géré par le client sans cet artifice.
Parfaitement géré ? Permets-moi de ne pas être d'accord
! Je te donne ici deux exemples de ce que je disais à 12
h 19 dans mon article précédent.
Tu pourras me répondre que dans ce cas l'émetteur devrait mettre
des espaces insécables au lieu des espaces simples, ce à quoi je te
rétorquerai d'essayer avec Internet Explorer ou Firefox : à moins
que ça n'ait été corrigé depuis la dernière fois que j'ai essayé,
c'est impossible.
> Encore que si les
> retours chariots automatiques étaient différents des retours chariots
> manuels je pourrais décider de les ignorer côté HTML,
Mais non, il ne s'agit pas de les ignorer, bien au contraire ! S'il y
a un saut de ligne fait automatiquement lors de la composition, et
si l'auteur est content avec ça (il n'en insère pas un autre avant),
alors c'est qu'il faut l'officialiser au moment de l'envoi. Finalement,
ça ne doit pas être si difficile que ça...
> Pour faciliter le travail de celui qui va répondre on dénature la
> syntaxe même de la phrase, laquelle n'exige un retour à la ligne qu'à la
> fin de celle ci, et pas là où on devine que le lecteur l'attend.
Pour ne *pas* dénaturer le texte écrit par l'auteur, il faut et il
suffit que ce qui est envoyé corresponde exactement à ce que l'auteur
voyait au moment de cliquer sur le bouton d'envoi.
> Pourtant il existe une solution, regarde ce message :
> http://news.julien-arlandis.fr/?MessageID=5162ed...@news.julien-arlandis.fr
Je ne vois rien, les deux grandes zones sont vides.
> Y aura une autre hiérarchie 100% compatible JNTP, ce n'est pas tout car
> toutes les évolutions du protocole ne seront pas compatibles avec NNTP,
> pour assurer l'intéropérabilité des deux protocoles elles ne seront pas
> activées pour l'usage des hiérarchies communes. Néanmoins, je compte
> développer une nouvelle hiérarchie Nemo qui appliquera le protocole JNTP
> à 100%, elle ne pourra donc pas être relayée sur NNTP pour des raisons
> de sécurité, car j'ai prévu que le nouvel identifiant (le JID) soit un
> hash de l'ensemle des entêtes obligatoires et non modifiables de
> l'article. Tout article dont le hash n'est pas valide sera
> automatiquement éjecté et par le client et par le serveur. J'ai
> également prévu un champ pour signer numériquement l'article, l'idée est
> simple : chaque utilisateur génère une phrase secrète qu'il stocke dans
> son client. Lors de la rédaction d'un article, il réalise avant
> d'expédier l'article les opérations suivantes :
>
> MyHash = SHA1(From + Subject + Body + Newsgroups + SHA1(From + Subject
> + Body + Newsgroups + phrase_secrete))
Ça me semble compliqué, et source d'erreurs dans les implémentations
concurrentes de la tienne (qui, je le rappelle, doivent exister si
tu comptes standardiser ton protocole). Par exemple, la suppression
des lignes vides à la fin du Body, ou un folding en plus ou en moins
dans le champ Subject, détruiraient ton hash.
Pourquoi pas tout simplement :
MyHash = SHA1(Message-ID + SHA1(Message-ID + phrase_secrete))
?
> Pour prouver son identité lors de la suppression ou de la modification
> de son message, l'auteur devra fournir la clé
> SHA1(From + Subject + Body + Newsgroups + phrase_secrete)
>
> Si le hash de cette clé concaténée au message est identique à MyHash
> c'est qu'il est l'auteur de l'article.
Étant entendu que la « modification » est aussi une suppression de
l'article d'origine, ça devrait fonctionner. Parce que sinon, dès
qu'un auteur aurait fait une modification, n'importe qui aurait pu
venir remodifier l'article d'origine avec la même clé.
> Chose nouvelle également, le JID sera de cette forme
> SHA1(enêtes+body)@domaine_du_serveur_de_news_emetteur
Entre les entêtes qui peuvent changer et l'obligation d'unicité, je
soupçonne qu'il risque d'y avoir des problèmes, sans en être sûr.
Il faudra soigneusement vérifier tout ça.
> Les serveurs devront avoir un certificat numérique valable et devront
> signer tous les articles émis par leurs abonnés. Toutes ces règles ne
> seront pas optionnelles, elles devront être appliquées.
Ça apportera quoi exactement, que n'apporte pas déjà le champ Path ?
>> Pour l'émetteur soucieux de bonne typographie : il insèrera de toute
>> façon des sauts de ligne, ne serait-ce que pour que la coupure ne
>> se fasse pas avant un « : » ou au milieu de « 20 h 30 ». S'il les
>> insère un tout petit peu trop loin par rapport à l'affichage de ceux
>> qui vont le lire, par exemple au bout de 90 caractères au lieu de
>> 80, cela reproduira à l'affichage le bug d'Outlook Express : une
>> alternance de lignes longues et de lignes courtes.
>
> Su un navigateur, la typographie se gère à l'affichage et pas à la
> rédaction, c'est ce qui assure la compatibilité de lecture sur
> différents médias.
Une page web est faite pour être affichée de plein de façons
différentes selon les préférences du lecteur, c'est pour ça que
l'auteur de cette page se doit d'utiliser des partout où
c'est nécessaire.
Un article de news est fait pour être affiché en texte, avec au
maximum 78 caractères par ligne, et de préférence dans une police
à espacement fixe. C'est sous ces conditions que l'on peut faire
un schéma en art-ascii, puisqu'on ne peut pas insérer une image.
> Je ne comprends toujours pas ce qu'est ce format=flowed, que fait il
> exactement, à quoi sert il, à qui est il destiné?
Ce n'est pas moi qui en ferai la pub. Il y a un RFC qui le décrit,
si ça t'intéresse d'en savoir plus.
>> J'ai trouvé comment traiter le cas où c'est le premier article qui
>> manque. Je n'ai pas encore testé, mais il suffit de rajouter une
>> dizaine de lignes dans mon code, sans rien changer d'autre. Dès
>> que j'ai le temps, je les écris ici (à moins que tu ne préfères
>> attendre que j'aie testé d'abord, et alors ce ne sera pas avant
>> cette nuit).
>
> Pas de soucis, je n'ai pas encore eu le temps d'implémenter ton algo en
> javascript, mais les choses avancent ...
Finalement ça vaut mieux, puisque j'avais oublié une ligne dans le code
d'origine. Voici la fonction modifiée.
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
// on peut placer le nouvel article.
// 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;
// voir un autre article, celui-ci sera traité
// plus tard.
// 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
// 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.
On est de plus en plus HS sur fclj. À défaut d'une meilleure idée, je
fais suivre vers fr.comp.usenet.serveurs
Le 08/04/2013 18:56, Julien Arlandis a écrit :
>>
>> Ça ne pourra fonctionner correctement que quand tu l'implémenteras
>> dans l'éditeur et non pas après coup. Au fait, est-ce seulement
>> possible ? Qu'est-ce que tu utilises pour la rédaction du contenu
>> des articles ?
>
> Un simple textarea, j'ai vérifié que google groups ne l'implémente pas
> non plus,
nouvelleur. Certes, ce n'est pas la seule.
> y a t-il seulement un webmail qui le propose?
GalacSys. Il propose par configuration de choisir la taille de la
zone de saisie (nombre de lignes et nombre de colonnes, par défaut
24 lignes de 78 colonnes), et il fait le wordwrap en conséquence.
Si j'insère des sauts de ligne, il en tient compte. Il semble donc
que celui-ci le propose.
> En fait je ne comprends toujours pas l'intérêt de couper une phrase en
> insérant un retour chariot en plein milieu alors même que l'affichage
> est parfaitement géré par le client sans cet artifice.
! Je te donne ici deux exemples de ce que je disais à 12
h 19 dans mon article précédent.
Tu pourras me répondre que dans ce cas l'émetteur devrait mettre
des espaces insécables au lieu des espaces simples, ce à quoi je te
rétorquerai d'essayer avec Internet Explorer ou Firefox : à moins
que ça n'ait été corrigé depuis la dernière fois que j'ai essayé,
c'est impossible.
> Encore que si les
> retours chariots automatiques étaient différents des retours chariots
> manuels je pourrais décider de les ignorer côté HTML,
a un saut de ligne fait automatiquement lors de la composition, et
si l'auteur est content avec ça (il n'en insère pas un autre avant),
alors c'est qu'il faut l'officialiser au moment de l'envoi. Finalement,
ça ne doit pas être si difficile que ça...
> Pour faciliter le travail de celui qui va répondre on dénature la
> syntaxe même de la phrase, laquelle n'exige un retour à la ligne qu'à la
> fin de celle ci, et pas là où on devine que le lecteur l'attend.
suffit que ce qui est envoyé corresponde exactement à ce que l'auteur
voyait au moment de cliquer sur le bouton d'envoi.
> Pourtant il existe une solution, regarde ce message :
> http://news.julien-arlandis.fr/?MessageID=5162ed...@news.julien-arlandis.fr
> Y aura une autre hiérarchie 100% compatible JNTP, ce n'est pas tout car
> toutes les évolutions du protocole ne seront pas compatibles avec NNTP,
> pour assurer l'intéropérabilité des deux protocoles elles ne seront pas
> activées pour l'usage des hiérarchies communes. Néanmoins, je compte
> développer une nouvelle hiérarchie Nemo qui appliquera le protocole JNTP
> à 100%, elle ne pourra donc pas être relayée sur NNTP pour des raisons
> de sécurité, car j'ai prévu que le nouvel identifiant (le JID) soit un
> hash de l'ensemle des entêtes obligatoires et non modifiables de
> l'article. Tout article dont le hash n'est pas valide sera
> automatiquement éjecté et par le client et par le serveur. J'ai
> également prévu un champ pour signer numériquement l'article, l'idée est
> simple : chaque utilisateur génère une phrase secrète qu'il stocke dans
> son client. Lors de la rédaction d'un article, il réalise avant
> d'expédier l'article les opérations suivantes :
>
> MyHash = SHA1(From + Subject + Body + Newsgroups + SHA1(From + Subject
> + Body + Newsgroups + phrase_secrete))
concurrentes de la tienne (qui, je le rappelle, doivent exister si
tu comptes standardiser ton protocole). Par exemple, la suppression
des lignes vides à la fin du Body, ou un folding en plus ou en moins
dans le champ Subject, détruiraient ton hash.
Pourquoi pas tout simplement :
MyHash = SHA1(Message-ID + SHA1(Message-ID + phrase_secrete))
?
> Pour prouver son identité lors de la suppression ou de la modification
> de son message, l'auteur devra fournir la clé
> SHA1(From + Subject + Body + Newsgroups + phrase_secrete)
>
> Si le hash de cette clé concaténée au message est identique à MyHash
> c'est qu'il est l'auteur de l'article.
l'article d'origine, ça devrait fonctionner. Parce que sinon, dès
qu'un auteur aurait fait une modification, n'importe qui aurait pu
venir remodifier l'article d'origine avec la même clé.
> Chose nouvelle également, le JID sera de cette forme
> SHA1(enêtes+body)@domaine_du_serveur_de_news_emetteur
soupçonne qu'il risque d'y avoir des problèmes, sans en être sûr.
Il faudra soigneusement vérifier tout ça.
> Les serveurs devront avoir un certificat numérique valable et devront
> signer tous les articles émis par leurs abonnés. Toutes ces règles ne
> seront pas optionnelles, elles devront être appliquées.
>> Pour l'émetteur soucieux de bonne typographie : il insèrera de toute
>> façon des sauts de ligne, ne serait-ce que pour que la coupure ne
>> se fasse pas avant un « : » ou au milieu de « 20 h 30 ». S'il les
>> insère un tout petit peu trop loin par rapport à l'affichage de ceux
>> qui vont le lire, par exemple au bout de 90 caractères au lieu de
>> 80, cela reproduira à l'affichage le bug d'Outlook Express : une
>> alternance de lignes longues et de lignes courtes.
>
> Su un navigateur, la typographie se gère à l'affichage et pas à la
> rédaction, c'est ce qui assure la compatibilité de lecture sur
> différents médias.
différentes selon les préférences du lecteur, c'est pour ça que
l'auteur de cette page se doit d'utiliser des partout où
c'est nécessaire.
Un article de news est fait pour être affiché en texte, avec au
maximum 78 caractères par ligne, et de préférence dans une police
à espacement fixe. C'est sous ces conditions que l'on peut faire
un schéma en art-ascii, puisqu'on ne peut pas insérer une image.
> Je ne comprends toujours pas ce qu'est ce format=flowed, que fait il
> exactement, à quoi sert il, à qui est il destiné?
si ça t'intéresse d'en savoir plus.
>> J'ai trouvé comment traiter le cas où c'est le premier article qui
>> manque. Je n'ai pas encore testé, mais il suffit de rajouter une
>> dizaine de lignes dans mon code, sans rien changer d'autre. Dès
>> que j'ai le temps, je les écris ici (à moins que tu ne préfères
>> attendre que j'aie testé d'abord, et alors ce ne sera pas avant
>> cette nuit).
>
> Pas de soucis, je n'ai pas encore eu le temps d'implémenter ton algo en
> javascript, mais les choses avancent ...
d'origine. Voici la fonction modifiée.
function construis_arbo($liste)
{
$arbre = array("" => array());
while ($liste) {
foreach ($liste as $id => &$refs) {
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 :
if (isset($arbre[$ref])) {
// on peut placer le nouvel article.
$arbre[$ref][] = $id;
$arbre[$id] = array();
unset($liste[$id]);
continue 3; /* while ($liste) */
}
if (isset($substitut[$ref])) {
$arbre[$id] = array();
unset($liste[$id]);
continue 3; /* while ($liste) */
}
// 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 :
unset($liste[$id]);
continue 3; /* while ($liste) */
}
if (isset($liste[$ref])) {
// 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]);
$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.
Olivier Miakinen
Apr 8, 2013, 8:08:24 PM4/8/13
to
Le 08/04/2013 19:21, Julien Arlandis a écrit :
>
>> Ah oui, j'ai vu sur fr.test que tu faisais des tests avec latex. Mais
>> quitte à envoyer autre chose que du text/plain, pourquoi ne pas passer
>> à HTML ?
>
> On ne peut pas permettre à un utilisateur d'injecter du HTML, c'est la
> porte ouverte aux failles XSS. Il faut nécessairement passer par un
> langage de balisage léger dont on contrôle la transition vers HTML.
Alors tu vas devoir définir de nouveaux types MIME :
>
>> Ah oui, j'ai vu sur fr.test que tu faisais des tests avec latex. Mais
>> quitte à envoyer autre chose que du text/plain, pourquoi ne pas passer
>> à HTML ?
>
> On ne peut pas permettre à un utilisateur d'injecter du HTML, c'est la
> porte ouverte aux failles XSS. Il faut nécessairement passer par un
> langage de balisage léger dont on contrôle la transition vers HTML.
<http://fr.wikipedia.org/wiki/Type_MIME>
<http://www.iana.org/assignments/media-types/text>
Probablement text/latex et text/bbcode ?
Julien Arlandis
Apr 8, 2013, 8:33:05 PM4/8/13
to
Le 09/04/13 02:08, Olivier Miakinen a écrit :
Pourquoi de nouveaux types MIME ? Le BBcode c'est du simple texte...
Olivier Miakinen
Apr 8, 2013, 8:37:32 PM4/8/13
to
J'avais oublié de faire suivre à fr.comp.usenet.serveurs, je le fais
maintenant.
Le 09/04/2013 02:33, Julien Arlandis a écrit :
>>
>> Alors tu vas devoir définir de nouveaux types MIME :
>> <http://fr.wikipedia.org/wiki/Type_MIME>
>> <http://www.iana.org/assignments/media-types/text>
>>
>> Probablement text/latex et text/bbcode ?
>
> Pourquoi de nouveaux types MIME ? Le BBcode c'est du simple texte...
Ce n'est ni plus ni moins du simple texte que le HTML, or HTML a son
propre type MIME.
maintenant.
Le 09/04/2013 02:33, Julien Arlandis a écrit :
>>
>> Alors tu vas devoir définir de nouveaux types MIME :
>> <http://fr.wikipedia.org/wiki/Type_MIME>
>> <http://www.iana.org/assignments/media-types/text>
>>
>> Probablement text/latex et text/bbcode ?
>
> Pourquoi de nouveaux types MIME ? Le BBcode c'est du simple texte...
propre type MIME.
0 new messages