Java.lang.IllegalArgumentException: метод сравнения нарушает общий контракт

Привет, ниже мой метод сравнения моего компаратора. Я не уверен, что не так. Я просмотрел другие похожие вопросы и ответы на переполнение стека, но не уверен, что не так с моим методом, но я продолжаю получать java.lang.IllegalArgumentException: метод сравнения нарушает общий контракт!

Любая помощь будет принята с благодарностью

public int compare(Node o1, Node o2)
{
    HashMap<Integer,Integer> childMap = orderMap.get(parentID);
    if(childMap != null && childMap.containsKey(o1.getID()) && 
                           childMap.containsKey(o2.getID()))
    {
        int order1 = childMap.get(o1.getID());
        int order2 = childMap.get(o2.getID());

        if(order1<order2) 
            return -1;
        else if(order1>order2) 
            return 1;
        else 
            return 0;
    }
    else
        return 0;
}

Добавление исключения, которое я получаю

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(TimSort.java:747)
at java.util.TimSort.mergeAt(TimSort.java:483)
at java.util.TimSort.mergeCollapse(TimSort.java:410)
at java.util.TimSort.sort(TimSort.java:214)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at java.util.Collections.sort(Collections.java:217)

Ответ 1

Ваш compare() метод не переходный. Если A == B и B == C, то A должно быть равно C.

Теперь рассмотрим этот случай:

Для A, B и C предположим, что метод containsKey() возвращает эти результаты:

childMap.containsKey(A.getID()) возвращает true
childMap.containsKey(B.getID()) возвращает false
childMap.containsKey(C.getID()) возвращает true

Также рассмотрим заказы для A.getId()!= B.getId().

Итак,

A и B вернут 0, поскольку внешнее условие if будет false = > A == B
B и C вернутся 0, поскольку внешнее условие if будет false = > B == C

Но A и C могут возвращать -1 или 1 на основе вашего теста внутри блока if. Итак, A != C. Это нарушает принцип транзитивности.

Я думаю, вы должны добавить какое-то условие в свой блок else, который выполняет проверку аналогично тому, как вы делаете в блоке if.

Ответ 2

Я думаю, проблема в вашем случае по умолчанию. Рассмотрим множество узлов A, B и C, где идентификаторы 'a', 'b' и 'c'. Рассмотрим далее, что ваш childMap, который содержит относительную информацию для упорядочения, имеет следующее содержимое:

{ 'a' => 1, 'c' => 3 }

Теперь, если вы запустите свой метод compare на A и B, вы возвращаете 0, указывая, что A и B эквивалентны. Кроме того, если вы сравниваете B и C, вы все равно возвращаете 0. Однако, если вы сравниваете A и C, вы возвращаете -1, указывая, что A меньше. Это нарушает свойство транзитивности контракт Comparator:

Разработчик должен также гарантировать, что отношение транзитивно: ((compare(x, y)>0) && (compare(y, z)>0)) подразумевает compare(x, z)>0.

Наконец, разработчик должен убедиться, что compare(x, y)==0 подразумевает, что sgn(compare(x, z))==sgn(compare(y, z)) для всех z.

Вы не можете обрабатывать "элементы, которые не имеют назначенного порядка", как имеющие значение "где-то смутно посередине", так как алгоритмы сортировки не знают, куда их поставить. Если вы хотите остаться с таким подходом, то в случае, когда значение отсутствует на карте, вам нужно назначить фиксированное значение порядковым номером; что-то вроде 0 или MIN_INT является разумным выбором (но любой выбор должен быть задокументирован в Javadoc для compare!).