Руководство по реализации метода compareTo

1. Обзор

Как разработчикам Java, нам часто приходится сортировать элементы, сгруппированные в коллекции. Java позволяет реализовать различные алгоритмы сортировки для любого типа данных .

Например, мы можем сортировать строки в алфавитном порядке, в обратном алфавитном порядке или по длине.

В этом руководстве мы рассмотрим интерфейс Comparable и его метод compareTo , который включает сортировку. Мы рассмотрим сортировку коллекций, содержащих объекты как из основных, так и из пользовательских классов.

Мы также упомянем правила для правильной реализации compareTo , а также неправильный шаблон, которого следует избегать.

2. Сопоставимый интерфейс

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

CompareTo — единственный метод, определенный интерфейсом Comparable . Его часто называют методом естественного сравнения.

2.1. Реализация сравнения

Метод compareTo сравнивает текущий объект с объектом , переданным в качестве параметра .

При его реализации нам нужно убедиться, что метод возвращает:

• Положительное целое число, если текущий объект больше объекта параметра
• Отрицательное целое число, если текущий объект меньше объекта параметра
• Ноль, если текущий объект равен объекту параметра

В математике мы называем это знаком или сигнум-функцией:

2.2. Пример реализации

Давайте посмотрим, как реализован метод compareTo в базовом классе Integer :

@Override
public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}

public static int compare (int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

2.3. Сломанный шаблон вычитания

Кто-то может возразить, что вместо этого мы можем использовать умный однострочник с вычитанием:

@Override
public int compareTo(BankAccount anotherAccount) {
    return this.balance - anotherAccount.balance;
}

Давайте рассмотрим пример, когда мы ожидаем, что положительный баланс счета будет больше, чем отрицательный:

BankAccount accountOne = new BankAccount(1900000000);
BankAccount accountTwo = new BankAccount(-2000000000);
int comparison = accountOne.compareTo(accountTwo);
assertThat(comparison).isNegative();

Однако целое число недостаточно велико для хранения разницы, что дает нам неверный результат. Конечно, этот шаблон не работает из-за возможного целочисленного переполнения, и его следует избегать .

Правильное решение — использовать сравнение вместо вычитания. Мы также можем повторно использовать правильную реализацию из основного класса Integer :

@Override
public int compareTo(BankAccount anotherAccount) {
    return Integer.compare(this.balance, anotherAccount.balance);
}

2.4. Правила реализации

Чтобы правильно реализовать метод compareTo , нам необходимо соблюдать следующие математические правила:

• sgn(x.compareTo(y)) == -sgn(y.compareTo(x))
• (x.compareTo(y) > 0 && y.compareTo(z) > 0) подразумевает x.compareTo(z) > 0
• x.compareTo(y) == 0 подразумевает, что sgn(x.compareTo(z)) == sgn(y.compareTo(z))

Также настоятельно рекомендуется, хотя и не обязательно, чтобы реализация compareTo соответствовала реализации метода equals : **** ``

• x.compareTo(e2) == 0 должно иметь то же логическое значение, что и x.equals(y)

Это гарантирует, что мы сможем безопасно использовать объекты в отсортированных наборах и отсортированных картах.

2.5. Согласованность с равными

Давайте посмотрим, что может произойти, если реализации compareTo и equals несовместимы .

В нашем примере метод compareTo проверяет забитые голы, а метод equals проверяет имя игрока:

@Override
public int compareTo(FootballPlayer anotherPlayer) {
    return this.goalsScored - anotherPlayer.goalsScored;
}

@Override
public boolean equals(Object object) {
    if (this == object)
        return true;
    if (object == null || getClass() != object.getClass())
        return false;
    FootballPlayer player = (FootballPlayer) object;
    return name.equals(player.name);
}

Это может привести к неожиданному поведению при использовании этого класса в отсортированных наборах или отсортированных картах:

FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 800);

TreeSet<FootballPlayer> set = new TreeSet<>();
set.add(messi);
set.add(ronaldo);

assertThat(set).hasSize(1);
assertThat(set).doesNotContain(ronaldo);

