12.4 Vergleichen von Objekten

Sollen Objekte verglichen werden, muss es eine Ordnung dieser Typen geben. Wie sollte das System sonst selbstständig entscheiden können, ob eine Person zum Beispiel kleiner als eine andere Person ist? Weil die eine Person 1,50 Meter groß ist, die andere aber 1,80 Meter, oder weil die eine Person eine Million Euro auf dem Konto hat und die andere nur fünf Euro? [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.] Diese Fragen sind wichtig, wenn wir zum Beispiel eine Liste sortieren wollen.

12.4.1 Die Schnittstellen Comparator und Comparable

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

• Comparable: Implementiert eine Klasse Comparable, so können sich die Objekte selbst mit anderen Objekten vergleichen. Da die Klassen im Allgemeinen nur ein Sortierkriterium implementieren, wird hierüber eine so genannte 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 nicht die Ordnung hat.

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.

Die Schnittstelle Comparable

Die Schnittstelle Comparable kommt aus dem java.lang-Paket und deklariert eine Methode:

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

e.compareTo(null) sollte eine NullPointerException auslösen, auch wenn e.equals(null) die Rückgabe false liefert.

Die Schnittstelle Comparator

Die Schnittstelle Comparator kommt aus dem Paket java.util und deklariert:

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

• boolean equals( Object obj )
  Testet, ob Comparator-Objekte gleich sind. Das testet keine Gleichheit von Objekten! Die Methode muss nicht zwingend implementiert werden, da ja schon Object eine Implementierung bereitstellt. Sie steht hier nur, damit eine API-Dokumentation dieses Missverständnis erklärt.

Rückgabewerte kodieren die Ordnung

Der Rückgabewert von compare() beim Comparator beziehungsweise compareTo() bei Comparable ist <0, =0 oder >0 und bestimmt so die Ordnung der Objekte. Nehmen wir zwei Objekte o1 und o2 an, deren Klassen Comparable implementieren. Dann gilt folgende Übereinkunft.

• o1.compareTo( o2 ) < 0 o1 < o2

• o1.compareTo( o2 ) == 0 o1 == o2

• o1.compareTo( o2 ) > 0 o1 > o2

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

• comp.compare( o1, o2 ) < 0 o1 < o2

• comp.compare( o1, o2 ) == 0 o1 == o2

• comp.compare( o1, o2 ) > 0 o1 > o2

Comparable und Comparator in der Java-API

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

• String

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

• Date

• File, URI

• Enum

• TimeUnit

Von Comparator finden wir in der API-Dokumentation nur java.text.Collator vermerkt.

12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten

Um Such- oder Sortieroperationen möglichst unabhängig von Klassen zu machen, die eine natürliche Ordnung besitzen oder die eine Ordnung über einen externen Comparator definiert bekommen, haben Utility-Klassen wie java.util.Arrays oder java.util.Collections oft zwei Arten von Funktionen: einmal Funktionen mit einem zusätzlichen Comparator und einmal ohne. Wird kein Comparator angegeben, so müssen die Objekte vom Typ Comparable sein.

class java.util.Arrays

• static void sort( Object[] a )
  Sortiert die Elemente. Zum Vergleichen wird vorausgesetzt, dass sie die Klasse Comparable implementieren. Falls sie dies nicht tun, wird eine Ausnahme ausgelöst.

• static <T> void sort( T[] a, Comparator<? super T> c )
  Vergleicht die Objekte mit einem externen Comparator. Falls die Objekte auch noch Comparable implementieren, wird diese Sortierordnung nicht genutzt.

• static int binarySearch( Object[] a, Object key )
  Sucht binär nach key. Die Objekte im Feld müssen Comparable implementieren.

• static <T> int binarySearch( T[] a, T key, Comparator<? super T> c )
  Sucht im sortierten Feld. Der Comparator bestimmt das Sortierkriterium.

class java.util.Collections

• static <T extends Comparable<? super T>> void sort( List<T> list )

• static <T> void sort( List<T> list, Comparator<? super T> c )

• static <T> int binarySearch( List<? extends Comparable<? super T>> list, T key )

• static <T> int binarySearch( List<? extends T> list, T key, Comparator<? super T> c )

Die Datenstrukturen, die eine Sortierung verlangen, wie TreeSet oder TreeMap, nehmen entweder einen Comparator entgegen oder erwarten von den Elementen eine Implementierung von Comparable.

12.4.3 Den größten und kleinsten Wert einer Collection finden

Bisher kennen wir die überladenen Funktionen min() und max() der Utility-Klasse Math für numerische Datentypen. Es gibt aber auch statische Methoden min() und max() in Collections, die das kleinste und größte Element einer Collection ermitteln. Die Laufzeit ist linear zur Größe der Collection. Die Funktionen unterscheiden nicht, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.

