Объектное Упорядочивание

A List l может быть сортирован следующим образом.

Collections.sort(l);

Если List состоит из String элементы, это будет сортировано в алфавитный порядок. Если это состоит из Date элементы, это будет сортировано в хронологический порядок. Как это происходит? String и Date оба реализуют Comparable интерфейс. Comparable реализации обеспечивают естественное упорядочивание для class, который позволяет объектам что class быть сортированными автоматически. Следующая таблица суммирует некоторые из более важных классов платформы Java та реализация Comparable.

Если Вы пытаетесь сортировать список, элементы которого не реализуют Comparable, Collections.sort(list) бросит a ClassCastException. Точно так же Collections.sort(list, comparator) бросит a ClassCastException если Вы пытаетесь сортировать список, элементы которого не могут быть по сравнению с друг другом, используя comparator. Элементы, которые могут быть по сравнению с друг другом, вызывают взаимно сопоставимые. Хотя элементы различных типов могут быть взаимно сопоставимыми, ни один из классов, перечисленных здесь, не разрешает сравнение межкласса.

Это - все, что Вы действительно должны знать о Comparable взаимодействуйте через интерфейс, если Вы только хотите сортировать списки сопоставимых элементов или создать сортированные наборы их. Следующий раздел будет представлять интерес для Вас, если Вы будете хотеть реализовать свое собственное Comparable ввести.

Запись Ваших Собственных Сопоставимых Типов

Comparable интерфейс состоит из следующего метода.

public interface Comparable<T> {
    public int compareTo(T o);
}

compareTo метод сравнивает объект получения с указанным объектом и возвращает отрицательное целое число, 0, или положительное целое число в зависимости от того, является ли объект получения меньше чем, равный, или больше чем указанный объект. Если указанный объект не может быть по сравнению с объектом получения, метод бросает a ClassCastException.

following class representing a person's name реализации Comparable.

import java.util.*;

public class Name implements Comparable<Name> {
    private final String firstName, lastName;

    public Name(String firstName, String lastName) {
        if (firstName == null || lastName == null)
            throw new NullPointerException();
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String firstName() { return firstName; }
    public String lastName()  { return lastName;  }

    public boolean equals(Object o) {
        if (!(o instanceof Name))
            return false;
        Name n = (Name) o;
        return n.firstName.equals(firstName) && n.lastName.equals(lastName);
    }

    public int hashCode() {
        return 31*firstName.hashCode() + lastName.hashCode();
    }

    public String toString() {
	return firstName + " " + lastName;
    }

    public int compareTo(Name n) {
        int lastCmp = lastName.compareTo(n.lastName);
        return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName));
    }
}

Чтобы сохранить предыдущий пример коротким, class несколько ограничивается: Это не поддерживает вторые имена, это требует и первое и фамилию, и это не интернационализируется всегда. Тем не менее, это иллюстрирует следующие важные моменты:

• Name объекты являются неизменными. При прочих равных условиях неизменные типы являются способом пойти, специально для объектов, которые будут использоваться в качестве элементов в Sets или как ключи Maps. Эти наборы повредятся, если Вы измените их элементы или ключи, в то время как они находятся в наборе.
• Конструктор проверяет его параметры за null. Это гарантирует что все Name объекты хорошо формируются так, чтобы ни один из других методов никогда не бросил a NullPointerException.
• hashCode метод пересматривается. Это важно для любого class, который пересматривает equals метод. (У равных объектов должны быть равные хэш-коды.)
• equals возвраты метода false если указанный объект null или несоответствующего типа. compareTo метод бросает исключение на этапе выполнения при этих обстоятельствах. Оба из этих поведений требуются общими контрактами соответствующих методов.
• toString метод был пересмотрен так, он печатает Name в удобочитаемой форме. Это всегда - хорошая идея, специально для объектов, которые собираются быть помещенными в наборы. Различные типы набора toString методы зависят от toString методы их элементов, ключей, и значений.

