.compareTo() with 2 Sorting-Columns

Question

I am trying to implement the comparable interface in Java for an object that I need to sort by two different columns/variables. I tried multiple approaches, and this one is the best so far:

public int compareTo(Object o) {
    Match m = (Match)o;
    int diff = m.matches - matches;
    if (diff == 0) {
        if (distance > m.distance) {
            return 1;
        } else if (distance < m.distance) {
            return -1;
        } else {
            return 0;
        }
    } else {
        return diff;
    }
}

but it still fails with

java.lang.IllegalArgumentException: Comparison method violates its general contract!

Any ideas what I'm doing wrong?

Side note 1: NPEs/ClassCastExceptions are expected, if o is null or of an unsuitable class - that is not the issue here.

Side note 2: I know about the change in the sorting algorithm in JDK 1.7, but I don't really see where I'm violating the contract here. So turning off the exception seems like the wrong solution.

Works for me in Java 7 without equals() http://ideone.com/lckk5 — Ray Toal, Jul 15 '12 at 21:31
You don't need to override `equals()`, was just wondering because the behavior of it and `compareTo()` can lead to violating the general contract. For example returning true for `.equals()` but returning non-zero for `compareTo()`. — Jon Lin, Jul 15 '12 at 21:38
Without NaNs, you should be good: http://ideone.com/u1HD9. With NaNs, ideone's Java 7 still works for me: http://ideone.com/OsixW. — Ray Toal, Jul 15 '12 at 21:40
Full stacktrace: http://ideone.com/7GV37 matches is an int, distance is a double, calculated using 2 lat/lng pairs. Would that result in NaNs? — Dexter, Jul 15 '12 at 21:41
+1 to Jon Lin. Without equals defined, you are likely to get two values with the same matches and distance value but they will compare as not equal because by default equals uses `==`. — Ray Toal, Jul 15 '12 at 21:42
@Ray Toal: Sorry about that - didn't select the proper language on the site. This is Java code. — Dexter, Jul 15 '12 at 21:45
just checking the obvious: does `int diff = m.matches - matches;` always return [-1,0,1] ? — maasg, Jul 15 '12 at 21:59
maasg: afaik it doesn't have to be in that range. Ray Toal: I don't know why Ideone's code doesn't fail with NaNs. I'm using Sun/Oracle's JVM too. — Dexter, Jul 15 '12 at 22:18

score 5 · Accepted Answer · edited May 23 '17 at 11:48

Since you say distance is a double, you likely have the same problem as described here:

Java error: "Comparison method violates its general contract!"

Perhaps:

public int compareTo(Object o) {
    Match m = (Match)o;
    int diff = m.matches - matches;
    if (diff == 0) {
        return Double.compare(distance, m.distance);
    } else {
        return diff;
    }
}

However ideally you should use the built-in comparison methods as I state below. The above code is an example of the "minimum change needed", illustrating the key problem.

Using existing comparison methods

Also, as @fabian-barney states in his answer, you should avoid taking the direct difference, and instead utilise the built-in comparison methods. So you should have something like:

public int compareTo(Object o) {
    Match m = (Match) o;
    return m.matches == matches ? Double.compare(m.distance, distance) : Integer.compare(m.matches, matches);
}

This way, Double.compare will handle the NaN values for you. For any number x (other than NaN) Double.compare(x, Double.NaN) == -1 will return true (i.e., NaN is considered greater than any other number).

Note here that you are OK using == with ints but it is more complicated with double because Double.NaN != Double.NaN. However, new Double(Double.NaN).equals(Double.NaN) is true. See Why is Java's Double.compare(double, double) implemented the way it is? for a nice discussion.

Contract breaking:

To see an example of why your original implementation might break the contract if you have NaNs, see Java compareTo documentation. There we have:

Finally, the implementer must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

So imagine you have x = NaN and y = 5 and z = 6, then:

x.compareTo(y) == 0 (since NaN > 5 and NaN < 5 are false)
x.compareTo(z) == 0 (same reasoning)
y.compareTo(z) == -1 (y < z).

So 2 and 3 (+sgn) are not equal as required.

Indeed, this does work, though I'm not sure why - or where I had gotten any NaNs in my list. — Dexter, Jul 15 '12 at 21:46
I've updated my answer with an example of where the contract is broken if NaNs are present. I can't say where they'd be present in your code or is that is definitely the issue :( — MGwynne, Jul 15 '12 at 22:07
You were right - there are NaNs in the calculated values for the distance: http://ideone.com/R9lTB — Dexter, Jul 15 '12 at 22:08
Glad it worked out! Don't forget to check out @fabian-barney 's answer regarding correct use of compare methods, if you haven't already. I'd update my answer fully to take it into account, but I'd rather ensure he gets his deserved votes :). — MGwynne, Jul 15 '12 at 22:11
@MGwynne Feel free to add it. I am sure it'll further improve your already very good answer. +1 from the beginning btw — Fabian Barney, Jul 16 '12 at 08:23
@fabian-barney Thanks! I've now updated it. If you see anything silly or stupid, please let me know! — MGwynne, Jul 16 '12 at 21:18

score 2 · Answer 2 · answered Jul 15 '12 at 21:51

Do not return the diff in compareTo(...) method. This is not valid for all values. For example the result of Integer.MAX_VALUE - Integer.MIN_VALUE is negative.

Rewrite it to something like:

public int compareTo(Object o) {
    Match m = (Match) o;
    return m.matches == matches ? Double.compare(m.distance, distance) : Integer.compare(m.matches, matches);
}

.compareTo() with 2 Sorting-Columns

2 Answers2

Using existing comparison methods

Contract breaking: