Discussion :

[kox2ee]

Bonjour,
Je souhaite trier une collection d'objets de type MaClasse unis par une relation hiérarchique.

Code :

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

1
2
3
4
5
Class Maclasse{
	public boolean estPereDe(MaClasse o2){
		//retourne vrai si this est parent de o2
	}
}

L'objectif du tri de la collection est de placer les objets pères avant les objets fils.

Je met une implémentation assez proche de mon exemple pour que vous puissiez tester facilement, implémentation basée sur l'héritage java :

Je veux classer une liste de classes java en respectant leur arbre d'héritage :
J'utilise l'interface Comparator de la façon suivante :

• si class1.isAssignableFrom(class2), class1 est parent de class2 (ou égale), et class1 doit se trouver avant class 2(donc retour négatif)
• si class2.isAssignableFrom(class1), class2 est parent de class1 (ou égale), et class 2 doit se trouver avant class1 (donc retour positif)
• retour zéro si aucune relation entre class1 et class2

Ca donne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Test {
 
	public static void main(String[] args) {
		List<Class<?>> classes = new ArrayList<>();
 
		classes.add(Integer.class);
		classes.add(BigDecimal.class);
		classes.add(Float.class);
		classes.add(Object.class);
		classes.add(String.class);
		classes.add(Number.class);
 
		Collections.sort(classes, new Comparator<Class<?>>() {
			@Override
			public int compare(Class<?> cls1, Class<?> cls2) {
				int result = 0;
				if (cls1.isAssignableFrom(cls2))
					result = -1;
				else if (cls2.isAssignableFrom(cls1))
					result = 1;
				System.out.println(cls1 + " " + cls2 + " : " + result);
				return result;
			}
		});
		System.out.println(classes);
	}
}

et tout est à priori ok après tri :

class java.math.BigDecimal class java.lang.Integer : 0
class java.lang.Float class java.math.BigDecimal : 0
class java.lang.Object class java.lang.Float : -1
class java.lang.Object class java.math.BigDecimal : -1
class java.lang.Object class java.lang.Integer : -1
class java.lang.String class java.math.BigDecimal : 0
class java.lang.String class java.lang.Float : 0
class java.lang.Number class java.math.BigDecimal : -1
class java.lang.Number class java.lang.Integer : -1
class java.lang.Number class java.lang.Object : 1
[class java.lang.Object, class java.lang.Number, class java.lang.Integer, class java.math.BigDecimal, class java.lang.Float, class java.lang.String]

Si par contre j'ajoute des classes :

Code :

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

1
2
classes.addAll(Arrays.asList(ArrayList.class, Test.class, Float.class, Integer.class, BigDecimal.class, Object.class, Number.class));
classes.addAll(Arrays.asList(AbstractList.class, List.class, Float.class, Object.class, String.class, Number.class));

Le résultat du tri devient du n'importe quoi :

[class java.lang.Object, class java.lang.Object, class java.util.ArrayList, class Test, class java.lang.Number, class java.lang.Number, class java.lang.Float, class java.lang.Float, class java.lang.Integer, class java.math.BigDecimal, interface java.util.List, class java.util.AbstractList, class java.lang.String]

ArrayList et AbstractList ne sont pas dans le bon ordre, et ne sont même pas comparés...

J'en déduis que je fais une erreur quelque part, mais où ?

[thelvin]

Bonjour,

Zéro ne veut pas dire qu'il n'y a pas de relation, mais qu'il y a relation d'égalité, transitive bien entendu. Dans ton cas, si tu as deux classes sœurs, elles ne sont pas égales, aucune n'est supérieure à l'autre, donc la méthode compare() n'a pas de sens.

Autrement dit les fonctions de tri fournies par Java supposent toutes que l'ensemble des données à trier est entièrement ordonné : on peut comparer tous les objets les uns avec les autres, et soit l'un est supérieur à l'autre, soit ils sont égaux. Bien sûr, si un objet est supérieur à un autre, alors tous ses égaux sont aussi supérieurs à cet autre.
Or dans ton cas, tu dis que les classes sœurs sont égales, mais si l'une est supérieure à ses descendantes, l'autre ne l'est pas. L'égalité n'est pas respectée.

