“Comparison method violates its general contract!”

Question

Can someone explain me in simple terms, why does this code throw an exception, "Comparison method violates its general contract!", and how do I fix it?

private int compareParents(Foo s1, Foo s2) {
    if (s1.getParent() == s2) return -1;
    if (s2.getParent() == s1) return 1;
    return 0;
}

Answer 1

I've seen this happen in a piece of code where the often recurring check for null values was performed:

if(( A==null ) && ( B==null )
  return +1;//WRONG: two null values should return 0!!!

Answer 2

In my case I was doing something like the following:

if (a.someField == null) {
    return 1;
}

if (b.someField == null) {
    return -1;
}

if (a.someField.equals(b.someField)) {
    return a.someOtherField.compareTo(b.someOtherField);
}

return a.someField.compareTo(b.someField);

What I forgot to check was when both a.someField and b.someField are null.

Answer 3

The violation of the contract often means that the comparator is not providing the correct or consistent value when comparing objects. For example, you might want to perform a string compare and force empty strings to sort to the end with:

if ( one.length() == 0 ) {
    return 1;                   // empty string sorts last
}
if ( two.length() == 0 ) {
    return -1;                  // empty string sorts last                  
}
return one.compareToIgnoreCase( two );

But this overlooks the case where BOTH one and two are empty - and in that case, the wrong value is returned (1 instead of 0 to show a match), and the comparator reports that as a violation. It should have been written as:

if ( one.length() == 0 ) {
    if ( two.length() == 0 ) {
        return 0;               // BOth empty - so indicate
    }
    return 1;                   // empty string sorts last
}
if ( two.length() == 0 ) {
    return -1;                  // empty string sorts last                  
}
return one.compareToIgnoreCase( two );

Answer 4

Your comparator is not transitive.

Let A be the parent of B, and B be the parent of C. Since A > B and B > C, then it must be the case that A > C. However, if your comparator is invoked on A and C, it would return zero, meaning A == C. This violates the contract and hence throws the exception.

It's rather nice of the library to detect this and let you know, rather than behave erratically.

One way to satisfy the transitivity requirement in compareParents() is to traverse the getParent() chain instead of only looking at the immediate ancestor.