Collections.sort() throws Comparison method violates its general contract! exception

Question

I'm trying to sort a List<> object and I get this exception thrown (for large lists only though)

sorting code:

List<FinalSentence> sentenceList = finalRepresentation.getSentences();
Collections.sort(sentenceList); // <=== EXCEPTION THROWN HERE!!!

FinalSentence class header:

public class FinalSentence implements Comparable<FinalSentence>{...}

compareTo() implementation:

@Override
public int compareTo(FinalSentence o) {
    if (this == o) {
        return 0;
    }
    if (this.score > o.score) {
        return 1;
    }
    if (this.score < o.score) {
        return -1;
    }
    return 0;
}

this is the exception:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.ComparableTimSort.mergeHi(Unknown Source)
at java.util.ComparableTimSort.mergeAt(Unknown Source)
at java.util.ComparableTimSort.mergeCollapse(Unknown Source)
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at java.util.Collections.sort(Unknown Source)
at feature.finalRepresentation.Summarizer.summarize(Summarizer.java:30)
at driver.Driver.main(Driver.java:114)

for a small list (less than 50 elements) it works. for a large list (it's supposed to work with those as well) it throws this exception. The instance type of the List is ArrayList, not that it should matter.

I have no idea how to get to the bottom of this. The list is full, the elements are of the same type (no polymorphism there) and yet I get this weird exception for large lists.

Any ideas?

Thanks ahead!!!

Log the call that leads to the exception, or use a debugger. — MrSmith42, Oct 04 '13 at 13:41
@Karna this is a shortcut - if comparing the `FinalSentence` to itself then return `0`. — Boris the Spider, Oct 04 '13 at 13:44
Do you people ever use google? http://stackoverflow.com/questions/6626437/why-does-my-compare-method-throw-exception-comparison-method-violates-its-gen http://stackoverflow.com/questions/9469308/java-error-comparison-method-violates-its-general-contract http://stackoverflow.com/questions/10234038/compare-method-throw-exception-comparison-method-violates-its-general-contract?rq=1 — Eel Lee, Oct 04 '13 at 13:46
@nocgod Ok, try replacing this whole thing with `return Double.compare(score, o.score)` and see if that works. — arshajii, Oct 04 '13 at 13:47
@arshajii you are right, my bad. Got confused with the LinkedBlockingQueue... — Eugene Krapivin, Oct 04 '13 at 13:53
@Etienne Miret I don't think so, I've worked very hard to find all the spots where I could get NaNs and eliminated them. — Eugene Krapivin, Oct 04 '13 at 13:56
@arshajii As simple as it sounds, your method actually worked :) please write it as an answer — Eugene Krapivin, Oct 04 '13 at 13:57
@Eel Lee I did use google, and looked quite a lot on stack overflow, couldn't find the answer, and I still can't find the problem, thos ashajii's solutions seems to work it out somehow. — Eugene Krapivin, Oct 04 '13 at 13:59
could this be a precision issue that is breaking the transitive property of your compareTo method? — telkins, Oct 04 '13 at 14:00
@nocgod See my answer below. I think I know what your issue was. — arshajii, Oct 04 '13 at 14:00
The (sub-)question why it fails for large lists only was just answered [here](http://stackoverflow.com/q/29866539/1639625). Seems like the cutoff is not 50 but 32, though. — tobias_k, Apr 25 '15 at 15:24

score 21 · Accepted Answer · edited May 23 '17 at 12:25

According to the OP's comment, my suggestion of using

Double.compare(score, o.score)

fixed the issue. My guess is that there was either a problem with ±0s or NaNs. In fact, if you look at the source of Double.compare(), you will find that it's slightly more complicated than you might think, and treats these cases specifically:

958    public static int compare(double d1, double d2) {
959        if (d1 < d2)
960            return -1;           // Neither val is NaN, thisVal is smaller
961        if (d1 > d2)
962            return 1;            // Neither val is NaN, thisVal is larger
963
964        long thisBits = Double.doubleToLongBits(d1);
965        long anotherBits = Double.doubleToLongBits(d2);
966
967        return (thisBits == anotherBits ?  0 : // Values are equal
968                (thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
969                 1));                          // (0.0, -0.0) or (NaN, !NaN)
970    }

(source)

Moral is: be careful when comparing doubles! :)

Reference:

Double.compare()

Yep. His objects probably contain NaNs / -0.0 etc. I initially thought his score was mutated between comparisons before heading over to the compare() method of the `Double` class. — Deepak Bala, Oct 04 '13 at 14:03
I've added a check before all the comparisons to check if either values is NaN, it figures I still have some 0/0 or inf/inf problems in the scoring system...thanks for the help, you actually found a bug in my program, now I have to find where it originates...31 metrics here I come :( — Eugene Krapivin, Oct 04 '13 at 14:06

score 4 · Answer 2 · answered Oct 04 '13 at 14:25

4

It could happen if you break the transitivity rule. If A>B and B>C, then C>A breaks the contract

answered Oct 04 '13 at 14:25

znat

13,144
17
71
106

Yeah you are right. I didn't notice that some of my values were NaNs (a bug that I found and fixed, now there are no NaNs whatsoever) – Eugene Krapivin Oct 04 '13 at 14:31

score -4 · Answer 3 · answered Oct 04 '13 at 13:48

-4

Didn't you mean typing:

    if (this.score == o.score) {
        return 0;
    }

instead of this:

    if (this == o) {
        return 0;
    }

?

answered Oct 04 '13 at 13:48

dstronczak

2,406
4
28
41

4

No, he likely didn't. – arshajii Oct 04 '13 at 13:49
I think he got confused between `o`(O) with `0` (zero). Just like me – Ajinkya Oct 04 '13 at 13:50
I compare references in case I try to compare an element to it-self – Eugene Krapivin Oct 04 '13 at 13:51
1

@Karna He didn't do that either. In fact putting `0` there would make no sense. – arshajii Oct 04 '13 at 13:51
@arshajii `if(this == 0)` ? How? – Ajinkya Oct 04 '13 at 13:52
@arshajii: It will cause compile time error `Incompatible operand types FinalSentence and int` – Ajinkya Oct 04 '13 at 13:58

Collections.sort() throws Comparison method violates its general contract! exception

3 Answers3

Linked