Si tu veux faire ça, tu vas devoir imaginer toi-même qu'est-ce qui va faire qu'une classe est avant une autre dans le résultat final, et ensuite le programmer toi-même. Ni l'un ni l'autre ne sont fournis par Java, et il n'y a pas de consensus.

[kox2ee]

Bonjour,
dans mon cas, le zéro est bien l'équivalent de l'absence de hiérarchie : aucune relation directe entre une ArrayList et un Integer, donc je n'attends pas un classement entre ces deux là, et je considère qu'il y a égalité...

J'ai essayé, en supposant ce que tu as expliqué, de hiérarchiser les classes sans relation, en remplaçant le zéro initial :

int result=0;

par :

int result = cls1.getSimpleName().compareTo(cls2.getSimpleName());

Quand il n'y a pas de relation, on range par ordre alpha du nom de la classe.
Le résultat obtenu est un peu mieux... mais pas juste pour autant

[thelvin]

dans mon cas, le zéro est bien l'équivalent de l'absence de hiérarchie : aucune relation directe entre une ArrayList et un Integer, donc je n'attends pas un classement entre ces deux là, et je considère qu'il y a égalité...

Égalité consiste à attendre un classement tel qu'ils sont égaux. Égaux donc librement échangeables. Des objets sans relation ne sont pas librement échangeables
=> Ça ne peut pas marcher.

J'ai essayé, en supposant ce que tu as expliqué, de hiérarchiser les classes sans relation,

Ce serait bien si c'était possible, mais ce n'est pas possible.
Ce n'est donc pas ce que je t'ai expliqué.

Je t'ai expliqué que tu ne peux pas. compare() ne s'applique pas à ce que tu essaies de faire. Tu dois l'oublier.
Et comme je te l'ai dit, à la question "alors je fais quoi à la place," eh bien, tu inventes toi-même le type d'ordre qui t'intéresse et tu le programmes toi-même. Java ne te propose rien.

Quand il n'y a pas de relation, on range par ordre alpha du nom de la classe.
Le résultat obtenu est un peu mieux... mais pas juste pour autant

Parce que cet ordre n'est pas cohérent. Tu peux avoir A > B et B > C mais C > A, ce qui n'a pas de sens.

[kox2ee]

Égalité consiste à attendre un classement tel qu'ils sont égaux. Égaux donc librement échangeables. Des objets sans relation ne sont pas librement échangeables
=> Ça ne peut pas marcher.

Je ne suis pas de cet avis. Si on utilise le seul critère hiérarchique, les classes String et Number sont égales (de même niveau), et librement échangeables dans le classement.

Le compare doit te permettre d'implémenter ta propre méthode de comparaison, c'est bien ce que je fais dans ce cas.

Si j'ai dans ma liste :
Integer,Number et String

Je m'attend à avoir après classement :
Number avant Integer, mais je me fiche de savoir où sera le String.

Je suis étonné que dans mon cas, le sort ne respecte pas ce qui est retourné par compare...

[kox2ee]

Cas fonctionnant :

Code :

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

1
2
3
4
5
6
classes.add(ArrayList.class);
classes.add(AbstractList.class);
classes.add(Object.class);
classes.add(String.class);
classes.add(Number.class);
classes.add(Float.class);

Résultat :

Code :

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

1
2
3
4
5
6
7
8
9
class java.lang.Object class java.util.AbstractList : -1
class java.lang.String class java.lang.Object : 1
class java.lang.String class java.util.AbstractList : 0
class java.lang.String class java.util.ArrayList : 0
class java.lang.Number class java.util.ArrayList : 0
class java.lang.Number class java.lang.String : 0
class java.lang.Float class java.util.ArrayList : 0
class java.lang.Float class java.lang.Number : 1
[class java.lang.Object, class java.util.AbstractList, class java.util.ArrayList, class java.lang.String, class java.lang.Number, class java.lang.Float]

Initialisation avec les mêmes classes, mais dans un ordre différent :

Code :

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

1
2
3
4
5
6
classes.add(ArrayList.class);
classes.add(AbstractList.class);
classes.add(Float.class);
classes.add(Object.class);
classes.add(String.class);
classes.add(Number.class);

