java - "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

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.