Java Comparator:违反总承包

Question

所以我有这个比较器:

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;
    }
}

几个月来我一直在看这个代码,我无法找出它违反比较器总合同的原因.

这个想法是每个ExpressionTree可以被评估为一个结果.(getValue()方法).如果它返回-1,它总是高于其他数字.如果值不同,则与其接近程度进行比较target.如果值相同,则按解决方案成本进行比较.

使用此比较器,Java抛出IllegalStatesException.但如果我删除基于成本的比较,它就有效.

---

编辑:异常跟踪

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

您Comparator违反了合同要求的平等传递:

最后,实现者必须确保compare(x,y)== 0意味着所有z的sgn(compare(x,z))== sgn(compare(y,z)).

假设有三个ExpressionTree小号o1, o2, o3与各值
v1, v2, v3
和solutionCosts
s1, s2, s3
使得
v1 == v2,
target - v1 == v3 - target(因此abs(target-v1) == abs(target-v3))
和
s1 < s2(因此compare(o1, o2) == -1,这可以说o1 < o2为简单起见).
然后o1 == o3和o2 == o3,但o1 < o2,那就是,
compare(o1, o3) == 0
但
sgn(compare(o1, o2)) != sgn(compare(o3, o2))
因为
sgn(compare(o1, o2)) == -1和sgn(compare(o3, o2)) == 0.

我不确定你会如何解决这个问题,但这就是它的原因.

编辑: @Nat(OP)提出了这个优雅的解决方案:

修复是替换
if (v1 == v2)
为
if (Math.abs(target-v1) == Math.abs(target-v2))