Написание правильной реализации сравнения

Question

private static class CharacterIndex implements Comparable<CharacterIndex> {
    private final char c;
    private final int index;

    public CharacterIndex(char c, int index) {
        this.c = c;
        this.index = index;
    }
}

Теперь я хочу переопределить метод compareTo для этого класса так, чтобы, если у меня были следующие List из CharacterIndex объектов [('y', 1), ('x', 2), ('b', 3), ('a', 3)], тогда после сортировки объекты должны быть похожи на [('b', 3), ('a', 3), ('x', 2), ('y', 1)].

Стратегия сортировки:

Объекты, для которых индекс отличается, могут быть перетасованы (и должны быть в отсортированном порядке, основываясь только на значении символа).Объекты с одинаковым индексом должны сохранять свой относительный порядок после сортировки.

Еще один пример:

Для [('y', 1), ('w', 2), ('x', 3)] отсортированный список должен быть [(w, 2), (x, 3), (y, 1)], а не [(x, 3), (w, 2), (y, 1)].

Моя попытка:

@Override
public int compareTo(CharacterIndex ci) {
    if (this.index == ci.index)
        return -1; // don't swap if the index is same
    return Character.compare(this.c, ci.c);
}

Но этот подход дает мне исключение:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.util.Arrays.sort(Arrays.java:1312)
    at java.util.Arrays.sort(Arrays.java:1506)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:141)

Я видел это .Но я не мог четко понять, почему я получаю это исключение.

Есть ли лучший способ отсортировать List<CharacterIndex> с помощью приведенной выше стратегии?

Answer 1

Ввод комментариев @ RealSkeptic в ответ:

java-docs из Comparable говорит, что:

Этот интерфейс налагает общий порядок наобъекты каждого класса, который его реализует.

Общее упорядочение должно соответствовать следующим свойствам:

• Рефлексивность
• Антисимметрия
• Транзитивность
• Сопоставимость

Чтобы узнать больше о полностью упорядоченных наборах, см. эту ссылку.

Моя стратегия сортировки не является переходной.

Предположим, мой первоначальный список [(d,2), (y,1), (b,1)]

• (y,1) < (b,1), как для того же индекса, я не хочу перетасовывать заказ.
• (b,1) < (d,2), как длядругой индекс, я могу перетасовать порядок, а затем мне нужно сравнить только символ.

По транзитивности, (y,1) < (d, 2).Что не соответствует действительности.

Так что это не полностью упорядоченное сравнение.И поэтому это нарушает правило, предоставляемое интерфейсом Comparable.

Таким образом, мы не можем иметь правильную реализацию compareTo (которая соблюдает контракт Comparable интерфейса) для этой стратегии сортировки.

Что вы узнали?

Ваша стратегия сортировки всегда должна определять общее упорядочение для объектов класса, который реализует Comparable

Answer 2

Это потому, что у вас есть o1.compareTo(o2) == -1 && o2.compareTo(o1) == -1, если o1.index == o2.index.Контракт для метода compareTo заключается в том, что эти два должны иметь разные знаки: o1.compareTo(o2) и o2.compareTo(o1).

Другими словами, это означает, что o1 меньше o2 и o2 меньше o1, что невозможно.

Возможное решение:

@Override
public int compareTo(CharacterIndex ci) {
    return Character.compare(this.c, ci.c);
}

Здесь мы сравниваем по характеру, который он несет.Как заметил @RealSkeptic, индекс не может быть учтен, так как отношение больше не является транзитивным.