Java Comparator: Violates 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 months, and I can't find out why it violates comparator general contract. The idea is that each ExpressionTree can be evaluated to one result. (t…

Accepted Answer

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

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

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

I'm not sure how you would fix this, but there's the reason for it.

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

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

Java Comparator: Violates General Contract

Solution

Problem