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

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> с приведенной выше стратегией?

Источник

2 ответа

Решение

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

Java-документы о Comparable Говорит, что:

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

Тотальный порядок должен соответствовать следующим свойствам:

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

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

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

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

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

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

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

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

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

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

Источник

Это потому что у вас есть 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, индекс не может быть учтен, так как отношение больше не является транзитивным.

Источник
Другие вопросы по тегам