Java компаратор: Нарушает Генподрядные

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. Но если я удалю сравнение затрат, это сработает.

---

EDIT: Исключение трассировки

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 нарушает транзитивность равенства требуемого the contract:

Наконец, реализатор должен обеспечить, чтобы сравнить (х, у) == 0 означает, что sgn (ср. (X, z)) == sgn (ср. (Y, z)) для всех z.

Предположим, у вас есть три ExpressionTree s 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.

Я не уверен, как вы это исправите, но есть причина для этого.

Edit: @Nat (OP) придумал это элегантное решение:

Фикс заменить
if (v1 == v2)
с
if (Math.abs(target-v1) == Math.abs(target-v2))