Impossibile replicare: "Il metodo di confronto viola il suo contratto generale!"

Question

Ho ricevuto il seguente errore: "Il metodo di confronto viola il suo contratto generale!" quando si utilizza il seguente comparatore, tuttavia non riesco a replicare l'eccezione usando jUnit. Mi piacerebbe sapere cosa ha causato questo problema e come replicarlo. Ci sono esempi di altri che hanno lo stesso problema ma non come replicarlo.

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; 
    } 
} 

Il codice viene chiamato utilizzando:

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

Grazie per qualsiasi aiuto.

Ulteriori informazioni: L'errore sembrava verificarsi nella classe TimSort all'interno dei programmi di utilità Java e all'interno di un metodo chiamato mergeLo. Link: 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

Dalla documentazione di compare.

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

I comparatori basati su sottrazione non soddisfano questa condizione. Questo perché la sottrazione può traboccare. Ad esempio

Integer.MIN_VALUE - 0 
0 - Integer.MIN_VALUE 

sono entrambi negativi.

C'è anche un problema con il modo in cui ti sei occupato di Date s. Dalla documentazione di compare:

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

vostri compare metodo pause questo. Per esempio, se x è null, y è 1 gennaio 1970 e z è 2 gennaio 1970, quindi

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

vorrei scrivere il metodo come segue:

@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); 
} 

sono riuscito a riprodurre il problema , ma solo per List s di lunghezza almeno 32. Vedere questo link per una spiegazione del motivo per cui è necessario un List di dimensioni pari a 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; 
       } 
      } 
     } 
    } 
}