Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > TreeSet.contains and an OVERLOADED equals...works?

Reply
Thread Tools

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

 
 
LastHope
Guest
Posts: n/a
 
      08-28-2007
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.jsp...sageID=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

 
Reply With Quote
 
 
 
 
Patricia Shanahan
Guest
Posts: n/a
 
      08-28-2007
LastHope wrote:
> 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.jsp...sageID=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

 
Reply With Quote
 
 
 
 
LastHope
Guest
Posts: n/a
 
      08-28-2007
>
> 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

 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      08-29-2007
LastHope wrote:
>> 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


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
 
Reply With Quote
 
Zig
Guest
Posts: n/a
 
      08-29-2007
On Tue, 28 Aug 2007 21:47:33 -0400, Patricia Shanahan <(E-Mail Removed)> wrote:

> 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
 
Reply With Quote
 
LastHope
Guest
Posts: n/a
 
      08-29-2007
On Aug 29, 5:40 am, Zig <(E-Mail Removed)> wrote:
> On Tue, 28 Aug 2007 21:47:33 -0400, Patricia Shanahan <(E-Mail Removed)> wrote:
> > 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).
>


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/ap...va.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

 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      08-29-2007
LastHope wrote:
> 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/ap...va.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,
<http://java.sun.com/javase/6/docs/api/java/lang/Comparable.html>
> 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.


--
Lew
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Overloaded typecast operators and copy constructors masood.iqbal@lycos.com C++ 1 02-07-2005 01:34 AM
Overloaded << and >> - Why Friend, Help TJ C++ 3 04-26-2004 09:32 PM
[lame] overloaded fun. virt. and inherity Rafal 'Raf256' Maj C++ 2 10-14-2003 05:58 PM
overloaded global operator new/new[] and corresponding deletes question Dodo C++ 1 08-26-2003 01:59 PM
overloaded >> and istream delimiters Todd Beauchemin C++ 1 07-31-2003 05:53 PM



Advertisments