oct.
2012
Jusqu'à Java 6 inclus, TreeMap et TreeSet avaient un comportement rigolo, pouvant fournir matière à quiz ou question d'entretien technique.
A votre avis, que fait ce bout de code ?
TreeSet set = new TreeSet(); set.add(new Object()); set.add(new Object()); System.out.println(set.size());
A l'exécution, on obtient une ClassCastException... à la ligne 3.
C'est-à-dire l'insertion du premier objet se passe bien, mais que la seconde provoque une exception.
La raison en est simple : un TreeSet (ou une TreeMap) étant implémenté sous forme d'arbre binaire, il doit comparer les objets entre eux pour les organiser. Or, nous voyons dans le code que les objets insérés n'implémentent pas Comparable, et qu'aucun Comparator n'est fourni au TreeSet.
Le premier objet étant... le premier justement, et donc le seul dans la structure, aucune comparaison n'est effectuée : il devient simplement la racine de l'arbre. A partir du second objet, une comparaison devient nécessaire, et les objets sont donc "castés" en Comparable... ce qui provoque une ClassCastException.
Funky, mais logique, quelque part.
Et bien, tout ceci est fini en Java 7 : on obtient une exception dès la première insertion.
C'est moins drôle, mais ce nouveau comportement est sans doute plus sain. On ne s'en plaindra donc pas.
Et puis, maintenant vous avez une nouvelle anecdote pour épater les convives dans les dîners mondains :)
Commentaires
Bonne remarque. A propos du "plus sain", personnellement, j'aurais tendance à dire que si quelqu'un doit émettre quelque chose, ce serait plutôt au compilateur de râler à la ligne 2.
Evidemment, ce n'est pas possible, parce qu'un TreeSet avec comparateur en argument et un TreeSet sans ont le même type. Et à mon sens, l'erreur de conception est à ce niveau. S'il y avait deux types distincts, il pourrait y avoir une erreur de compilation.
Hop ... je retourne à mes petits fours ...
Benoît
Côté Scala, c'est plus simple : il n'est pas possible de construire un TreeSet sans donner le type.
scala> def set = new TreeSet()
<console>:10: error: diverging implicit expansion for type Ordering[A]
starting with method Tuple9 in object Ordering
Rien à voir : le problème n'est pas dû au fait que je n'ai pas précisé le type de la collection, mais à l'absence de moyen de comparaison entre les objets (soit via un Comparator, soit du fait que les objets eux-mêmes implémentent Comparable).
J'ai ici pris des Object (qui n'est pas Comparable) parce que cela m'évitait d'introduire une classe bidon, qui aurait complexifié l'exemple. Un TreeSet<Voiture> provoquerait exactement la même exception si Voiture n'était pas Comparable.
On ne devrait jamais se plaindre d'un mode "fail fast".
Cependant, j'aurais préféré que cela aille un peu plus loin. Puisque TreeSet ne sait gérer que des Objets comparable, pourquoi ne pas définir TreeSet<E extends Comparable> avec une méthode add(E element). Comme ça, la ligne 2 ne compile même pas.
Parce que ça nous priverait de la possibilité d'utiliser un Comparator sur des objets non-Comparable !
PS : la bonne signature serait plutôt TreeSet<E extends Comparable<? super E>>
Effectivement, l'exemple était juste là pour illustrer qu'il est sans doute possible d'aller plus loin.
D'où l'intérêt d'une approche à base de typeclass.
Ça donne la souplesse d'avoir un comparator défini de manière externe et d'avoir le bon comportement (gueuler à la compilation).
@Clément tu peux préciser ton explication et/ou donner un exemple ?
@OlivierCroisier En réponse au commentaire #5
C'est pour ça que je disais qu'il faudrait deux type TreeSet :
Benoît
Je précisais la réponse de Nicolas.
En scala, la nécessité de pouvoir comparer ces deux objets est fixée par le type.
La manière dont c'est fait garantit non pas que les objets implémentent Comparable,
mais qu'il existe un comparateur permettant d'établir une relation d'ordre entre les éléments (une instance d'OrderingA).
On a donc l'erreur à la compil et non au runtime tout en gardant la souplesse d'avoir le comportement défini en dehors de la classe et pas par héritage.
C'est ce qui fait la puissance des typeclass.
@Olivier
Really nice! Since we're still running Java 6, I will present that as a puzzle in the next developer meeting *evilgrin*
@Sebastien
If you happen to have a lot of objects that implement Comparable, you might want to create a subclass of TreeSet that only accepts Comparables.
But then again, almost only simple types have a natural ordering. A more complex object like a person can be sorted by name, date of birth, place of birth etc.
In addition, the upcoming closures and method references in Java 8 will turn Comparators into one-liners.