Comparison method violates its general contract - Java Error

Question

I have defined a Comparator using the ordering wrapper. Could you explain why does this code throw an exception, "Comparison method violates its general contract!"? I would really appreciate it if you could tell me how to fix it.

Ordering<Foo> order = new Ordering<Foo>() {

        @Override
        public int compare(Foo left, Foo right) {
                return getCompare(orderMap, left.getItemId(), right.getItemId());
        }
};

Collections.sort(Foos, order);

getCompare :

private int getCompare(Map<Long, Integer> orderMap, Long leftId, Long rightId) {

        int indexLeft = orderMap.get(leftId) == null ? -1 : orderMap.get(leftId);
        int indexRight = orderMap.get(leftId) == null ? -1 : orderMap.get(rightId);

        if (indexLeft < 0 || indexRight < 0) {
            return 1;
        }

        return Integer.compare(indexLeft, indexRight);

    }   

Answer 1

This is the contract:

• If `a.compare(b) is X, and b.compare(c) is X, then a.compare(c) must also be X, whether X is negative, or positive, or zero.
• If a.compare(b) is X, then b.compare(a) must be -X: 0 remains 0, -1 turns to +1, etc.
• a.compare(a) must be 0.

That's it. Your compare method breaks this in many, many ways. For example, your second line has a bug in it(surely that'd be orderMap.get(rightId) == null, you can clean that up using getOrDefault instead), if either index is not found or less than 0, your code always returns 1, which breaks the rule (a.compare(b), where a is not in the map, returns 1, and b.compare(a) would also return 1. It needs to return a negative number instead).

You're going to have to come up with a rule for what happens if one of these is not in the map. If your code is written with the assumption it can't happen, well, it is - throw an exception when your assumption doesn't hold so you can investigate why your assumption (that all provided left/rightIds are always in the map and always non-negative). As written, your code straight up asplodes in a nasty way if that happens - that's what exceptions are for. Explode in an easily debuggable way.

If that was the intent, you're going to have to make up some rules. For example: If a is in the map but b is not, then a is always higher than b. That means if (indexLeft < 0 && indexRight >= 0) return -1 and also if (indexLeft >= 0 && indexRight < 0) return +1;, in order to stick to the rules. That leaves the question: What if neither is in. You can either choose that there is then no way to order them (Return 0), but do know that means you can't put more than once such item in a TreeMap or TreeSet - but sorting a list, that's fine. Individually not-comparables are allowed, and they'll end up clumped together in an arbitrary order. That doesn't break the rules.