11.4    Vergleichen von Objekten und Ordnung herstellen 

Die Object-Methode equals(Object) gibt Auskunft darüber, ob zwei Objekte die gleichen Eigenschaften haben, sagt aber nichts darüber aus, welches Objekt »größer« oder »kleiner« ist. Doch in vielen Anwendungen spielt die Ordnung von Objekten eine Rolle. Offensichtlich ist das bei der Sortierung, aber auch bei einfacheren Fragen, wie der nach dem größten oder kleinsten Element einer Sammlung. Sollen Objekte in Java verglichen werden, muss es immer eine Ordnung dieser Objekte geben. Das System wird nie selbstständig entscheiden können, und oftmals gibt es mehrere Kriterien. Warum ist zum Beispiel eine Person kleiner als eine andere Person? Weil die eine Person 1,50 Meter groß ist, die andere aber 1,80 Meter, oder weil es die eine Person beim Dschungelcamp bis ins Finale geschafft hat?

 

11.4.1    Natürlich geordnet oder nicht? 

In Java gibt es zwei unterschiedliche funktionale Schnittstellen (in zwei unterschiedlichen Paketen) zur Bestimmung der Ordnung:

• Comparable: Wenn eine Klasse Comparable implementiert, können sich die Objekte selbst mit anderen Objekten vergleichen. Da die Klassen im Allgemeinen nur ein Sortierkriterium implementieren, wird hierüber eine sogenannte natürliche Ordnung (engl. natural ordering) realisiert.

• Comparator: Eine implementierende Klasse, die sich Comparator nennt, nimmt zwei Objekte an und vergleicht sie. Ein Comparator für Räume könnte zum Beispiel nach der Anzahl der Personen oder auch nach der Größe in Quadratmetern vergleichen. Die Implementierung von Comparable wäre nicht sinnvoll, weil hier nur ein Kriterium natürlich umgesetzt werden kann, ein Raum aber keine natürliche Ordnung hat.[ 199 ](Im 10. Jahrhundert lebte der Großwesir Abdul Kassem Ismael, der immer seine gesamte Bibliothek mit 117.000 Bänden mitführte. Die trainierten 400 Kamele transportierten die Werke in alphabetischer Reihenfolge. )

Zusammenfassend lässt sich sagen: Während Comparable üblicherweise nur ein Sortierkriterium umsetzt, kann es viele Extraklassen vom Typ Comparator geben, die jeweils unterschiedliche Ordnungen definieren.

Comparable und Comparator in der Java-API

Eine Implementierung von Comparable findet sich genau dort, wo eine natürliche Ordnung naheliegt, etwa bei:

• BigDecimal, BigInteger, Byte, Character, Double, Float, Integer, Long, Short

• Date, Calendar, LocalTime, LocalDate

• String, StringBuilder, StringBuffer (Die letzten beiden gibt es erst seit Java 11.)

• File, URI

• Enum

• TimeUnit

Von Comparator finden wir in der API-Dokumentation nur java.text.Collator (und seine Unterklasse) vermerkt.

Abbildung 11.3     Vereinfachtes UML-Diagramm von »Comparator« und »Comparable«

 

11.4.2    compare*()-Methode der Schnittstellen Comparable und Comparator 

Die funktionale Schnittstelle Comparable kommt aus dem java.lang-Paket und deklariert eine Methode compareTo(…):

interface java.lang.Comparable<T>

• int compareTo(T o)
  
  Vergleicht sich mit einem anderen Objekt.

Die funktionale Schnittstelle Comparator kommt aus dem Paket java.util (nicht wie Comparable aus java.lang, siehe Abbildung 11.3) und deklariert eine abstrakte Methode:

interface java.util.Comparator<T>

• int compare(T o1, T o2)
  
  Vergleicht zwei Argumente auf ihre Ordnung.

 

11.4.3    Rückgabewerte kodieren die Ordnung 

