Java comparator: violates the general contract

Question

So I have this comparator:

import java.util.Comparator; public class SolutionComparator implements Comparator<ExpressionTree> { private final int target; public SolutionComparator(int target) { this.target = target; } @Override public int compare(ExpressionTree o1, ExpressionTree o2) { int v1 = o1.getValue(); int v2 = o2.getValue(); if (v1 == -1 && v2 == -1) return 0; else if (v1 == -1) return 1; else if (v2 == -1) return -1; else if (v1 == v2) return (int)Math.signum(solutionCost(o1) - solutionCost(o2)); else return (int)Math.signum(Math.abs(target-v1) - Math.abs(target-v2)); } private int solutionCost(ExpressionTree v) { int cost = 0; Operation o = v.getOperator(); if (o != Operation.NONE) { cost += o.getCost(); for (ExpressionTree e : v.getChildren()) cost += solutionCost(e); } return cost; } } 

I have been looking at this code for several months, and I cannot understand why it violates the general comparator contract.

The idea is that each ExpressionTree can be rated on a single result. ( getValue() method). If it returns -1, it is always higher than the other. If the value is different, compare how close it is to target . If the value is the same, compare the cost of the solution.

Using this comparator, Java throws an IllegalStatesException. But if I remove the cost comparison, it will work.

---

EDIT: Trace exceptions

 Exception in thread "Thread-3" java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeHi(TimSort.java:868) at java.util.TimSort.mergeAt(TimSort.java:485) at java.util.TimSort.mergeCollapse(TimSort.java:408) at java.util.TimSort.sort(TimSort.java:214) at java.util.TimSort.sort(TimSort.java:173) at java.util.Arrays.sort(Arrays.java:659) at java.util.Collections.sort(Collections.java:217) at ***.run(***:123) at java.lang.Thread.run(Thread.java:722) 

Answer 1

Your Comparator violates the transitivity of equality required by the contract :

Finally, the developer must ensure that comparing (x, y) == 0 means that sgn (compare (x, z)) == sgn (compare (y, z)) for all z.

Suppose you have three ExpressionTree o1, o2, o3 with the corresponding values v1, v2, v3
and solutionCosts
s1, s2, s3
so v1 == v2 ,
target - v1 == v3 - target (so abs(target-v1) == abs(target-v3) )
and
s1 < s2 (so compare(o1, o2) == -1 , which for simplicity can be said o1 < o2 ).
Then o1 == o3 and o2 == o3 , but o1 < o2 , that is, compare(o1, o3) == 0
but
sgn(compare(o1, o2)) != sgn(compare(o3, o2))
So
sgn(compare(o1, o2)) == -1 and sgn(compare(o3, o2)) == 0 .

I'm not sure how you will fix this, but there is a reason for this.

Edit: @Nat (OP) came up with this elegant solution:

Fix - replace if (v1 == v2)
with
if (Math.abs(target-v1) == Math.abs(target-v2))