Java error: Comparison method violates its general contract

Question

I saw many questions about this, and tried to solve the problem, but after one hour of googling and a lots of trial & error, I still can't fix it. I hope some of you catch the problem.

This is what I get:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:835)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:453)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:392)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:191)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:146)
    at java.util.Arrays.sort(Arrays.java:472)
    at java.util.Collections.sort(Collections.java:155)
    ...

And this is my comparator:

@Override
public int compareTo(Object o) {
    if(this == o){
        return 0;
    }

    CollectionItem item = (CollectionItem) o;

    Card card1 = CardCache.getInstance().getCard(cardId);
    Card card2 = CardCache.getInstance().getCard(item.getCardId());

    if (card1.getSet() < card2.getSet()) {
        return -1;
    } else {
        if (card1.getSet() == card2.getSet()) {
            if (card1.getRarity() < card2.getRarity()) {
                return 1;
            } else {
                if (card1.getId() == card2.getId()) {
                    if (cardType > item.getCardType()) {
                        return 1;
                    } else {
                        if (cardType == item.getCardType()) {
                            return 0;
                        }
                        return -1;
                    }
                }
                return -1;
            }
        }
        return 1;
    }
}

Any idea?

Sunken

What line of code causes this Exception to be thrown? What's on lines 835 and 453 of ComparableTimSort.java? – Negro

It seems to me that you should have this method delegate to the Card class: return card1.compareTo(card2) and implement this logic there. – Denominational

@HovercraftFullOfEels It's a class from Oracle, not wroted by me. It's thows an exception on that line. The method is very long and looks hard to understand. – Sunken

@HunterMcMillen I can't do that. Card only contains the static data of a card (name, text etc...) while this class contains some changing variables like type and amount. – Sunken

I really wonder what makes you to write such a weird asymmetrical and unreadable compareTo??? – Corrinnecorrival

After reading the Clean Code book I don't know either. – Sunken

Possible duplicate of "Comparison method violates its general contract!" – Beltz

Answer 1

The exception message is actually pretty descriptive. The contract it mentions is transitivity: if A > B and B > C then for any A, B and C: A > C. I checked it with paper and pencil and your code seems to have few holes:

if (card1.getRarity() < card2.getRarity()) {
  return 1;

you do not return -1 if card1.getRarity() > card2.getRarity().

---

if (card1.getId() == card2.getId()) {
  //...
}
return -1;

You return -1 if ids aren't equal. You should return -1 or 1 depending on which id was bigger.

---

Take a look at this. Apart from being much more readable, I think it should actually work:

if (card1.getSet() > card2.getSet()) {
    return 1;
}
if (card1.getSet() < card2.getSet()) {
    return -1;
};
if (card1.getRarity() < card2.getRarity()) {
    return 1;
}
if (card1.getRarity() > card2.getRarity()) {
    return -1;
}
if (card1.getId() > card2.getId()) {
    return 1;
}
if (card1.getId() < card2.getId()) {
    return -1;
}
return cardType - item.getCardType();  //watch out for overflow!

Timeworn

Actually, the example you given does not violate transitivity, but the rule sgn(compare(x, y)) == -sgn(compare(y, x)) as stated in docs.oracle.com/javase/7/docs/api/java/util/… - that's antisymmetry in mathematical terms. – Metcalfe

I'd suggest to use if (card1.getSet() != card2.getSet()) return card1.getSet() > card2.getSet() ? 1 : -1; for more speed, if someone cares. – Corrinnecorrival

I encountered this and it was a symmetry issue in my Comparator. The hard part to diagnose was that my weakness was the first field (a boolean field check, not a proper comparison) which did not check for both being true correct. This was only exposed, however, after I added a subsequent subordinate comparison which must have perturbed the sort order. – Bollinger

@Corrinnecorrival thanks for your suggestion! It was perfect for me :) – Tye

Answer 2

You can use the following class to pinpoint transitivity bugs in your Comparators:

/**
 * @author Gili Tzabari
 */
public final class Comparators
{
    /**
     * Verify that a comparator is transitive.
     *
     * @param <T>        the type being compared
     * @param comparator the comparator to test
     * @param elements   the elements to test against
     * @throws AssertionError if the comparator is not transitive
     */
    public static <T> void verifyTransitivity(Comparator<T> comparator, Collection<T> elements)
    {
        for (T first: elements)
        {
            for (T second: elements)
            {
                int result1 = comparator.compare(first, second);
                int result2 = comparator.compare(second, first);
                if (result1 != -result2)
                {
                    // Uncomment the following line to step through the failed case
                    //comparator.compare(first, second);
                    throw new AssertionError("compare(" + first + ", " + second + ") == " + result1 +
                        " but swapping the parameters returns " + result2);
                }
            }
        }
        for (T first: elements)
        {
            for (T second: elements)
            {
                int firstGreaterThanSecond = comparator.compare(first, second);
                if (firstGreaterThanSecond <= 0)
                    continue;
                for (T third: elements)
                {
                    int secondGreaterThanThird = comparator.compare(second, third);
                    if (secondGreaterThanThird <= 0)
                        continue;
                    int firstGreaterThanThird = comparator.compare(first, third);
                    if (firstGreaterThanThird <= 0)
                    {
                        // Uncomment the following line to step through the failed case
                        //comparator.compare(first, third);
                        throw new AssertionError("compare(" + first + ", " + second + ") > 0, " +
                            "compare(" + second + ", " + third + ") > 0, but compare(" + first + ", " + third + ") == " +
                            firstGreaterThanThird);
                    }
                }
            }
        }
    }

