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. (the getValue() method). If it returns -1, it is always higher than other number. If the value differs, compare to how close it is to target. If the value is same, compare by solution cost.

With this comparator Java throws IllegalStatesException. But if I remove cost-based comparison, it works.

---

EDIT: Exception Trace

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 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 ExpressionTrees 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))