Search code examples
javasortingcollectionscomparable

.compareTo() with 2 Sorting-Columns

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.

Solution

  • 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:

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

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