CODEWITHSUNDEEP
javacollectionssetlogictreeset
T_01
T_01

Reputation: 1359

How to fix a Comparator for use in TreeSet

I have a TreeSet with a custom comparator, but the remove() operation isn't working. Here is the code:

new TreeSet<>(new Comparator<Tile>(){
            public int compare(Tile o1, Tile o2){
                if(o1 == o2){
                    return 0;
                }
                if(o1.getValue() > o2.getValue()){
                    return 1;
                }
                return -1;
            }
        });

I think, with this comparator a duplicate is defined as o1 == o2, and de order is ascending based on getValue(). But something is wrong.. what?

Upvotes: 1

Views: 124

Answers (2)

Paul Boddington
Paul Boddington

Reputation: 37645

The way you have written compare doesn't meet the contract for that method. One of the conditions you must meet is:

sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y

But your compare method doesn't satisfy this condition because if you have two Tiles x and y satisfying x != y and x.getValue() == y.getValue() then compare(x, y) and compare(y, x) are both -1.

If you break the contract for compare, you get unpredictable results,

If you want two instances of Tile to only be considered duplicates if they have the same identity, then it is difficult to see how you could possibly meet the above condition, so a this rules out using a TreeSet. Instead you could use a HashSet where you don't override equals or hashCode for the class Tile. If you are not in control of the class Tile, and equals and hashCode are already overridden then you could use the keySet view of an IdentityHashMap or Guava's newIdentityHashSet(). Unfortunately these solutions don't keep the collection sorted.

If you need the collection to be sorted based on the values returned by getValue() and you only want to remove duplicates when the instances are identically equal, I don't think there's any sensible way of doing this. You could use an ArrayList which you keep sorted using Collections.sort (in combination with the comparator returning Double.compare(o1.getValue(), o2.getValue());). Whenever you need to remove duplicates you could do something like this

Map<Tile, Void> map = new IdentityHashMap<>();
for (Tile tile : list)
    map.put(tile, null);
list = new ArrayList<>(map.keySet());

Upvotes: 1

Todd
Todd

Reputation: 31700

o1 == o2

This is comparing object references, not the value. You aren't covering the case where the values are equal. Assuming the call to getValue() isn't expensive, I usually skip the object refrence equality check to make my code a bit simpler.

public int compare(Tile o1, Tile o2){
    if(o1.getValue() == o2.getValue()){
         return 0;
    }
    if(o1.getValue() > o2.getValue()){
         return 1;
    }
    return -1;
}

Or, more simply:

public int compare(Tile o1, Tile o2){
    return o1.getValue() - o2.getValue();
}

Upvotes: 3

Related Questions