SortedSet - bug de SUN ?

Jéjé wrote:

$ java -version
java version "1.4.2"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2-b28)
Java HotSpot(TM) Client VM (build 1.4.2-b28, mixed mode)

Salut à tous. Voici une petit discussion sur les SortedSet.

J'aimerais avoir vos avis éclairés sur le sujet.

Merci et bonne lecture !!

<snip code>

Si on regarde la doc des méthodes contains et remove d'un sorted set,
voici ce qu'on apprend:

*contains*

[=public boolean contains(Object o)]

Returns true if this set contains the specified element. More formally,
returns true if and only if this set contains an element e such that
(o==null ? e==null : o.equals(e)).

Pareillement, la methode add et la methode remove d'un Set
(ou d'un SortedSet) sont sensée d'après la doc utiliser la méthode equals sur les objects.

*Ces méthodes devraient selon la doc utiliser la méthode equals
sur o et non un cas particulier de la méthode compare.*

C'est pourtant ce qui arrive.


Voici des implications très désagréables:

Imaginons que vous vouliez afficher des personnes triées
par age en utilisant un sortedSet (pourquoi pas, ca parait être
une méthode valable et simple).

Jean 19 ans, Pierre 20 ans, Paul 20 ans, Mattieu 21 ans.

Vous implémentez en toute innocence un comparateur qui donne ceci:
compare(p1,p2) { return p2.age - p1.age ;}

Et bien, si vous utilisez ce comparateur, il devient impossible
d'inserer Paul après que vous ayez inséré Pierre.
Comment résoudre ce casse tête ?

hummm, question interessante mais certainement pas un bug :)

en gros si ton Set doit cotenir toutes tes données, alors il ne faut pas
ecrire un tel comparator et l'utiliser pour trier...
par contre on utilise un set pour trier des données contenues dans une
liste et là tu auras bien inséré tes 10 elements et t'auras l'ordre
semantique desire....

un petit conseil: ne pas redefinir equals() sans redefinir hashcode()

Etonnant non ?
pas vraiment :)

Jerome

--
Auteur cahier du programmeur Java tome 2 - Eyrolles 10/2003
http://www.eyrolles.com/php.informatique/Ouvrages/ouvrage.php3?ouv_ean13—82212111941

Dans l'article <bqkbev$59d$1@biggoron.nerim.net>, "jerome moliere"
<jmoliere@nerim.net> a tapoté :

Imaginons que vous vouliez afficher des personnes triées
par age en utilisant un sortedSet (pourquoi pas, ca parait être une
méthode valable et simple).

Jean 19 ans, Pierre 20 ans, Paul 20 ans, Mattieu 21 ans.

Vous implémentez en toute innocence un comparateur qui donne ceci:
compare(p1,p2) { return p2.age - p1.age ;}

Et bien, si vous utilisez ce comparateur, il devient impossible
d'inserer Paul après que vous ayez inséré Pierre.
Comment résoudre ce casse tête ?

hummm, question interessante mais certainement pas un bug :) en gros si

ton Set doit cotenir toutes tes données, alors il ne faut pas ecrire un
tel comparator et l'utiliser pour trier... par contre on utilise un set
pour trier des données contenues dans une liste et là tu auras bien
inséré tes 10 elements et t'auras l'ordre semantique desire....

Ca veut dire qu'en gros, il faut une liste contenant
Mattieu 21 ans, Paul 20 ans, Jean 19 ans et Pierre 20 ans.

Ensuite, on constuit un SortedTree a partir de cette liste en passant en
paramètre une instance d'ApotreComparator qui contient notre méthode.

Aucun constructeur de TreeSet ne permet de faire ça. Comment faire alors
? Utiliser un static sort sur un tableau d'objets ?

En fait, mon but était de maintenir un ensemble trié selon un ordre et
non pas de le trier entièrement une fois de temps en temps.

un petit conseil: ne pas redefinir equals() sans redefinir hashcode()
Merci du conseil !

--
--
His ideas of first-aid stopped short of squirting soda water.
-- P.G. Wodehouse
----------------------------
jerome.eteve_at_it-omics.com

Salut,

Ca veut dire qu'en gros, il faut une liste contenant
Mattieu 21 ans, Paul 20 ans, Jean 19 ans et Pierre 20 ans.

Ensuite, on constuit un SortedTree a partir de cette liste en passant en
paramètre une instance d'ApotreComparator qui contient notre méthode.

Aucun constructeur de TreeSet ne permet de faire ça. Comment faire alors
? Utiliser un static sort sur un tableau d'objets ?

En fait, mon but était de maintenir un ensemble trié selon un ordre et
non pas de le trier entièrement une fois de temps en temps.

Essaie d intitialier de cette facon :
Set set = new TreeSet( new ApotreComparator() );

