Problem in implementing a TreeSet

[Anil Giri]

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:

import java.util.*;

import java.util.Comparator;
import java.util.Set;



class Person {
	String name;
	int priorityOne,priorityTwo;
	Set<String> chkdVars; 
		
	public Person(String testID,int p1, int p2, Set<String> vars){
		this.name=testID;
		this.priorityOne=p1;
		this.priorityTwo=p2;
		this.chkdVars=vars;
	}
	
	public boolean equals (Object o) {
		if ((o instanceof Person)&& ( (((Person)o).name) == (this.name) ))
			return true;
		else return false;
	}
	
	public int hashcode() {
		return name.hashCode();
	}
	
	public String toString() {
		return (name+'\t'+priorityOne+'\t'+priorityTwo+'\t'+chkdVars.toString()+"\n");
	}
	
}

class PersonComparator implements Comparator<Person> {
	 public int compare (Person t1, Person t2) {
		 if(t1.equals(t2))
			 return 0;
		 else if (t1.priorityOne < t2.priorityOne)
			 return -1;
		 else if (t1.priorityOne > t2.priorityOne)
			 return 1;
		 else if ((t1.priorityOne==t2.priorityOne)&&(t1.priorityTwo < t2.priorityTwo))
			 return -1;
		 else if ((t1.priorityOne==t2.priorityOne)&&(t1.priorityTwo > t2.priorityTwo))
			 return 1;
		 else 
			 return ((t1.name).compareTo(t2.name));
	 }
}

public class ChkComparator {
	public static void main(String args[] ) {
		Set<Person> testcaseset =new TreeSet<Person>(new PersonComparator());
		
		Set<String> tmpSet= new HashSet<String>();
		tmpSet.add("a");
		tmpSet.add("b");
		
		System.out.println(testcaseset.add(new Person("T1",1,1,new HashSet<String>(tmpSet))));
		tmpSet.add("d");
		System.out.println(testcaseset.add(new Person("T2",1,2,new HashSet<String>(tmpSet))));
		tmpSet.add("e");
		System.out.println(testcaseset.add(new Person("T1",0,1,new HashSet<String>(tmpSet))));
		tmpSet.add("f");
		System.out.println(testcaseset.add(new Person("T3",2,1,new HashSet<String>(tmpSet))));
		tmpSet.add("g");
		System.out.println(testcaseset.add(new Person("T3",1,1,new HashSet<String>(tmpSet))));
		tmpSet.add("i");
		System.out.println(testcaseset.add(new Person("T3",3,1,new HashSet<String>(tmpSet))));
		
		System.out.println(testcaseset.add(new Person("T2",2,1,new HashSet<String>(tmpSet))));
		
		Set<Person> duplset=new HashSet<Person>();
		duplset.add(new Person("T1",2,3,new HashSet<String>(tmpSet)));
		duplset.add(new Person("T3",0,3,new HashSet<String>(tmpSet)));
		duplset.add(new Person("T2",2,1,new HashSet<String>(tmpSet)));
		System.out.println(testcaseset.addAll(duplset));
		
		Person x1=new Person("T1",1,1,new HashSet<String>(tmpSet));
		Person x2=new Person("T1",2,3,new HashSet<String>(tmpSet));
		
		System.out.println(testcaseset);
		System.out.println("Checking if Equals works: "+x1.equals(x2));
	}

}
    

The output I get is as follows:

  true
true
false
true
true
false
false
true
[T3	0	3	[f, g, d, e, b, a, i]
, T1	1	1	[b, a]
, T3	1	1	[f, g, d, e, b, a]
, T2	1	2	[d, b, a]
, T3	2	1	[f, d, e, b, a]
, T1	2	3	[f, g, d, e, b, a, i]
]
Checking if Equals works: true  

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.

[Campbell Ritchie]

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]

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

[Anil Giri]

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]

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]

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?