Java Comparator：违反总承包

所以我有这个比较器：

import java.util.Comparator; public class SolutionComparator implements Comparator { 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跟踪

 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 s o1, o2, o3
v1, v2, v3
和解决方案成本
s1, s2, s3
这样的
v1 == v2 ，
target - v1 == v3 - target （so 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))