    /**
     * Prevent construction.
     */
    private Comparators()
    {
    }
}

Simply invoke Comparators.verifyTransitivity(myComparator, myCollection) in front of the code that fails.

Beltz

This code validates compare(a,b) = - compare(b, c). It does not check that if compare(a,b) > 0 && compare(b,c) > 0 then compare(a,c) > 0 – Horta

Beware this can be very slow. We got a few ANRs using this. – Yonah

Answer 3

It also has something to do with the version of JDK. If it does well in JDK6, maybe it will have the problem in JDK 7 described by you, because the implementation method in jdk 7 has been changed.

Look at this:

Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation. If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behaviour.

I don't know the exact reason. However, if you add the code before you use sort. It will be OK.

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

Caruso

That should only be used as a quick and ugly workaround to make things work again until you fix the comparator. If the exception happens it means you comparator is buggy and the sort order will be weird. You have to consider all the rules given in docs.oracle.com/javase/7/docs/api/java/util/… . – Metcalfe

What if "weird" is what I was going for? (a,b) -> { return (new int[]{-1,1})[(int)((Math.random()*2)%2)]} I know Collections.shuffle exists, but I dislike being over-protected. – Odoacer

I have an old application and with JDK8 I got this error. Using JDK6 it works correctly, so I simply downgrade to 6, thanks. – Depone

Answer 4

Consider the following case:

First, o1.compareTo(o2) is called. card1.getSet() == card2.getSet() happens to be true and so is card1.getRarity() < card2.getRarity(), so you return 1.

Then, o2.compareTo(o1) is called. Again, card1.getSet() == card2.getSet() is true. Then, you skip to the following else, then card1.getId() == card2.getId() happens to be true, and so is cardType > item.getCardType(). You return 1 again.

From that, o1 > o2, and o2 > o1. You broke the contract.

Avuncular

Answer 5

I had the same symptom. For me it turned out that another thread was modifying the compared objects while the sorting was happening in a Stream. To resolve the issue, I mapped the objects to immutable temporary objects, collected the Stream to a temporary Collection and did the sorting on that.

Helium

Answer 6

If you try to run this code you will meet the kind this exception:

    public static void main(String[] args) {
        Random random = new Random();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 50000; i++) {
            list.add(random.nextInt());
        }
        list.sort((x, y) -> {
            int c = random.nextInt(3);
            if (c == 0) {
                return 0;
            }
            if (c == 1) {
                return 1;
            }
            return -1;
        });
    }

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:777)
    at java.util.TimSort.mergeAt(TimSort.java:514)
    at java.util.TimSort.mergeCollapse(TimSort.java:441)
    at java.util.TimSort.sort(TimSort.java:245)
    at java.util.Arrays.sort(Arrays.java:1512)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at Test.main(Test.java:14)

The reason is when implementing the Comparator, it may meet the case of A > B and B > C and C > A and the sort method will be run around to be broken. Java prevent this case by throw exception this case:

