CODEWITHSUNDEEP
javaequalshashsettreeset
Louis
Louis

Reputation: 89

Why doesn't TreeSet compare all elements before adding a new element?

I try to write a program that stores non-equal pair-objects, consisting of 2 Strings. For that matter, the pair (john, bob) is considered equal to (bob, john). My equals and compareTo implementations should work fine. To check whats wrong I let my program output the comparisions made for each new Pair I try to add. Looks like this:

@Override
public boolean equals(Object o){
    if (o==null){
        return false;
    }
    final Pair other = (Pair) o;
    return (this.compareTo(other)==0);
}



@Override
public int compareTo (Pair o){
  if (this.first.equals(o.first)){
      if (this.second.equals(o.second)){
          System.out.println("equal: "+this.first+" "+this.second+" and  " + o.first+" "+o.second);
          return 0;
      }
  }
  else if (this.first.equals(o.second)){
        if (this.second.equals(o.first)){
            System.out.println("equal: "+this.first+" "+this.second+" and  " + o.first+" "+o.second);
            return 0;
        }
  }
    System.out.println(" not equal " +this.first+" "+this.second+" and  " + o.first+" "+o.second);
  return -1;

Exampleinput:

 bob john
 john john
 john john
 john bob
 bob will
 john hohn

If I let this run it will print out the size of the TreeSat after each trial to add a new element. It will also print what is written in the compareTo method. I added comments to specifify my problem.

   equal: bob john and  bob john    //Why comparing the first element at  
                                      all?
1
 not equal john john and  bob john
2
 not equal john john and  bob john
equal: john john and  john john
2
equal: john bob and  bob john
2
 not equal bob will and  bob john
 not equal bob will and  john john
3

 not equal john hohn and  john john    //no comparision of (john hohn) and                                       
 not equal john hohn and  bob will     //(bob john) why?
4

Upvotes: 1

Views: 577

Answers (1)

Amadán
Amadán

Reputation: 758

ONE: To answer your question: TreeSet does not need to compare all elements, because there is a defined order for the elements. Consider a dictionary: open it in the middle and you will instantly know, if the word you need is before or after that page. You won't need to check both halfs of the dictionary.

TWO: Your compareTo() method is faulty. Consider two objects:

Pair a = Pair.of(1, 2);
Pair b = Pair.of(3, 4);

Your compareTo() will return -1 in both cases, wich it must not:

a.compareTo(b) == -1
b.compareTo(a) == -1

Mathematically spoken your relation "compareTo" does not define an order and thus violates the API contract:

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y.

Upvotes: 4

Related Questions