Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage
<< | < | > | >> | API | Kapitel 15 - Collections II

## 15.7 Sortierte Collections

- 15.7 Sortierte Collections
  - 15.7.1 Comparable und Comparator
  - 15.7.2 SortedSet und TreeSet
  - 15.7.3 SortedMap und TreeMap

### 15.7.1 Comparable und Comparator

Die bisher vorgestellten `Set`- und `Map`-Collections waren unsortiert, d.h. ihre Iteratoren haben die Elemente in keiner bestimmten Reihenfolge zurückgegeben. Im Gegensatz dazu gibt ein `List`-Iterator die Elemente in der Reihenfolge ihrer Indexnummern zurück. Im JDK gibt es nun auch die Möglichkeit, die Elemente eines `Set` oder einer `Map` zu sortieren. Dabei kann entweder die natürliche Ordnung der Elemente verwendet werden, oder die Elemente können mit Hilfe eines expliziten Vergleichsobjekts sortiert werden.

Bei der natürlichen Ordnung muß sichergestellt sein, daß alle Elemente der Collection eine `compareTo`-Methode besitzen und je zwei beliebige Elemente miteinander verglichen werden können, ohne daß es zu einem Typfehler kommt. Dazu müssen die Elemente das Interface `Comparable` aus dem Paket `java.lang` implementieren:

    public int compareTo(Object o)
| java.lang.Comparable

`Comparable` besitzt lediglich eine einzige Methode `compareTo`, die aufgerufen wird, um das aktuelle Element mit einem anderen zu vergleichen.

- `compareTo` muß einen Wert kleiner 0 zurückgeben, wenn das aktuelle Element vor dem zu vergleichenden liegt.
- `compareTo` muß einen Wert größer 0 zurückgeben, wenn das aktuelle Element hinter dem zu vergleichenden liegt.
- `compareTo` muß 0 zurückgeben, wenn das aktuelle Element und das zu vergleichende gleich sind.

|  |  |  | Während in älteren JDKs bereits einige Klassen sporadisch eine `compareTo`-Methode besaßen, wird seit dem JDK 1.2 das `Comparable`-Interface bereits von vielen der eingebauten Klassen implementiert, etwa von `String`, `Character`, `Double` usw. Die natürliche Ordnung einer Menge von Elementen ergibt sich nun, indem man alle Elemente paarweise miteinander vergleicht und dabei jeweils das kleinere vor das größere Element stellt. |  |
JDK1.1-1.4

Die zweite Möglichkeit, eine Menge von Elementen zu sortieren, besteht darin, an den Konstruktor der Collection-Klasse ein Objekt des Typs `Comparator` zu übergeben. `Comparator` ist ein Interface, das lediglich eine einzige Methode `compare` definiert:

    public int compare(Object o1, Object o2)
| java.util.Comparator

Das übergebene `Comparator`-Objekt übernimmt die Aufgabe einer »Vergleichsfunktion«, deren Methode `compare` immer dann aufgerufen wird, wenn bestimmt werden muß, in welcher Reihenfolge zwei beliebige Elemente zueinander stehen.

### 15.7.2 SortedSet und TreeSet

Zur Realisierung von sortierten Mengen wurde aus `Set` das Interface `SortedSet` abgeleitet. Es erweitert das Basisinterface um einige interessante Methoden:

    Object first()
    Object last()

    SortedSet headSet(Object toElement)
    SortedSet subSet(Object fromElement, Object toElement)
    SortedSet tailSet(Object fromElement)
| java.util.SortedSet

Mit `first` und `last` kann das (gemäß der Sortierordnung) erste bzw. letzte Element der Menge beschafft werden. Die übrigen Methoden dienen dazu, aus der Originalmenge Teilmengen auf der Basis der Sortierung der Elemente zu konstruieren:

- `headSet` liefert alle Elemente, die echt kleiner als das als Argument übergebene Element sind.
- `tailSet` liefert alle Elemente, die größer oder gleich dem als Argument übergebenen Element sind.
- `subSet` liefert alle Elemente, die größer oder gleich `fromElement` und kleiner als `toElement` sind.

Neben dem hier beschriebenen Interface fordert die Dokumentation zu `SortedSet` eine Reihe von Konstruktoren:

- Ein parameterloser Konstruktor erzeugt eine leere Menge, deren (zukünftige) Elemente bezüglich ihrer natürlichen Ordnung sortiert werden.
- Ein Konstruktor mit einem Argument des Typs `Comparator` erzeugt eine leere Menge, deren (zukünftige) Elemente bezüglich der durch den `Comparator` vorgegebenen Ordnung sortiert werden.
- Ein Konstruktor mit einem Argument vom Typ `Collection` erzeugt eine Menge, die alle eindeutigen Elemente der als Argument übergebenen Collection in ihrer natürlichen Ordnung enthält.
- Ein Konstruktor mit einem Argument des Typs `SortedSet` erzeugt eine Menge mit denselben Elementen und derselben Sortierung wie die als Argument übergebene Menge.

