Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Sort Order, Duplicacy and ClassCastException in TreeSet

Md. Minhajur Rahman
Ranch Hand
Posts: 33
I think, Sort order Rules has to define in CompareTo() method (of Comparable interface) or compare method (of Comparator interface). Both return int value.
So what i did in following program, If it returns -1 (at line 15), then I have found almost Descending sort order with one unsorted.

output:
TreeSetTest 4
TreeSetTest 3
TreeSetTest 3
TreeSetTest 2
String 1
String 2

Case1(SortOrder):
Q1: Why "String 1" is before "String 2" ?

Case2(Duplicate):
Q2: why TreeSetTest 3 is duplicate but String 2 is not ?

Case 3 (Class Class Exceptions):
Q3: If it returns 1 (at line 15) and discard line 27, Then I have found descending order. But If it returns 1 (at line 15) and don't discard line 27, Why Class Class Exception is thrown?

Q4: If it returns -1 (at line 15) and only discard line 27, Why Class Class Exception is thrown?

Q4: If it returns -1 (at line 15) and only discard line 25, Why Class Class Exception is thrown?

Q5: String Object and TreeSetTest Object are two different objects. It is supposed not to be possible to be added in same collection. But Why does the above program allow it?

Stephan van Hulst
Bartender
Posts: 6337
79
There is no general answer for your first four questions. The problems are all caused by the fact that your compareTo() method is broken. The comparison should be reflexive, transitive and commutative. This means that if x, y and z are comparable, then if x.compareTo(x) should return 0; if x.compareTo(y) < 0, then y.compareTo(x) > 0; and if x.compareTo(y) > 0 and y.compareTo(z) > 0, then x.compareTo(z) > 0 and vice versa. Since you always return the same value, there's no way you can fulfill this contract.

Furthermore, your implementation is not consistent with equals. Consistent with equals means that if x.equals(y), then x.compareTo(y) == 0. If not, then x.compareTo(y) != 0. This is the reason you're getting duplicates in your set.

Finally, the reason you can add different types to the same set, is because you're using raw generic types. Don't do this. Instead of doing Set set = new TreeSet(); do Set<TreeSetTest> set = new TreeSet<>();

Tim McGuire
Ranch Hand
Posts: 820
Md. Minhajur Rahman wrote:
output:
TreeSetTest 4
TreeSetTest 3
TreeSetTest 3
TreeSetTest 2
String 1
String 2

Case1(SortOrder):
Q1: Why "String 1" is before "String 2" ?

because String uses its own compareTo, not the one you have here.

Case2(Duplicate):
Q2: why TreeSetTest 3 is duplicate but String 2 is not ?

it will duplicate TreeSetTest 3 because your equals method is comparing an object with a String using String's equals method and Strings equals method uses instance of String to check equals and this will never be true, so the second TreeSetTest 3 will be allowed into the Set

Case 3 (Class Class Exceptions):
Q3: If it returns 1 (at line 15) and discard line 27, Then I have found descending order. But If it returns 1 (at line 15) and don't discard line 27, Why Class Class Exception is thrown?

Q4: If it returns -1 (at line 15) and only discard line 27, Why Class Class Exception is thrown?

this happens because objects introduced to the TreeSet will use their own compareTo. If you compare a string with a TreeSetTest, String's compareTo() will blow up because it attempts to
cast a TreeSetTest (the object used as argument to the compareTo method in the String class) to a String.

Q4: If it returns -1 (at line 15) and only discard line 25, Why Class Class Exception is thrown?

Q5: String Object and TreeSetTest Object are two different objects. It is supposed not to be possible to be added in same collection. But Why does the above program allow it?

