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

15.7 Sortierte Collections



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.

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:

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

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.1
 <<    <     >    >>   API  © 1998-2003 Guido Krüger, http://www.javabuch.de