java包中的总包,Java Comparator：违反总承包

柔情只为你懂 2023-10-03 11:17 62阅读 0赞

![Image 1][]

So I have this 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;

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)