Так как этот раздел об упорядочивании элемента, давайте говорить немного больше о Name's compareTo метод. Это реализует упорядочивающий стандартное имя алгоритм, где фамилии имеют приоритет по именам. Это точно, что Вы хотите в естественном упорядочивании. Очень сбило бы с толку действительно, если бы естественное упорядочивание было неестественным!

Смотрите на как compareTo реализуется, потому что это довольно типично. Во-первых, Вы сравниваете старшую значащую часть объекта (в этом случае, фамилия). Часто, можно только использовать естественное упорядочивание типа части. В этом случае часть является a String и естественное (лексикографическое) упорядочивание точно, что требуется. Если сравнение приводит к чему-нибудь кроме нуля, который представляет равенство, Вы делаетесь: Вы только возвращаете результат. Если старшие значащие части равны, Вы продолжаете сравнивать следующие старшие значащие части. В этом случае есть только две части — имя и фамилия. Если бы было больше частей, то Вы продолжили бы очевидным способом, сравнивая части, пока Вы не нашли два, которые не были равны, или Вы сравнивали младшие значащие части, в которой точке Вы возвратите результат сравнения.

Только, чтобы показать, что все это работает, вот a program that builds a list of names and sorts them.

import java.util.*;

public class NameSort {
    public static void main(String[] args) {
        Name nameArray[] = {
            new Name("John", "Smith"),
            new Name("Karl", "Ng"),
            new Name("Jeff", "Smith"),
            new Name("Tom", "Rich")
        };

        List<Name> names = Arrays.asList(nameArray);
        Collections.sort(names);
        System.out.println(names);
    }
}

Если Вы выполняете эту программу, вот то, что она печатает.

[Karl Ng, Tom Rich, Jeff Smith, John Smith]

Есть четыре ограничения на поведение compareTo метод, в который мы не будем входить теперь, потому что они являются довольно техническими и скучными и лучше оставляются в документации API. Действительно важно что все классы та реализация Comparable повинуйтесь этим ограничениям, таким образом, читает документацию для Comparable если Вы пишете class, который реализует это. У попытки сортировать список объектов, которые нарушают ограничения, есть неопределенное поведение. С технической точки зрения эти ограничения гарантируют, что естественное упорядочивание является полным порядком на объекты class, который реализует его; это необходимо, чтобы гарантировать, что сортировка четко определена.

Компараторы

Что, если Вы хотите сортировать некоторые объекты в порядке кроме их естественного упорядочивания? Или что, если Вы хотите сортировать некоторые объекты, которые не реализуют Comparable? Чтобы сделать любую из этих вещей, Вы должны будете обеспечить a Comparator — объект, который инкапсулирует упорядочивание. Как Comparable интерфейс, Comparator интерфейс состоит из единственного метода.

public interface Comparator<T> {
    int compare(T o1, T o2);
}

compare метод сравнивает свои два параметра, возвращая отрицательное целое число, 0, или положительное целое число в зависимости от того, являются ли первым параметром меньше чем, равный, или больше чем второе. Если у любого из параметров есть несоответствующий тип для Comparator, compare метод бросает a ClassCastException.

Большая часть того, что было сказано о Comparable применяется к Comparator также. Запись a compare метод почти идентичен записи a compareTo метод, за исключением того, что прежний получает оба объекта, которые передают в как параметры. compare метод должен повиноваться тем же самым четырем техническим ограничениям как Comparable's compareTo метод по той же самой причине — a Comparator должен вызвать полный порядок на объекты, которые он сравнивает.

Предположите, что Вам вызывали class Employee, следующим образом.

public class Employee implements Comparable<Employee> {
    public Name name()     { ... }
    public int number()    { ... }
    public Date hireDate() { ... }
       ...
}

Давайте предполагать что естественное упорядочивание Employee экземпляры Name упорядочивание (как определено в предыдущем примере) на имени сотрудника. К сожалению, босс попросил список сотрудников в порядке старшинства. Это означает, что мы должны сделать некоторую работу, но не очень. Следующая программа произведет необходимый список.