Der Rückgabewert von compare(…) beim Comparator bzw. von compareTo(…) bei Comparable ist kleiner 0 (negativ), gleich 0 oder größer 0 (positiv) und bestimmt so die Ordnung der Objekte – das wird auch Drei-Wege-Vergleich (engl. three-way comparison) genannt.[ 200 ](Programmiersprachen wie Perl, Groovy und Facebooks PHP-Dialekt Hack haben hierfür einen <=>-Operator. Da der wie ein Raumschiff aussieht, heißt er auch spaceship operator. ) Nehmen wir zwei Objekte o1 und o2 an, deren Klassen Comparable implementieren. Dann gilt folgende Übereinkunft:

Ein externer Comparator (symbolisch comp genannt) verhält sich ähnlich:

LocalTime elevenses = LocalTime.of( 11, 0 );

LocalTime lunchtime = LocalTime.of( 12, 0 );

System.out.println( elevenses.compareTo( lunchtime ) );  //  -1

System.out.println( lunchtime.compareTo( elevenses ) );  //  1

 

11.4.4    Beispiel-Comparator: den kleinsten Raum einer Sammlung finden 

Wir wollen Räume ihrer Größe nach sortieren und müssen dafür einen Comparator schreiben (dass Räume Comparable sind, ist nicht angebracht, da es keine natürliche Ordnung für Räume gibt). Daher soll ein externes Comparator-Objekt entscheiden, welches Raum-Objekt nach der Anzahl seiner Quadratmeter größer ist. Weniger Quadratmeter bedeuten, der Raum ist kleiner.

Die Raum-Klasse enthält für das kleine Demoprogramm einen parametrisierten Konstruktor, der sich die Quadratmeter merkt, und einen Getter.

Listing 11.21     src/main/java/com/tutego/insel/util/Room.java, Room

public class Room {

  private int sqm;

  public Room( int sqm ) {

    this.sqm = sqm;

  }

  public int getSqm() {

    return sqm;

  }

}

Ein Raum, aufgebaut durch new Room(100), soll kleiner sein als new Room(1123). Dazu muss der Raum-Comparator auf die Quadratmeter zurückgreifen, andere Kriterien gibt es nicht:

Listing 11.22     src/main/java/com/tutego/insel/util/RoomComparatorDemo.java, RoomComparator

class RoomComparator implements Comparator<Room> {

  @Override public int compare( Room room1, Room room2 ) {

    return Integer.compare( room1.getSqm(), room2.getSqm() );

  }

}

Alle Wrapper-Klassen haben compare(…)-Methoden für einen Drei-Wege-Vergleich. Das ist kürzer als Anweisungen wie:

int v1 = room1.getSqm(), v2 = room2.getSqm();

if ( v1 < v2 ) return -1;

else if ( v1 > v2 ) return 1;

return 0; 

Es gibt in den Bibliotheken viele Stellen, die Ordnung benötigen, etwa bei der Suche nach dem maximalen Element oder bei der Sortierung einer Liste. Collections.max(…) zum Beispiel findet das größte Element einer Liste, Arrays.sort(…) sortiert ein Array.

Abbildung 11.4     Der eigene Comparator muss nur »compare(…)« von der Schnittstelle überschreiben.

Beispiel: Mit dem Comparator-Objekt lässt sich ein Array mit Räumen sortieren. Vorne steht dann der kleinste Raum:

Listing 11.23     src/main/java/com/tutego/insel/util/RoomComparatorDemo.java, Ausschnitt

Room[] rooms = { new Room(1123), new Room(100), new Room(123) };

Arrays.sort( rooms, new RoomComparator() );

System.out.println( rooms[0].getSqm() );      // 100

Die Sortierungsmethode greift für die Raumpaare immer wieder auf den Comparator zurück und fragt nach der Ordnung. Wer in die compare(…)-Methode ein println(…) einbaut, kann dem Algorithmus bei der Arbeit zusehen.

 

11.4.5    Tipps für Comparator- und Comparable-Implementierungen 

Sollen Objekte mit einem Comparator verglichen werden, aber null-Werte vorher aussortiert werden, so ist die statische Methode int compare(T a, T b, Comparator<? super T> c) aus der Klasse Objects nützlich. Die Methode liefert 0, wenn a und b beide entweder null sind oder der Comparator die Objekte a und b für gleich erklärt. Sind a und b beide ungleich null, so ist die Rückgabe c.compare(a, b). Ist nur a oder b gleich null, so hängt es vom Comparator und von der Reihenfolge der Parameter ab.