Au lieu de mettre tes apotres dans une liste tu les mets directement
dans le set et l ensemble sera toujours trie.
set.add( "un apotre" );
ou
set.addAll( "une collection d apotres" );

Mais tout ca c est quand meme marque dans la doc...

Olivier.

Essaie d intitialier de cette facon : Set set = new TreeSet( new
ApotreComparator() );

Au lieu de mettre tes apotres dans une liste tu les mets directement
dans le set et l ensemble sera toujours trie. set.add( "un apotre" ); ou
set.addAll( "une collection d apotres" );

Mais tout ca c est quand meme marque dans la doc...

C'est donc exactement ce que j'ai fait en premier lieu. Je suis alors
tombé sur le problème suivant:
Si le comparateur renvoie 0 (par exemple si on veut garder les apôtres
triés par âge), la méthode add considère que l'objet est égal à celui
déja présent et ne l'insère pas. Par exemple, impossible d'insérer Paul
20 après Pierre 20 ans si le comparateur est fait de telle sorte que le
set devrait être trié suivant les ages.

Le code tiré de la classe TreeMap (c'est le code utilisé en fait, TreeSet
utilisant une TreeMap en interne) le
montre:

public Object put(Object key, Object value) {
Entry t = root;

if (t == null) {
incrementSize();
root = new Entry(key, value, null);
return null;
}

while (true) {
int cmp = compare(key, t.key);
^^^^^^^
if (cmp == 0) {
return t.setValue(value);
} else if (cmp < 0) {
if (t.left != null) {

[SNIP]
private int compare(Object k1, Object k2) {
return (comparator==null ? ((Comparable)k1).compareTo(k2)
: comparator.compare(k1, k2));
=========> ^^^^ Comparateur utilisé ^^^^^
}


Dans la doc de l'interface Set (super interface de SortedSet que la classe
TreeSet implémente, on lit :

add

public boolean add(Object o)

Adds the specified element to this set if it is not already present (optional
operation).
More formally, adds the specified element, o, to this set if this set contains no element
e
such that (o==null ? e==null : o.equals(e)).
^^^^^^^ LE CONTRAT FORMEL PARLE DE LA METHODE
EQUALS ^^^^^


If this set already contains the specified element,
the call leaves this set unchanged and returns false.
In combination with the restriction on constructors,
this ensures that sets never contain duplicate elements.

The stipulation above does not imply that sets must accept all
elements; sets may refuse to add any particular element, including null, and throwing an
exception,
as described in the specification for Collection.add.
Individual set implementations should clearly document any restrictions
on the the elements that they may contain.


A mon sens, on a ici clairement affaire à une incohérence entre quelque
chose de stipulé par la doc et l'implémentation réelle.

L'explication de tout ça vient de la doc de l'interface Comparator qui dit
que la méthode compare lorsque qu'elle renvoie 0 est considéré comme
identique à la méthode equals d'un object lorsqu'elle renvoie vrai.

On peut donc conclure à l'impossibilité de classer ces quatres apôtres
par age ( 19, 20, 20 et 21 ans ) en
suivant la méthode du comparateur et de l'insertion dans un SortedSet.

D'ou ma question.


Jérôme.

--
--
I feel partially hydrogenated!
----------------------------
jerome.eteve_at_it-omics.com

Le 03.12 2003, Jéjé s'est levé et s'est dit : "tiens, si j'écrivais aux
mecs de fr.comp.lang.java ?"

Salut à tous. Voici une petit discussion sur les SortedSet.

Miam ! J'adore jouer avec ces collections !

J'aimerais avoir vos avis éclairés sur le sujet.

Merci et bonne lecture !!


Pour commencer un petit code:

J'ai enlevé les morceaux inutiles.

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

/**
* @author jerome.eteve@it-omics.com

Ce serait pas à côté de Lille, ton truc ?
Et ils embaucheraient pas des développeurs java, par hasard ?

* on 2 déc. 2003
*/
public class SortedSetTry {

public class Item{

Je passe sur l'utilisation de classes internes (c'est mal) parce que
c'est un exemple.

Integer v;

public Item(int v){
this.v = new Integer(v);
}

public Integer getV(){ return v ;}

}

Comme equals n'est pas surchargée, on peut supposer que tu vas utiliser
le equals de Object, lequel fait appel aux références en mémoire des
objets (ce qu'on appelait jadis des "pointeurs").

protected class ItemComparator implements Comparator{

/* (non-Javadoc)
* @see java.util.Comparator#compare(java.lang.Object,
java.lang.Object) */
public int compare(Object o1, Object o2) {
Item i1 = (Item)o1;
Item i2 = (Item)o2;
// TODO Auto-generated method stub
int diff = i1.getV().compareTo(i2.getV());
if ( diff == 0 ){ diff++;}

Donc en gros, tu compares tes deux objets et, si ils sont égaux, tu
retourne un.
Je vais pas faire mon chieur, mais là, rien qu'avec cette instruction, tu
violes gravement le contrat d'implémentation de Comparator. Je cite :

It is generally the case, but not strictly required that (compare(x, y)= 0) == (x.equals(y)). Generally speaking, any comparator that violates
this condition should clearly indicate this fact. The recommended
language is "Note: this comparator imposes orderings that are
inconsistent with equals."

Le point intéressant est que, si ton comparateur n'est pas consistant
avec égal, tu as intérêt à le faire plutôt balaise, pour qu'il produise
un ordre total, ce qui n'est manifestement pas le cas du tien. En effet,
dans ton cas (si j'appelle A(x) un objet contenant la valeur entière x),
ton comparateur va donner o1(x)<o2(x) et o2(x)<o1(x), ce qui donne une
belle salade pour ton SortedSet.

return diff;
}

}

public static void main(String[] args) throws Exception{
SortedSetTry sst = new SortedSetTry();

Pas vraiment la peine d'instancier cet objet, mais c'est pas grave, car
c'est là qu'on commence à bien rigoler.

SortedSet set = new TreeSet(sst.new ItemComparator());

Tu utilises donc une collection ordonnée utilisant le comparateur bancal
défini plus haut.

for ( int i = 1 ; i <= 5 ; ++i){
set.add(sst.new Item(i));
}
for( int i = 5 ; i >= 1 ; --i){
set.add(sst.new Item(i));
}


Item f = (Item)set.first();
System.out.println(" First : " + f);
System.out.println(" Contains : " + set.contains(f));
System.out.println(" Remove : " + set.remove(f));

}

}

Sa sortie:

First : sandbox.SortedSetTry$Item@194df86
Contains : false
Remove : false

Logique. (explication plus bas).

Maintenant, si on enlève la ligne if ( diff == 0 ){ diff++;} dans
la méthode de comparaison et qu'on ajoute un
System.out.println(" Size " : set.size()); :

Il aurait été bon de l'écrire dans la première version (celle avec le
diff bidulé) pour confirmer que la taille de la collection valait bien
10.

Size : 5
First : sandbox.SortedSetTry$Item@194df86
Contains : true
Remove : true

Alors qu'on pensait avoir inséré 10 items et non cinq.

Non, non, dans ce TreeSet, avec ce Comparateur, on a bien ajouté cinq
items.

Si on regarde la doc des méthodes contains et remove d'un sorted set,
voici ce qu'on apprend:

Il faut aussi, et surtout, regarder celle de TreeSet(Comparator) et de
TreeSet.add()

*contains*

[=public boolean contains(Object o)]

Returns true if this set contains the specified element. More
formally,
returns true if and only if this set contains an element e such that
(o==null ? e==null : o.equals(e)).

Pareillement, la methode add et la methode remove d'un Set
(ou d'un SortedSet) sont sensée d'après la doc utiliser la méthode
equals sur les objects.

*Ces méthodes devraient selon la doc utiliser la méthode equals
sur o et non un cas particulier de la méthode compare.*

C'est pourtant ce qui arrive.

Et c'est d'ailleurs bien pratique, et nettement plus logique, non ?

Voyons maintenant pourquoi ça se passe comme ça. En fait, il y a deux
étapes, l'ajout, et la recherche.
A l'ajout, on vérifie que l'entrée n'existe pas déja (!contains), donc on
recherche l'objet. Comment se passe cette recherche ?
Le TreeSet ne va pas se fouler à faire une recherche sur toutes les
entrées, il va seulement utiliser celles pour lesquelles compareTo==0.
C'est une optimisation logique, tant que conpareTo est consistant avec un
ordre total plausible. plus clairement, tant que compareTo et equals
donnent des résultats cohérents, tou va bien; Ca n'est pas ton cas.

C'est d'ailleurs clairement expliqué dans la javadoc de TreeSet :

Note that the ordering maintained by a set (whether or not an explicit
comparator is provided) must be consistent with equals if it is to
correctly implement the Set interface. (See Comparable or Comparator for
a precise definition of consistent with equals.) This is so because the
Set interface is defined in terms of the equals operation, but a TreeSet
instance performs all key comparisons using its compareTo (or compare)
method, so two keys that are deemed equal by this method are, from the
standpoint of the set, equal. The behavior of a set is well-defined even
if its ordering is inconsistent with equals; it just fails to obey the
general contract of the Set interface.


En français, ça donne : Le TreeSet sera compatible avec l'interface set
tant que la comparaison utilisée donnera des résultats compatibles avec
la méthode equals. Et ça n'est pas ton cas.

Voici des implications très désagréables:

Imaginons que vous vouliez afficher des personnes triées
par age en utilisant un sortedSet (pourquoi pas, ca parait être
une méthode valable et simple).

Et ça marche très bien.

Jean 19 ans, Pierre 20 ans, Paul 20 ans, Mattieu 21 ans.

Vous implémentez en toute innocence un comparateur qui donne ceci:
compare(p1,p2) { return p2.age - p1.age ;}

Ca marchera sans problème, je t'encourage à essayer.

Et bien, si vous utilisez ce comparateur, il devient impossible
d'inserer Paul après que vous ayez inséré Pierre.

C'est normal, puisque là encore, si deux objets sont égaux au sens de ton
comparateur, ils ne le sont pas au sens de equals.

Comment résoudre ce casse tête ?

En utilisnt un comparateur plus malin :
si j'avais à implémenter ce genre de cas, je testerais tous les chaps
pour lesquels la comparaison à un sens dans un ordre de priorité.
Par exemple, ici, je veux trier d'abord par l'âge, puis par le prénom, il
me semble. Et là, tu pourras insérer Paul après avoir inséré Pierre.

Et, comme le rappelait Jérôme, si jamais dans ce cas j'ai à surcharger
equals, je n'oublierais pas de surcharger hashCode. parce que le même
problème, mais en beaucoup plus lourd, peut arriver dans les HashMap. en
beaucoup plus lourd, parce qu'il n'est pas évident de penser que hashCode
est la clé de rangement dans une HashMap ;-)

Etonnant non ?

Ben ... Non.

--
Nicolas Delsaux
"A lutter avec les mêmes armes que ton ennemi, tu deviendras comme lui."
Friedrich Nietzsch

Dans l'article <XnF9446B1A5C52FCnicolasdelsauxonline@213.228.0.136>,
"Nicolas Delsaux" <nicolas.delsaux@online.fr.invalid> a tapoté :

Le 03.12 2003, Jéjé s'est levé et s'est dit : "tiens, si j'écrivais aux
mecs de fr.comp.lang.java ?"

Ce serait pas à côté de Lille, ton truc ? Et ils embaucheraient pas des
développeurs java, par hasard ?

Oui oui, à coté de Lille. Les embauches de developpeurs java ne sont pas
à l'ordre du jour. Pkoi ? Tu penses qu'il faudrait me remplacer ? ;)

En utilisnt un comparateur plus malin : si j'avais à implémenter ce
genre de cas, je testerais tous les chaps pour lesquels la comparaison à
un sens dans un ordre de priorité. Par exemple, ici, je veux trier
d'abord par l'âge, puis par le prénom, il me semble. Et là, tu pourras
insérer Paul après avoir inséré Pierre.

Merci pour ces explications limpides.
J'implémente de ce pas la solution de la comparaison avec ordre de
priorité. Je crois bien que j'avais du mal avec la notion d'ordre total.


--
--
You are a wish to be here wishing yourself.
-- Philip Whalen
----------------------------
jerome.eteve_at_it-omics.com

Le 03.12 2003, Jéjé s'est levé et s'est dit : "tiens, si j'écrivais aux
mecs de fr.comp.lang.java ?"

Merci pour ces explications limpides.
J'implémente de ce pas la solution de la comparaison avec ordre de
priorité. Je crois bien que j'avais du mal avec la notion d'ordre total.

Je crois aussi.

Mais rassures-toi, c'est une notion qui est très loin d'être évidente.

--
Nicolas Delsaux
"Etre un humain était bien, j'y ai même pris du plaisir. Mais être un
cyborg a tellement plus à offrir"
Kevin Warwick

On ne peut pas parler de bug, puisque la spécification met en garde
spécifiquement contre cette utilisation de TreeSet. Voici ce que dit la
JavaDoc :

"Note that the ordering maintained by a set (whether or not an explicit
comparator is provided) must be consistent with equals if it is to
correctly implement the Set interface. (See Comparable or Comparator for
a precise definition of consistent with equals.) This is so because the
Set interface is defined in terms of the equals operation, but a TreeSet
instance performs all key comparisons using its compareTo (or compare )
method, so two keys that are deemed equal by this method are, from the
standpoint of the set, equal. The behavior of a set is well-defined even
if its ordering is inconsistent with equals; it just fails to obey the
general contract of the Set interface."

En d'autres termes, on doit garantir que
a.equals(b) <=> compare(a,b) = 0
ce qui n'est pas le cas de la structure que tu suggères.

Vous implémentez en toute innocence un comparateur qui donne ceci:
compare(p1,p2) { return p2.age - p1.age ;}

Ce n'est pas innocent. :) TreeSet gère correctement les ensembles
admettant un ordre total mais pas ceux n'admettant qu'un ordre partiel.

Il suffirait pour obtenir la propriété ci-dessus de définir un
comparateur spécifiant un ordre total et non un ordre partiel: comparer
d'abord sur l'âge, puis secondairement sur le prénom.

Laurent
http://bossavit.com/