Java comparator: violation of general contracting

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've been looking at this code for months, and I can't find out why it violates the total contract of the comparator

The idea is that each expressiontree can be evaluated as a result (getValue () method) If it returns - 1, it is always higher than other numbers If the value is different, compare its proximity to the target If the values are the same, compare by solution cost

Using this comparator, Java throws illegalstatesexception But if I delete the cost - based comparison, it works

Editing: exception tracking

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)

Solution

Your comparator violated the equal transitivity required by the contract:

Suppose you have three expressiontrees O1, O2, O3, V1, V2, V3 and solution costs S1, S2, S3 with corresponding values, such as V1 = = V2, target – V1 = = V3 – target (so ABS (target-v1) = = ABS (target-v3)) and S1 < S2 (so comparison (O1, O2) = = - 1. For simplicity, you can say O1 then O1 = = O3 and O2 = = O3 but O1 < O2, that is, comparison (O1, O3) = = 0 but SGN (comparison (O1, O2))= Since SGN (compare (O3, O2)), SGN (compare (O1, O2)) = - 1 and SGN (compare (O3, O2)) = = 0

I'm not sure how you will solve this problem, but that's why

Editor: @ nat (OP) proposed this elegant solution: