Discussion :

[need2learn]

Bonjour,

Je voudrais trier des objets de ma liste connaissant l'ordre de quelques éléments :
Je sais que :
Pomme > Banane
Banne > Orange
mais je ne sais pas ordonner :
Orange et Pomme

Or si j’implémente

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
@Override
public int compare(Fruit o1, Fruit o2) {
// que retourner dans le cas de Orange et Pomme ?
}

Logiquement si :
Pomme > Banane
Banne > Orange
alors
Pomme > Orange

que retourner "compare" dans le cas de Orange et Pomme ?
Programmation par contrainte peut être ?

Merci à vous !

[joel.drigo]

Salut,

Pour trier des objets, il faut qu'ils soient "triables", c'est-à-dire, qu'on puisse définir une relation d'ordre pour l'ensemble des objets. Le comparateur peut retourner 0 lorsque deux objets sont considérés comme "égaux" dans la relation d'ordre. D'une part, ça peut induire une instabilité dans l'ordre de tri (ces objets peuvent apparaitre dans des ordres différents, selon les collections (ou tableaux) qu'on trie. D'autre part, il faut faire attention à l'utilisation d'un tel comparateur dans certains composants, comme TreeSet par exemple : seule l'une des instances considérées comme égales par le comparateur sera conservée.

S'il n'y a pas de relation d'ordre logique entre certains éléments, on peut toujours en définir une arbitraire, ou sur un autre critère stable par exemple (ordre alphabétique par exemple, entre Orange et Pomme). Maintenant, à la base, je ne vois pas quelle relation d'ordre pourrait-il y avoir sur des fruits, suivant le critère "nature du fruit". Il n'y a pas plus de logique d'avoir un ordre entre Pomme et Banane, et Pomme et Orange. Mais si tu peux déterminer un critère qui définit une relation d'ordre entre 2 couples d'élements, dont un est commun, tu dois avoir un moyen d'en déterminer un entre les 2 élements non communs, forcément, quitte à "chercher" cet ordre quand les 2 éléments ne sont pas comparables à première vue.

[need2learn]

Donc on gros si :

Pomme > Banane
Banane > Orange

L’implémentation de Comparator ne pourra pas déduire que :

Pomme > Orange

??

[thelvin]

Ben... L'implémentation de Comparator c'est ton boulot.

Rien ne t'empêche de l'implémenter de sorte qu'il sache que Pomme > Banane et Banane > Orange, même sans que qui que ce soit vienne lui parler de Pomme, Banane et Orange, et de là, faire en sorte qu'il déduise que Pomme > Orange.

Mais si quelqu'un le fait, ce sera toi et personne d'autre. Java ne fournit pas d'implémentation de Comparator.

[need2learn]

Ok je comprends que c'est à moi de le faire mais je ne trouve pas un moyen intuitif pour le faire

En fait mes objets sont des arbres du design pattern "component composite" et je sais que :
quand monObj2 est fils de monObj1 alors monObj1 > monObj2
et que :
quand monObj3 est fils de monObj2 alors monObj2 > monObj3
mais (pour une raison qui est difficile à expliquer sur un post, car il faudra expliquer tout le projet) :
"impossible" dans mon cas de déduire la relation entre monObj1 et monObj3 car n'est monObj3 n'est pas fils de monObj1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
@Override
public int compare(Object o1, Object o2) {
...
}

tout ce que je sais c'est que :
quand o1=monObj1 et o2=monObj2 return 1; // car je creuse récursivement dans monObj1 et je retrouve monObj2
quand o1=monObj2 et o2=monObj3 return 1; // car je creuse récursivement dans monObj2 et je retrouve monObj3
quand o1=monObj1 et o2=monObj3 return ????; // je ne sais pas quoi faire ! car dans mon contexte du projet même si je creuse dans monObj1 je ne retrouverais pas monObj3 !

peut être qu'il faudra utiliser autre chose que comparator ? une autre astuces ? proposez moi svp une solution ? programmation par contrainte ?

Merci, et désolé si je ne suis pas claire dans mon explication !

[joel.drigo]

Et il n'y a pas de relation d'ordre entre 2 fils d'un même nœud ?

[need2learn]

Non il n'y a pas de relation d'ordre entre 2 fils du même noeud.
L'ordre est connu par la "hiérarchie" : le père est > au fils
Et chaque père connait uniquement ses fils sans connaitre ses petit-fils !

La question est comment déduire que le grand-père est > aux petit-fils ?

La récursivité ne me donnera pas grand chose car je travail avec plusieurs arbres (ou contexte) différents :
dans un arbre a>b et dans un autre arbre b>c ... et "a" et "c" appartiennent à deux arbres différents donc pas possible de les comparer récursivement !

Merci pour votre patience

[adiGuba]

Salut,



Il y a un truc que je ne comprend pas : s'il n'y a pas d'ordre pourquoi tu tries ?
Et à quel résultat tu veux t'attendre ???


Parce que je ne vois pas à quoi ca sert de trier des éléments si on ne sait pas les comparer...


a++

[need2learn]

Merci adiGuba pour ta réponse, mais si, il y a un ordre :
Ordre est : père > fils
Je m'attends à : père > petit-fils !

sauf que dans compare(o1,o2) le grand-père et le petit-fils n'ont aucun lien ! par contre dans compare(o1,o2) le père > fils et le fils > petit-fils.

[joel.drigo]

Et chaque père connait uniquement ses fils sans connaitre ses petit-fils !

Si tout père connait ses fils, alors tout grand-père connait ses petits-fils. On peut n'avoir que les pointeurs que dans un sens (un fils ne connait pas son père), que l'on résout en parcourant l'arbre depuis la racine (et en construisant éventuellement un arbre-cache, pour éviter de refaire le parcourt à chaque comparaison).

La récursivité ne me donnera pas grand chose car je travail avec plusieurs arbres (ou contexte) différents :
dans un arbre a>b et dans un autre arbre b>c ... et "a" et "c" appartiennent à deux arbres différents donc pas possible de les comparer récursivement !

Ça ne change rien au principe pour moi : il suffit de chercher l'arbre qui définit la relation père-fils parmi tous les arbres qu'on a. Ou préparer à l'avance un arbre qui "concatène" tous les arbres.

Mais dans tous les cas, comme on te la tous dit, il faut pouvoir déterminer une relation d'ordre entre tous les éléments comparables 2 à 2. Si quelque chose (un arbre en l'occurence) définit A > B, et autre chose (un autre arbre) définit B > C, comme il y a transitivité de >, on peut déterminer que A > C. Simplement, comme le premier arbre ne permet pas de savoir que A est ancètre de C, on va chercher un élément en commun qui relie A et C dans tous les arbres, et on va trouver B, ce qui va permettre de dire que C étant fils de B, et B de A, alors A est bien ancêtre de C, donc A > C.

Mais si on a A > B, et A > D, (B et D fils du même nœud), sans notion d'ordre entre B et D, je vois mal comment on pourrait trier B et D, a moins qu'un autre arbre définisse que D > B, ou B > D. Au quel cas, on revient au principe de base : quand on a pas directement la relation, on cherche les éléments qui la définissent.

[need2learn]

Ça ne change rien au principe pour moi : il suffit de chercher l'arbre qui définit la relation père-fils parmi tous les arbres qu'on a. Ou préparer à l'avance un arbre qui "concatène" tous les arbres.

La solution de préparer à l'avance un arbre qui "concatène" tous les arbres me parait une bonne solution. je la test et reviens vers vous