Replizieren nicht möglich: "Vergleichsmethode verletzt seinen allgemeinen Vertrag!"

Question

Ich erhalte den folgenden Fehler: "Vergleichsmethode verletzt seinen allgemeinen Vertrag!" Wenn ich den folgenden Vergleicher verwende, kann ich die Ausnahme mit jUnit nicht replizieren. Ich würde gerne wissen, was dieses Problem verursacht hat und wie es repliziert wurde. Es gibt Beispiele für andere, die das gleiche Problem haben, aber nicht, wie man es repliziert.

für jede Hilfe

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

Danke:

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

Der Code wird unter Verwendung genannt.

Extra info: Der Fehler schien in der TimSort-Klasse innerhalb von Java-utils und von einer Methode namens mergeLo auftreten. 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

Aus der Dokumentation von compare.

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

Subtraktionsbasierte Komparatoren erfüllen diese Bedingung nicht. Dies liegt daran, dass die Subtraktion überlaufen kann. Zum Beispiel

Integer.MIN_VALUE - 0 
0 - Integer.MIN_VALUE 

sind beide negativ.

Es gibt auch ein Problem mit der Art, wie Sie mit Date s umgegangen sind. Aus der Dokumentation von compare:

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

Ihre compare Methode bricht dieses. wenn xnull Zum Beispiel ist, ist y 1. Januar 1970 und z ist der 2. Januar 1970 dann

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

Ich kann das Verfahren wie folgt schreiben:

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

Ich habe es geschafft, das Problem zu reproduzieren , aber nur für List s der Länge mindestens 32. Unter diesem Link finden Sie eine Erklärung, warum eine List der Größe mindestens 32 erforderlich ist. 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; 
       } 
      } 
     } 
    } 
}