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.