import java.util.*;
public class EmpSort {
    static final Comparator<Employee> SENIORITY_ORDER = 
                                        new Comparator<Employee>() {
            public int compare(Employee e1, Employee e2) {
                return e2.hireDate().compareTo(e1.hireDate());
            }
    };

    // Employee database
    static final Collection<Employee> employees = ... ;

    public static void main(String[] args) {
        List<Employee> e = new ArrayList<Employee>(employees);
        Collections.sort(e, SENIORITY_ORDER);
        System.out.println(e);
    }
}

Comparator в программе является разумно прямым. Это полагается на естественное упорядочивание Date примененный к значения, возвращенные hireDate метод средства доступа. Отметьте что Comparator передает арендную дату его второго параметра его первому, а не наоборот. Причина состоит в том, что сотрудник, который был нанят последний раз, наименее старше; сортировка в порядке, арендной даты поместила бы список в обратный порядок старшинства. Другой метод, который люди иногда используют, чтобы достигнуть этого эффекта, должен поддержать порядок параметра, но инвертировать результат сравнения.

// Don't do this!!
return -r1.hireDate().compareTo(r2.hireDate());

Следует всегда использовать прежний метод в пользу последнего, потому что последний, как гарантируют, не будет работать. Причина этого состоит в том что compareTo метод может возвратить любое отрицание int если его параметром являются меньше чем объект, на который это вызывается. Есть одно отрицание int это остается отрицательным когда отрицающийся, странный, поскольку это может казаться.

-Integer.MIN_VALUE == Integer.MIN_VALUE

Comparator в предыдущей программе хорошо работает для того, чтобы сортировать a List, но у этого действительно есть один недостаток: Это не может использоваться, чтобы упорядочить сортированный набор, такой как TreeSet, потому что это генерирует упорядочивание, которое не является совместимым с, равняется. Это означает что это Comparator приравнивает объекты что equals метод не делает. В частности любые два сотрудника, которые были наняты в ту же самую дату, сравнятся как равный. Когда Вы сортируете a List, это не имеет значения; но когда Вы используете Comparator чтобы упорядочить сортированный набор, это является фатальным. Если Вы используете это Comparator вводить многократных сотрудников, нанятых в ту же самую дату в a TreeSet, только первый будет добавлен к набору; второе будет замечено как двойной элемент и будет проигнорировано.

Чтобы решить эту проблему, просто настройте Comparator так, чтобы это произвело упорядочивание, которое является совместимым с equals. Другими словами настройте это так, чтобы единственные элементы, замеченные как равное при использовании compare те, которые также замечаются как равные, когда сравнено используя equals. Способ сделать это должно выполнить сравнение с двумя частями (что касается Name), где первая часть является той, мы интересуемся — в этом случае, арендная дата — и вторая часть является атрибутом, который однозначно определяет объект. Здесь число сотрудника является очевидным атрибутом. Это Comparator это заканчивается.

static final Comparator<Employee> SENIORITY_ORDER = 
                                        new Comparator<Employee>() {
    public int compare(Employee e1, Employee e2) {
        int dateCmp = e2.hireDate().compareTo(e1.hireDate());
        if (dateCmp != 0)
            return dateCmp;

        return (e1.number() < e2.number() ? -1 :
               (e1.number() == e2.number() ? 0 : 1));
    }
};

Одно последнее примечание: Вы могли бы испытать желание заменить финал return оператор в Comparator с более простым:

return e1.number() - e2.number();

Не делайте этого, если Вы не будете абсолютно уверены, что ни у кого никогда не будет отрицательного числа сотрудника! Этот прием не работает вообще, потому что тип целого числа со знаком не является достаточно большим, чтобы представить различие двух произвольных целых чисел со знаком. Если i большое положительное целое число и j большое отрицательное целое число, i - j переполнит и возвратит отрицательное целое число. Получающееся comparator нарушает одно из четырех технических ограничений, мы продолжаем говорить о (транзитивности), и производит ужасные, тонкие ошибки. Это не просто теоретическое беспокойство; люди записываются этим.