Bei Implementierungen von Comparable ist neben einer Implementierung von compareTo(…) auch die passende Realisierung in equals(…) wichtig. Sie ist erst dann konsistent, wenn e1.compareTo(e2) == 0 das gleiche Ergebnis wie e1.equals(e2) liefert, wobei e1 und e2 den gleichen Typ besitzen. Ein Verstoß gegen diese Regel kann bei sortierten Mengen schnell Probleme bereiten; ein Beispiel nennt die API-Dokumentation. Auch sollte die hashCode()-Methode korrekt realisiert sein, denn sind Objekte gleich, müssen auch die Hashwerte gleich sein. Und die Gleichwertigkeit bestimmen eben equals(…)/compareTo(…).

e.compareTo(null) sollte eine NullPointerException auslösen, auch wenn e.equals(null) die Rückgabe false liefert. null ist in der Regel nicht größer, kleiner oder gleich einem anderen mit compareTo(…)verglichenen Wert, daher ist eine Ausnahme die einzig vernünftige Reaktion.

Java unterstützt eine sogenannte Serialisierung, bei der Zustände von komplexen Objekten seriell in einen Datenstrom geschrieben werden. Aus diesen Daten lässt sich später ein Objekt rekonstruieren, wir sprechen dabei von Deserialisierung. Serialisierbare Objekte implementieren die Schnittstelle Serializable. Ist ein Comparator mit einer Datenstruktur – wie dem TreeSet oder der TreeMap – verbunden und soll die Datenstruktur serialisiert werden, muss auch die Comparator-Implementierung Serializable implementieren.

 

11.4.6    Statische und Default-Methoden in Comparator 

Die Schnittstelle Comparator bietet eine ganze Reihe von statischen und Default-Methoden. (In Comparable gibt es übrigens keine statischen oder Default-Methoden.) Besonders interessant sind die Möglichkeiten, mehrere Comparatoren zusammenzubinden.

Beginnen wir mit den einfach zu verstehenden Methoden:

interface java.util.Comparator<T>

• static <T extends Comparable<? super T>> Comparator<T> naturalOrder()
  
  Liefert einen Comparator, der die natürliche Ordnung von Objekten verwendet. Sprich, int compare(Comparable<Object> c1, Comparable<Object> c2) ist implementiert als return c1.compareTo(c2);.

• static <T extends Comparable<? super T>> Comparator<T> reverseOrder()
  
  Die statische Methode liefert einen Comparator, der wie naturalOrder() die natürliche Ordnung verwendet, sie allerdings umdreht. Entspricht Collections.reverseOrder(). Im Grunde ist das ein Comparator mit einer compare(Comparable<Object> c1, Comparable<Object> c2)-Methode, die c2.compareTo(c1) liefert.

• default Comparator<T> reversed()
  
  Liefert für diesen aktuellen Comparator einen, der die Sortierreihenfolge umdreht. Entspricht Collections.reverseOrder(this).

• static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator) und

• static <T> Comparator<T> nullsLast(Comparator<? super T> comparator)
  
  Liefern für einen gegebenen comparator einen neuen Comparator, der Vergleiche mit null erlaubt und null von der Ordnung her entweder vor oder hinter die anderen Werte setzt.

Aneinanderreihung von Comparatoren

Oftmals ist das Ordnungskriterium aus mehreren Bedingungen zusammengesetzt, wie die Sortierung in einem Telefonbuch zeigt. Erst gibt es eine Sortierung nach dem Nachnamen, dann folgt die Sortierung nach Vornamen. Um dies mit einem Comparator-Objekt zu lösen, müssen entweder alle Einzelvergleiche in ein neues Comparator-Objekt verpackt werden oder einzelne Comparatoren zu einem »Super«-Comparator zusammengebunden werden. Die zweite Lösung ist natürlich schöner, weil sie die Wiederverwendbarkeit erhöht, denn einzelne Comparatoren können dann leicht für andere Zusammenhänge genutzt werden. Genau für so eine Aneinanderreihung gibt es in Comparator eine nützliche Methode:

interface java.util.Comparator<T>

