File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Problem in implementing a TreeSet Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Problem in implementing a TreeSet" Watch "Problem in implementing a TreeSet" New topic
Author

Problem in implementing a TreeSet

Anil Giri
Greenhorn

Joined: Jun 04, 2009
Posts: 9
I am trying to creat a TreeSet of "Person" objects. I expect that no duplicates shall be allowed to be added and that the "persons" shall be automatically sorted on the criteria as defined in the Comparator:compare The code follows:


The output I get is as follows:


I am not able to figure out, why is this TreeSet allowing duplicate entries. As is evident, persons with same name e.g. T1or T3 must be treated as equal.
Please help me out.


SillyCon!
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38087
    
  22
Because Trees use compareTo/compare, not equals. You are returning true from equals when there are fields with different values in the same object. The Comparator finds those differences.

By the way: your equals method with instanceof is only reliable is you declare the Person class final. You shouldn't write
if ( booleanExpression ) return true; else return false;
You should write
return booleanExpression;
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18550
    
  40

Anil Giri wrote:
I am not able to figure out, why is this TreeSet allowing duplicate entries. As is evident, persons with same name e.g. T1or T3 must be treated as equal.


Your comparator is not valid. If you read the JavaDoc on the Comparator, you will notice that your comparator must enforce "total ordering" which it does not. Here is an example of why it fails...

Let's say you have three items - A, B, and C. A & B has the same name, while C is different.

A is first added to the set. No problem. B is then added to the set. Duplicate. No allowed. No problem. C is then added. No problem. Everything works.

Let's change the order.

A is first added to the set. No problem. C is then added to the set. No problem. B is then added. Now... What happens?

1. If B is first compared to A. It will be found as a duplicate. No problem.

2. If B is first compared to C, then it will be sorted depending on the order. So...

2a. If both A and B are both greater than or less than C, then they will fall on the same side as C, causing A and B to be compared, and found as a duplicate. No problem.

2b. If A and B don't compare the same with C -- meaning one is greater than and one is less than C, then there is no reason to compare A and B... because how can A and B be equal? One is greater and one is less than C. The ordering is ACB or BCA.

Henry

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Anil Giri
Greenhorn

Joined: Jun 04, 2009
Posts: 9
Thank you very much Mr. Wong and Ritchie.
@Mr. Wong, I got the problem sir. But isn't it true that for the purposes of ensuring set property (i.e. uniqueness) the TreeSet will use the equals() function rather than the comparator.

Further, could someone suggest me a solution. I wish to avoid duplicates and keep the elements sorted on priorityOne>>PriorityTwo>>Name.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18550
    
  40

Anil Giri wrote:Further, could someone suggest me a solution. I wish to avoid duplicates and keep the elements sorted on priorityOne>>PriorityTwo>>Name.


Simple. You need to keep your comparator consistent with your equals. Have your comparator compare via priority one first, then priority two, then name. And have your equals method require equality on priority one, priority two, and name.

You can't have it both ways. You can't say two items are are greater or less than one another based on priority, but if there names are the same, then ignore the priority. Total ordering requires comparisons to be transitive, and this requirement isn't.


As a subtle note, this isn't really a case of you keeping the equals and comparator consistent. This is more of a case of the comparator not being valid. Your comparator needs to support total ordering.

Henry
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38087
    
  22
Anil Giri wrote:Thank you very much Mr. Wong and Ritchie.
. . . the TreeSet will use the equals() function rather than the comparator. . . .
Did you read the previous posts?
 
 
subject: Problem in implementing a TreeSet
 
Similar Threads
Using classes as Keys in Map problem
Question 10 Chapter 7 : K and B
equals hashcode doubt sjcp 1.4
Strings
Please Explain (Hashcode)