Die einzige Klasse im JDK, die das Interface `SortedSet` implementiert, ist `TreeSet`. Sie implementiert die sortierte Menge mit Hilfe der Klasse `TreeMap`. Diese verwendet einen Red-Black-Tree als Datenstruktur, also einen Baum, der durch eine imaginäre Rot-Schwarz-Färbung seiner Knoten und spezielle Einfüge- und Löschfunktionen davor geschützt wird, im Extremfall zu einer linearen Liste zu entarten. Alle Basisoperationen können in logarithmischer Zeit bezüglich der Anzahl der Elemente des Baums ausgeführt werden und sind damit auch bei großen Elementzahlen recht schnell.

Für uns interessanter ist die Fähigkeit, einen sortierten Iterator zu erzeugen. Wir wollen uns dazu ein Beispiel ansehen. Das folgende Programm erzeugt eine sortierte Menge und fügt einige Strings unsortiert ein. Anschließend werden die Strings mit Hilfe eines Iterators ausgegeben:

    001 /* Listing1508.java */
    002
    003 import java.util.*;
    004
    005 public class Listing1508
    006 {
    007   public static void main(String[] args)
    008   {
    009     //Konstruieren des Sets
    010     TreeSet s = new TreeSet();
    011     s.add("Kiwi");
    012     s.add("Kirsche");
    013     s.add("Ananas");
    014     s.add("Zitrone");
    015     s.add("Grapefruit");
    016     s.add("Banane");
    017     //Sortierte Ausgabe
    018     Iterator it = s.iterator();
    019     while (it.hasNext()) {
    020       System.out.println((String)it.next());
    021     }
    022   }
    023 }
| Listing1508.java

Listing 15.8: Die Klasse TreeSet

Die Ausgabe des Programms ist:

    Ananas
    Banane
    Grapefruit
    Kirsche
    Kiwi
    Zitrone

Der Iterator hat die Elemente also in alphabetischer Reihenfolge ausgegeben. Der Grund dafür ist, daß die Klasse `String` seit dem JDK 1.2 das `Comparable`-Interface implementiert und eine Methode `compareTo` zur Verfügung stellt, mit der die Zeichenketten in lexikographischer Ordnung angeordnet werden. Sollen die Elemente unserer Menge dagegen rückwärts sortiert werden, ist die vorhandene `compareTo`-Methode dazu nicht geeignet. Statt dessen wird nun einfach ein `Comparator`-Objekt an den Konstruktor übergeben, dessen `compare`-Methode so implementiert wurde, daß zwei zu vergleichende Strings genau dann als aufsteigend beurteilt werden, wenn sie gemäß ihrer lexikographischen Ordnung absteigend sind. Das folgende Listing zeigt dies am Beispiel der Klasse `ReverseStringComparator`:

    001 /* Listing1509.java */
    002
    003 import java.util.*;
    004
    005 public class Listing1509
    006 {
    007   public static void main(String[] args)
    008   {
    009     //Konstruieren des Sets
    010     TreeSet s = new TreeSet(new ReverseStringComparator());
    011     s.add("Kiwi");
    012     s.add("Kirsche");
    013     s.add("Ananas");
    014     s.add("Zitrone");
    015     s.add("Grapefruit");
    016     s.add("Banane");
    017     //Rückwärts sortierte Ausgabe
    018     Iterator it = s.iterator();
    019     while (it.hasNext()) {
    020       System.out.println((String)it.next());
    021     }
    022   }
    023 }
    024
    025 class ReverseStringComparator
    026 implements Comparator
    027 {
    028   public int compare(Object o1, Object o2)
    029   {
    030     return ((String)o2).compareTo((String)o1);
    031   }
    032 }
| Listing1509.java

Listing 15.9: Rückwärts sortieren mit einem Comparator

Das Programm gibt nun die Elemente in umgekehrter Reihenfolge aus:

    Zitrone
    Kiwi
    Kirsche
    Grapefruit
    Banane
    Ananas

|  | Mit Hilfe eines Comparators kann eine beliebige Sortierung der Elemente eines `SortedSet` erreicht werden. Wird ein `Comparator` an den Konstruktor übergeben, so wird die `compareTo`-Methode überhaupt nicht mehr verwendet, sondern die Sortierung erfolgt ausschließlich mit Hilfe der Methode `compare` des `Comparator`-Objekts. So können beispielsweise auch Elemente in einem `SortedSet` gespeichert werden, die das `Comparable`-Interface nicht implementieren. |  |
Hinweis

### 15.7.3 SortedMap und TreeMap

Neben einem sortierten `Set` gibt es auch eine sortierte `Map`. Das Interface `SortedMap` ist analog zu `SortedSet` aufgebaut und enthält folgende Methoden:

    Object first()
    Object last()

    SortedMap headMap(Object toElement)
    SortedMap subMap(Object fromElement, Object toElement)
    SortedMap tailMap(Object fromElement)
| java.util.SortedMap

Als konkrete Implementierung von `SortedMap` gibt es die Klasse `TreeMap`, die analog zu `TreeSet` arbeitet. Die Methoden `keySet` und `entrySet` liefern Collections, deren Iteratoren ihre Elemente in aufsteigender Reihenfolge abliefern. Auch bei einer `SortedMap` kann wahlweise mit der natürlichen Ordnung der Schlüssel gearbeitet werden oder durch Übergabe eines `Comparator`-Objekts an den Konstruktor eine andere Sortierfolge erzwungen werden.

Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage, Addison Wesley, Version 3.0
<< | < | > | >> | API | © 1998-2002 Guido Krüger, http://www.javabuch.de