TreeSet.contains and an OVERLOADED equals...works?

[LastHope]

Hi to all,
today I've come across this strange behaviour in my code, and I tried
to set-up a little test...I don't know if it's already known or
not...didn't find any of this through google,except of this:
http://forum.java.sun.com/thread.jspa?threadID=549491&messageID=2680884
However, no code is specified...
Take this class as an example:

---
public class Tipo implements Comparable<Tipo>
{
private int tipo;

public Tipo(int tipo)
{
this.tipo = tipo;
}

public boolean equals(Tipo t) {return tipo == t.tipo;}

public int compareTo(Tipo t) {return tipo - t.tipo;}
}
---

My error: equals doesn't support generics, and this is overloading,
not overriding the method...however, try this "test suite" :

---
import java.util.*;

public class TestTipaggio
{
public static void main(String[] args)
{
Tipo t1 = new Tipo(3);
Tipo t2 = new Tipo(3);
System.out.println("Are t1 and t2 'equal'? " + t1.equals(t2));
Object o1 = t1;
System.out.println("Are o1 and t2 'equal'? " + o1.equals(t2));
System.out.println("Are t2 and o1 'equal'? " + t2.equals(o1));
List<Tipo> tipoList = new ArrayList<Tipo>();
System.out.println("Can I add t1 to the list? " + tipoList.add(t1));
System.out.println("Does the list contain t2 (which is 'equal' to
t1)? " + tipoList.contains(t2));
Set<Tipo> tipoSet = new TreeSet<Tipo>();
System.out.println("Can I add t1 to the set? " + tipoSet.add(t1));
System.out.println("Can I add t2 to the set? " + tipoSet.add(t2));
System.out.println("So, Does the set contain t2 (which is 'equals'
to t1)? " + tipoSet.contains(t2));
}

}
---

My output (compiled both with jdk1.5.0_03 and jdk 1.6.0_01) is always
like this:

---
Are t1 and t2 'equal'? true
Are o1 and t2 'equal'? false
Are t2 and o1 'equal'? false
Can I add t1 to the list? true
Does the list contain t2 (which is 'equal' to t1)? false
Can I add t1 to the set? true
Can I add t2 to the set? false //weird
So, Does the set contain t2 (which is 'equals' to t1)? true //weird
---
It seems like it's calling the overloaded method, differently from the
ArrayList...and this doesn't respect what it says on the javadoc

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)).

Am I right? In any case, on my machine, the contains of TreeSet
behaves differently from the contains of ArrayList...
Thank you

LastHope

 

[Patricia Shanahan]

Hi to all,
today I've come across this strange behaviour in my code, and I tried
to set-up a little test...I don't know if it's already known or
not...didn't find any of this through google,except of this:
http://forum.java.sun.com/thread.jspa?threadID=549491&messageID=2680884
However, no code is specified...
Take this class as an example:

---
public class Tipo implements Comparable<Tipo>
{
private int tipo;

public Tipo(int tipo)
{
this.tipo = tipo;
}

public boolean equals(Tipo t) {return tipo == t.tipo;}

public int compareTo(Tipo t) {return tipo - t.tipo;}
}

Tipo has two versions of equals, "public boolean equals(Tipo t)",
declared in Tipo, and "public boolean equals(Object o)", declared in
Object and inherited by Tipo. These methods are inconsistent - the
inherited Object method considers each object to be equal to itself and
nothing else.

The compiler chooses between these two methods, based on the compile
time type of the argument. If the argument is of type Object, the Object
version is used, even if, at run time, it happens to reference a Tipo.

I think this explains all your results, but ask again if there is
anything that still does not make sense.

Incidentally, overriding equals without also overriding hashCode to keep
it consistent is scary. Maybe you don't intend to use any hash data
structures now, but it is a bug waiting to happen.

Patricia

 

[LastHope]

The compiler chooses between these two methods, based on the compile
time type of the argument. If the argument is of type Object, the Object
version is used, even if, at run time, it happens to reference a Tipo.

I agree to what you say, but what I can't understand is why in my
example it seems that the compiler chooses two different methods while
applying the same arguments:

