From 33613a85afc4b1481367fbe92a17ee59c240250b Mon Sep 17 00:00:00 2001 From: Sven Eisenhauer Date: Fri, 10 Nov 2023 15:11:48 +0100 Subject: add new repo --- .../hjp5/html/k100103.html | 475 +++++++++++++++++++++ 1 file changed, 475 insertions(+) create mode 100644 Master/Reference Architectures and Patterns/hjp5/html/k100103.html (limited to 'Master/Reference Architectures and Patterns/hjp5/html/k100103.html') diff --git a/Master/Reference Architectures and Patterns/hjp5/html/k100103.html b/Master/Reference Architectures and Patterns/hjp5/html/k100103.html new file mode 100644 index 0000000..be10ac5 --- /dev/null +++ b/Master/Reference Architectures and Patterns/hjp5/html/k100103.html @@ -0,0 +1,475 @@ + + + +Handbuch der Java-Programmierung, 5. Auflage + + + + + + + + + +
 Titel  + Inhalt  + Suchen  + Index  + DOC  +Handbuch der Java-Programmierung, 5. Auflage +
 <<  +  <   +  >   + >>  + API  +Kapitel 15 - Collections II +
+
+ + + + +

15.6 Sortierte Collections

+
+ +
+ + + + +

15.6.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 muss sichergestellt sein, dass alle +Elemente der Collection eine compareTo-Methode +besitzen und je zwei beliebige Elemente miteinander verglichen werden +können, ohne dass 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-6.0 
+
+ +

+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 muss, in welcher +Reihenfolge zwei beliebige Elemente zueinander stehen. + + + + +

15.6.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 /* Listing1505.java */
+002 
+003 import java.util.*;
+004 
+005 public class Listing1505
+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 }
+ +		 +Listing1505.java
+ +Listing 15.5: 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, dass 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 lexikografischer +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, dass zwei zu vergleichende Strings genau dann +als aufsteigend beurteilt werden, wenn sie gemäß ihrer +lexikografischen Ordnung absteigend sind. Das folgende Listing zeigt +dies am Beispiel der Klasse ReverseStringComparator: + + +

+ + + + + +
+ +
+001 /* Listing1506.java */
+002 
+003 import java.util.*;
+004 
+005 public class Listing1506
+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 }
+ +		 +Listing1506.java
+ +Listing 15.6: 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.6.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, 5. Auflage, Addison +Wesley, Version 5.0.1 +
 <<  +  <   +  >   + >>  + API  +© 1998, 2007 Guido Krüger & Thomas +Stark, http://www.javabuch.de +
+ + + -- cgit v1.2.3