“Comparison method violates its general contract!”

Question

I have googled some same question and I know the reason.However the crash happened only once so I come here to ask you what may lead to crash.

    Collections.sort(downloadTasks, new Comparator<DownloadTask>() {
        @Override
        public int compare(DownloadTask lhs, DownloadTask rhs) {
            if (lhs == null || rhs == null) return 0;
            return (int) (lhs.mTaskInfo.time - rhs.mTaskInfo.time);
        }
    });

The error is :

java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeHi(TimSort.java:864) at java.util.TimSort.mergeAt(TimSort.java:481) at java.util.TimSort.mergeCollapse(TimSort.java:406) at java.util.TimSort.sort(TimSort.java:210) at java.util.TimSort.sort(TimSort.java:169) at java.util.Arrays.sort(Arrays.java:2010) at java.util.Collections.sort(Collections.java:1883)

As you see, I compare two objects by their time member. The time is long type.

I think the crash may be from:

Whether does converting long to int lead to crash?
if (lhs == null || rhs == null) return 0; But theoretically lhs and rhs neither is null.

EDIT

If lhs and rhs can be null , what should I do ?

EDIT For Android

In Android, Long.compare() requires API 19. You can do this under API 19 :

public static int compare(long lhs, long rhs) {
    return lhs < rhs ? -1 : (lhs == rhs ? 0 : 1);
}

What crash? What error do you get, when, with what code, what happens, what do you expect to happen? Take a look at [ask] — pvg, Sep 24 '17 at 03:46
As the title says the error is `Comparison method violates its general contract!` — CoXier, Sep 24 '17 at 03:47

score 5 · Accepted Answer · answered Sep 24 '17 at 04:16

Both these cases are problematic.

if (lhs == null || rhs == null) return 0;

If you have [123, null, 234], then you compare 123 as equal to null, null as equal to 234, and by transitivity you should get 123 equals 234. But that is not what your comparator returns.

The solution here would be to either disallow null or sort all nulls to the bottom (or top), i.e. only return 0 is both are null, otherwise return 1 or -1 (depending on the null being left or right).

return (int) (lhs.mTaskInfo.time - rhs.mTaskInfo.time);

Consider comparing Integer.MAX_VALUE + 1 to 0. The difference between the two is Integer.MAX_VALUE + 1. Casting this to int wraps to Integer.MIN_VALUE. The opposite comparison should then give you - Integer.MIN_VALUE, but that is Integer.MIN_VALUE again due to overflow.

The solution here is to use Long.compare(a,b).

score 2 · Answer 2 · edited Jun 20 '20 at 09:12

The "general contract" of the comparison method is well documented in the javadoc of the compare(T o1, T o2) method:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

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

So, which of these 3 rules are you violating? All 3

First rule is violated because time is a long, so (int) (lhs.mTaskInfo.time - rhs.mTaskInfo.time) can be equal to Integer.MIN_VALUE. If you flip the two parameters to compare(), the result would still be Integer.MIN_VALUE, because an int value cannot store the negated value.

The second rule is violated because int overflows. Since time is long, I'll assume they contain standard millisecond values, and an int can only store values up to 24 days. So let's say input is Jan 1, Jan 15, Jan 30. compare(Jan 1, Jan 15) is +14 days, and compare(Jan 15, Jan 30) is +15 days, but compare(Jan 1, Jan 30) should be +29 days, but it overflows are returns something like -19 days. Oops!!!!

The third rule is violated because of the bad null checks. Let's say input is null, Jan 1, Jan 2. compare(null, Jan 1) is 0, and so is compare(null, Jan 2), but compare(Jan 1, Jan 2) is +1 day.

Solution

The int overflow and MIN_VALUE issues can be easily fixed by using Long.compare(long x, long y).

For the null issue, you need to decide if nulls should sort first or last. The following will sort nulls first:

public int compare(DownloadTask lhs, DownloadTask rhs) {
    if (lhs == null) {
        if (rhs == null)
            return 0;
        return -1;
    }
    if (rhs == null)
        return 1;
    return Long.compare(lhs.mTaskInfo.time, rhs.mTaskInfo.time);
}

Or the single-statement version:

public int compare(DownloadTask lhs, DownloadTask rhs) {
    return (lhs == null ? (rhs == null ? 0 : -1)
            : (rhs == null ? 1 : Long.compare(lhs.mTaskInfo.time, rhs.mTaskInfo.time)));
}

Awesome and clear answer. Thanks very much. – CoXier Sep 24 '17 at 05:41 — CoXier, Sep 24 '17 at 05:41

“Comparison method violates its general contract!”

EDIT

EDIT For Android

2 Answers2