This is not a rule. Maybe you are thinking of Arrays. Collections are collections of objects (unless you use generics and then that is only a compiler check. The JVM would still allow it.

Md. Minhajur Rahman
Ranch Hand
Posts: 33
Thanks a lot to Stephan van Hulst and Tim McGuire.
Stephan van Hulst wrote:
The problems are all caused by the fact that your compareTo() method is broken. The comparison should be reflexive, transitive and commutative. This means that if x, y and z are comparable, then if x.compareTo(x) should return 0; if x.compareTo(y) < 0, then y.compareTo(x) > 0; and if x.compareTo(y) > 0 and y.compareTo(z) > 0, then x.compareTo(z) > 0 and vice versa. Since you always return the same value, there's no way you can fulfill this contract.

I understood, compareTo() is not well defined and is not consistent with equals as always return -1, that's why sort order is not consistent.

Stephan van Hulst wrote:
Furthermore, your implementation is not consistent with equals. Consistent with equals means that if x.equals(y), then x.compareTo(y) == 0. If not, then x.compareTo(y) != 0. This is the reason you're getting duplicates in your set.

So, Actually You are saying, x.compareTo(y) == 0 takes care of duplicacy not x.equals(y) method in sorted set/ map. But Set/map other than sorted set/ map, x.equals(y) takes care of duplicacy.
As compareTo() returns -1, compareTo() allows duplicate of TreeSetTest 3, this should returns 0, in this case. right Stephan?
Stephan van Hulst wrote:
Finally, the reason you can add different types to the same set, is because you're using raw generic types. Don't do this. Instead of doing Set set = new TreeSet(); do Set<TreeSetTest> set = new TreeSet<TreeSetTest>();

Thanks Stephan.

Tim McGuire wrote:
it will duplicate TreeSetTest 3 because your equals method is comparing an object with a String using String's equals method and Strings equals method uses instance of String to check equals and this will never be true, so the second TreeSetTest 3 will be allowed into the Set

Thanks Tim, I understood, With same value, TreeSetTest object and String object can never be equal as i defined in TreeSetTest class. Strings equals also return false as instance of check fails in String class. I understood, This case ie. equals method() avoid duplicacy in unsorted set/ map.
But for the case, sorted set/map like TreeSet/ Treemap, duplicacy is handled by compareTo() method. Tim, Please correct me if i am wrong. I understood this from Stephan's reply and
java doc
suppose one adds two elements a and b such that (a.equals(b) && c.compare(a, b) != 0) to an empty TreeSet with comparator c. The second add operation will return true (and the size of the tree set will increase) because a and b are not equivalent from the tree set's perspective, even though this is contrary to the specification of the Set.add method.

Ok, Understood Sort Order and Duplicacy. But Still having trouble understanding Class Class Exception. So far i understood, compareTo() method causes this Class Class Exception when calling on String Object passing TreeSetTest object.

But my question is, Shouldn't it be thrown in all cases?
Q6. Why Class Class Exception is not thrown in above program demonstrated in case1 ( not likes defined as Q3, Q4, Q4).
Q7. Why Class Class Exception is thrown only in scenery in case2( defined Q3, Q4, Q4)?.
Q8. When set.add(new String("String 2")) is called, Does compareTo() method is called on String Object passing into it as an argument each object already have in Collection ie. if there are a,b,c in set collection and set.add(object) is called, then Are object.compareTo(a), object.compareTo(b), object.compareTo(c) called? or Are a.compareTo(object), b.compareTo(object), c.compareTo(object) called?

Henry Wong
author
Marshal
Posts: 21511
84
Md. Minhajur Rahman wrote:

Ok, Understood Sort Order and Duplicacy. But Still having trouble understanding Class Class Exception. So far i understood, compareTo() method causes this Class Class Exception when calling on String Object passing TreeSetTest object.

But my question is, Shouldn't it be thrown in all cases?

The String class implements the Comparable<String> interface, which only allows it to be comparable to other Strings. Your class, however, just implemented the Comparable interface, which technically allows it to be compared to any Object. If you want it in all cases, then you need to implement Comparable<TreeSetTest> instead.

Henry

Md. Minhajur Rahman
Ranch Hand
Posts: 33
Henry Wong wrote:
Md. Minhajur Rahman wrote:

Ok, Understood Sort Order and Duplicacy. But Still having trouble understanding Class Class Exception. So far i understood, compareTo() method causes this Class Class Exception when calling on String Object passing TreeSetTest object.

But my question is, Shouldn't it be thrown in all cases?

The String class implements the Comparable<String> interface, which only allows it to be comparable to other Strings. Your class, however, just implemented the Comparable interface, which technically allows it to be compared to any Object. If you want it in all cases, then you need to implement Comparable<TreeSetTest> instead.

Henry

Thanks a lot Henry. But i am still wondering why class cast exception is not thrown in the above program. First I have added at line 25, a string object. then at line 26, i have added a TreeSetTest object. what actually happens when this object is added. What i am thinking, when a TreeSetTest object is trying to be added, compareTo() method is called on TreeSetTest object is being passed already added String Object internally. As my TreeSetTest's compareTo() is called and this actually returns -1 which means this object has not been in collection yet, No exception needs to be thrown, So this TreeSetTest object is added in collection set. Then at line 27, again a String is trying to be added and it is being passed a string Object and a TreeSetTest object which are already in collection set. So when this string object is comparing using it's compareTo(), no ClassCast Exception should be thrown when it was comparing to String Object, After that when it is going to compare with TreeSetTest object passing as argument, I think Here It should be thrown a classCast Exception. But it didn't. I couldn't understand this. Please anyone help why it didn't throw a class cast exception?

Henry Wong
author
Marshal
Posts: 21511
84
Md. Minhajur Rahman wrote:
Thanks a lot Henry. But i am still wondering why class cast exception is not thrown in the above program. First I have added at line 25, a string object. then at line 26, i have added a TreeSetTest object. what actually happens when this object is added. What i am thinking, when a TreeSetTest object is trying to be added, compareTo() method is called on TreeSetTest object is being passed already added String Object internally. As my TreeSetTest's compareTo() is called and this actually returns -1 which means this object has not been in collection yet, No exception needs to be thrown, So this TreeSetTest object is added in collection set. Then at line 27, again a String is trying to be added and it is being passed a string Object and a TreeSetTest object which are already in collection set. So when this string object is comparing using it's compareTo(), no ClassCast Exception should be thrown when it was comparing to String Object, After that when it is going to compare with TreeSetTest object passing as argument, I think Here It should be thrown a classCast Exception. But it didn't. I couldn't understand this. Please anyone help why it didn't throw a class cast exception?

You have elements in a set that .... (1) don't play nice with each other, (2) are not reflexive, symmetric, or transitive, (3) are not consistent between comparable and equals, ie. are completely broken, and you are wondering why the corrupted TreeSet is not broken correctly?

One option to try out. Change "string 2" to something less that "string 1". And see what happens.

Henry