Ca ne fonctionne plus :

class java.util.AbstractList class java.util.ArrayList : -1
class java.lang.Float class java.util.AbstractList : 0
class java.lang.Float class java.util.ArrayList : 0
class java.lang.Object class java.util.ArrayList : -1
class java.lang.Object class java.util.AbstractList : -1
class java.lang.String class java.util.ArrayList : 0
class java.lang.String class java.lang.Float : 0
class java.lang.Number class java.util.ArrayList : 0
class java.lang.Number class java.lang.String : 0
[class java.lang.Object, class java.util.AbstractList, class java.util.ArrayList, class java.lang.Float, class java.lang.String, class java.lang.Number]

En même temps, c'est un peu normal, Number et Float ne sont jamais comparés...

[thelvin]

Je ne suis pas de cet avis. Si on utilise le seul critère hiérarchique, les classes String et Number sont égales (de même niveau), et librement échangeables dans le classement.

Vraiment ? Ajoutons-y Integer.

String = Number. Donc ils sont interchangeables.
Number < Integer. Par définition du tri.
Donc String < Integer, en remplaçant Number par String.
... Mais ton compare() indique que String = Integer. Number et String ne sont donc pas interchangeables.

Le tri n'est donc pas cohérent, ou comme on le dit en Math, l'ensemble n'est pas complètement ordonné.

sort() ne peut rien donner de logique avec un compare() incohérent.

Aaaah, combien de fois j'ai entendu "il y a pas besoin de savoir les maths pour programmer." Quelqu'un qui sait les maths comprend le problème au premier coup d'œil et sait depuis le début qu'il doit trouver autre chose.

[kox2ee]

Vraiment ? Ajoutons-y Integer.

String = Number. Donc ils sont interchangeables.
Number < Integer. Par définition du tri.
Donc String < Integer, en remplaçant Number par String.
... Mais ton compare() indique que String = Integer. Number et String ne sont donc pas interchangeables.

Oui, je suis d'accord avec ton raisonnement, pas de problèmes. Mais l'algo de Tri de la méthode sort ne le fait pas, lui, ce raisonnement.

D'autant que comme l'indique la javadoc du sort :

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

On peut donc supposer que les éléments "égaux" au sens du comparator ne sont pas déplacés.

Et même si je définis un Compare incohérent, il devrait (en théorie) être respecté non ?
Si je met dans compare que 14<21, que 21<2 et 14==2 :
j'obtiens bien après sort : 14 21 2
peu importe la cohérence mathématique du compare !


Une chose semble acquise : l'algorithme utilisé pour la méthode sort (mergesort) n'est pas compatible avec le tri d'éléments hiérarchisés...

Quelqu'un qui sait les maths comprend le problème au premier coup d'œil et sait depuis le début qu'il doit trouver autre chose.

?? étrange remarque !

[thelvin]

Oui, je suis d'accord avec ton raisonnement, pas de problèmes. Mais l'algo de Tri de la méthode sort ne le fait pas, lui, ce raisonnement.

sort() ne raisonne pas. sort() exige, pour bien fonctionner, que compare() soit cohérent.
compare() n'est pas cohérent.
Donc sort() ne fonctionne pas bien.

D'autant que comme l'indique la javadoc du sort

Cela signifie simplement que si A et B sont égaux, et que avant le tri A était situé avant B, alors après le tri A sera encore situé avant B. Mais probablement pas au même endroit.

Ça n'a rien à voir avec la cohérence de compare(), qui doit être cohérent et c'est tout, aucune alternative autorisée.

Et même si je définis un Compare incohérent, il devrait être respecté non ?

Respecté comment ? Qu'est-ce que ça veut dire, respecter un comparateur incohérent ? L'effet sera quoi ?
Ça n'a pas de sens.

Si je met dans compare que 14<21, que 21<2 et 14==2 :
j'obtiens bien après sort : 14 21 2

Ce qui n'a aucune espèce de sens, puisque 14 et 2 sont égaux, et qu'ils sont séparés par un élément qui n'est pas égal ni à l'un, ni à l'autre. Le résultat n'est donc pas trié.

Par ailleurs, as-tu essayé de trier 2, 21, 14 ? 21 se retrouve avant 14.

