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

Discussion in 'Java' started by LastHope, Aug 28, 2007.

  1. LastHope

    LastHope Guest

    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
     
    LastHope, Aug 28, 2007
    #1
    1. Advertising

  2. 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.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
     
    Patricia Shanahan, Aug 28, 2007
    #2
    1. Advertising

  3. LastHope

    LastHope Guest

    >
    > 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
     
    LastHope, Aug 28, 2007
    #3
  4. 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
     
    Patricia Shanahan, Aug 29, 2007
    #4
  5. LastHope

    Zig Guest

    On Tue, 28 Aug 2007 21:47:33 -0400, Patricia Shanahan <> 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
     
    Zig, Aug 29, 2007
    #5
  6. LastHope

    LastHope Guest

    On Aug 29, 5:40 am, Zig <> wrote:
    > On Tue, 28 Aug 2007 21:47:33 -0400, Patricia Shanahan <> 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/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
     
    LastHope, Aug 29, 2007
    #6
  7. LastHope

    Lew Guest

    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/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,
    <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
     
    Lew, Aug 29, 2007
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Edward A Thompson
    Replies:
    4
    Views:
    532
    Tony Morris
    Feb 11, 2004
  2. GeorgeH
    Replies:
    3
    Views:
    480
    Patricia Shanahan
    Oct 14, 2006
  3. Ye Dafeng

    HashSet and TreeSet

    Ye Dafeng, Nov 15, 2006, in forum: Java
    Replies:
    4
    Views:
    1,657
    Mike Schilling
    Nov 16, 2006
  4. StM
    Replies:
    4
    Views:
    1,748
  5. Karsten Wutzke

    Contains/equals

    Karsten Wutzke, Aug 19, 2010, in forum: Python
    Replies:
    7
    Views:
    365
    Hrvoje Niksic
    Aug 24, 2010
Loading...

Share This Page