1

I have used list.sort() to sort a list of objects with type Date, and got java.lang.IllegalArgumentException: Comparison method violates its general contract! I feel quite confusing about this error.

The code as below shown

List<Date> list = new ArrayList<>(200);

Date now = new Date();
for (int i = 0; i < 200; ++i) {
    int delta = ThreadLocalRandom.current().nextInt(2, 10);
    list.add(DateUtils.addMinutes(now, delta));
}

list.sort((x, y) ->  {
    int cmp = x.before(y) ? -1 : 1;
    return cmp;
});

I have searched on Google, and found many similar issues (Java error: Comparison method violates its general contract), which say that the comparator does not meet transitivity rule. However, it seems that Date.before should follow transitivity rule.

And I know the comparator has an issue when comparing two same dates. For any two same date, say d1, d2, both cmp(d1, d2) and cmp(d2, d1) return 1.

However, if we replace the comparator, always return 1, no error throw out. How surprising!

list.sort((x, y) -> 1);

In the above example, I created lots duplicated date which used to reproduce the error. Even though I know how to solve the issue, I still want to know why using before() would fail.

By the way, I tested it on JDK 8 and 11, both failed.

Jacky1205
  • 3,273
  • 3
  • 22
  • 44
  • Why not just use `list.sort(Date::compareTo);`? – small_ticket May 29 '20 at 09:21
  • 3
    But if ``cmp`` is not 0 if two dates are the same, then it does not follow the transitivity rule. So, this is the issue here. – ThexXTURBOXx May 29 '20 at 09:22
  • Let's say there are 3 date with the same value, d1, d2, d3: we have d1 > d2 (`d1.before(d2) == 1`), d2 > d3, and then d1 > d3 still true, right? – Jacky1205 May 29 '20 at 09:26
  • 1
    It violates the "sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. " rule. – Sweeper May 29 '20 at 09:30
  • Yes, it breaks the rule, however, breaking such rule does not always trigger the error. I want to know why. @Sweeper – Jacky1205 May 29 '20 at 09:32
  • You don't _always_ get caught. In the cases where you don't trigger it, it's simply because that particular sequence of comparisons doesn't happen, which could be for any number of random reasons, such as relative starting positions or internal behavior of the sorting algorithm. – chrylis -cautiouslyoptimistic- May 29 '20 at 09:42
  • "does not always" is not "never". In this case, it's triggered by you breaking this rule. – Sweeper May 29 '20 at 09:42
  • 1
    Anyhow, `Date` is already `Comparable`, so just use the natural order, and use the `java.time` classes instead of `Date` anyway. – chrylis -cautiouslyoptimistic- May 29 '20 at 09:44
  • If the comparator meet the the below 2 rules, does we could always get the right result? 1. compare(a,b) should equal -compare(b,a). 2. a < b, b < c then a < c. Note that we could never return 0, as in some cases, equation has no real meaning in conceptual. – Jacky1205 May 29 '20 at 09:51
  • In your comparison you need to take care of -1 for before .. 0 for same 1 for after, Otherwise it will break transitivity contract. You can use Collections.sort(list); as Date already implements Comparable for natural order.... OR you can use list.sort(Date::compareTo); – Kunal Kishore May 29 '20 at 09:57
  • It sounds like you are asking about "can I create a valid `compare` implementation without ever returning 0?" I suggest you [edit] your question to change what you are asking, if this is true. – Sweeper May 29 '20 at 10:04
  • Why? Because the documentation says so. If you mean why the specs were written this way, it’s guesswork, though qualified guesses could be made. – Ole V.V. May 29 '20 at 14:46

0 Answers0