• default Comparator<T> thenComparing(Comparator<? super T> other)
  
  Wendet erst den eigenen Comparator an, und wenn er Zustände als gleich anzeigt, dann den anderen, other. Anders gesagt: Wenn der eigene Comparator zum Ergebnis 0 kommt, muss der zweite übergebene Comparator die Frage nach der Ordnung beantworten.

Wir wollen diese thenComparing(…)-Methoden aus Comparator für ein Beispiel nutzen, das eine Liste nach Nach- und Vornamen sortiert.

Listing 11.24     src/main/java/com/tutego/insel/util/ComparatorThenComparingDemo.java, Ausschnitt

public class ComparatorThenComparingDemo {



  public static class Person {



    public String firstname, lastname;



    public Person( String firstname, String lastname ) {

      this.firstname = firstname;

      this.lastname  = lastname;

    }



    @Override public String toString() {

      return firstname + " " + lastname;

    }

  }



  public static final Comparator<Person> PERSON_FIRSTNAME_COMPARATOR =

      new Comparator<Person>() {

        public int compare( Person p1, Person p2 ) {

          return p1.firstname.compareTo( p2.firstname );

        }

      };

 

  public static final Comparator<Person> PERSON_LASTNAME_COMPARATOR =

      new Comparator<Person>() {

        public int compare( Person p1, Person p2 ) {

          return p1.lastname.compareTo( p2.lastname );

        }

      };



  public static void main( String[] args ) {

    List<Person> persons = Arrays.asList(

      new Person( "Onkel", "Ogar" ), new Person( "Olga", "Ogar" ),

      new Person( "Peter", "Lustig" ), new Person( "Lara", "Lustig" ) );



    persons.sort( PERSON_LASTNAME_COMPARATOR );

    System.out.println( persons );

    persons.sort( PERSON_FIRSTNAME_COMPARATOR );

    System.out.println( persons );

    persons.sort( PERSON_LASTNAME_COMPARATOR.thenComparing( 

       PERSON_FIRSTNAME_COMPARATOR ) );

    System.out.println( persons );

  }

}

Die Ausgabe ist:

[Peter Lustig, Lara Lustig, Onkel Ogar, Olga Ogar]

[Lara Lustig, Olga Ogar, Onkel Ogar, Peter Lustig]

[Lara Lustig, Peter Lustig, Olga Ogar, Onkel Ogar]

Mit Lambda-Ausdrücken lässt sich das Ganze noch ein wenig kompakter schreiben. Sie sind Thema von Kapitel 13, »Lambda-Ausdrücke und funktionale Programmierung«.

Vergleichswert extrahieren und Vergleiche anstellen *

Die verbleibenden Methoden in Comparator bieten alle die Spezialität, dass sie besondere Funktionsobjekte annehmen, die den »Schlüssel« für die Vergleiche extrahieren und dann für den Vergleich heranziehen. Mit der Syntax der Methodenreferenzen lassen sich sehr kompakte Comparator-Objekte formulieren.

Zu den Methoden:

interface java.util.Comparator<T>

• static <T,U> Comparator<T> comparing(Function<? super T,? extends U> keyExtractor, Comparator<? super U> keyComparator)

• static <T,U extends Comparable<? super U>> Comparator<T> comparing(Function<? super T, ? extends U> keyExtractor)

• static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor)

• static <T> Comparator<T> comparingLong(ToLongFunction<? super T> keyExtractor)

• static<T> Comparator<T> comparingDouble(ToDoubleFunction<? super T> keyExtractor)

• default <U extends Comparable<? super U>> Comparator<T> thenComparing(Function<? super T,? extends U> keyExtractor)

• default <U> Comparator<T> thenComparing(Function<? super T,? extends U>
  
  keyExtractor, Comparator<? super U> keyComparator)

• default Comparator<T> thenComparingDouble(ToDoubleFunction<? super T> keyExtractor)

• default Comparator<T> thenComparingInt(ToIntFunction<? super T> keyExtractor)

• default Comparator<T> thenComparingLong(ToLongFunction<? super T> keyExtractor)

Comparator<Room> comp = Comparator.comparingInt( Room::getSqm );

// kurz für Comparator.comparingInt( (Room r) -> r.getSqm() );

list.sort( comp );

persons.sort( Comparator.comparing( Person::getLastname )

                        .thenComparing( Person::getFirstname ) );