• static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)

• static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

• static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)

• static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)

Wir sehen, dass es eine überladene Version der jeweiligen Funktion gibt, da für beliebige Objekte eventuell ein Comparator-Objekt erforderlich ist, das den Vergleich vornimmt. Es sei auch bemerkt, dass dies mit die komplexesten Beispiele für Generics sind.

Den größten Club einer Sammlung finden

Unsere bisherigen Disko-Klassen implementierten kein Comparable, da es keine natürliche Ordnung für Diskotheken gibt. Wir wollen daher ein externes Comparator-Objekt angeben, welches Disko-Objekte nach ihren Quadratmetern einordnet.

Listing 12.12 com/tutego/insel/util/ClubComparatorDemo.java

package com.tutego.insel.util; 
 
import java.util.*; 
 
class Club 
{ 
  int qm; 
 
  Club( int qm ) 
  { 
    this.qm = qm; 
  } 
} 
 
class ClubComparator implements Comparator<Club> 
{ 
  @Override public int compare( Club c1, Club c2 ) 
  { 
    return c1.qm – c2.qm; 
  } 
} 
 
public class ClubComparatorDemo 
{ 
  public static void main( String[] args ) 
  { 
 
    Collection<Club> list = Arrays.asList( 
                             new Club(100), new Club(1123), new Club(123) ); 
 
    Club club = Collections.max( list, new ClubComparator() ); 
    System.out.println( club.qm );      // 1123 
  } 
}

Implementierung der Extremwertfunktionen bei Comparable-Objekten

Wenn wir ein String-Objekt in eine Liste packen oder ein Double-Objekt in eine Menge, werden sie korrekt gesucht, da insbesondere die Wrapper-Klassen die Schnittstelle Comparable implementieren. In der Implementierung min() ohne extra Comparator lässt sich gut der Aufruf von compareTo() sehen:

public static <T extends Object & Comparable<? super T>> 
              T min( Collection<? extends T> coll ) 
{ 
  Iterator<? extends T> i = coll.iterator(); 
  T candidate = i.next(); 
 
  while( i.hasNext() ) 
  { 
    T next = i.next(); 
 
    if ( next.compareTo(candidate) < 0 ) 
      candidate = next; 
  } 
 
  return candidate; 
}

Die generische Schreibweise verlangt, dass die Elemente in der Collection vom Typ Comparable sein müssen und somit eine compareTo()-Methode vorhanden ist.

12.4.4 Sortieren

Mit zwei sort()-Funktionen bietet die Utility-Klasse Collections die Möglichkeit, die Elemente einer Liste stabil zu sortieren.

• static <T extends Comparable<? super T>> void sort( List<T> list )
  Sortiert die Elemente der Liste gemäß ihrer natürlichen Ordnung, die ihnen die Implementierung über Comparable gibt.

• static <T> void sort( List<T> list, Comparator<? super T> c )
  Sortiert die Elemente der Liste gemäß der Ordnung, die durch den Comparator c festgelegt wird. Eine mögliche natürliche Ordnung spielt keine Rolle.

Die Sortierfunktion arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen wäre das ohnehin kaum sinnvoll, weil diese entweder unsortiert sind oder extern eine bestimmte Ordnung aufweisen, wie oben schon angemerkt. Eine analoge Sortierfunktion sort() für die Elemente von Arrays bietet die Klasse Arrays.

Beispielprogramm zum Sortieren

Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend. Zunächst nutzt es die Funktion Arrays.asList(), um aus einem String-Feld eine Liste zu konstruieren und daraus eine veränderbare Liste aufzubauen. (Leider gibt es keinen Konstruktor für ArrayList, der ein Array von Strings direkt verarbeitet, daher dieser Umweg.) Anschließend setzen wir mit Collections.addAll() eine Reihe von weiteren Strings in die Liste. Praktisch an der Funktion addAll() ist, dass sie beliebig viele Argumente über Varargs annimmt.

Listing 12.13 com/tutego/insel/util/CollectionsSortDemo.java, main()

List<String> list = new ArrayList<String>( 
  Arrays.asList( new String[]{ 
  "Noah", "Abraham", "Isaak", "Ismael", "Moses", "Jesus", "Muhammed"  } 
) ); 
 
Collections.addAll( list, 
  "Saskia", "Regina",  "Angela", "Astrid", "Manuela", "Silke", 
  "Linda",  "Daniela", "Silvia", "Samah",  "Radhia",  "Mejda" 
); 
 
Collections.sort( list ); 
 
System.out.println( list );

Merge-Sort steht dahinter