Отсортированный набор выполняет все сравнения элементов, используя метод compareTo , а не метод equals . Таким образом, два игрока кажутся эквивалентными с его точки зрения, и он не добавит второго игрока.

3. Сортировка коллекций

Основное назначение интерфейса Comparable — обеспечить естественную сортировку элементов, сгруппированных в коллекции или массивы .

Мы можем отсортировать все объекты, которые реализуют Comparable , используя служебные методы Java Collections.sort или Arrays.sort .

3.1. Основные классы Java

Большинство базовых классов Java, таких как String , Integer или Double , уже реализуют интерфейс Comparable .

Таким образом, сортировать их очень просто, поскольку мы можем повторно использовать их существующую естественную реализацию сортировки.

Сортировка чисел в их естественном порядке приведет к возрастанию:

int[] numbers = new int[] {5, 3, 9, 11, 1, 7};
Arrays.sort(numbers);
assertThat(numbers).containsExactly(1, 3, 5, 7, 9, 11);

С другой стороны, естественная сортировка строк приведет к алфавитному порядку:

String[] players = new String[] {"ronaldo",  "modric", "ramos", "messi"};
Arrays.sort(players);
assertThat(players).containsExactly("messi", "modric", "ramos", "ronaldo");

3.2. Пользовательские классы

Напротив, для сортировки любых пользовательских классов нам необходимо вручную реализовать интерфейс Comparable .

Компилятор Java выдаст ошибку, если мы попытаемся отсортировать набор объектов, которые не реализуют Comparable .

Если мы попробуем то же самое с массивами, то при компиляции не произойдет сбой. Однако это приведет к исключению времени выполнения приведения класса:

HandballPlayer duvnjak = new HandballPlayer("Duvnjak", 197);
HandballPlayer hansen = new HandballPlayer("Hansen", 196);
HandballPlayer[] players = new HandballPlayer[] {duvnjak, hansen};
assertThatExceptionOfType(ClassCastException.class).isThrownBy(() -> Arrays.sort(players));

3.3. TreeMap и TreeSet

TreeMap и TreeSet — это две реализации из Java Collections Framework, которые помогают нам с автоматической сортировкой их элементов .

Мы можем использовать объекты, реализующие интерфейс Comparable , в отсортированной карте или как элементы в отсортированном наборе.

Давайте рассмотрим пример пользовательского класса, который сравнивает игроков по количеству забитых ими голов:

@Override
public int compareTo(FootballPlayer anotherPlayer) {
    return Integer.compare(this.goalsScored, anotherPlayer.goalsScored);
}

В нашем примере ключи автоматически сортируются на основе критериев, определенных в реализации compareTo :

FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 900);
FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer modric = new FootballPlayer("modric", 100);

Map<FootballPlayer, String> players = new TreeMap<>();
players.put(ronaldo, "forward");
players.put(messi, "forward");
players.put(modric, "midfielder");

assertThat(players.keySet()).containsExactly(modric, messi, ronaldo);

4. Альтернатива компаратора

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

Интерфейс Comparator позволяет использовать несколько различных стратегий сравнения отдельно от сортируемых объектов:

FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 900);
FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer modric = new FootballPlayer("Modric", 100);

List<FootballPlayer> players = Arrays.asList(ronaldo, messi, modric);
Comparator<FootballPlayer> nameComparator = Comparator.comparing(FootballPlayer::getName);
Collections.sort(players, nameComparator);

assertThat(players).containsExactly(messi, modric, ronaldo);

Как правило, это также хороший выбор, когда мы не хотим или не можем изменять исходный код объектов, которые хотим отсортировать.

5. Вывод

В этой статье мы рассмотрели, как мы можем использовать интерфейс Comparable для определения естественного алгоритма сортировки для наших классов Java. Мы рассмотрели общий сломанный шаблон и определили, как правильно реализовать метод compareTo .

Мы также исследовали коллекции сортировки, которые содержат как базовые, так и пользовательские классы. Далее мы рассмотрели реализацию метода compareTo в классах, используемых в отсортированных множествах и отсортированных картах.

Наконец, мы рассмотрели несколько вариантов использования, когда вместо этого нам следует использовать интерфейс Comparator .

Как всегда, исходный код доступен на GitHub .