Why I get "Comparison method violates its general contract"

Question

if I call this line of code

Arrays.sort(allNew, 0, sizeNew, mCatBPosComparator);

with that comparator

 private class BPosComparator implements Comparator<CatBPos> {

    private static final int SWAP_BPosS = 1;

    @Override
    public int compare(CatBPos p1, CatBPos p2) {
      int lCompare;

      if (TimeUtils.isNotVoid(p1.getHdopBPos().getTime()) && TimeUtils.isNotVoid(p2.getHdopBPos().getTime())) {
        lCompare = p1.getHdopBPos().getTime().compareTo(p2.getHdopBPos().getTime());
        if (lCompare != 0) {
          return lCompare;
        }
      }

      lCompare = p1.getBPos().getTime().compareTo(p2.getBPos().getTime());
      if (lCompare != 0) {
        return lCompare;
      }

      if (p1.getBPos().isDeparture() && p2.getBPos().isVacation()) {
        return SWAP_BPOS;
      } else if (p1.getBPos().isVacation() && p2.getBPos().isArrival()) {
        return SWAP_BPOS;
      }

      // Ankunft und Abfahrt für denselben Bahnhof sollen in der richtigen Reihenfolge sein
      if (p1.getBPos().isDeparture() && p2.getBPos().isArrival() && p1.getBPos().getStat().equals(p2.getBPos().getStat())) {
        return SWAP_BPOS;
      }

      return 0;
    }
  }

I runs into that Exception:

Comparison method violates its general contract!

I see a lot of topics regarding this. But I dont understand it. Could you help me?

Answer 1

I suspect this is at least one immediate problem:

if (p1.getBPos().isDeparture() && p2.getBPos().isVacation()) {
    return SWAP_BPOS;
} else if (p1.getBPos().isVacation() && p2.getBPos().isDeparture()) {
    return SWAP_BPOS;
}

If you call compare(p1, p2) and then compare(p2, p1) you'll get the same non-zero result... which breaks the comparison rules.

Basically, your comparison needs to obey the documented rules. The above is one problem - it's entirely possible there are more. You should read the rules very carefully and think about how your comparison needs to work.

You can start off by negating SWAP_BPOS for the reverse situation:

if (p1.getBPos().isDeparture() && p2.getBPos().isVacation()) {
    return SWAP_BPOS;
} else if (p1.getBPos().isVacation() && p2.getBPos().isDeparture()) {
    return -SWAP_BPOS;
}

That may not be everything required, but it's a start.

Answer 2

You need to make sure your comparison operator obeys all the appropriate mathematical rules:

1. If A < B and B < C then A < C.
2. If A < B then B > A.
3. If A == B then B == A.

In particular, look out for code that may be returning the same ordering / result for opposite inputs. Your comparison needs to be able to definitively order your items.

In my experience, mistakes in point 2 seem to be the most common mistake.

Answer 3

A comparison operator needs to be transitive. In short this means that you should define it in such a manner that if a.compareTo(b) is negative and b.compareTo(c) is negative, then a.compareTo(c) is also negative. This is somewhat intuitive - if a is less than b and b is less than c then a is less than c, too. Also you should make sure that if a.compareTo(b) is zero, than b.compareTo(a) is zero, i.e. if a equals b then b equals a.

Answer 4

Basically, your compare method needs to be consistent. If A > B, and B > C, then A must be greater than C. Your code is probably failing there.