Der Funktion Collections.sort(List) liegt als Algorithmus ein optimierter Merge-Sort zugrunde. Er arbeitet in der Regel sehr schnell; die Laufzeit beträgt n*log(n), wenn n Elemente zu sortieren sind. Obwohl Quick-Sort bei einigen Sortierfolgen schneller ist, hat dieser den großen Nachteil, dass er nicht stabil arbeitet und keine garantierte Laufzeit von n*log(n) besitzt. [Die STL-Bibliothek bei C(++) unterstützt stabile und nicht stabile Sortieralgorithmen. Davon können wir in Java nur träumen.] Auf nahezu sortierten Datenfolgen arbeitet jedoch Merge-Sort wesentlich schneller.

Implementierung von sort() über Arrays.sort()

Collections.sort(List) arbeitet intern so, dass zunächst die Listenelemente in ein temporäres Array kopiert werden. Das übernimmt die toArray()-Methode von List. Anschließend wird Arrays.sort() zum Sortieren genutzt. Am Ende überträgt ein ListIterator das sortierte Array zurück in die Liste.

public static <T extends Comparable<? super T>> void sort( List<T> list ) 
{ 
  Object[] a = list.toArray(); 
  Arrays.sort( a ); 
  ListIterator<T> i = list.listIterator(); 
  for ( int j = 0; j < a.length; j++ ) { 
    i.next(); 
    i.set( (T)a[j] ); 
  } 
}

Stabiles Sortieren

Stabile Sortieralgorithmen lassen die Reihenfolge von gleichen Elementen unverändert. Dies spielt dann eine Rolle, wenn nicht alle Attribute der Elemente in den Vergleich eingehen. Wenn wir etwa die Folge (27,1), (3,2), (56,1), (4,2) (3,1) nach der zweiten Komponente der Zahlenpaare sortieren und anschließend nach der ersten Komponente, dann erwarten wir, dass (3,1) vor (3,2) liegt und der Algorithmus die Reihenfolge der beiden Zahlenpaare nicht wieder ändert. Diese Eigenschaft ist nur dann garantiert, wenn die zweite Sortierung mit einem stabilen Sortieralgorithmus erfolgt. Etwas praktischer lässt sich diese Eigenschaft an einem E-Mail-Programm demonstrieren: Sortieren wir unsere Nachrichten zuerst nach dem Datum und anschließend nach dem Absender, so sollen die Nachrichten von demselben Absender immer noch nach dem Datum sortiert bleiben.

Strings sortieren, auch unabhängig von der Groß- und Kleinschreibung

Die Klasse String realisiert über die Implementierung von Comparable eine natürliche Sortierung. Alle String-Objekte, die in einem Feld sind, können problemlos über Array.sort() und alle Strings in Collection-Sammlungen über Collections.sort() sortiert werden.

Um unabhängig von der Groß- und Kleinschreibung zu sortieren, bietet die Klasse String eine praktische Konstante: String.CASE_INSENSITIVE_ORDER. Das ist ein Comparator<String>, der gut als Argument für sort() passt. (Im Übrigen ist es die einzige statische Variable der Klasse.)

Kommen weitere Sortierkriterien hinzu – und die gibt es in den unterschiedlichen Ländern allemal –, so helfen die Collator-Objekte, da sie spezielle Comparator-Objekte sind.

Comparator deutschCollator = Collator.getInstance( Locale.GERMAN );

Daten in umgekehrter Reihenfolge sortieren

Da es keine spezielle Funktion reverseSort() gibt, ist hier ein spezielles Comparator-Objekt im Einsatz, um Daten entgegensetzt zu ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Funktion reverseOrder() der Klasse Collections können wir ein geeignetes Comparator-Exemplar anfordern. Im folgenden Programm fügen wir einige Zeichenketten in eine Liste ein, die wir anschließend absteigend sortieren lassen:

Listing 12.14 com/tutego/insel/util/CollectionsReverseSortDemo.java, main()

List<String> list = new ArrayList<String>(); 
Collections.addAll(list, "Adam", "Eva", "Set", "Enosch", "Kenan", "Mahalalel", "Jered"); 
Comparator<String> comparator = Collections.<String>reverseOrder(); 
Collections.sort( list, comparator ); 
System.out.println( list ); // [Set, Mahalalel, Kenan, Jered, Eva, Enosch, Adam]

Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit sort() zu sortieren und anschließend mit Collections.reverse(List<?> list) umzudrehen. Die Lösung mit einem Comparator über reverseOrder() ist jedoch stabil. Für einen existierenden Comparator liefert Collections.reverseOrder(Comparator<T> cmp) einen Comparator<T>, der genau umgekehrt arbeitet.

Ihr Kommentar