SortedSet - sorting and equality tests not working as expected

Question

I have instances of a class which I'd like to sort in a particular order, but also be able to tell if an instance exists in a set using a different criteria. Example:

public class Foo {
    int x;
    int y;

    public Foo(int x, int y) { this.x = x; this.y = y }

    // equality determined by value of 'x':
    @Override 
    public boolean equals(Object obj) {
        if (obj instanceof Foo) {
            return ((Foo)obj).x == this.x;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return this.x;
    }

    @Override
    public int compareTo(Foo foo) {
        if (this.x < foo.x return -1;
        else if (this.x > foo.x return 1;
        return 0;
    }
}

...

// Would like to keep a set of Foos, but sorted by 'y' value.
// Passing in an explicit comparator which sorts on 'y'.
SortedSet<Foo> test = new TreeSet<Foo>(new ComparatorFoo());

public static class ComparatorFoo implements Comparator<Foo> {
    @Override
    public int compare(Foo o1, Foo o2) {
        if (o1.y < o2.y) return -1;
        else if (o1.y > o2.y) return 1;
        return 0;
    }
}

Now trying:

test.add(new Foo(3, 4));
test.add(new Foo(1, 2));
test.add(new Foo(5, 6));

// sorts by 'y' ok.
for (Foo foo : test) {
    System.out.println(foo.toString());
}

// but can't find an instance with the same 'x' value:
test.contains(new Foo(1, 999));

Do I need to keep two separate data structures to do this? (One for sorting, one for equality testing?)

Thank you

------ Update ---------

End result: the comparator used to initialize the SortedSet also gets used when contains() is invoked. Therefore I couldn't have the set sorted by 'y', and check for existence of an element by 'x'.

How does it compile when you override the compareTo method without implementing Comparable? You do not need this method, provided that you use a Comparator. — arjacsoh, Dec 03 '12 at 19:57

Amit Deshpande · Accepted Answer · 2012-10-30T18:05:44.160

5

You should define your compareTo consistent with equals

From java doc of SortedSet check the highlighted part.

Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface. (See the Comparable interface or Comparator interface for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

Change your comparator like below

public static class ComparatorFoo implements Comparator<Foo> {
    @Override
    public int compare(Foo o1, Foo o2) {
        if (o1.x < o2.x)
            return -1;
        else if (o1.x > o2.x)
            return 1;
        return 0;
    }
}

It will return you true

edited Oct 30 '12 at 18:05

answered Oct 30 '12 at 17:57

Amit Deshpande

19,001
4
46
72

Man. Didn't actually knew that. +1 – Rohit Jain Oct 30 '12 at 18:07
@RohitJain note that your answer was good but sadly it doesn't apply to `TreeSet`/`TreeMap`: [Java - TreeSet and hashCode()](http://stackoverflow.com/q/1470735/1065197) – Luiggi Mendoza Oct 30 '12 at 18:09
Correct, but in my case, I'd like to explicitly sort my set by the 'y' value. But I also want to know if an instance exists in the set using a given 'x' value. It doesn't seem like this is possible when the supplied comparator is sorting by 'y'? – user291701 Oct 30 '12 at 18:09
@LuiggiMendoza. Yeah, I actually didn't knew that, so I though this might be the reason. Thanks for the link though :) – Rohit Jain Oct 30 '12 at 18:11
@user291701: Yes, you will need to maintain two separate data structures -- unless you're willing to do an explicit linear-time search through the iterator instead of using the provided `contains` method. – Louis Wasserman Oct 30 '12 at 19:01

SortedSet - sorting and equality tests not working as expected

1 Answers1