CODEWITHSUNDEEP
java
user291701
user291701

Reputation: 39691

SortedSet - sorting and equality tests not working as expected

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'.

Upvotes: 2

Views: 2229

Answers (1)

Amit Deshpande
Amit Deshpande

Reputation: 19185

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

Upvotes: 5

Related Questions