Java error: Comparison method violates its general contract

Я видел много вопросов по этому поводу и пытался решить проблему, но после часа поиска в Google и множества проб и ошибок я все еще не могу это исправить. Я надеюсь, что некоторые из вас уловили проблему.

Это то, что я получаю:

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)
    ...

И это мой компаратор:

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

Есть идеи?

Сообщение об исключении на самом деле довольно описательное. Упомянутый в нем контракт - это транзитивность: если A > B и B > C, то для любого A, B и C: A > C. Я проверил это с помощью бумаги и карандаша, и, похоже, в вашем коде мало дыр:

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

вы не возвращаете -1 if card1.getRarity() > card2.getRarity().

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

Вы возвращаете, -1 если идентификаторы не равны. Вы должны вернуть, -1 или 1 в зависимости от того, какой идентификатор был больше.

Взгляните на это. Помимо того, что он намного более удобочитаем, я думаю, он действительно должен работать:

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!

Вы можете использовать следующий класс для точного определения ошибок транзитивности в ваших компараторах:

/**
 * @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()
    {
    }
}

Просто вызовите Comparators.verifyTransitivity(myComparator, myCollection) перед кодом, который завершается ошибкой.

Это также как-то связано с версией JDK. Если он работает хорошо в JDK6, возможно, у него возникнет проблема в JDK 7, описанная вами, потому что метод реализации в jdk 7 был изменен.

Посмотрите на это:

Описание: Алгоритм сортировки, используемый java.util.Arrays.sort и (косвенно) by java.util.Collections.sort, был заменен. Новая реализация сортировки может выдать IllegalArgumentException если она обнаружит Comparable, который нарушает Comparable контракт. Предыдущая реализация молча игнорировала такую ситуацию. Если требуется предыдущее поведение, вы можете использовать новое системное свойство, java.util.Arrays.useLegacyMergeSort, чтобы восстановить предыдущее поведение сортировки слиянием.

Я не знаю точной причины. Однако, если вы добавите код перед использованием sort . Все будет в порядке.

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

Рассмотрим следующий случай:

Сначала вызывается o1.compareTo(o2). card1.getSet() == card2.getSet() оказывается true, и так оно и есть card1.getRarity() < card2.getRarity(), поэтому вы возвращаете 1.

Затем, o2.compareTo(o1) вызывается. Опять же, card1.getSet() == card2.getSet() верно. Затем вы переходите к следующему else, тогда card1.getId() == card2.getId() оказывается true, и так оно и есть cardType > item.getCardType(). Вы снова возвращаете 1.

Из этого, o1 > o2, и o2 > o1. Вы нарушили контракт.