peu importe la cohérence mathématique du compare !

Euh. Les mathématiques sont un moyen de description de règles de vérité.
On peut décider que c'est sans importance de respecter des règles de vérité, après tout pourquoi pas. Mais dans ce cas-là il n'y a pas de résultat prédictible à attendre. Juste du hasard.

Il n'y a évidemment rien de plus important, dans un comparateur, que respecter la cohérence mathématique. C'est la raison d'être d'un comparateur, c'est la raison pour laquelle on décide d'en faire un.

?? étrange remarque !

Oui, un accès de vanité de ma part. J'entends si souvent dire qu'il n'y a pas besoin de maths pour programmer, que je ne peux pas m'empêcher de le signaler quand on tombe sur une preuve du contraire.

[kox2ee]

Oui Thelvin, je suis d'accord et j'ai bien compris :
Collection.sort et compare reposent sur la transitivité, ce que je ne peux pas appliquer à mon absence de relation hiérarchique que j'assimilais à tort à une égalité (compte tenu de l'implémentation du sort des Arrays java)

Je m'atèle donc à un algo spécifique...

[kox2ee]

Bon, je dois refaire la roue, parce que j'imagine que ça doit exister quelque part...

Version 1 :
Pour rappel, il s'agit de classer une collection d'objets hiérarchisés (Chaque Objet peut avoir un Parent).
Le résultat du classement doit permettre de placer les parents avant leurs enfants.

Interface permettant de définir la relation hiérarchique :

Code :

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

1
2
3
4
5
6
7
8
9
10
public interface HierarchicalComparator<T> {
	/**
         * Détermine si obj1 est le père de obj2
         * 
         * @param obj1
         * @param obj2
         * @return Vrai si obj1 est le père de obj2
         */
	public boolean isParent(T obj1, T obj2);
}

Implémentation de la comparaison :
A relation hierarchique, algo récursif...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class KHierarchicalSort {
	/**
         * Trie une liste en fonction du comparateur hiérarchique passé en paramètre
         * Pour le principe, dès qu'un Parent est trouvé, on cherche récursivement s'il a lui même un parent
         * et ensuite on le place dans la liste triée
         * 
         * @param list
         *            Liste à ordonner
         * @param comparator
         *            Comparateur hiérarchique
         */
	public static <T extends Object> void sort(List<T> list, HierarchicalComparator<T> comparator) {
		List<T> sortedList = new ArrayList<T>();
		while (list.size() > 0) {
			sortedList = innerSort(list, list.get(0), sortedList, comparator);
		}
		list.addAll(sortedList);
	}
 
	private static <T extends Object> List<T> innerSort(List<T> list, T object, List<T> sortedList, HierarchicalComparator<T> comparator) {
		int i = 0;
		while (i < list.size()) {
			if (!list.get(i).equals(object)) {
				if (comparator.isParent(list.get(i), object)) {
					innerSort(list, list.get(i), sortedList, comparator);
				}
			}
			i++;
		}
		list.remove(object);
		sortedList.add(object);
		return sortedList;
	}
}

Test :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Test {
 
	public static void main(String[] args) {
		List<Class<?>> classes = new ArrayList<>();
		classes.addAll(Arrays.asList(ArrayList.class, Test.class, Integer.class, BigDecimal.class, Number.class));
		classes.addAll(Arrays.asList(AbstractList.class, Float.class, Object.class, String.class, Number.class));
 
		KHierarchicalSort.sort(classes, new HierarchicalComparator<Class<?>>() {
			@Override
			public boolean isParent(Class<?> cls1, Class<?> cls2) {
				boolean result = cls1.isAssignableFrom(cls2);
				System.out.println(cls1 + " " + cls2 + " : " + result);
				return result;
			}
		});
		System.out.println(classes);
	}
 
}

Résultat :
A priori, le résultat est dans l'ordre.
Pas vraiment optimisé, compte tenu du nombre d'itérations.

[class java.lang.Object, class java.util.AbstractList, class java.util.ArrayList, class Test, class java.lang.Number, class java.lang.Number, class java.lang.Integer, class java.math.BigDecimal, class java.lang.Float, class java.lang.String]

Si vous avez des idées d'améliorations...