Невозможно воспроизвести: «Метод сравнения нарушает его общий контракт!»

Question

Я получаю следующее сообщение об ошибке: «Метод сравнения нарушает общий контракт!» при использовании следующего компаратора, однако я не могу реплицировать исключение с помощью jUnit. Я хотел бы знать, что вызвало эту проблему и как ее реплицировать. Есть примеры других, имеющих одну и ту же проблему, но не как их повторить.

public class DtoComparator implements Comparator<Dto> { 

    @Override 
    public int compare(Dto r1, Dto r2) { 

     int value = 0; 

     value = r1.getOrder() - r2.getOrder(); 

     if (value == 0 && !isValueNull(r1.getDate(), r2.getDate())) 
      value = r1.getDate().compareTo(r2.getDate()); 

     return value; 
    } 

    private boolean isValueNull(Date date, Date date2) { 
     return date == null || date2 == null; 
    } 
} 

код вызывается с помощью:

Collections.sort(dtos, new DtoComparator()); 

Спасибо за любую помощь.

Дополнительная информация: Ошибка, по-видимому, произошла в классе TimSort внутри Java-utils и из метода, называемого mergeLo. Ссылка: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/TimSort.java#TimSort.mergeLo%28int%2Cint%2Cint%2Cint%29

Answer 1

Из документации compare.

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y

Компараторы на основе вычитаний не соответствуют этому условию. Это связано с тем, что вычитание может переполняться. Например,

Integer.MIN_VALUE - 0 
0 - Integer.MIN_VALUE 

оба являются отрицательными.

Существует также проблема с тем, как вы имели дело с Date. Из документации compare:

Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)) , for all z .

compare Your метод нарушает это. Например, если x является null, y является 1 января 1970 и z это 2 января 1970, а затем

compare(x, y) == 0 // x == null 
compare(x, z) == 0 // x == null 
compare(y, z) == -1 // January 1st is before January 2nd. 

Я хотел бы написать метод следующим образом:

@Override 
public int compare(Dto r1, Dto r2) { 

    int value = Integer.compare(r1.getOrder(), r2.getOrder()); 
    if (value != 0) 
     return value; 
    Date date1 = r1.getDate(); 
    Date date2 = r2.getDate(); 
    if (date1 == null && date2 == null) 
     return 0; 
    if (date1 == null) 
     return -1; 
    if (date2 == null) 
     return 1; 
    return date1.compareTo(date2); 
} 

мне удалось воспроизвести проблему , но только для List с длиной не менее 32. См. Эту ссылку для объяснения причины List размером не менее 32. Why does this program using Collections.sort only fail for lists of size 32 or more?

public class Main { 

    private static final class NumAndDate { 
     private final int num; 
     private final Date date; 

     NumAndDate(int num, Date date) { 
      this.num = num; 
      this.date = date; 
     } 
    } 

    public static final class NumAndDateComparator implements Comparator<NumAndDate> { 

     @Override 
     public int compare(NumAndDate r1, NumAndDate r2) { 

      int value = 0; 

      value = r1.num - r2.num; 

      if (value == 0 && !isValueNull(r1.date, r2.date)) 
       value = r1.date.compareTo(r2.date); 

      return value; 
     } 

     private boolean isValueNull(Date date, Date date2) { 
      return date == null || date2 == null; 
     } 
    } 

    public static void main(String[] args) { 
     NumAndDate[] array = { 
       new NumAndDate(0, new Date(0)), 
       new NumAndDate(0, new Date(1)), 
       new NumAndDate(0, null) 
     }; 
     Random random = new Random(); 
     for (int i = 0; i < 100; i++) { 
      for (int j = 0; j < 10000; j++) { 
       List<NumAndDate> list = new ArrayList<>(); 
       int[] arr = new int[i]; 
       for (int k = 0; k < i; k++) { 
        int rand = random.nextInt(3); 
        arr[k] = rand; 
        list.add(array[rand]); 
       } 
       try { 
        Collections.sort(list, new NumAndDateComparator()); 
       } catch (Exception e) { 
        System.out.println(arr.length + " " + Arrays.toString(arr)); 
        return; 
       } 
      } 
     } 
    } 
}