---
System.out.println("Does the list contain t2 (which is 'equal' to t1)?
" + tipoList.contains(t2));
// returns false, which means that the argument is
treated as an Object, and so the Object version was used
System.out.println("So, Does the set contain t2 (which is 'equal' to
t1)? " + tipoSet.contains(t2));
// returns true, which means that the argument is
treated as a Tipo, and so the Tipo version was used
---
At compile time, the arguments are the same, but the choice is then
different.

Incidentally, overriding equals without also overriding hashCode to keep
it consistent is scary. Maybe you don't intend to use any hash data
structures now, but it is a bug waiting to happen.

Patricia

I do usually override also hashCode when developing (I've already
banged my head against the wall before reading more carefully the
Javadoc ). However, in this case I'm not overriding, but
overloading since I changed the signature of the equals method...and
that's what's confusing me: I thought because overloading and not
overriding it wouldn't work...instead "works partially", because once
the compiler chooses one method, and in the other case the
other...while at compile time the arguments seem the same to me, as
written above.
Thank you for your very kind answer.

LastHope

 

[Patricia Shanahan]

I agree to what you say, but what I can't understand is why in my
example it seems that the compiler chooses two different methods while
applying the same arguments:

---
System.out.println("Does the list contain t2 (which is 'equal' to t1)?
" + tipoList.contains(t2));
// returns false, which means that the argument is
treated as an Object, and so the Object version was used
System.out.println("So, Does the set contain t2 (which is 'equal' to
t1)? " + tipoSet.contains(t2));
// returns true, which means that the argument is
treated as a Tipo, and so the Tipo version was used

I don't think TreeSet<Tipo> contains uses equals at all. It uses
compareTo(Tipo) from the Comparable<Tipo> interface. TreeSet contains is
declared to throw "ClassCastException - if the specified object cannot
be compared with the elements currently in the set."

ArrayList, on the other hand, only requires an Object, and uses the
Object equals method in its comparison.

More generally, any time equals(Object), equals(otherType), and
compareTo are not consistent with each other you need to look VERY
closely at documentation, and in some cases at implementation, to work
out what is going to happen. Do you really need them to be inconsistent?

Patricia

 

[Zig]

I don't think TreeSet<Tipo> contains uses equals at all. It uses
compareTo(Tipo) from the Comparable<Tipo> interface.

Just for confirmation, you can check the javadocs for Comparable:

It is strongly recommended (though not required) that natural orderings be
consistent with equals. This is so because sorted sets (and sorted maps)
without explicit comparators behave "strangely" when they are used with
elements (or keys) whose natural ordering is inconsistent with equals. In
particular, such a sorted set (or sorted map) violates the general
contract for set (or map), which is defined in terms of the equals method.

For example, if one adds two keys a and b such that (!a.equals(b) &&
a.compareTo(b) == 0) to a sorted set that does not use an explicit
comparator, the second add operation returns false (and the size of the
sorted set does not increase) because a and b are equivalent from the
sorted set's perspective.

(note that the code in this sense has no knowledge that you're class has
an overloaded version of equals, and equals(Object) is the inconsistancy).

More generally, any time equals(Object), equals(otherType), and
compareTo are not consistent with each other you need to look VERY
closely at documentation, and in some cases at implementation, to work
out what is going to happen. Do you really need them to be inconsistent?

Quite right. I hope that this post is just as a thought problem.

HTH,

-Zig

 

[LastHope]

Just for confirmation, you can check the javadocs for Comparable:

It is strongly recommended (though not required) that natural orderings be
consistent with equals. This is so because sorted sets (and sorted maps)
without explicit comparators behave "strangely" when they are used with
elements (or keys) whose natural ordering is inconsistent with equals. In
particular, such a sorted set (or sorted map) violates the general
contract for set (or map), which is defined in terms of the equals method.

For example, if one adds two keys a and b such that (!a.equals(b) &&
a.compareTo(b) == 0) to a sorted set that does not use an explicit
comparator, the second add operation returns false (and the size of the
sorted set does not increase) because a and b are equivalent from the
sorted set's perspective.

(note that the code in this sense has no knowledge that you're class has
an overloaded version of equals, and equals(Object) is the inconsistancy).

That's cleared me, thank you . I have written this because I kept
reading instead the javadoc of contains method of TreeSet, which
doesn't mention this:

http://java.sun.com/javase/6/docs/api/java/util/TreeSet.html#contains(java.lang.Object)

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)).

Thank you both for your kind answers.

LastHope

 

[Lew]

That's cleared me, thank you . I have written this because I kept
reading instead the javadoc of contains method of TreeSet, which
doesn't mention this:

http://java.sun.com/javase/6/docs/api/java/util/TreeSet.html#contains(java.lang.Object)

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)).

That's the contract for the contains() method generally. Collections cannot
keep that contract for contained classes that violate the symmetry of
compareTo(), equals() and hashCode(). In particular,