Erreur de Java : La méthode de comparaison viole son contrat général

Question

J'ai vu beaucoup de questions à ce sujet, et j'ai essayé de résoudre le problème, mais après une heure de recherche sur Google et beaucoup d'essais et d'erreurs, je ne peux toujours pas le résoudre. J'espère que certains d'entre vous ont compris le problème.

Voilà ce que je reçois :

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

Et voici mon comparateur :

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

Une idée ?

Answer 1

Le message d'exception est en fait assez descriptif. Le contrat qu'il mentionne est transitivité : si A > B et B > C alors pour tout A , B et C : A > C . Je l'ai vérifié avec du papier et un crayon et votre code semble avoir quelques trous :

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

vous ne revenez pas -1 si card1.getRarity() > card2.getRarity() .

---

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

Vous revenez -1 si les ids ne sont pas égaux. Vous devez retourner -1 o 1 en fonction de l'identité la plus importante.

---

Jetez un coup d'oeil à ça. En plus d'être beaucoup plus lisible, je pense que cela devrait fonctionner :

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!

Answer 2

Vous pouvez utiliser la classe suivante pour identifier les problèmes de transitivité dans vos comparateurs :

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

Il suffit d'invoquer Comparators.verifyTransitivity(myComparator, myCollection) devant le code qui échoue.

Answer 3

Cela a également quelque chose à voir avec la version du JDK. S'il fonctionne bien dans le JDK6, il aura peut-être le problème décrit par vous dans le JDK 7, car la méthode de mise en œuvre dans le JDK 7 a été modifiée.

Regardez ça :

Description : L'algorithme de tri utilisé par java.util.Arrays.sort et (indirectement) par java.util.Collections.sort a été remplacé. La nouvelle implémentation du tri peut lancer un IllegalArgumentException s'il détecte un Comparable qui viole la Comparable contrat. L'implémentation précédente ignorait silencieusement une telle situation. Si le comportement précédent est souhaité, vous pouvez utiliser la nouvelle propriété du système, java.util.Arrays.useLegacyMergeSort pour rétablir le comportement antérieur du tri par fusion.

Je ne connais pas la raison exacte. Cependant, si vous ajoutez le code avant d'utiliser le tri. Tout ira bien.

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

Answer 4

Considérons le cas suivant :

D'abord, o1.compareTo(o2) s'appelle. card1.getSet() == card2.getSet() se trouve être vrai et donc card1.getRarity() < card2.getRarity() donc vous rendez 1.

Ensuite, o2.compareTo(o1) est appelé. Encore une fois, card1.getSet() == card2.getSet() est vrai. Ensuite, vous passez à ce qui suit else alors card1.getId() == card2.getId() se trouve être vrai, ainsi que cardType > item.getCardType() . Vous retournez encore 1.

De ça, o1 > o2 y o2 > o1 . Vous avez rompu le contrat.

Answer 5

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

Toutefois, si card2.getRarity() est inférieur à card1.getRarity() vous pourriez ne pas revenir -1 .

Vous passez également à côté d'autres cas. Je ferais ceci, vous pouvez changer autour selon votre intention :

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;

    }
}