123

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?

7
  • What line of code causes this Exception to be thrown? What's on lines 835 and 453 of ComparableTimSort.java? Jul 11, 2012 at 21:23
  • It seems to me that you should have this method delegate to the Card class: return card1.compareTo(card2) and implement this logic there. Jul 11, 2012 at 21:24
  • 2
    @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. Jul 11, 2012 at 21:32
  • @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. Jul 11, 2012 at 21:34
  • 1
    After reading the Clean Code book I don't know either. Sep 2, 2014 at 6:55

13 Answers 13

132

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!
4
  • 17
    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. Jul 25, 2014 at 6:40
  • 1
    I'd suggest to use if (card1.getSet() != card2.getSet()) return card1.getSet() > card2.getSet() ? 1 : -1; for more speed, if someone cares.
    – maaartinus
    Sep 1, 2014 at 14:22
  • 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.
    – Thomas W
    Oct 13, 2016 at 1:42
  • 1
    @maaartinus thanks for your suggestion! It was perfect for me :)
    – Sonhja
    Mar 29, 2017 at 7:50
63

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.

2
  • 5
    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 Feb 15, 2016 at 13:42
  • Beware this can be very slow. We got a few ANRs using this.
    – doctorram
    May 6, 2022 at 14:25
43

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");
3
  • 13
    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/… . Jul 25, 2014 at 6:42
  • 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. Jan 15, 2016 at 23:11
  • I have an old application and with JDK8 I got this error. Using JDK6 it works correctly, so I simply downgrade to 6, thanks. Jan 20, 2020 at 11:09
8

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.

3

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.

3

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.

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

    }
}
2

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.

0
1

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.

1

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;
        });
1
  • It works also for Collections.sort
    – djdance
    Oct 28, 2021 at 19:43
1

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

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.