所以我有这个比较器：
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,它总是高于其他数字.如果值不同,则比较它与目标的接近程度.如果值相同,则按解决方案成本进行比较.
使用此比较器,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)
解决方法
您的比较者违反了
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.
假设您有三个具有相应值的ExpressionTrees o1,o2,o3
v1,v2,v3
和解决方案成本
s1,s2,s3
这样的
v1 == v2,
target – v1 == v3 – target(so abs(target-v1)== abs(target-v3))
和
s1< s2(因此比较(o1,o2)== -1,为简单起见,可以说o1
比较(o1,o3)== 0
但
sgn(比较(o1,o2))！= sgn(比较(o3,o2))
以来
sgn(比较(o1,o2))== -1和sgn(比较(o3,o2))== 0.
我不确定你会如何解决这个问题,但这就是它的原因.
编辑：@Nat(OP)提出了这个优雅的解决方案：
Fix is to replace
if (v1 == v2)
with
if (Math.abs(target-v1) == Math.abs(target-v2))
