Unable to replicate : "Comparison method violates its general contract!"

Question

I receive the following error: "Comparison method violates its general contract!" when using the following comparator, however I am unable to replicate the exception using jUnit. I'd like to know what caused this issue and how to replicate it. There are examples of others having the same problem but not how to replicate it.

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

The code is called by using:

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

Thanks for any help.

Extra info: The error seemed to occur in the TimSort class inside Java utils and from within a method called 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

From the documentation of compare.

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

Subtraction-based comparators do not meet this condition. This is because the subtraction can overflow. For example

Integer.MIN_VALUE - 0
0 - Integer.MIN_VALUE 

are both negative.

There is also a problem with the way you have dealt with Dates. From the documentation of compare:

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

Your compare method breaks this. For example, if x is null, y is January 1st 1970 and z is January 2nd 1970, then

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

I would write the method as follows:

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

I have managed to reproduce the problem, but only for Lists of length at least 32. See this link for an explanation of why a List of size at least 32 is required. 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;
                }
            }
        }
    }
}