class TimSort<T> {
.
.
.
else if (len1 == 0) {
            throw new IllegalArgumentException(
                "Comparison method violates its general contract!");
.
.
.

In conclusion, to handle this issue. You have to make sure the comparator will not meet the case of A > B and B > C and C > A.

Detraction

Answer 7

        if (card1.getRarity() < card2.getRarity()) {
            return 1;

However, if card2.getRarity() is less than card1.getRarity() you might not return -1.

You similarly miss other cases. I would do this, you can change around depending on your intent:

public int compareTo(Object o) {    
    if(this == o){
        return 0;
    }

    CollectionItem item = (CollectionItem) o;

    Card card1 = CardCache.getInstance().getCard(cardId);
    Card card2 = CardCache.getInstance().getCard(item.getCardId());
    int comp=card1.getSet() - card2.getSet();
    if (comp!=0){
        return comp;
    }
    comp=card1.getRarity() - card2.getRarity();
    if (comp!=0){
        return comp;
    }
    comp=card1.getSet() - card2.getSet();
    if (comp!=0){
        return comp;
    }   
    comp=card1.getId() - card2.getId();
    if (comp!=0){
        return comp;
    }   
    comp=card1.getCardType() - card2.getCardType();

    return comp;

    }
}

Scorify

Answer 8

The origin of this exception is a wrong Comparator implementation. By checking the docs, we must implement the compare(o1, o2) method as an equivalence relation by following the rules:

• if a.equals(b) is true then compare(a, b) is 0
• if a.compare(b) > 0 then b.compare(a) < 0 is true
• if a.compare(b) > 0 and b.compare(c) > 0 then a.compare(c) > 0 is true

You may check your code to realize where your implementation is offending one or more of Comparator contract rules. If it is hard to find it by a static analysis, you can use the data which cast the exception to check the rules.

Corduroys

Answer 9

I got the same error with a class like the following StockPickBean. Called from this code:

List<StockPickBean> beansListcatMap.getValue();
beansList.sort(StockPickBean.Comparators.VALUE);

public class StockPickBean implements Comparable<StockPickBean> {
    private double value;
    public double getValue() { return value; }
    public void setValue(double value) { this.value = value; }

    @Override
    public int compareTo(StockPickBean view) {
        return Comparators.VALUE.compare(this,view); //return 
        Comparators.SYMBOL.compare(this,view);
    }

    public static class Comparators {
        public static Comparator<StockPickBean> VALUE = (val1, val2) -> 
(int) 
         (val1.value - val2.value);
    }
}

After getting the same error:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

I changed this line:

public static Comparator<StockPickBean> VALUE = (val1, val2) -> (int) 
         (val1.value - val2.value);

to:

public static Comparator<StockPickBean> VALUE = (StockPickBean spb1, 
StockPickBean spb2) -> Double.compare(spb2.value,spb1.value);

That fixes the error.

Brandt

Answer 10

I ran into a similar problem where I was trying to sort a n x 2 2D array named contests which is a 2D array of simple integers. This was working for most of the times but threw a runtime error for one input:-

Arrays.sort(contests, (row1, row2) -> {
            if (row1[0] < row2[0]) {
                return 1;
            } else return -1;
        });

Error:-

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
    at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
    at java.base/java.util.TimSort.sort(TimSort.java:254)
    at java.base/java.util.Arrays.sort(Arrays.java:1441)
    at com.hackerrank.Solution.luckBalance(Solution.java:15)
    at com.hackerrank.Solution.main(Solution.java:49)

Looking at the answers above I tried adding a condition for equals and I don't know why but it worked. Hopefully we must explicitly specify what should be returned for all cases (greater than, equals and less than):

        Arrays.sort(contests, (row1, row2) -> {
            if (row1[0] < row2[0]) {
                return 1;
            }
            if(row1[0] == row2[0]) return 0;
            return -1;
        });

Welterweight

It works also for Collections.sort – Kofu

Answer 11

A variation of Gili's answer to check if the comparator satisfies the requirements described in the compare method's javadoc - with a focus on completeness and readability, e.g. by naming the variables the same as in the javadoc. Note that this is O(n^3), only use it when debugging, maybe just on a subset of your elements, in order to be fast enough to finish at all.

  public static <T> void verifyComparator(Comparator<T> comparator, Collection<T> elements) {
    for (T x : elements) {
      for (T y : elements) {
        for (T z : elements) {
          int x_y = comparator.compare(x, y);
          int y_x = comparator.compare(y, x);
          int y_z = comparator.compare(y, z);
          int x_z = comparator.compare(x, z);

          // javadoc: The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x))
          if (Math.signum(x_y) == -Math.signum(y_x)) { // ok
          } else {
            System.err.println("not holding: sgn(compare(x, y)) == -sgn(compare(y, x))" //
                + " | x_y: " + x_y + ", y_x: " + y_x + ",  x: " + x + ", y: " + y);
          }

          // javadoc: The implementor must also ensure that the relation is transitive:
          // ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.
          if (x_y > 0 && y_z > 0) {
            if (x_z > 0) { // ok
            } else {
              System.err.println("not holding: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0" //
                  + " | x_y: " + x_y + ", y_z: " + y_z + ",  x_z: " + x_z + ", x: " + x + ", y: " + y + ", z: " + z);
            }
          }

          // javadoc: Finally, the implementor must ensure that:
          // compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.
          if (x_y == 0) {
            if (Math.signum(x_z) == Math.signum(y_z)) { // ok
            } else {
              System.err.println("not holding: compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z" //
                  + " | x_y: " + x_y + ", x_z: " + x_z + ",  y_z: " + y_z + ", x: " + x + ", y: " + y + ", z: " + z);
            }
          }
        }
      }
    }
  }

Delija

Answer 12

I had to sort on several criterion (date, and, if same date; other things...). What was working on Eclipse with an older version of Java, did not worked any more on Android : comparison method violates contract ...

After reading on StackOverflow, I wrote a separate function that I called from compare() if the dates are the same. This function calculates the priority, according to the criteria, and returns -1, 0, or 1 to compare(). It seems to work now.

Gamine

Answer 13

What about doing something simpler like this:

int result = card1.getSet().compareTo(card2.getSet())
if (result == 0) {
    result = card1.getRarity().compareTo(card2.getRarity())
}
if (result == 0) {
    result = card1.getId().compareTo(card2.getId())
}
if (result == 0) {
    result = card1.getCardType().compareTo(card2.getCardType())
}
return result;

You just need to order the comparisons in order of preference.

Dangelo