Programmiermethoden - Hochschule Rheinmain

Transcript

Programmiermethoden Sven Eric Panitz Hochschule RheinMain Version 451 Generiert von LectureNotes Teaching System 17. April 2016 Dieses Skript ist das kombinierte Skript zum Modul Programmiermethoden des Studiengangs WI und zu einem Teil des Moduls Programmiermethoden und Techniken im Studiengang AI. 2 Inhaltsverzeichnis 1 Iterierbare Objekte 1.1 Eine Schnittstelle zum Iterieren . . . . . . . . . . . . . 1.2 Eine generische Version der Iterationsschnittstelle . . . 1.3 Die Standard-Schnittstelle Iterator . . . . . . . . . . 1.4 Die Schnittstelle Iterable . . . . . . . . . . . . . . . . 1.4.1 Iterator als Innere Klasse . . . . . . . . . . . . 1.4.2 Verknüpfung zweier iterierbarer Objekte . . . . 1.5 Funktionen als Parameter . . . . . . . . . . . . . . . . 1.5.1 Schleifen als Methoden . . . . . . . . . . . . . . 1.5.2 Standard- (default) Methoden in Schnittstellen 1.5.3 Iterable als verzögerte Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6 7 9 12 14 15 30 31 31 32 2 Hierarchische Strukturen 2.1 Einfach verkettete Listen . . . . . . . . . . 2.1.1 Formale Definition . . . . . . . . . 2.1.2 Implementierung . . . . . . . . . . 2.1.3 Mathematische Definition . . . . . 2.2 Bäume als verallgemeinerte Listen . . . . . 2.2.1 Formale Definition . . . . . . . . . 2.2.2 Implementierung einer Baumklasse 2.3 XML als serialisierte Baumstruktur . . . . 2.4 Das syntaktische XML-Format . . . . . . 2.4.1 Elementknoten . . . . . . . . . . . 2.4.2 Leere Elemente . . . . . . . . . . . 2.4.3 Gemischter Inhalt . . . . . . . . . 2.4.4 XML Dokumente sind Bäume . . . 2.4.5 Chracter Entities . . . . . . . . . . 2.4.6 CData Sections . . . . . . . . . . . 2.4.7 Kommentare . . . . . . . . . . . . 2.4.8 Processing Instructions . . . . . . . 2.4.9 Attribute . . . . . . . . . . . . . . 2.4.10 Zeichencodierungen . . . . . . . . . 2.4.11 DTD . . . . . . . . . . . . . . . . . 2.5 XML Verarbeitung . . . . . . . . . . . . . 2.5.1 Das DOM Api . . . . . . . . . . . 2.5.2 XPath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 41 41 43 44 53 54 54 67 69 69 70 70 71 72 73 73 74 74 75 76 78 78 81 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Inhaltsverzeichnis 2.5.3 2.5.4 2.5.5 XSLT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Das SAX-API . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Das StAx-API . . . . . . . . . . . . . . . . . . . . . . . . . 105 3 Eine graphische Komponente für Baumstrukturen 4 107 Kapitel 1 Iterierbare Objekte Eine häufig zu lösende Aufgabe in der Programmierung ist es, durch bestimmte Elemente zu iterieren. Für die Iteration stehen die Schleifenkonstrukte zur Verfügung. Eine Iteration (lateinisch iteratio, die Wiederholung), soll nacheinander einen bestimmten Code-Block für verschiedene Elemente durchführen. In klassischer Weise wird zum Iterieren eine Indexvariable in einer Schleife durchgezählt. Mit dem Index wird dann in einem Schleifenrumpf jeweils etwas gerechnet. Eine klassische Schleife zum Durchlaufen der geraden Zahlen kleiner 10: 1 2 3 4 5 6 7 package name . p a n i t z . pmt . i t e r a t i o n ; p u b l i c c l a s s I t e r a t i o n 1 { p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { f o r ( i n t i = 2 ; i <10; i = i +2){ System . out . p r i n t l n ( i ) ; } } } Listing 1.1: Iteration1.java Das obige Beispiel ist in keiner Weise ein objektorientiertes Beispiel. Es ist eine ganz einfache Schleife, wie aus der imperativen Programmierung gewohnt. In einer objektorientierten Umsetzung wird stets versucht, ein Objekt zu definieren, das seine Funktionalität kapselt. In diesem Fall ein Objekt, das weiß, wie zu iterieren ist. Hierzu kann man versuchen alle im Kopf der for-Schleife gebündelten Informationen in einem Objekt zu kapseln. In der for-Schleife gibt es zunächst eine Zählvariable i. Dann einen Test, ob die Schleife noch weiter durchlaufen werden soll, und eine Anweisung, wie sich die Schleifenvariable verändert, wenn es zum nächsten Durchlauf geht. Packt man diese drei Informationen in ein Objekt, so erhalten wir die folgende Klasse: 1 2 3 4 5 package name . p a n i t z . pmt . i t e r a t i o n ; public class GeradeZahlenKleiner10Iterierer { i n t i ; // d i e S c h l e i f e n v a r i a b l e GeradeZahlenKleiner10Iterierer ( int i ){ t h i s . i = i ; // I n i t i a l i s i e r u n g d e r S c h l e i f e n v a r i a b l e 5 Kapitel 1 Iterierbare Objekte } boolean s c h l e i f e n T e s t ( ) { r e t u r n i < 1 0 ; // Test u e b e r d i e S c h l e i f e n v a r i a b l e } void s c h l e i f e W e i t e r s c h a l t e n ( ) { i = i + 2 ; // f u e r n a e c h s t e n S c h l e i f e n d u r c h l a u f } 6 7 8 9 10 11 12 Listing 1.2: GeradeZahlenKleiner10Iterierer.java Im Schleifenrumpf wird der aktuelle Wert der Iteration benutzt. In der obigen forSchleife ist das die Zahl i. Auch hierfür können wir noch eine Methode vorsehen. int schleifenWert () { return i ; } 13 14 15 Listing 1.3: GeradeZahlenKleiner10Iterierer.java Mit einem Objekt dieser Klasse können wir jetzt eine Schleife durchlaufen, ebenso wie in der ersten Schleife oben: p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { for ( GeradeZahlenKleiner10Iterierer i t = new G e r a d e Z a h l e n K l e i n e r 1 0 I t e r i e r e r ( 0 ) ; it . schleifenTest () ; it . schleifeWeiterschalten () ){ System . out . p r i n t l n ( i t . s c h l e i f e n W e r t ( ) ) ; } } 16 17 18 19 20 21 22 23 24 } Listing 1.4: GeradeZahlenKleiner10Iterierer.java 1.1 Eine Schnittstelle zum Iterieren Noch ist überhaupt kein Vorteil darin erkennbar, dass wir die Komponenten, die zur Programmierung einer Schleife benötigt werden (Initialisierung des Iterierungsobjektes, Test, Weiterschaltung, Abfragen des Schleifenelementes) in einem Objekt gekapselt haben. Der Vorteil der Objektorientierung liegt in zusätzlichen Abstraktionen. Eine der stärksten Abstraktionen in Java sind Schnittstellen. Naheliegend ist es, die Methoden der obigen Klasse in einer Schnittstelle vorzugeben: 1 2 3 4 package name . p a n i t z . pmt . i t e r a t i o n ; public interface I n t I t e r i e r e r { boolean s c h l e i f e n T e s t ( ) ; void s c h l e i f e W e i t e r s c h a l t e n ( ) ; 6 1.2 Eine generische Version der Iterationsschnittstelle Integer schleifenWert () ; 5 6 } Listing 1.5: IntIterierer.java Die Klasse oben lässt sich nun als Implementierung dieser Schnittstelle schreiben. Um die Klasse dabei noch ein wenig allgemeiner zu schreiben, übergeben wir jetzt auch die obere Schranke der Iteration im Konstruktor. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 package name . p a n i t z . pmt . i t e r a t i o n ; p u b l i c c l a s s G e r a d e Z a h l e n I t e r i e r e r implements I n t I t e r i e r e r { i n t from ; i n t to ; G e r a d e Z a h l e n I t e r i e r e r ( i n t from , i n t t o ) { t h i s . from = from ; t h i s . to = to ; } public boolean s c h l e i f e n T e s t ( ) { r e t u r n from < t o ; } public void s c h l e i f e W e i t e r s c h a l t e n ( ) { from = from + 2 ; } public Integer schleifenWert () { r e t u r n from ; } Listing 1.6: GeradeZahlenIterierer.java Eine Schleife für dieses Klasse sieht jetzt wie folgt aus. Man erkennt, dass die Schleife nur noch für die Initialisierung des Objektes der Iteration anwendungsspezifischen Code hat. Ansonsten liegt die Anwendungslogik komplett im Iterations-Objekt. p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { f o r ( I n t I t e r i e r e r i t = new G e r a d e Z a h l e n I t e r i e r e r ( 0 , 1 0 ) ; it . schleifenTest () ; it . schleifeWeiterschalten () ){ System . out . p r i n t l n ( i t . s c h l e i f e n W e r t ( ) ) ; } } 18 19 20 21 22 23 24 25 } Listing 1.7: GeradeZahlenIterierer.java 1.2 Eine generische Version der Iterationsschnittstelle Eine weitere Abstraktion, die von heutigen Programmiersprachen angeboten wird, liegt in der Möglichkeit, Typen variabel zu halten über generische Klassen und 7 Kapitel 1 Iterierbare Objekte Schnittstellen. Statt eine Iterations-Schnittstelle für ganze Zahlen zu definieren, lässt sich allgemein eine solche für beliebig aber feste Typen definieren: 1 2 3 4 5 6 package name . p a n i t z . pmt . i t e r a t i o n ; p u b l i c i n t e r f a c e G e n e r i s c h e r I t e r i e r e r { boolean s c h l e i f e n T e s t ( ) ; void s c h l e i f e W e i t e r s c h a l t e n ( ) ; A schleifenWert () ; } Listing 1.8: GenerischerIterierer.java Beim Implementieren dieser generischen Schnittstelle gilt es jetzt zu entscheiden, welcher konkrete Typ für die Typvariable eingesetzt werden soll, also was für einen Typ die Elemente haben, über die iteriert werden soll. In unserem Beispielfall sind dieses ganze Zahlen. Da für Typvariablen in generischen Typen keine primitiven Typen eingesetzt werden dürfen, benutzen wir hier die Klasse Integer und vertrauen an mehreren Stellen darauf, dass intern Daten vom Typ int und Integer gegenseitig konvertiert werden. Dieses wird als automatisches Boxing/Unboxing bezeichnet. Die neue Implementierung der Iterationsklasse sieht entsprechend wie folgt aus: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 package name . p a n i t z . pmt . i t e r a t i o n ; public class GeradeZahlenIterierer2 implements G e n e r i s c h e r I t e r i e r e r { i n t from ; i n t to ; G e r a d e Z a h l e n I t e r i e r e r 2 ( i n t from , i n t t o ) { t h i s . from = from ; t h i s . to = to ; } public boolean s c h l e i f e n T e s t () { r e t u r n from < t o ; } public void s c h l e i f e W e i t e r s c h a l t e n ( ) { from = from + 2 ; } public Integer schleifenWert () { r e t u r n from ; } Listing 1.9: GeradeZahlenIterierer2.java An der Benutzung ändert sich in diesem Fall wenig, gegenüber der nicht generischen Version. p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { f o r ( G e n e r i s c h e r I t e r i e r e r i t = new G e r a d e Z a h l e n I t e r i e r e r 2 ( 0 , 1 0 ) 19 20 21 8 1.3 Die Standard-Schnittstelle Iterator ; it . schleifenTest () ; it . schleifeWeiterschalten () ){ int i = i t . schleifenWert () ; System . out . p r i n t l n ( i ) ; 22 23 24 25 } 26 } 27 28 } Listing 1.10: GeradeZahlenIterierer2.java Gewonnen haben wir nun die Möglichkeit, auf gleiche Weise Iteratorobjekte zu implementieren, deren Elemente andere Typen haben. 1.3 Die Standard-Schnittstelle Iterator Die im vorangegangenen Abschnitt entwickelte Schnittstelle GenerischerIterierer hat ein Pendant in Javas Standard-API. Im Paket java.util findet sich dort ebenfalls eine generische Schnittstelle, die beschreibt, dass ein Objekt zum Iterieren benutzt werden kann, die Schnittstelle Iterator. Diese ist allerdings ein wenig anders aufgebaut, als unsere Schnittstelle. Sie definiert drei Methoden: • boolean hasNext(): diese Methode entspricht ziemlich genau unserer Methode schleifenTest. Sie ergibt true, wenn es noch weitere Elemente zum Iterieren gibt. • A next(): diese Methode vereint die zwei Methoden schleifenWert() und schleifeWeiterschalten unserer Schnittstelle. Es wird dabei das aktuelle Element zurück gegeben und gleichzeitig intern der Schritt weiter zum nächsten Element vorgenommen. Dieser Schritt kann nicht mehr rückgängig gemacht werden. • void remove(): diese Methode ist in der Schnittstelle als optional bezeichnet. Mit ihr soll es möglich sein, das aktuelle Element aus dem Objekt, über das iteriert wird, zu löschen. Handelt es sich bei dem Iterator um einen Iterator, der über die Elemente einer Liste iteriert, soll also das entsprechende Element aus der Liste gelöscht werden. In unserem Fall der Iteration über einen Bereich der ganzen Zahlen ergibt diese Operation keinen Sinn. Genau aus diesem Grund wurde sie in der Dokumentation als optional markiert. Um unsere Überlegungen zu einer Iterationsschnittstelle mit der Standardschnittstelle Iterator zu verbinden, bietet sich an, eine abstrakte Klasse zu definieren, die unsere drei Methoden als abstrakte, noch zu implementierende Methoden vorgibt, die Methoden der Standardschnittstelle mit Hilfe der abstrakten Methoden aber bereits implementiert. Wir definieren zunächst die drei bereits bekannten abstrakten Methoden: 9 Kapitel 1 Iterierbare Objekte 1 2 package name . p a n i t z . pmt . i t e r a t i o n ; p u b l i c a b s t r a c t c l a s s A b s t r a c t I t e r a t o r implements j a v a . u t i l . I t e r a t o r { 3 public abstract boolean s c h l e i f e n T e s t ( ) ; public abstract void s c h l e i f e W e i t e r s c h a l t e n ( ) ; public abstract A schleifenWert () ; 4 5 6 Listing 1.11: AbstractIterator.java Nun können wir mit diesen die Methoden der Standardschnittstelle Iterator umsetzen. Beginnen wir mit der Methode next(): p u b l i c A next ( ) { A result = schleifenWert () ; schleifeWeiterschalten () ; return r e s u l t ; } 7 8 9 10 11 Listing 1.12: AbstractIterator.java Man sieht genau die Bedeutung der Methode next() der aktuelle Schleifenwert wird zurück gegeben. zusätzlich wird der Iterator weiter geschaltet, so dass ein nächster Aufruf das darauffolgende Iterationselement zurück gibt. Die Methode schleifenTest() entspricht exakt der Methode hasNext() der Standardschnittstelle. Deshalb können wir in der Implementierung unsere Methode direkt aufrufen. p u b l i c b o o l e a n hasNext ( ) { return schleifenTest () ; } 12 13 14 Listing 1.13: AbstractIterator.java Schließlich sind wir noch gezwungen die Methode remove() zu implementieren. Da sie optional ist und wir sie in unseren Beispielen nicht sinnvoll umsetzen können, soll nur eine Laufzeitausnahme geworfen werden. p u b l i c v o i d remove ( ) { throw new Unsu pp ortedOperati onExc eptio n ( ) ; } 15 16 17 18 } Listing 1.14: AbstractIterator.java Um wieder an unseren konkreten Iterator über einen bestimmten Zahlenbereich zu kommen, können wir jetzt eine konkrete Unterklasse dieser abstrakten Klasse 10 1.3 Die Standard-Schnittstelle Iterator schreiben. Diese implementiert dann automatisch über die geerbten Methoden auch die Standardschnittstelle Iterator. Um noch ein wenig flexibler zu werden, sei noch ein drittes Feld der Klasse zugefügt, dass die Schrittweite beim Weiterschalten des Iterators speichert. 1 2 3 4 5 package name . p a n i t z . pmt . i t e r a t i o n ; p u b l i c c l a s s I n t e g e r R a n g e I t e r a t o r e x t e n d s A b s t r a c t I t e r a t o r { i n t from ; i n t to ; int step ; 6 I n t e g e r R a n g e I t e r a t o r ( i n t from , i n t to , i n t s t e p ) { t h i s . from = from ; t h i s . to = to ; this . step = step ; } public boolean s c h l e i f e n T e s t ( ) { r e t u r n from <= t o ; } public void s c h l e i f e W e i t e r s c h a l t e n ( ) { from = from + s t e p ; } public Integer schleifenWert () { r e t u r n from ; } 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Listing 1.15: IntegerRangeIterator.java Damit können wir jetzt in der standardmäßig in Java empfohlenen Art und Weise mit dem Iterationsobjekt über die Elemente mit einer for-Schleife iterieren. Der Iterator wird initialisiert und seine Methode hasNext() zum Schleifentest benutzt. Das Weiterschalten wird nicht im Kopf der for-Schleife vorgenommen, sondern als erster Befehl im Rumpf, indem dort die Methode next() als erste Anweisung aufgerufen wird. p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { f o r ( j a v a . u t i l . I t e r a t o r i t = new I n t e g e r R a n g e I t e r a t o r (0 ,10 ,2) ; i t . hasNext ( ) ; ) { i n t i = i t . next ( ) ; System . out . p r i n t l n ( i ) ; } } 21 22 23 24 25 26 27 28 } Listing 1.16: IntegerRangeIterator.java 11 Kapitel 1 Iterierbare Objekte 1.4 Die Schnittstelle Iterable Bisher haben wir definiert, was unter Iterator-Objekten zu verstehen ist. In Javas Standard-API gibt es eine weitere Schnittstelle, die sich mit dem Konzept der Iteration beschäftigt. Es handelt sich dabei um die Schnittstelle Iterable. Diese liegt nicht im Paket java.util sondern im Standardpaket java.lang. Sie muss also nicht explizit importiert werden, wenn man sie benutzen will. Auch die Schnittstelle Iterable ist generisch. Sie soll ausdrücken, dass ein Objekt iterierbar ist, in dem Sinne, dass es ein Iterator-Objekt gibt, mit dessen Hilfe über die Elemente des Objekts iteriert werden kann. Deshalb kommt die Schnittstelle Iterable zunächst (im nächsten Abschnitt werden wir sehen, das dem bald nicht mehr so ist) mit einer einzigen Methode aus. Die Methode heißt iterator() und ist dazu gedacht, das Iteratorobjekt für die Klasse zu erfragen. Typische Beispiele sind hierbei natürlich die klassischen Sammlungsklassen, wie Listen und Mengen. Diese implementieren alle die Schnittstelle Iterable. Bleiben wir zunächst bei unserem durchgängigen Beispiel. Statt jetzt direkt die Iteratorklasse für einen Zahlenbereich zu definieren, können wir zunächst eine Klasse definieren, die nur einen Zahlenbereich beschreibt. Wir lassen sie aber die Schnittstelle Iterable implementieren. Erst der Aufruf der Methode iterator() erzeugt dann ein entsprechendes Iterator-Objekt. 1 2 3 4 5 package name . p a n i t z . pmt . i t e r a t i o n ; p u b l i c c l a s s I n t e g e r R a n g e implements I t e r a b l e { i n t from ; i n t to ; int step ; 6 p u b l i c I n t e g e r R a n g e ( i n t from , i n t to , i n t s t e p ) { t h i s . from = from ; t h i s . to = to ; this . step = step ; } 7 8 9 10 11 Listing 1.17: IntegerRange.java Um diese Klasse noch etwas flexibler benutzen zu können, sehen wir zwei weitere Konstruktoren vor. Diese setzen die Schrittweite und die obere Schranke auf Standardwerte: p u b l i c I n t e g e r R a n g e ( i n t from , i n t t o ) { t h i s ( from , to , 1 ) ; } p u b l i c I n t e g e r R a n g e ( i n t from ) { t h i s ( from , I n t e g e r .MAX_VALUE, 1 ) ; } 12 13 14 15 16 17 12 1.4 Die Schnittstelle Iterable Listing 1.18: IntegerRange.java Die Klasse zum Iterieren über einen Zahlenbereich haben wir bereits entwickelt. Diese kann nun für die Methode iterator() benutzt werden. p u b l i c j a v a . u t i l . I t e r a t o r i t e r a t o r ( ) { r e t u r n new I n t e g e r R a n g e I t e r a t o r ( from , to , s t e p ) ; } 18 19 20 Listing 1.19: IntegerRange.java Java hat eine syntaktische Besonderheit für Objekte, die die Schnittstelle Iterable implementieren, eingeführt. Eine besondere Art der Schleife, die als for-each Schleife bezeichnet wird. Diese hat im Schleifenrumpf zwei Komponenten, die durch einen Doppelpunkt getrennt werden. Nach dem Doppelpunkt steht das iterierbare Objekt, vor dem Doppelpunkt wird die Variable definiert, an der in jedem Schleifendurchlauf das aktuelle Element gebunden ist. Für unser Beispiel erhalten wir dann die folgende kompakte Schleife: p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { I n t e g e r R a n g e i s = new I n t e g e r R a n g e ( 0 , 1 0 , 2 ) ; for ( int i : is ){ System . out . p r i n t l n ( i ) ; } 21 22 23 24 25 Listing 1.20: IntegerRange.java Gelesen wird dieses Konstrukt als: Für alle Zahlen i aus dem iterierbaren Objekt is führe den Schleifenrumpf aus. Im Vergleich hierzu, sei hier noch einmal die entsprechende Schleife ohne Verwendung der for-each Schleife geschrieben. In diesem Fall wird explizit nach dem Iterator-Objekt gefragt. f o r ( j a v a . u t i l . I t e r a t o r i t = i s . i t e r a t o r ( ) ; i t . hasNext ( ) ; ) { i n t i = i t . next ( ) ; System . out . p r i n t l n ( i ) ; } 26 27 28 29 } 30 31 } Listing 1.21: IntegerRange.java 13 Kapitel 1 Iterierbare Objekte 1.4.1 Iterator als Innere Klasse Da in der Regel die Iteratorklasse fest an der Klasse gebunden ist, über deren Elemente iteriert werden soll, bietet sich an, die Iteratorklasse zu verstecken. In Java kann hierfür eine innere Klasse benutzt werden. Mit einem Sichtbarkeitsattribut private ist dann die Iteratorklasse komplett versteckt: Wir sehen also zunächst die Klasse mit den notwendigen Feldern für die beschreibung des Iterationsbereichs vor: 32 33 package name . p a n i t z . pmt . u t i l ; import j a v a . u t i l . I t e r a t o r ; 34 35 36 37 38 p u b l i c c l a s s I n t e g e r R a n g e implements I t e r a b l e { i n t from ; i n t to ; int step ; 39 p u b l i c I n t e g e r R a n g e ( i n t from , i n t to , i n t s t e p ) { t h i s . from = from ; t h i s . to = to ; this . step = step ; } 40 41 42 43 44 45 p u b l i c I n t e g e r R a n g e ( i n t from , i n t t o ) { t h i s ( from , to , 1 ) ; } p u b l i c I n t e g e r R a n g e ( i n t from ) { t h i s ( from , I n t e g e r .MAX_VALUE, 1 ) ; } 46 47 48 49 50 51 Listing 1.22: IntegerRange.java Für diese Klasse kann ein Iterator-Objekt erzeugt werden: p u b l i c I t e r a t o r i t e r a t o r ( ) { r e t u r n new I n t e g e r R a n g e I t e r a t o r ( from , to , s t e p ) ; } 52 53 54 Listing 1.23: IntegerRange.java Das Iterator-Objekt ist dabei von einer inneren Klasse, die beschreibt, wie durch die Elemente iteriert wird: p r i v a t e s t a t i c c l a s s I n t e g e r R a n g e I t e r a t o r implements I t e r a t o r < I n t e g e r >{ i n t from ; i n t to ; int step ; 55 56 57 58 59 14 1.4 Die Schnittstelle Iterable I n t e g e r R a n g e I t e r a t o r ( i n t from , i n t to , i n t s t e p ) { t h i s . from = from ; t h i s . to = to ; this . step = step ; } p u b l i c b o o l e a n hasNext ( ) { r e t u r n from < t o ; } p u b l i c I n t e g e r next ( ) { i n t r e s u l t = from ; from = from + s t e p ; return r e s u l t ; } p u b l i c v o i d remove ( ) {} 60 61 62 63 64 65 66 67 68 69 70 71 72 73 } 74 75 } Listing 1.24: IntegerRange.java 1.4.2 Verknüpfung zweier iterierbarer Objekte In diesem Abschnitt werden wir aus zwei iterierbaren Objekten eines machen. Das neue Objekte soll erst durch die Elemente des einen iterierebaren Objekts und anschließend durch die Elemente des zweiten iterieren. Es ist also ein Aneinanderhängen der beiden Iterables. Fast wie bei Listen, die aneinander gehängt werden. Hierzu sei die Klasse Append entwickelt. Objekte dieser Klasse sollen aus zwei iterierbaren Objekten ein neues erzeugen. Somit ist sie als generische Klasse, die Iterable implementiert entworfen: 1 2 package name . p a n i t z . pmt . u t i l ; import j a v a . u t i l . I t e r a t o r ; 3 4 p u b l i c c l a s s Append implements I t e r a b l e { Listing 1.25: Append.java Die Klasse Append soll zwei iterierbare Objekte zu einem neuen verbinden. Hierzu braucht sie Felder, um die beiden zu verkknüpfenden Objekte zu speichern: 5 6 I t e r a b l e xs ; I t e r a b l e ys ; Listing 1.26: Append.java In gewohnter Weise ist ein Konstruktor vorzusehen, der diese Felder initialisiert. 15 Kapitel 1 Iterierbare Objekte p u b l i c Append ( I t e r a b l e xs , I t e r a b l e ys ) { t h i s . xs = xs ; t h i s . ys = ys ; } 7 8 9 10 Listing 1.27: Append.java Es muss schließlich eine Methode geben, die den neuen Iterator zurück gibt, der durch beide Objekte iteriert. @Override p u b l i c I t e r a t o r i t e r a t o r ( ) { r e t u r n new MyIt ( ) ; } 11 12 13 14 Listing 1.28: Append.java Die hier instantiierte Klasse MyIt wird als innere Klasse der Klasse Append realisiert: p u b l i c c l a s s MyIt implements I t e r a t o r { 15 Listing 1.29: Append.java Der neue Iterator muss die beiden ursprünglichen Iteratoren kennen. Daher werden zwei Felder für diese vorgesehen. Initialisiert werden die Felder mit den Iteratoren, die die beiden zu verknüpfenden iterierbaren Objekte der äußeren Klasse Append zurück geben: I t e r a t o r x s I t = xs . i t e r a t o r ( ) ; I t e r a t o r y s I t = ys . i t e r a t o r ( ) ; 16 17 Listing 1.30: Append.java Es bleiben die Methoden der Schnittstelle Iterator, die implementiert werden müssen. Es stellt sich die Methode hasNext() als besonders einfach heraus. Der neue Iterator hat noch weitere Elemente, wenn einer der beiden ursprünglichen Iteratoren noch ein nächstes Element hat. @Override p u b l i c b o o l e a n hasNext ( ) { r e t u r n x s I t . hasNext ( ) | | y s I t . hasNext ( ) ; } 18 19 20 21 Listing 1.31: Append.java Wo holt der neue Iterator sein nächstes Element her? Wenn es noch weitere Elemente im ersten Iterator gibt, dann aus diesem, ansonsten aus dem zweiten Iterator. 16 1.4 Die Schnittstelle Iterable @Override p u b l i c E next ( ) { i f ( x s I t . hasNext ( ) ) r e t u r n x s I t . next ( ) ; r e t u r n y s I t . next ( ) ; } 22 23 24 25 26 Listing 1.32: Append.java Auf einer Implementierung der Methode remove() verzichten wir wieder. @Override p u b l i c v o i d remove ( ) {} 27 } 28 29 } Listing 1.33: Append.java In einer kleinen Testklasse soll die Klasse Append an zwei Beispielen ausprobiert werden. 1 package name . p a n i t z . pmt . u t i l ; Listing 1.34: AppendTest.java Einer der beiden Beispielaufrufe soll mit Standardlisten gemacht werden, so dass diese importiert werden. 2 3 4 5 6 import import import import import java . u t i l . ArrayList ; java . u t i l . I t e r a t o r ; java . u t i l . LinkedList ; java . u t i l . List ; name . p a n i t z . pmt . i t e r a t i o n . I n t e g e r R a n g e ; Listing 1.35: AppendTest.java Im ersten Beispielaufruf sollen zwei iterierte Zahlenbereiche nacheinander iteriert werden: 7 8 9 10 11 p u b l i c c l a s s AppendTest { p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { f o r ( i n t i : new Append<>(new I n t e g e r R a n g e ( 1 , 1 5 ) , new I n t e g e r R a n g e (47 ,52) ) ){ System . out . p r i n t l n ( i ) ; } Listing 1.36: AppendTest.java Im zweiten Beispielaufruf werden als iterierbare Objekte zunächst Listen erzeugt: 17 Kapitel 1 Iterierbare Objekte L i s t xs = new L i n k e d L i s t <>() ; xs . add ( ” Freunde ” ) ; xs . add ( ” Roemer ” ) ; xs . add ( ” L a n d s l e u t e ” ) ; 12 13 14 15 16 L i s t ys = new A r r a y L i s t <>() ; ys . add ( ” l e i h t ” ) ; ys . add ( ” mir ” ) ; ys . add ( ” Euer ” ) ; ys . add ( ”Ohr” ) ; 17 18 19 20 21 Listing 1.37: AppendTest.java Diese beiden Listen lassen sich nun auch zu einem neuen iterierbaren Objekt mit Append verbinden: f o r ( S t r i n g s : new Append<>(xs , ys ) ) { System . out . p r i n t l n ( s . toUpperCase ( ) ) ; } 22 23 24 } 25 26 } Listing 1.38: AppendTest.java Aufgabe 1 In dieser Aufgabe sollen Sie Klassen schreiben, die die Schnittstelle Iterable implementieren und es ermöglichen über unterschiedliche Daten zu iterieren. Der Iterator soll dabei jeweils als private innere Klasse realisiert werden. a) Schreiben Sie noch einmal, wie bereits in diesem Kapitel vorgemacht, eine Iterable-Klasse, die es es erlaubt über einen Zahlenbereich zu iterieren. Nennen Sie die Klasse IntRange und sehen Sie viele verschiedene Konstruktoren vor: • IntRange(): es wird endlos über alle int Werte beginnend bei 0 iteriert. • IntRange(int from): es wird endlos über alle int Werte beginnend bei from iteriert. • IntRange(int from, int to): es wird beginnend bei from bis einschließlich to iteriert. • IntRange(int from, int to, int step): es wird beginnend bei from bis einschließlich to in step Schritten iteriert. Lösung 1 2 18 package name . p a n i t z . u t i l ; import j a v a . u t i l . I t e r a t o r ; 1.4 Die Schnittstelle Iterable 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 p u b l i c c l a s s IntRange implements I t e r a b l e { i n t from ; i n t to ; int step ; boolean i n f i n i t e ; p u b l i c IntRange ( i n t from , i n t to , int step ){ t h i s . from = from ; t h i s . to = to ; this . step = step ; infinite = false ; } p u b l i c IntRange ( i n t from , i n t to ) { t h i s ( from , to , 1 ) ; } p u b l i c IntRange ( i n t from ) { t h i s ( from , 0 ) ; i n f i n i t e = true ; } p u b l i c IntRange ( ) { this (1) ; } @Override p u b l i c I t e r a t o r i t e r a t o r ( ) { r e t u r n new I t e r ( from ) ; } p r i v a t e c l a s s I t e r implements I t e r a t o r { i n t from ; I t e r ( i n t from ) { t h i s . from = from ; } @Override p u b l i c b o o l e a n hasNext ( ) { r e t u r n i n f i n i t e | | from<= t o ; } @Override p u b l i c I n t e g e r next ( ) { i n t r e s u l t = from ; from = from+s t e p ; return r e s u l t ; } } } Listing 1.39: IntRange.java b) Schreiben Sie eine Klasse Fib, die Iterable so implementiert, dass beim Aufruf der Methode next nacheinander die Fibonaccizahlen zurück gegeben werden. Lösung Da die Fibonaccizahlen so schnell wachsen, dass sie nach wenigen Zahlen den Bereich des Datentyps Integer sprengen, hier abweichend von der Aufgabenstellung eine Lösung, die die Klasse BigInteger benutzt und somit beliebig große Zahlen berechnen kann. 1 package name . p a n i t z . u t i l ; 19 Kapitel 1 Iterierbare Objekte 2 3 4 5 6 7 8 9 10 import j a v a . u t i l . I t e r a t o r ; import j a v a . math . B i g I n t e g e r ; p u b l i c c l a s s Fib implements I t e r a b l e { @Override p u b l i c I t e r a t o r i t e r a t o r ( ) { r e t u r n new I t e r ( ) ; } p r i v a t e c l a s s I t e r implements I t e r a t o r { B i g I n t e g e r n2 = B i g I n t e g e r . v a l u e O f ( 0 ) ; B i g I n t e g e r n1 = B i g I n t e g e r . v a l u e O f ( 1 ) ; 11 @Override p u b l i c b o o l e a n hasNext ( ) { return true ; } @Override p u b l i c B i g I n t e g e r next ( ) { B i g I n t e g e r tmp = n2 . add ( n1 ) ; n2 = n1 ; n1 = tmp ; r e t u r n n2 ; } 12 13 14 15 16 17 18 19 20 } p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { new Fib ( ) . f o r E a c h ( x−> System . out . p r i n t l n ( x ) ) ; } 21 22 23 24 25 } Listing 1.40: Fib.java c) Schreiben Sie eine Klasse IterableString. Sie soll im Konstruktor ein String-Objekt erhalten. Die Klasse soll Iterable so implementieren, dass über die einzelnen Zeichen des Strings iteriert wird. Lösung Die iterierbare Klasse bekommt einen String im Konstruktor übergeben. Als Iterator wird ein Objekt einer inneren Iteratorklasse erzeugt: 1 2 package name . p a n i t z . u t i l ; import j a v a . u t i l . I t e r a t o r ; 3 4 5 public class I t e r a b l e S t r i n g implements I t e r a b l e { f i n a l private String str ; 6 7 8 9 public IterableString ( String str ){ this . str = str ; } 10 11 12 13 p u b l i c I t e r a t o r i t e r a t o r ( ) { r e t u r n new I t e r ( ) ; } Listing 1.41: IterableString.java 20 1.4 Die Schnittstelle Iterable Nun wird die innere Iteratorklasse definiert. Diese hat ein int Feld, in dem der Iterator wich merkt, wie oft schon das nächste Element erfragt wurde. p r i v a t e c l a s s I t e r implements I t e r a t o r { private int i = 0; 14 15 Listing 1.42: IterableString.java Wenn bereits alle Zeichen des Strings mit next() erfragt wurden, dann gibt es kein nächstes Element. p u b l i c b o o l e a n hasNext ( ) { return i < str . length () ; } 16 17 18 Listing 1.43: IterableString.java Um das nächste Element zurück zu geben, wird das i-te Element des Strings erfragt. Anschließend wird i um 1 erhöht. p u b l i c C h a r a c t e r next ( ) { r e t u r n s t r . charAt ( i ++) ; } 19 20 21 } 22 23 p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { f o r ( c h a r c : new I t e r a b l e S t r i n g ( ” H e l l o world ! ” ) ) { System . out . p r i n t l n ( c ) ; } } 24 25 26 27 28 29 } Listing 1.44: IterableString.java d) Schreiben Sie eine Klasse Lines. Sie soll Iterable so implementieren, dass nacheinander die Zeilen eines im Konstruktor übergebenen Strings bei der Iteration durchlaufen werden. Lösung 1 2 package name . p a n i t z . u t i l ; import j a v a . u t i l . I t e r a t o r ; 3 4 5 6 7 8 p u b l i c c l a s s L i n e s implements I t e r a b l e { s t a t i c S t r i n g NEW_LINE = System . g e t P r o p e r t y ( ” l i n e . s e p a r a t o r ”) ; String [ ] l i n e s ; public Lines ( String s t r ) { l i n e s = s t r . s p l i t (NEW_LINE) ; 21 Kapitel 1 Iterierbare Objekte } 9 10 @Override p u b l i c I t e r a t o r i t e r a t o r ( ) { r e t u r n new MyIt ( ) ; } 11 12 13 14 p u b l i c c l a s s MyIt implements I t e r a t o r { int i = 0; @Override p u b l i c b o o l e a n hasNext ( ) { r e t u r n i so implementieren, dass über die einzelnen Zeichen, die ein im Konstruktor übergebenes Reader-Objekt liefert, iteriert wird. Bei der Lösung dieser Aufgabe ergibt sich ein Problem. Ein Reader kann nur einmal zum Iterieren benutzt werden. Würde man erlauben, das zwei Iteratoren die Methode desselben Readers benutzen, um das nächste Element zu holen, dann würden beide Iteratoren implizit ein Zeichen weiter geschaltet werden. Daher werden wir verbieten, dass zweimal die Methode iterator() aufgerufen wird. Beim zweiten Mal wird dann eine Ausnahme geworfen. Lösung Bei der Lösung dieser Aufgabe ergibt sich ein Problem. Ein Reader kann nur einmal zum Iterieren benutzt werden. Würde man erlauben, das zwei Iteratoren die Methode desselben Readers benutzen, 22 1.4 Die Schnittstelle Iterable um das nächste Element zu holen, dann würden beide Iteratoren implizit ein Zeichen weiter geschaltet werden. Daher werden wir verbieten, dass zweimal die Methode iterator() aufgerufen wird. Beim zweiten Mal wird dann eine Ausnahme geworfen. 1 2 3 4 5 package name . p a n i t z . u t i l ; import j a v a . u t i l . I t e r a t o r ; import j a v a . i o . Reader ; import j a v a . i o . IOException ; import j a v a . i o . F i l e R e a d e r ; 6 7 8 9 p u b l i c c l a s s R e a d e r I t e r a b l e implements I t e r a b l e { f i n a l p r i v a t e Reader i n ; boolean iteratorGiven = f a l s e ; 10 11 12 13 p u b l i c R e a d e r I t e r a b l e ( Reader i n ) { this . in = in ; } 14 15 16 17 18 19 20 21 p u b l i c I t e r a t o r i t e r a t o r ( ) { i f ( iteratorGiven ) throw new RuntimeException ( ” R e a d e r I t e r a b l e can o n l y be i t e r a t e d once ” ) ; iteratorGiven = true ; r e t u r n new I t e r ( ) ; } 22 23 24 25 26 27 28 29 30 31 32 33 34 p r i v a t e c l a s s I t e r implements I t e r a t o r { i n t nextChar ; Iter () { try { nextChar = i n . r e a d ( ) ; } c a t c h ( IOException ex ) { throw new j a v a . u t i l . NoSuchElementException ( ) ; } } p u b l i c b o o l e a n hasNext ( ) { r e t u r n nextChar >= 0 ; } 35 p u b l i c C h a r a c t e r next ( ) { c h a r r e s u l t = ( c h a r ) nextChar ; try { nextChar = i n . r e a d ( ) ; } c a t c h ( IOException ex ) { throw new j a v a . u t i l . NoSuchElementException ( ) ; } return r e s u l t ; } 36 37 38 39 40 41 42 43 44 45 } 46 23 Kapitel 1 Iterierbare Objekte p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) throws E x c e p t i o n { f o r ( c h a r c : new R e a d e r I t e r a b l e ( new F i l e R e a d e r ( a r g s [ 0 ] ) ) ) { System . out . p r i n t l n ( c ) ; } } 47 48 49 50 51 52 } Listing 1.46: ReaderIterable.java Aufgabe 1 In dieser Aufgabe geht es darum unterschiedliche Iteratorklassen zu implementieren: a) Lösen Sie die Aufgabe 1 aus Übungsblatt 11. Vergleichen Sie mit der Musterlösung. b) Schreiben Sie eine Klasse ArrayIterator, die im Konstruktor einen Array erhält und bei der Iteratoin über die einzelnen Arrayelemente iteriert. c) Schreiben Sie eine Klasse Words. Sie soll Iterable so implementieren, dass nacheinander die Wörter eines im Konstruktor übergebenen Strings bei der Iteration durchlaufen werden. Wörter werden durch Leerzeichen, Zeilenenden und Tabulatorzeichen getrennt. Es soll keine leeren Wörter geben. d) Schreiben Sie eine generische Klasse IndexIterator. Im Konstruktor soll ein Obejekt des Typs java.util.function.Function übergeben werden. Beim i-ten Aufruf der Methode next() soll der Iterator diese Funktion benutzen, um das nächste Element für den Index i zu erzeugen. e) Benutzen Sie die Klasse aus Teil d) um einen Iterator zu implementieren, der über die Quadratzahlen iteriert. f) Schreiben Sie eine generische Klasse GenerationIterator. Im Konstruktor soll ein Obejekt f des Typs java.util.function.Function und ein Element a des Typs A übergeben werden. Beim Aufruf der Methode next() soll der Iterator die folgende Folge generieren: a, f(a), f(f(a)), f(f(f(a))),.... g) Benutzen Sie die Klasse aus Teil f) um einen Iterator zu implementieren, der über alle ungeraden Zahlen iteriert. h) Ergänzen Sie die Klassen IndexIterator und GeneratorIterator um ein Feld des Typs predicate. Es soll einen überladenen Konstruktor geben, der auch dieses Feld initialisiert. Mit dem Typ des Typs Predicate soll in der Methode next getestet werden, ob der Iterator noch ein weiteres Element generiert. Aufgabe 2 In dieser Aufgabe sollen Sie aus einem oder mehreren übergebenen iterierbaren Objekten neue iterierbare Objekte erzeugen, so wie es die Klasse Append in diesem Kapitel bereits macht. 24 1.4 Die Schnittstelle Iterable a) Schreiben Sie eine generische Klasse Cons, die Iterable implementiert. Es soll folgenden Konstruktor geben: Cons(E head, Iterable tail). Der Iterator zu dieser Klasse soll beim ersten Aufruf von next() das Element head zurück geben und anschließend die Elemente des Iterators von tail. b) Wenn es zwei iterierbare Objekte gibt, dann benötigt man manchmal, gleichzeitig zusammen durch die beiden Objekte zu iterieren. Das Ergebnis ist dann ein iterierbares Objekt, das über Paare von Objekten iteriert. Das erste Paar besteht aus den beiden ersten Objekten der Iterationen, das zweite Paar aus den beiden zweiten usw. Schließlich endet die Iteration, wenn eines der beiden iterierbaren Objekte kein nächstes Element hat. Schreiben Sie zunächst eine generische Klasse Pair, die es ermöglicht Paare von Objekten zu repräsentieren. Schreiben Sie eine generische Klasse PairIterable, die Iterable> implementiert . Sie soll in einem Konstruktor zwei iterierbare Objekte übergeben bekommen: public PairIterable(Iterable it1, Iteratable it2) Beim Iterieren soll dann paarweise durch beide Iterable gelaufen werden. Lösung 1 2 3 4 5 6 7 8 package name . p a n i t z . u t i l ; p u b l i c c l a s s Pair { public A f s t ; p u b l i c B snd ; p u b l i c P a i r (A a , B b ) { fst = a; snd = b ; } 9 @Override p u b l i c S t r i n g t o S t r i n g ( ) { r e t u r n ” ( ” + f s t + ” , ” + snd + ” ) ” ; } 10 11 12 13 } Listing 1.47: Pair.java 1 2 package name . p a n i t z . u t i l ; import j a v a . u t i l . I t e r a t o r ; 3 4 5 6 p u b l i c c l a s s P a i r I t e r a b l e implements I t e r a b l e > { f i n a l p r i v a t e j a v a . l a n g . I t e r a b l e a s ; f i n a l p r i v a t e j a v a . l a n g . I t e r a b l e bs ; 25 Kapitel 1 Iterierbare Objekte p u b l i c P a i r I t e r a b l e ( j a v a . l a n g . I t e r a b l e as , j a v a . l a n g . I t e r a b l e bs ) { t h i s . as = as ; t h i s . bs = bs ; } 7 8 9 10 11 p u b l i c I t e r a t o r > i t e r a t o r ( ) { r e t u r n new I t e r ( ) ; } 12 13 14 15 p r i v a t e c l a s s I t e r implements I t e r a t o r > { p r i v a t e I t e r a t o r a I t ; p r i v a t e I t e r a t o r b I t ; Iter () { a I t = as . i t e r a t o r ( ) ; b I t = bs . i t e r a t o r ( ) ; } 16 17 18 19 20 21 22 23 p u b l i c b o o l e a n hasNext ( ) { r e t u r n b I t . hasNext ( ) && a I t . hasNext ( ) ; } 24 25 26 27 p u b l i c Pair next ( ) { r e t u r n new Pair <>( a I t . next ( ) , b I t . next ( ) ) ; } 28 29 30 } 31 32 } Listing 1.48: PairIterable.java c) Oft braucht man die Situation, dass man über zwei Dimensionen iteriert. Hierzu hat man für jede Dimension einen eigenen Iterator. Man kann sich das so vorstellen, dass, wenn man an ein übliches Koordinatensystem denkt, die eine Dimension die Punkte auf der x-Achse ist, die zweite Dimension die Punkte auf der y-Achse. Soll über den zweidimensionalen Raum iteriert werden, so wird ein Iterator benötigt, der über alle möglichen (x,y) Paare iteriert. Schreiben Sie eine generische Iteratorklasse TwoDimIterable. Sie soll in einem Konstruktor zwei iterierbare Objekte übergeben bekommen: public TwoDimIterable(Iterable it1, Iterable it2) Lösung Wir geben zwei Lösungen für die Aufgabe. Die erste ist die einfachere, wird aber dem Namen der Klasse nicht wirklich gerecht. Sie funktioniert wie zwei ineinander verschachtelte Schleifen. Die äußere läuft über den einen Iterator, die innere über den anderen. Der Nachteil ist: wenn der innere Iterator nie terminiert, sprich unendlich viele Elemente 26 1.4 Die Schnittstelle Iterable liefert, dann ist nicht mehr gewährleistet, dass jedes Element der Paarmenge irgendwann im Ergebnisiterator erhalten wird. 1 2 3 package name . p a n i t z . u t i l ; import name . p a n i t z . pmt . i t e r a t i o n . I n t e g e r R a n g e ; import j a v a . u t i l . I t e r a t o r ; 4 5 6 7 p u b l i c c l a s s D i a g o n a l I t e r a b l e implements I t e r a b l e >{ j a v a . l a n g . I t e r a b l e a s ; j a v a . l a n g . I t e r a b l e bs ; 8 9 10 11 12 13 14 15 16 17 18 19 p r i v a t e c l a s s I t e r implements I t e r a t o r >{ I t e r a t o r a I t ; I t e r a t o r b I t ; A a = null ; Iter () { a I t = as . i t e r a t o r ( ) ; b I t = bs . i t e r a t o r ( ) ; } p u b l i c b o o l e a n hasNext ( ) { r e t u r n b I t . hasNext ( ) | | a I t . hasNext ( ) ; } 20 p u b l i c Pair next ( ) { i f ( a == n u l l ) a = a I t . next ( ) ; i f ( b I t . hasNext ( ) ) r e t u r n new Pair <>(a , b I t . next ( ) ) ; a = a I t . next ( ) ; b I t = bs . i t e r a t o r ( ) ; 21 22 23 24 25 26 27 r e t u r n next ( ) ; 28 } 29 30 } 31 32 33 34 p u b l i c I t e r a t o r > i t e r a t o r ( ) { r e t u r n new I t e r ( ) ; } 35 36 37 38 39 p u b l i c D i a g o n a l I t e r a b l e ( j a v a . l a n g . I t e r a b l e as , j a v a . l a n g . I t e r a b l e bs ) { t h i s . as = as ; t h i s . bs = bs ; } 40 41 42 43 p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { I t e r a b l e a s = new IntRange ( 2 , 2 0 , 2 ) ; I t e r a b l e bs = new IntRange ( 5 1 , 9 9 , 4 ) ; 44 45 f i n a l I t e r a b l e > ps = new D i a g o n a l I t e r a b l e (as , bs ) ; 46 27 Kapitel 1 Iterierbare Objekte f o r ( Pair p : ps ) { System . out . p r i n t l n ( p ) ; } 47 48 49 } 50 51 } Listing 1.49: DiagonalIterable.java Die zweite Umsetzung führt tatsächlich eine Diagonalisierung durch. Hierzu werden zwei interne Hilfslisten verwendet. Diese beinhalten immer die bereits von den beiden Iteratoren gesehenen Elemente. Allerdings sind beide in entgegengesetzter Reihenfolge. Nun kann mit dem PairIterable aus der letzten Aufgabe jeweils der Iterator für eine Diagonale in diesem Zweidimensionalen Raum erzeugt werden. Etwas kompliziert wird die Lösung, weil die beiden Listen, sobald die Iteratoren keine neuen Elemente mehr liefern auf korrekte Weise wieder stückchenweise abgebaut werden müssen. 1 2 3 4 package name . p a n i t z . u t i l ; import j a v a . u t i l . I t e r a t o r ; import j a v a . u t i l . L i n k e d L i s t ; import j a v a . u t i l . L i s t ; 5 6 7 8 p u b l i c c l a s s Diagonal implements I t e r a b l e > { f i n a l p r i v a t e j a v a . l a n g . I t e r a b l e a s ; f i n a l p r i v a t e j a v a . l a n g . I t e r a b l e bs ; 9 10 11 12 13 p u b l i c D i a g o n a l ( j a v a . l a n g . I t e r a b l e as , j a v a . l a n g . I t e r a b l e bs ) { t h i s . as = as ; t h i s . bs = bs ; } 14 15 16 17 p u b l i c I t e r a t o r > i t e r a t o r ( ) { r e t u r n new I t e r ( ) ; } 18 19 20 21 p r i v a t e c l a s s I t e r implements I t e r a t o r > { p r i v a t e I t e r a t o r a I t = a s . i t e r a t o r ( ) ; p r i v a t e I t e r a t o r b I t = bs . i t e r a t o r ( ) ; 22 23 24 25 26 27 // d i e f o l g e n d e b e i d e n L i s t e n s p e i c h e r n d i e b e r e i t s ges eh en d e n i t e r i e r t e n // Element // S i e s o l l e n immer zusammen e i n e D i a g o n a l e d a r s t e l l e n p r i v a t e L i s t xs = new L i n k e d L i s t <>() ; p r i v a t e L i s t ys = new L i n k e d L i s t <>() ; 28 29 30 28 // d e r Paar−I t e r a t o r g e h t immer u e b e r e i n e D i a g o n a l e p r i v a t e I t e r a t o r > ps = new P a i r I t e r a b l e <>(xs , ys ) . i t e r a t o r ( ) ; 1.4 Die Schnittstelle Iterable 31 @Override p u b l i c b o o l e a n hasNext ( ) { r e t u r n ps . hasNext ( ) | | ( a I t . hasNext ( ) && b I t . hasNext ( ) ) | | ( xs . s i z e ( ) >= 1 && b I t . hasNext ( ) ) | | ( ys . s i z e ( ) >= 1 && a I t . hasNext ( ) ) | | ( xs . s i z e ( ) > 1 && xs . s i z e ( ) > 1 ) ; } 32 33 34 35 36 37 38 39 @Override p u b l i c Pair next ( ) { i f ( ! ps . hasNext ( ) ) { b o o l e a n aitHadNext = a I t . hasNext ( ) ; 40 41 42 43 44 // das n a e c h s t e x wird h i n t e n angehaengt i f ( a I t . hasNext ( ) ) { xs . add ( a I t . next ( ) ) ; } // wenn k e i n ne u e s y mehr kommt , wird x l i s t e vorne um e i n // Element g e k u e r z t i f ( ! b I t . hasNext ( ) ) { xs = xs . s u b L i s t ( 1 , xs . s i z e ( ) ) ; } 45 46 47 48 49 50 51 52 53 54 // das n a e c h s t e y wird vorne angehaengt i f ( b I t . hasNext ( ) ) { ys . add ( 0 , b I t . next ( ) ) ; } // wenn k e i n ne u e s x mehr kam , wird y l i s t e h i n t e n um 55 56 57 58 59 ein // Element g e k u e r z t 60 61 i f ( ! aitHadNext ) { ys = ys . s u b L i s t ( 0 , ys . s i z e ( ) − 1 ) ; } 62 63 64 65 // D i a g o n a l e wurde a u f g e b a u t und kann j e t z t i t e r i e r t werden ps = new P a i r I t e r a b l e <>(xs , ys ) . i t e r a t o r ( ) ; } r e t u r n ps . next ( ) ; } 66 67 68 69 70 71 } 72 73 74 75 76 77 78 79 p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { L i s t xs = new L i n k e d L i s t <>() ; xs . add ( ” x1 ” ) ; xs . add ( ” x2 ” ) ; xs . add ( ” x3 ” ) ; xs . add ( ” x4 ” ) ; L i s t ys = new L i n k e d L i s t <>() ; 29 Kapitel 1 Iterierbare Objekte ys . add ( ” y1 ” ) ; ys . add ( ” y2 ” ) ; ys . add ( ” y3 ” ) ; ys . add ( ” y4 ” ) ; ys . add ( ” y5 ” ) ; new Diagonal <>(xs , ys ) . f o r E a c h ( p −>System . out . p r i n t l n ( p ) ) ; 80 81 82 83 84 85 } 86 87 } Listing 1.50: Diagonal.java d) Schreiben Sie eine generische Iterableklasse Interleave. Sie soll in einem Konstruktor zwei iterierbare Objekte übergeben bekommen. Die resultierende Iteration, soll abwechselnd aus den beiden Iterable, die Elemente beziehen, bis einer der beiden Iteratoren kein weiteres Element liefert. 1.5 Funktionen als Parameter Mit der Version 1.8 von Java sollte die Schnittstelle Iterable zunächst eine gewaltige Aufwertung erhalten. Dieses führte schließlich dazu, dass für die neuen Funktionalitäten, die in die Schnittstelle eingebaut wurden, eine komplett neue Schnittstelle entwickelt wurde, die sich nun in dem Paket java.util.stream befindet. Es ist die Schnittstelle Stream, die in Zukunft eine wesentliche Erweiterung des Konzeptes für Iteratoren ausdrücken wird. Da diese zum jetzigen Zeitpunkt noch nicht endgültig definiert ist, werden wir sie in diesem Semester noch nicht betrachten. Dafür betrachten wir mögliche Erweiterungen der Schnittstelle Iterable. Bisher hatte die Schnittstelle Iterable nur die einzige Methode iterator(), mit der ein Iterator-Objekt erzeugt wurde, das zum einmaligen Iterieren durch die Elemente eines Objekts benutzt werden konnte. Zwei neue Konzepte bringt Java 1.8 mit, die es ermöglichen, die Schnittstelle Iterable um wesentliche Funktionalität zu erweitern und ihre eine noch zentralere Rolle zukommen zu lassen. • Mit Java 1.8 können Schnittstellen, wie bisher nur von abstrakten Klassen her bekannt, auch Methoden bereits konkret implementieren, wobei sie die abstrakten Methoden bereits benutzen können. • Mit Java 1.8 werden sogenannte Lambda-Ausdrücke, die auch als Closures bezeichnet werden, sowie auch Methodenobjekte der Sprache Java hinzugefügt. Mit diesen neuen Sprachkonzepten wird eine bisher in Java nur schwer realisierbare Programmiermethodik möglich. Die sogenannte Programmierung höherer Ordnung. 30 1.5 Funktionen als Parameter Dabei werden Methoden oder auch Codeblöcke als Parameter anderen Methoden übergeben. Dieses ermöglicht eine wesentlich stärkere Abstraktion in der Parameterisierung des Codes. Es kann jetzt über eine ganze Befehlsfolge auf einfache Weise abstrahiert werden. Die Schnittstelle Iterable hat weiterhin nur einen abstrakte Methode, die Methode iterator(), die wir bereits kennen. Zusätzlich sind eine ganze Menge weiterer Methoden implementiert. Bei diesen handelt es sich zum großen Teil um Methoden höherer Ordnung. Um die Beispiele dieses Kapitels zu übersetzen, wird ein Compiler benötigt, der bereits die entsprechenden Sprachkonstrukte für Java 1.8 unterstützt. Er kann auf der Webseite des Project Lambda (http://openjdk.java.net/projects/lambda) herunter geladen werden. 1.5.1 Schleifen als Methoden Die erste neue Methode höherer Ordnung der Schnittstelle Iterable, die wir betrachten, ist die Methode forEach. Sie hat ein Argument. Dieses ist ein Parameter vom neuen Typ Block. Es handelt sich dabei um einen belieben Code-Block, der abhängig ist von einer Variablen. Hierfür gibt es eine neue Syntax. Es wird die Variable (eine in diesem Kontext neu deklarierte Variable) in runde Klammern geschrieben. Anschließend folgt ein aus einem Minuszeichen und dem Größerzeichen gebildeter Pfeil. Danach kommt in geschweifte Klammern ein beliebiger Code-Block. Damit ist es möglich, die for-Schleife komplett als Methodenaufruf darzustellen: 1 2 3 4 package name . p a n i t z . pmt . i t e r a t i o n ; p u b l i c c l a s s ForEachExample { p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { I n t e g e r R a n g e i s = new I n t e g e r R a n g e ( 0 , 1 0 , 1 ) ; 5 i s . f o r E a c h ( ( x ) −> { System . out . p r i n t l n ( x ) ; } ) ; 6 } 7 8 } Listing 1.51: ForEachExample.java Die Zeile is.forEach( (x) -> {System.out.println(x);}) ist wie folgt zu lesen: Für jedes Element x im iterierbaren Objekt is führe den Code-Block aus, der aus der einzigen Anweisung println besteht. 1.5.2 Standard- (default) Methoden in Schnittstellen Mit Java 1.8 ist es jetzt möglich, ähnlich wie in abstrakten Klassen bestimmte Methoden bereits auszuimplementieren und dabei bereits auf die noch abstrakten Methoden zuzugreifen. Ein Beispiel hierfür haben wir bereits gesehen. In der Schnittstelle 31 Kapitel 1 Iterierbare Objekte Iterable gibt es nun die Methode forEach. Diese ist bereits in der Schnittstelle konkret implementiert. Beim Implementieren der Schnittstelle brauchten wir diese nicht selbst zu implementieren. Wir haben sie quasi geschenkt bekommen. Mit Java 1.8 wird auch in der Schnittstelle Iterator eine Standardmethode eingeführt. Die bisher abstrakte aber in der Dokumentation als optional beschriebene Methode remove hat von nun an eine Standardimplementierung und braucht beim Implementieren der Schnittstelle nicht mehr selbst implementiert werden. Wie man sieht, könnte man mit dieser Methode fast auf die Schleifen in Java verzichten. Tatsächlich gibt Es Programmiersprachen, die diesen Weg gegangen sind und keine speziellen Schleifenkonstrukte kennen. 1.5.3 Iterable als verzögerte Listen Man kann mit den default-Methoden jetzt soweit gehen, dass man gleich die Schnittstelle Iterable soweit aufmotzt, dass sie bereits eine einfach verkettete Liste darstellt. Hierzu braucht sie im Prinzip fünf Methoden: • eine Testmethode empty(), die testet, ob die Liste leer ist. • eine Methode head(), die das erste Element zurück gibt. • eine Methode tail(), die die Liste ohne das erste Element zurück gibt. • eine Methode nil() zum Erzeugen einer leeren Liste. • eine Methode cons(x,xs), die eine neue Liste erzeugt, bestehend aus einem neuem ersten Element und einer Restliste. Wir können tatsächlich eine eigene Schnittstelle Iterable schreiben, die diese fünf Methoden hat. Hierzu schreiben wir eine Unterschnittstelle von Iterable mit den entsprechenden dafault-Methoden: 1 2 3 4 5 package name . p a n i t z . u t i l ; import j a v a . u t i l . I t e r a t o r ; import j a v a . u t i l . f u n c t i o n . * ; p u b l i c i n t e r f a c e I t e r a b l e e x t e n d s j a v a . l a n g . I t e r a b l e { p u b l i c I t e r a t o r i t e r a t o r ( ) ; Listing 1.52: Iterable.java Die Testmethode, ob es sich um eine leere Liste handelt, lässt sich einfach implementieren. Man lässt sich einen Iterator geben und fragt diesen, ob er ein nächstes Element hat. p u b l i c d e f a u l t b o o l e a n empty ( ) { r e t u r n ! i t e r a t o r ( ) . hasNext ( ) ; } 6 7 8 Listing 1.53: Iterable.java 32 1.5 Funktionen als Parameter Die Methode head ist einfach zu implementieren. Es muss das Iterable-Objekt nach seinem Iterator gefragt werden und von diesem das erste Element zurück gegeben werden. 9 10 11 p u b l i c d e f a u l t A head ( ) { r e t u r n i t e r a t o r ( ) . next ( ) ; } Listing 1.54: Iterable.java Auch die Methode tail ist einfach zu implementieren. Es wird zunächst der Iterator erfragt. Dieser wird durch einmaliges Aufrufen von next() auf das zweite Element geschaltet. Nun ist es der Iterator für das neue Iterable. 12 13 14 15 16 17 18 p u b l i c d e f a u l t I t e r a b l e t a i l ( ) { r e t u r n ( )−>{ I t e r a t o r r e s u l t = i t e r a t o r ( ) ; r e s u l t . next ( ) ; return r e s u l t ; }; } Listing 1.55: Iterable.java Aufmerksamen Beobachtern mag aufgefallen sein, dass sich mit den Methoden empty und tail bereits viele typische Methoden für Listenstrukturen umsetzen lassen. So zum Beispiel die Berechnung der Länge: 19 20 21 public default int length () { r e t u r n empty ( ) ? 0 : 1+ t a i l ( ) . l e n g t h ( ) ; } Listing 1.56: Iterable.java cons und nil für Iterables Wir brauchen die Methode nil() die uns eine Iterable-Objekt erzeugt, dessen Iterator über kein einziges Element iteriert. Es ist also ein leeres Iterable-Objekt. Deshalb gibt die Methode hasNext immer false zurück.: 22 23 24 25 26 27 p u b l i c s t a t i c I t e r a b l e n i l ( ) { r e t u r n ( )−>{ r e t u r n new I t e r a t o r () { p u b l i c b o o l e a n hasNext ( ) { r e t u r n f a l s e ; } p u b l i c A next ( ) { throw new j a v a . u t i l . NoSuchElementException ( ” next f o r empty iterator ”) ; 33 Kapitel 1 Iterierbare Objekte } 28 }; 29 }; 30 } 31 Listing 1.57: Iterable.java Als Objektmethode schreiben wir als nächstes die Methode cons, diese erhält ein Element, welches bei der resultierenden Iteration als erstes Element zurück gegeben werden soll. Es wird also an den Iterationsbereich vorne noch ein Element angehängt. p u b l i c d e f a u l t I t e r a b l e c o n s ( f i n a l A hd ) { f i n a l I t e r a b l e t l = t h i s ; r e t u r n ( ) −> { f i n a l j a v a . u t i l . I t e r a t o r i t = t l . i t e r a t o r ( ) ; f i n a l A f i r s t = hd ; r e t u r n new I t e r a t o r () { boolean f i r s t C a l l = true ; p u b l i c b o o l e a n hasNext ( ) { r e t u r n f i r s t C a l l | | i t . hasNext ( ) ; } p u b l i c A next ( ) { i f ( firstCall ){ firstCall = false ; return f i r s t ; } else { r e t u r n i t . next ( ) ; } } }; }; } 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 Listing 1.58: Iterable.java Als eine statische Methode wird noch eine Variante dieser Methode implementiert. Diese Variante erhält das erste Element für die Iteration, sowie ein iterierbares Objekt für die übrigen Elemente. Dieses zweite iterierbare Objekt wird allerdings nicht direkt übergeben, sondern über ein Supplier-Objekt. Dieses hat genau eine Methode namens get, mit der das Objekt erfragt werden kann, das der Supplier liefert. p u b l i c s t a t i c I t e r a b l e c o n s (A hd , f i n a l j a v a . u t i l . f u n c t i o n . S u p p l i e r > t l ) { r e t u r n ( )−>{ f i n a l A f i r s t = hd ; r e t u r n new I t e r a t o r () { j a v a . u t i l . I t e r a t o r i t = n u l l ; boolean f i r s t C a l l = true ; 51 52 53 54 55 56 57 p u b l i c b o o l e a n hasNext ( ) { 58 34 1.5 Funktionen als Parameter i f ( f i r s t C a l l ) return true ; i f ( i t==n u l l ) i t=t l . g e t ( ) . i t e r a t o r ( ) ; r e t u r n i t . hasNext ( ) ; 59 60 61 } 62 63 p u b l i c A next ( ) { i f ( firstCall ){ firstCall = false ; return f i r s t ; }else { i f ( i t==n u l l ) i t=t l . g e t ( ) . i t e r a t o r ( ) ; r e t u r n i t . next ( ) ; } } 64 65 66 67 68 69 70 71 72 }; 73 }; 74 75 } Listing 1.59: Iterable.java Filter für die Iteration Mit den oben geschriebenen Methoden head, tail und cons lassen sich jetzt auf einfache Weise weitere sinnvolle Methoden für iterierbare Objekte schreiben. Zum Beispiel ein einfacher Filter. Es wird hierzu ein Prädikat übergeben, dass für ein einzelnen Element zu wahr oder falsch auswertet. Es soll ein neues iterierbares Objekt erzeugt werden, das nur noch als den Objekten des ursprünglichen existiert, für die das Prädikat zu wahr auswertet. Es gibt drei Fälle: • für ein leeres iterierbares Objekt ist auch das Ergebnis ein solche leeres Objekt. • dann ist zu testen, ob das erste Element das Prädikat erfüllt. Wenn ja, dann wird dieses als erstes Element des Ergebnisses mit cons auf den rekursiven Aufruf auf den Reste zugefügt. • ansonsten wird die Methode nur rekursiv auf die übrigen Elemente des Iterationsbereiches angewendet. 76 77 78 79 80 p u b l i c d e f a u l t I t e r a b l e f i l t e r ( P r e d i c a t e p ) { i f ( empty ( ) ) r e t u r n t h i s ; i f ( p . t e s t ( head ( ) ) ) r e t u r n c o n s ( head ( ) , ( )−> t a i l ( ) . f i l t e r ( p ) ) ; return t a i l () . f i l t e r (p) ; } Listing 1.60: Iterable.java 35 Kapitel 1 Iterierbare Objekte Elemente Abbilden Eine einfache und vielfach in Sprachen, die Lambda-Ausdrücke unterstützen, verwendete Funktion, generiert aus einem Iterationsbereich mit Elementen eines bestimmten Typs einen neuen Iterationsbereich ,der entsteht, indem eine Funktion auf jedes Element angewendet wird. Es ist also wieder eine Form, der Anwendung für alle Elemente. Hier wird für jedes Element in ein neues Element mit Hilfe einer übergebenen Funktion generiert. p u b l i c d e f a u l t I t e r a b l e map( Function f ) { i f ( empty ( ) ) r e t u r n n i l ( ) ; r e t u r n c o n s ( f . apply ( head ( ) ) , ( )−> t a i l ( ) . map( f ) ) ; } 81 82 83 84 Listing 1.61: Iterable.java Faltungen Eine mächtige Funktion für Iterationsbereiche sind sogenannte Faltungen (in vielen Bibliotheken heißen die entsprechenden Funtionen fold). Bei Faltungen geht es darum, die Elemente alle mit einer Operation zu verknüpfen. Hierzu wird eine Operation benötigt, die zwei Elemente verknüpfen kann. Zusätzlich wird ein Startwert erwartet, der insbesondere als Ergebnis benutzt wird, wenn keine Elemente in der Iteration sind. Für eine Funktion ⊗ als Operation in Infix-Schreibweise sei die Faltung wie folgt definiert: reduce([x1 , x2 , . . . , xn ], start, ⊗) = start ⊗ x1 ⊗ x2 ⊗ · · · ⊗ xn Die Implementierung dieser Funktion lässt sich wunderbar per Iteration machen. Dazu werden die Elemente in einer Schleife nacheinander mit dem Startwert verknüpft. p u b l i c d e f a u l t B r e d u c e (B s t a r t , BiFunction op ) { f o r (A x : t h i s ) s t a r t = op . apply ( s t a r t , x ) ; return start ; } 85 86 87 88 Listing 1.62: Iterable.java So kurz und einfach diese Funktion wirkt, umso mächtiger ist sie, was auf den ersten Blick nicht so ersichtlich ist. Ein paar Beispiele für weitere Funktionen, die sich mit reduce umsetzen lassen. Im Prinzip ist es die Verallgemeinerung einer Iteration, bei der nacheinander die Elemente der Iteration auf ein Ergebnis akkumuliert werden. Dabei ist der Parameter start jeweils die Initialisierung der Ergebnisvariablen. 36 1.5 Funktionen als Parameter So lässt sich zum Beispiel eine Funktion schreiben, die testet, ob eines der Elemente im Iterationsbereich ein bestimmtes Prädikat erfüllt. Diese Funktion entspricht dem logischen Existenzquantor. Der Startwert ist in diesem Fall false. Es wird für jedes Element getestet, ob es das Prädikat erfüllt und schließlich die Teilergebnisse mit Oder verknüpft. 89 90 91 p u b l i c d e f a u l t b o o l e a n e x i s t s ( P r e d i c a t e p ) { r e t u r n r e d u c e ( f a l s e , ( x , y )−> x | | p . t e s t ( y ) ) ; } Listing 1.63: Iterable.java Analog funktioniert die Funktion, die testet, ob ein Prädikat für alle Elemente des Iterationsbereichs zutrifft. Diese Funktion entspricht dem logischen Allquantor. 92 93 94 p u b l i c d e f a u l t b o o l e a n f o r A l l ( P r e d i c a t e p ) { r e t u r n r e d u c e ( t r u e , ( x , y )−> x && p . t e s t ( y ) ) ; } Listing 1.64: Iterable.java So lässt sich wiederum mit der Funktion exists schnell testen, ob ein bestimmtes Element in einem Iterationsbereich enthalten ist. 95 96 97 p u b l i c d e f a u l t b o o l e a n c o n t a i n s (A e l ) { r e t u r n e x i s t s ( x −> x . e q u a l s ( e l ) ) ; } Listing 1.65: Iterable.java Es lassen sich auch wie bei einer Methode toString die Stringdarstellungen aller Elemente in einem String zusammenfügen: 98 99 100 public default String stringRepresentation () { r e t u r n r e d u c e ( ” ” , ( x , y ) −> x+” ”+y ) ; } Listing 1.66: Iterable.java Eine entsprechende Funktion, die ein Objekt der Klasse StringBuffer nutzt, um die Elemente zu einem Gesamtstring zu akkumulieren, lässt sich auch mit Hilfe von reduce formulieren: 101 102 103 104 105 p u b l i c d e f a u l t S t r i n g show ( ) { r e t u r n r e d u c e ( new S t r i n g B u f f e r ( ) , ( buf , y ) −> { buf . append ( ” ” ) ; buf . append ( y ) ; 37 Kapitel 1 Iterierbare Objekte r e t u r n buf ; }) . t o S t r i n g ( ) ; 106 107 } 108 Listing 1.67: Iterable.java Auch die Längenberechnung lässt sich mittels reduce formulieren. Als Operation wird immer die Konstante 1 hinzuaddiert: public default int length2 () { r e t u r n r e d u c e ( 0 , ( r e s u l t , x ) −> r e s u l t +1) ; } 109 110 111 Listing 1.68: Iterable.java Es lässt sich sogar die Funktion filter aus diesem Abschnitt nun komplett mit Hilfe von reduce darstellen: p u b l i c d e f a u l t I t e r a b l e f i l t e r 2 ( P r e d i c a t e p ) { r e t u r n ( ) −> ( r e d u c e ( new j a v a . u t i l . A r r a y L i s t () , ( r e s u l t , y ) −> { i f ( p . t e s t ( y ) ) r e s u l t . add ( y ) ; return r e s u l t ; }) . i t e r a t o r ( ) ) ; } 112 113 114 115 116 117 118 Listing 1.69: Iterable.java Gleiches gilt auch für die Funktion map, die sich mit Hilfe von reduce formulieren lässt. p u b l i c d e f a u l t I t e r a b l e map2 ( Function f ) { r e t u r n ( ) −> ( r e d u c e ( new j a v a . u t i l . A r r a y L i s t () , ( r e s u l t , y ) −> { r e s u l t . add ( f . apply ( y ) ) ; return r e s u l t ; }) . i t e r a t o r ( ) ) ; } 119 120 121 122 123 124 125 Listing 1.70: Iterable.java Ebenso lässt sich für einen größer Vergleich mittels eines Comparator-Objekts mit reduce das Maximum der Elemente eines Iterationsbereichs ermitteln. p u b l i c d e f a u l t A max( j a v a . u t i l . Comparator comp ) { return reduce ( null , ( r e s u l t , y ) −> { i f ( n u l l==r e s u l t ) r e t u r n y ; i f ( comp . compare ( r e s u l t , y ) > 0 ) r e t u r n r e s u l t ; 126 127 128 129 130 38 1.5 Funktionen als Parameter return y ; 131 } 132 ); 133 } 134 135 } Listing 1.71: Iterable.java Sieb des Eratosthenes Mit der obigen Filter-Funktion lässt sich eine iterierbares Objekt schreiben, dass über alle Primzahlen iteriert. Hierzu kann das bekannte Verfahren des Siebs des Eratosthenes angewendet werden. Gestartet wird mit der Folge von Zahlen beginnend von 2. 1 2 3 4 5 6 7 package name . p a n i t z . pmt . u t i l ; import name . p a n i t z . u t i l . I t e r a b l e ; p u b l i c c l a s s PrimesExample { p u b l i c s t a t i c I t e r a b l e s i e v e ( f i n a l I t e r a b l e i t ) { f i n a l i n t f i r s t = i t . head ( ) ; r e t u r n I t e r a b l e . c o n s ( f i r s t , ( )−>s i e v e ( i t . f i l t e r ( ( x )−> x%f i r s t != 0 ))); } 8 p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { I t e r a b l e i s = ( )−>new I n t e g e r R a n g e ( 2 ) . i t e r a t o r ( ) ; I t e r a b l e pr im e s = s i e v e ( i s ) ; p r i m e s . f o r E a c h ( x−>System . out . p r i n t l n ( x ) ) ; } 9 10 11 12 13 14 } Listing 1.72: PrimesExample.java Aufgabe 1 Schreiben Sie in dieser Aufgabe eine Klasse, die eine auf einem Array als Speicher benutzende generische Liste realisiert. (Eine solche Klasse wurde bereits im ersten Semester entwickelt.) Sie soll folgende Eigenschaften haben: a) Es soll das Interface name.panitz.util.Iterable implementiert werden. b) Es soll eine Methode add zum Hinzufügen neuer Elemente geben. c) Es soll zwei Konstruktoren geben. Einen Standardkonstruktor ohne Parameter und einen Konstruktor mit einer variablen Parameteranzahl. Im zweiten Fall sollen die Parameter die Elemente der Liste werden. d) Die Standardmethode length soll überschrieben werden. Warum ist dieses sinnvoller als auf die bereits in name.panitz.util.Iterable implementierte Standardmethode zu vertrauen? 39 Kapitel 1 Iterierbare Objekte Schreiben Sie umfangreiche Tests für alle Methoden. Aufgabe 2 Schreiben Sie für die Schnittstelle name.panitz.util.Iterable weitere Standardmethoden: a) Eine Methode zum Anhängen eines weiteren Iterable-Objekts: public default Iterable append(java.lang.Iterable that) Sie dürfen dabei die Klasse Append des ersten Übungsblattes verwenden. b) Schreiben Sie unter Zuhilfenahme der Klasse PairIterable des letzten Übungsblattes folgende Methode, die das Iterable-Objekt paarweise mit einem zweiten Iterable-Objekt verbindet: public default Iterable> zip(java.lang.Iterable that) c) Schreiben Sie jetzt unter Zuhilfenahme der Klasse TwoDimIterable folgende Methode, die alle Paare aus den beiden Iterable-Objekten bereit stellt: public default Iterable> cross(java.lang.Iterable that) d) Schreiben Sie eine Standardmethode für die Stringdarstellung eines Iterable-Objekts. public default String asString() Was passiert, wenn Sie versuchen als Standardmethode die Methode toString zu überschreiben. Testen Sie mit Hilfe der Klasse AList aus der ersten Aufgabe alle Standardmethoden der Klasse Iterable. 40 Kapitel 2 Hierarchische Strukturen Von zentraler Bedeutung in der Softwareentwicklung ist es, Daten auf eine hierarchische Art und Weise zu strukturieren. Solche hierarchisch strukturierten Daten sind als Bäume bekannt. Sie sind in der Softwareentwicklung von so zentraler Bedeutung, dass sich verschiedene Standards durchgesetzt haben, solche Daten in textueller Form zu serialisieren. Zum einen in Form von XML-Dokumenten, zum anderen aber auch z.B. durch das JASON-Format. In diesem Kapitel werden wir uns mit hierarchischen Daten zunächst in allgemeiner Form und anschließend in Form von XML-Dokumenten beschäftigen. 2.1 Einfach verkettete Listen Eine der häufigsten Datenstrukturen in der Programmierung sind Sammlungstypen. In fast jedem nichttrivialen Programm wird es Punkte geben, an denen eine Sammlung mehrerer Daten gleichen Typs anzulegen sind. Eine der einfachsten Strukturen, um Sammlungen anzulegen, sind Listen. Da Sammlungstypen oft gebraucht werden, stellt Java entsprechende Klassen als Standardklassen zur Verfügung. Bevor wir uns aber diesen bereits vorhandenen Klassen zuwenden, wollen wir in diesem Kapitel Listen selbst spezifizieren und programmieren. 2.1.1 Formale Definition Wir werden Listen als abstrakten Datentyp formal spezifizieren. Ein abstrakter Datentyp (ADT) wird spezifiziert über eine endliche Menge von Methoden. Hierzu wird spezifiziert, auf welche Weise Daten eines ADT konstruiert werden können. Dazu werden entsprechende Konstruktormethoden spezifiziert. Dann wird eine Menge von Funktionen definiert, die wieder Teile aus den konstruierten Daten selektieren können. Schließlich werden noch Testmethoden spezifiziert, die angeben, mit welchem Konstruktor ein Datenobjekt erzeugt wurde. Der Zusammenhang zwischen Konstruktoren und Selektoren sowie zwischen den Konstruktoren und den Testmethoden wird in Form von Gleichungen spezifiziert. 41 Kapitel 2 Hierarchische Strukturen Der Trick, der angewendet wird, um abstrakte Datentypen wie Listen zu spezifizieren, ist die Rekursion. Das Hinzufügen eines weiteren Elements zu einer Liste wird dabei als das Konstruieren einer neuen Liste aus der Ursprungsliste und einem weiteren Element betrachtet. Mit dieser Betrachtungsweise haben Listen eine rekursive Struktur: eine Liste besteht aus dem zuletzt vorne angehängten neuen Element, dem sogenannten Kopf der Liste, und aus der alten Teilliste, an die dieses Element angehängt wurde, dem sogenannten Schwanz der Liste. Wie bei jeder rekursiven Struktur bedarf es eines Anfangs der Definition. Im Falle von Listen wird dieses durch die Konstruktion einer leeren Liste spezifiziert.1 Listenkonstruktoren Abstrakte Datentypen wie Listen lassen sich durch ihre Konstruktoren spezifizieren. Die Konstruktoren geben an, wie Daten des entsprechenden Typs konstruiert werden können. In dem Fall von Listen bedarf es nach den obigen Überlegungen zweier Konstruktoren: • einem Konstruktor für neue Listen, die noch leer sind. • einem Konstruktor, der aus einem Element und einer bereits bestehenden Liste eine neue Liste konstruiert, indem an die Ursprungsliste das Element angehängt wird. Wir benutzen in der Spezifikation eine mathematische Notation der Typen von Konstruktoren.2 Dem Namen des Konstruktors folgt dabei mit einem Doppelpunkt abgetrennt der Typ. Der Ergebnistyp wird von den Parametertypen mit einem Pfeil getrennt. Somit lassen sich die Typen der zwei Konstruktoren für Listen wie folgt spezifizieren: • Empty: () → List • Cons: (Object,List) →List Listenselektoren Die Selektoren können wieder auf die einzelnen Bestandteile der Konstruktion zurückgreifen. Der Konstruktor Cons hat zwei Parameter. Für Cons-Listen werden zwei Selektoren spezifiziert, die jeweils einen dieser beiden Parameter wieder aus der Liste selektieren. Die Namen dieser beiden Selektoren sind traditioneller Weise head und tail. • head: (List) →Object 1 Man vergleiche es mit der Definition der natürlichen Zahlen: die 0 entspricht der leeren Liste, der Schritt von n nach n + 1 dem Hinzufügen eines neuen Elements zu einer Liste. 2 Entgegen der Notation in Java, in der der Rückgabetyp kurioser Weise vor den Namen der Methode geschrieben wird. 42 2.1 Einfach verkettete Listen • tail: (List) →List Der funktionale Zusammenhang von Selektoren und Konstruktoren läßt sich durch folgende Gleichungen spezifizieren: head(Cons(x, xs)) = x tail(Cons(x, xs)) = xs Testmethoden für Listen Um für Listen Algorithmen umzusetzen, ist es notwendig, unterscheiden zu können, welche Art der beiden Listen vorliegt: die leere Liste oder eine Cons-Liste. Hierzu bedarf es noch einer Testmethode, die mit einem bool’schen Wert als Ergebnis angibt, ob es sich bei der Eingabeliste um die leere Liste handelte oder nicht. Wir wollen diese Testmethode isEmpty nennen. Sie hat folgenden Typ: • isEmpty: List→ boolean Das funktionale Verhalten der Testmethode läßt sich durch folgende zwei Gleichungen spezifizieren: isEmpty(Empty()) = true isEmpty(Cons(x, xs)) = f alse Somit ist alles spezifiziert, was eine Listenstruktur ausmacht. Listen können konstruiert werden, die Bestandteile einer Liste wieder einzeln selektiert und Listen können nach der Art ihrer Konstruktion unterschieden werden. 2.1.2 Implementierung 1 2 3 4 package name . p a n i t z . u t i l ; p u b l i c c l a s s LiLi implements I t e r a b l e { p r i v a t e f i n a l A hd ; p r i v a t e f i n a l LiLi t l ; 5 6 7 8 9 p u b l i c L i L i (A hd , LiLi t l ) { t h i s . hd = hd ; this . tl = tl ; } 10 11 12 13 14 public LiLi () { t h i s . hd = n u l l ; this . tl = null ; } 15 43 Kapitel 2 Hierarchische Strukturen p u b l i c b o o l e a n isEmpty ( ) { r e t u r n t l==n u l l && hd==n u l l ; } 16 17 18 19 p u b l i c A getHead ( ) { r e t u r n hd ; } p u b l i c LiLi g e t T a i l ( ) { return t l ; } 20 21 22 23 24 25 Listing 2.1: LiLi.java Ein Iterator für Listen Für die so definierten Listen können wir jetzt sofort das gelernte aus dem letzten Kapitel anwenden, indem wir einen Iterator für Listen schreiben. Listen sind natürlich die Paradeanwendung für iterierbare Objekte. p u b l i c j a v a . u t i l . I t e r a t o r i t e r a t o r ( ) { r e t u r n new I t ( t h i s ) ; } 26 27 28 29 p r i v a t e c l a s s I t implements j a v a . u t i l . I t e r a t o r { LiLi t h e L i s t ; I t ( LiLi l i ) { t h e L i s t = l i ; } p u b l i c b o o l e a n hasNext ( ) { r e t u r n ! t h e L i s t . isEmpty ( ) ; } p u b l i c A next ( ) { A r e s u l t = t h e L i s t . getHead ( ) ; theList = theList . getTail () ; return r e s u l t ; } } 30 31 32 33 34 35 36 37 38 39 40 41 Listing 2.2: LiLi.java 2.1.3 Mathematische Definition Betrachten wir jetzt wieder die Listen von der mathematischen Seite. Die obige Javaklasse definiert implizit eine induktive Struktur, indem gesagt wird, dass man eine leere Liste konstruieren kann und aus einer Liste und einem weiteren Element eine neue Liste konstruieren kann. Etwas formaler und nicht programmiersprachlich ließen sich Listen wie folgt definieren: Definition 2.1.1 Sei eine Menge E der Elemente gegeben. Die Menge der Listen über E im Zeichen ListE sei dann die kleinste Menge, für die gilt: 44 2.1 Einfach verkettete Listen • Die leere Liste ist eine Liste: Nil() ∈ ListE . • Sei e ∈ E und sei es ∈ ListE . Dann ist auch Cons(e, es) ∈ ListE . Induktive Strukturen Daten sollen nach Möglichkeit dynamisch wachsen können, d.h. potentiell beliebig groß werden können. Um einen Datentyp zu definieren, dessen Elemente potentiell beliebig groß werden können, bedient man sich einer strukturell induktiven Definition. Mit den einfach verketteten Listen haben wir eine induktive Struktur definiert. Dieses Verfahren, Mengen mit zu definieren, ist aus der Mathematik bekannt. Dort ist die Menge der natürlichen Zahlen ein prominentes Beispiel einer induktiv definierten Menge. Die Zahl 0 ist Element der Menge der natürlichen Zahlen. Bei unseren Listen entspricht dieses der leeren Liste. Zusätzlich gilt, wenn eine Zahl n in der Menge der natürlichen Zahlen ist, dass ist auch eine Zahl n + 1 in der Menge der natürlichen Zahlen enthalten. Entsprechend können wir für jede Liste xs eine Liste, die ein Element mehr enthält, erzeugen. Um in der Mathematik eine Eigenschaft für alle Elemente der Menge der natürlichen Zahlen zu beweisen, gibt es ein spezielles Beweisverfahren, dass sich an der strukturellen Definition orientiert: die vollständige Induktion. Diese besteht aus drei Schritte: • Induktions-Anfang: zeige, dass die Eigenschaft für die Zahl 0 gilt. • Induktions-Vorraussetzung: nimm an, dass die Eigenschaft bereits für alle Zahlen kleiner gleich einer bestimmten Zahl n korrekt bewiesen ist. • Induktions-Schluss: zeige, dass die Annahme dann auch für die Zahl n + 1 gilt. Als Beispiel können wir die Gaußsche Summenformel beweisen, die behauptet: n ∑ i= i=0 n ∗ (n + 1) 2 • Induktions-Anfang: 0 = (0 ∗ 1)/2 ist korrekt. • Induktions-Vorraussetzung: n ∑ i=0 i= n ∗ (n + 1) 2 ist beweisen für alle Zahlen kleiner oder gleich eines bestimmten n . 45 Kapitel 2 Hierarchische Strukturen • Induktions-Schluss: n+1 ∑ i= i=0 (n + 1) + n ∑ i i=0 = = = = = n ∗ (n + 1) (n + 1) + 2 2 ∗ (n + 1) n ∗ (n + 1) + 2 2 2 ∗ (n + 1) + n ∗ (n + 1) 2 (n + 2) ∗ (n + 1) 2 (n + 1) ∗ (n + 2) 2 Rekursive Algorithmen Ebenso wie der Mathematiker bei einem Beweis per vollständiger Induktion vorgeht, können wir Algorithmen für die induktiv definierte Struktur unserer Listen definieren. Auch hier gibt es die drei Schritte: • Induktionsanfang: das Ergebnis der zu entwickelnden Funktion wird für die leere Liste definiert. • Induktionsvorraussetzung. wir nehmen an, dass die Funktion bereits für kürzere Listen funktioniert. Insbesondere für die um ein Element kürzere Liste, nämlich für die Liste, die wir mit getTail() erhalten. • Induktionsschritt: aus dem Ergebnis für die Induktionsvorraussetzung wird das Ergebis für den Gesamtliste definiert. Für viele einfache Algorithmen ist dieser Weg recht einfach. Längenberechnung für Listen Ein einfacher Algorithmus für unsere induktive Listendefinition stellt die Berechnung der Länge der Liste dar, mit Hilfe der wir die einzelnen Elemente zählen. public int length () { 42 Listing 2.3: LiLi.java Zunächst als der Induktionsanfang. Das Ergebnis für die leere List. Dieses ist einfach. Eine leere Liste hat die Länge 0. 46 2.1 Einfach verkettete Listen i f ( isEmpty ( ) ) r e t u r n 0 ; 43 Listing 2.4: LiLi.java Anschließend können wir über die Induktionsvoraussetzung annehmen, dass die Funktion für die um ein Element kleinere Liste bereits definiert ist und das korrekte Ergebnis berechnet: f i n a l int tailResult = getTail () . length () ; 44 Listing 2.5: LiLi.java Schließlich ist zu überlegen, wie von dem Ergebnis der Voraussetzung das Gesamtergebnis zu definieren ist. Im Falle der Länge ist dieses besonders einfach, es muss 1 hinzugezählt werden: final int result = 1 + tailResult ; 45 Listing 2.6: LiLi.java Damit lässt sich das Ergebnis zurück geben: return r e s u l t ; 46 47 } Listing 2.7: LiLi.java Test auf ein Element Nach dem gleichen Schema lässt sich auch die Funktion schreiben, die testet, ob in der Liste ein bestimmtes Element enthalten ist: 48 p u b l i c b o o l e a n c o n t a i n s (A a ) { Listing 2.8: LiLi.java Zunächst als der Induktionsanfang. Das Ergebnis für die leere List. 49 i f ( isEmpty ( ) ) r e t u r n f a l s e ; Listing 2.9: LiLi.java Anschließend können wir über die wieder Induktionsvoraussetzung annehmen, dass die Funktion für die um ein Element kleinere Liste bereits definiert ist und das korrekte Ergebnis berechnet: 47 Kapitel 2 Hierarchische Strukturen f i n a l boolean t a i l R e s u l t = getTail ( ) . contains ( a ) ; 50 Listing 2.10: LiLi.java Schließlich ist zu überlegen, wie von dem Ergebnis der Voraussetzung das Gesamtergebnis zu definieren ist. In diesen Falle betrachten wir erst das erste Element und benutzen dann das Ergebnis der Induktionsvoraussetzung. f i n a l boolean r e s u l t = getHead ( ) . e q u a l s ( a ) | | t a i l R e s u l t ; 51 52 Listing 2.11: LiLi.java Damit haben wir das Ergebnis: return r e s u l t ; 53 } 54 Listing 2.12: LiLi.java Inhaltlich liegt eine komplett andere Aufgabenstellung als bei der Längenberechnung vor. Strukturell benutzen wir exakt dasselbe Vorgehen, das der vollständigen Induktion der Mathematik entspricht. Aneinanderhängen von Listen Nach dem gleichen Schema lässt sich auch die Funktion schreiben, die eine neue Liste erzeugt durch das Anhängen einer zweiten Liste.: p u b l i c LiLi append ( LiLi t h a t ) { 55 Listing 2.13: LiLi.java Zunächst als der Induktionsanfang. Das Ergebnis für die leere List. i f ( isEmpty ( ) ) r e t u r n t h a t ; 56 Listing 2.14: LiLi.java Anschließend können wir über die wieder Induktionsvoraussetzung annehmen, dass die Funktion für die um ein Element kleinere Liste bereits definiert ist und das korrekte Ergebnis berechnet: f i n a l LiLi t a i l R e s u l t = g e t T a i l ( ) . append ( t h a t ) ; 57 Listing 2.15: LiLi.java 48 2.1 Einfach verkettete Listen Schließlich ist zu überlegen, wie von dem Ergebnis der Voraussetzung das Gesamtergebnis zu definieren ist. In diesem Fall ist noch das erste Element an die Ergebnisliste vorne anzuhängen.: f i n a l LiLi r e s u l t 58 = new LiLi (getHead ( ) , t a i l R e s u l t ) ; Listing 2.16: LiLi.java Damit haben wir das Ergebnis: return r e s u l t ; 59 } 60 Listing 2.17: LiLi.java Inhaltlich liegt wieder eine komplett andere Aufgabenstellung als bei der Längenberechnung oder dem Test auf ein Element vor. Strukturell benutzen wir aber wieder exakt dasselbe Vorgehen, das der vollständigen Induktion der Mathematik entspricht. 61 } Listing 2.18: LiLi.java Aufgabe 1 Gegeben sei folgende Schnittstelle: 1 2 3 4 5 6 package name . p a n i t z . u t i l ; import j a v a . u t i l . f u n c t i o n . Consumer ; p u b l i c i n t e r f a c e OurList e x t e n d s I t e r a b l e { b o o l e a n isEmpty ( ) ; A head ( ) ; OurList t a i l ( ) ; 7 @Override i n t l e n g t h ( ) ; b o o l e a n c o n t a i n s (A e l ) ; v o i d machtAlle ( Consumer c ) ; OurList add (A e l ) ; 8 9 10 11 12 OurList drop ( i n t i ) ; OurList t a k e ( i n t i ) ; OurList s u b l i s t ( i n t s t a r t , i n t l e n g t h ) ; i n t indexOf (A e l ) ; A get ( i n t index ) ; 13 14 15 16 17 18 19 } Listing 2.19: OurList.java 49 Kapitel 2 Hierarchische Strukturen Sie sollen in dieser Aufgabe folgende noch nicht vollständige Klasse vervollständigen: 1 2 3 package name . p a n i t z . u t i l ; import j a v a . u t i l . f u n c t i o n . Consumer ; import j a v a . u t i l . I t e r a t o r ; 4 5 6 7 c l a s s L i s t e implements OurList{ p r i v a t e A head ; p r i v a t e OurList t a i l ; 8 p u b l i c L i s t e (A head , OurList t a i l ) { t h i s . head = head ; this . tail = tail ; } 9 10 11 12 13 public Liste () { this ( null , null ) ;} 14 15 p u b l i c L i s t e (A . . . xs ) { f o r (A x : xs ) { add ( x ) ; } } 16 17 18 19 20 21 @Override p u b l i c b o o l e a n isEmpty ( ) { r e t u r n head == n u l l && t a i l == n u l l ; } 22 23 24 25 @Override p u b l i c A head ( ) { r e t u r n head ; } @Override p u b l i c OurList t a i l ( ) { r e t u r n t a i l ; } 26 27 28 } Dabei sind die einzelnen zu implementierenden Methoden wie folgt spezifiziert. Schreiben Sie auch mehrere Testaufrufe. a) @Override int length(); Berechnet die Anzahl der Elemente in der Liste. b) boolean contains(A el); Wird wahr, wenn ein Element der Liste gleich dem übergebenen Argument ist. c) void machtAlle(Consumer c); Wendet die Methode des Consumer-Objekts auf alle Elemente an. 50 2.1 Einfach verkettete Listen d) OurList add(A el); Modifiziert die Liste, indem am Ende das neue Element hinzugefügt wird. e) OurList drop(int i); Gibt die Teilliste zurück, die entsteht, wenn die ersten i Elemente von der Liste genommen werden. Ist i zu groß, so wird eine leere Liste zurück gegeben. f) OurList take(int i); Gibt die Teilliste bestehend aus den ertsen i Elementen zurück. g) OurList sublist(int start, int length); Gibt eine Teilliste zurück, die von dem Index start beginnt und die spezifizierte Länge hat. Ist die Liste zu kurz, wird eine entsprechend kürzere bis hin zur leeren Liste zurück gegeben. h) int indexOf(A el); Gibt an, an welchem Index ein bestimmtes Element liegt. Ist das Element nicht enthalten, so wird -1 zurück gegeben. i) A get(int index); Gibt das Element an einem bestimmten Index zurück. Ist der Index zu groß, so wird null zurück gegeben. Aufgabe 2 (Nur für das Modul im Studiengang »Angewandte Informatik«) Gegeben sei folgende C-Header Datei: 1 #i n c l u d e 2 3 4 5 6 s t r u c t Li { v o i d * head ; s t r u c t Li * t a i l ; }; 7 8 t y p e d e f s t r u c t Li L i s t ; 9 10 11 12 b o o l isEmpty ( L i s t * t h i s ) ; L i s t * newEmptyList ( ) ; L i s t * newConsList ( v o i d * hd , L i s t * t l ) ; 13 14 void d e l e t e L i s t ( L i s t * t h i s ) ; 15 51 Kapitel 2 Hierarchische Strukturen 16 17 unsigned i n t length ( L i s t * t h i s ) ; L i s t * add ( L i s t * t h i s , v o i d * e l ) ; 18 19 20 21 22 23 24 List * List * List * List * List * void * copyList ( List * thi s ) ; append ( L i s t * t h i s , L i s t * t h a t ) ; drop ( L i s t * t h i s , i n t i ) ; take ( L i s t * this , i n t i ) ; s u b l i s t ( List * this , int start , int length ) ; get ( L i s t * this , i n t index ) ; 25 26 v o i d macheFuerAlle ( L i s t * t h i s , v o i d consumer ( v o i d * ) ) ; Listing 2.20: List.h Folgende Datei enthält eine rudimentäre Implementierung: 1 2 #i n c l u d e ” L i s t . h” #i n c l u d e < s t d l i b . h> 3 4 5 6 b o o l isEmpty ( L i s t * t h i s ) { r e t u r n t h i s −>head==NULL && t h i s −> t a i l==NULL; } 7 8 9 10 11 12 13 L i s t * newEmptyList ( ) { L i s t * t h i s = malloc ( s i z e o f ( L i s t ) ) ; t h i s −>head = NULL; t h i s −> t a i l = NULL; return this ; } 14 15 16 17 18 19 20 L i s t * newConsList ( v o i d * head , L i s t * t a i l ) { L i s t * t h i s = malloc ( s i z e o f ( L i s t ) ) ; t h i s −>head = head ; t h i s −> t a i l = t a i l ; return this ; } 21 22 23 24 25 void d e l e t e L i s t ( L i s t * t h i s ) { i f ( ! isEmpty ( t h i s ) ) d e l e t e L i s t ( t h i s −> t a i l ) ; free ( this ) ; } Listing 2.21: List.c Implementieren Sie die fehlenden Funktionen entsprechend der Spezifikation aus Aufgabe 1. 52 2.2 Bäume als verallgemeinerte Listen 2.2 Bäume als verallgemeinerte Listen In diesem Abschnitt soll jetzt das Prinzip der Listen verallgemeinert werden zu Bäumen, Listen sind nämlich nur ein Speziellfall einer Baumstruktur. Bäume sind ein gängiges Konzept um hierarchische Strukturen zu modellieren. Sie sind bekannt aus jeder Art von Baumdiagramme, wie Stammbäumen oder Firmenhierarchien. In der Informatik sind Bäume allgegenwärtig. Fast alle komplexen Daten stellen auf die eine oder andere Art einen Baum dar. Beispiele für Bäume sind mannigfach: • Dateisystem: Ein gängiges Dateisystem, wie es aus Unix, MacOS und Windows bekannt ist, stellt eine Baumstruktur dar. Es gibt einen ausgezeichneten Wurzelordner, von dem aus zu jeder Datei einen Pfad existiert. • Klassenhierarchie: Die Klassen in Java stellen mit ihrer Ableitungsrelation eine Baumstruktur dar. Die Klasse Object ist die Wurzel dieses Baumes, von der aus alle anderen Klassen über einen Pfad entlang der Ableitungsrelation erreicht werden können. • XML: Die logische Struktur eines XML-Dokuments ist ein Baum. Die Kinder eines Elements sind jeweils die Elemente, die durch das Element eigeschlossen sind. • Parserergebnisse: Ein Parser, der gemäß einer Grammatik prüft, ob ein bestimmter Satz zu einer Sprache gehört, erzeugt im Erfolgsfall eine Baumstruktur. Im nächsten Kapitel werden wir dieses im Detail kennenlernen. • Listen: Auch Listen sind Bäume, allerdings eine besondere Art, in denen jeder Knoten nur maximal ein Kind hat. • Berechnungsbäume: Zur statischen Analyse von Programmen, stellt man Bäume auf, in denen die Alternativen eines bedingten Ausdrucks Verzweigungen im Baum darstellen. • Tableaukalkül: Der Tableaukalkül ist ein Verfahren zum Beweis logischer Formeln. Die dabei verwendeten Tableaux sind Bäume. • Spielbäume: Alle möglichen Spielverläufe eines Spiels können als Baum dargestellt werden. Die Kanten entsprechen dabei einem Spielzug. • Prozesse: Auch die Prozesse eines Betriebssystems stellen eine Baumstruktur dar. Die Kinder eines Prozesses sind genau die Prozesse, die von ihm gestartet wurden. Wie man sieht, lohnt es sich, sich intensiv mit Bäumen vertraut zu machen, und man kann davon ausgehen, was immer in der Zukunft neues in der Informatik entwickelt werden wird, Bäume werden darin in irgendeiner Weise eine Rolle spielen. Ein Baum besteht aus einer Menge von Knoten die durch gerichtete Kanten verbunden sind. Die Kanten sind eine Relation auf den Knoten des Baumes. Die Kanten 53 Kapitel 2 Hierarchische Strukturen verbinden jeweils einen Elternknoten mit einem Kinderknoten. Ein Baum hat einen eindeutigen Wurzelknoten. Dieses ist der einzige Knoten, der keinen Elternknoten hat, d.h. es gibt keine Kante, die zu diesen Knoten führt. Knoten, die keinen Kinderknoten haben, d.h. von denen keine Kante ausgeht, heißen Blätter. Die Kinder eines Knotens sind geordnet, d.h. sie stehen in einer definierten Reihenfolge. Eine Folge von Kanten, in der der Endknoten einer Vorgängerkante der Ausgangsknoten der nächsten Kanten ist, heißt Pfad. In einem Baum darf es keine Zyklus geben, das heißt, es darf keinen Pfad geben, auf dem ein Knoten zweimal liegt. Knoten können in Bäumen markiert sein, z.B. einen Namen haben. Mitunter können auch Kanten eine Markierung tragen. Bäume, in denen Jeder Knoten maximal zwei Kinderknoten hat, nennt man Binärbäume. Bäume, in denen jeder Knoten maximal einen Kinderknoten hat, heißen Listen. 2.2.1 Formale Definition Auch Bäume werden wir induktiv definieren: Definition 2.2.1 Sei eine Menge E der Elemente gegeben. Die Menge der Bäume über E im Zeichen T reeE sei dann die kleinste Menge, für die gilt: • Der leere Baum ist ein Baum: Empty ∈ TreeE . • Sei e ∈ E und seien t1 , . . . , tn ∈ TreeE . Dann ist auch Branch(e, t1 , . . . , tn ) ∈ TreeE . Der einzige Unterschied zu unserer formalem Definition der Listen ist, dass im zweiten Punkt ein Baum aus n bereits existierenden Bäumen und einen neuem Element gebaut werden und nicht wie bei Listen aus einer existierenden Liste und einem Element. Wenn in der Definition der Bäume das n immer nur 1 ist, dann ist die Definition identisch mit der Definition von Listen. 2.2.2 Implementierung einer Baumklasse Die Definition eines Baumes war sehr ähnlich der Definition der Listen. Entsprechend ist auch die Implementierung sehr ähnlich zu unserer Listenimplementierung. Wir schreiben eine Klasse, die generisch über die Elemente, die an den Baumknoten stehen, ist: 54 2.2 Bäume als verallgemeinerte Listen 1 2 3 4 package name . p a n i t z . u t i l ; import j a v a . u t i l . L i s t ; import j a v a . u t i l . A r r a y L i s t ; import j a v a . u t i l . I t e r a t o r ; 5 6 7 p u b l i c c l a s s Tree implements I t e r a b l e { Listing 2.22: Tree.java Ebenso wie bei Listen, benötigen wir ein Feld, für das an dem Baumknoten stehende Element. Dieses wurde bei Listen meist als head bezeichnet. 8 p u b l i c E element = n u l l ; Listing 2.23: Tree.java Eine Listenzelle hatte einen Verweis auf die Restliste. Bei Bäumen gibt es nicht nur einen Unterbaum, sondern mehrere Unterbäume, die wiederum in einer Liste gespeichert werden. Hierzu nutzen wir die Standardliste. Also anstatt eines Feldes LiLi tail wie bei Listen, benötigen wir für Bäume ein Feld, das eine Liste von Teilbäumen enthält. 9 p u b l i c L i s t > c h i l d N o d e s = new A r r a y L i s t <>() ; Listing 2.24: Tree.java In einem boolschen Flag sei vermerkt, ob es sich um einen leeren Baum, der noch gar keinen Knoten enthält handelt oder nicht. 10 p u b l i c b o o l e a n isEmptyTree ; Listing 2.25: Tree.java Wir verketten unsere Bäume auch rückwärts, von den Kindern zu ihren Elternknoten. 11 p u b l i c Tree p a r e n t = n u l l ; Listing 2.26: Tree.java Laut Spezifikation gibt es zwei Konstruktoren. Den ersten zum Erzeugen eines leeren Baumes: 12 13 14 p u b l i c Tree ( ) { isEmptyTree = t r u e ; } Listing 2.27: Tree.java 55 Kapitel 2 Hierarchische Strukturen Der zweite erzeugt eine neue Baumwurzel mit einer bestimmten Markierung. p u b l i c Tree (E e , Tree . . . t s ) { element = e ; isEmptyTree = f a l s e ; f o r ( Tree t : t s ) { i f ( ! t . isEmptyTree ) { c h i l d N o d e s . add ( t ) ; t . parent = t h i s ; } } } 15 16 17 18 19 20 21 22 23 24 Listing 2.28: Tree.java Hier wird das Konstrukt einer variablen Parameteranzahl verwendet. Die drei Punkte an dem letzten Parameter zeigen an, dass hier 0 bis n Parameter eines Typs erwartet werden. Intern wird für diese Parameter ein Array erzeugt, über den wir in diesem Fall mit einer for-each Schleife iterieren. Für weitere kleine Tests seien ein paar Beispielbäume bereit gestellt. static static static static static static static static static static static static 25 26 27 28 29 30 31 32 33 34 35 36 Tree Tree Tree Tree Tree Tree Tree Tree Tree Tree Tree Tree a1 a2 a3 b1 a4 a5 b2 a6 a7 a8 b3 c1 = = = = = = = = = = = = new new new new new new new new new new new new Tree <>(” a1 ” ) ; Tree <>(” a2 ” ) ; Tree <>(” a3 ” ) ; Tree <>(” b1 ” , a1 , Tree <>(” a4 ” ) ; Tree <>(” a5 ” ) ; Tree <>(” b2 ” , a4 , Tree <>(” a6 ” ) ; Tree <>(” a7 ” ) ; Tree <>(” a8 ” ) ; Tree <>(” b3 ” , a6 , Tree <>(” c1 ” , b1 , a2 , a3 ) ; a5 ) ; a7 , a8 ) ; b2 , b3 ) ; Listing 2.29: Tree.java Als ein weniger abstraktes Beispiel seien die Nachfahren des englische Königs George VI als ein Stammbaum angegeben: s t a t i c Tree wind sor = new Tree<> ( ” George ” , new Tree<> ( ” Elizabeth ” , new Tree<> ( ” Charles ” , new Tree <>(” William ” , new Tree <>(” George ” ) ) , new Tree <>(” Henry ” ) 37 38 39 40 41 42 43 44 45 56 2.2 Bäume als verallgemeinerte Listen 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 ) , new Tree<> ( ”Andrew” , new Tree <>(” B e a t r i c e ” ) , new Tree <>(” Eugenie ” ) ) , new Tree<> ( ”Edward” , new Tree <>(” L o u i s e ” ) , new Tree <>(” James ” ) ) , new Tree<> ( ”Anne” , new Tree <>(” P e t e r ” ) , new Tree <>(” Zara ” ) ) ) , new Tree<> ( ” Magaret ” , new Tree<> ( ” David ” , new Tree <>(” C a r l e s ” ) , new Tree <>(” M a r a g r i t a ” ) ) 70 , new Tree <>(” Sarah ” ) ) 71 72 73 ); Listing 2.30: Tree.java Stringdarstellung Eine der ersten Methoden, die üblicher Weise für Klassen geschrieben wird, ist die Darstellung des Objektes als ein Text in Form eines Stringobjektes. Hierzu wird gängiger Weise die Methode toString aus der Klasse Objekt überschrieben. Für die Baumklassen wäre folgende Umsetzung denkbar, die wir allerdings auf Deutsch als alsString bezeichnet haben. 74 75 76 77 78 79 80 81 public String alsString () { i f ( isEmptyTree ) r e t u r n ”Empty ( ) ” ; S t r i n g r e s u l t = ” Branch ( ”+e l e m e n t+” ) [ ” ; f o r ( Tree c h i l d : c h i l d N o d e s ) { r e s u l t = r e s u l t+c h i l d . a l s S t r i n g ( ) ; } r e t u r n r e s u l t+” ] ” ; } Listing 2.31: Tree.java 57 Kapitel 2 Hierarchische Strukturen Diese Umsetzung ist rekursiv, indem die Methode für jeden Kindknoten rekursiv aufgerufen wird. Die Teilergebnisse für die Kindbäume werden dabei über die Stringkonkatenation mit dem eingebauten Operator + aneinander gehängt. Dieses ist nicht ganz unproblematisch. Stringobjekte sind in Java unveränderbar (unmutable). Ein einmal erzeugtes Stringobjekt wird nie verändert. Der plusOperator erzeugt aus zwei Stringobjekten ein neues Stringobjekt. Dieses geschieht dadurch, dass ein neues Objekt erzeugt wird und alle Zeichen der beiden Ausgangsobjekte in dieses neue Objekt kopiert werden. Wenn für die Berechnung eines Stringergebnisses viele Teilsstring mit dem plus-Operator aneinander gehängt werden, dann werden sehr viele Objekte erzeugt und insbesondere sehr viele Zeichen immer wieder im Speicher von einem Speicherbereich auf einen anderen kopiert.. Dieses werden wir im zweiten Teil der Vorlesung noch direkter sehen, wenn in der Programmiersprache C, die Operationen des plus-Operators explizit selbst programmiert werden müssen. Es empfiehlt sich also, bei der Konstruktion großer Texte, nicht gleich alle Teilstrings mit dem plus-Operator aneinander zu hängen und so permament Teilstrings zu kopieren. Strings puffern mit StringBuffer Das Java Standard-API stellt eine Klasse zur Verfügung, die es ermöglicht eine Folge von Strings zu sammeln, die dann im Endeffekt zu einem großen String konkateniert werden: die Klasse StringBuffer. Diese hat intern eine Liste der einzelnen aneinander zu hängenden Strings. Erst wenn alle Strings eingesammelt wurden, dann werden alle Strings zu einem großen String zusammen kopiert. Somit werden die Zeichen der einzelnen Strings nicht mehrfach im Speicher kopiert und das Anlegen temporärer Stringobjekte vermieden. Die Methode toString() kann mit Hilfe der Klasse StringBuffer effizienter umgesetzt werden. Es wird ein StringBuffer-Objekt angelegt. Mit der Methode append werden die einzelnen Strings dann diesem Objekt angefügt. Ein terminaler Aufruf der Methode toString auf dem StringBuffer-Objekt führt dann dazu, dass der Ergebnisstring erzeugt wird: Zunächst nehmen wir aber den einfachen Fall des leeren Baumes aus: @Override p u b l i c S t r i n g t o S t r i n g ( ) { i f ( isEmptyTree ) r e t u r n ”Empty ( ) ” ; 82 83 Listing 2.32: Tree.java Andernfalls wird ein StringBuffer-Objekt mit dem Anfang des Ergebnisstrings erzeugt: S t r i n g B u f f e r r e s u l t = new S t r i n g B u f f e r ( ” Branch ( ” ) ; 84 Listing 2.33: Tree.java 58 2.2 Bäume als verallgemeinerte Listen Diesem wird zunächst das Element in Stringdarstellung zugefügt: r e s u l t . append ( e l e m e n t . t o S t r i n g ( ) ) ; r e s u l t . append ( ” ) [ ” ) ; 85 86 Listing 2.34: Tree.java Schließlich werden noch die Kinder durchiteriert, um deren String-Darstellung dem StringBuffer-Objekt zuzufügen: f o r ( Tree c h i l d : c h i l d N o d e s ) { r e s u l t . append ( c h i l d . t o S t r i n g ( ) ) ; } r e s u l t . append ( ” ] ” ) ; 87 88 89 90 Listing 2.35: Tree.java Nun sind alle Teilstrings aufgesammelt und das Ergebnisobjekt kann erzeugt werden: return r e s u l t . toString () ; 91 92 } Listing 2.36: Tree.java String schreiben mit einem Writer Wer sich die letzte Lösung der Methode toString() etwas genauer angeschaut hat, der wird bemerkt haben, dass trotzdem viele temporäre Teilstrings erzeugt werden. Bei jedem rekursiven Aufruf, wird wieder ein neues StringBuffer-Objekt erzeugt, welches bei der Rückgabe einen neuen String erzeugt. Es werden also auch in dieser Umsetzung immer wieder dieselben Teilstrings im Speicher kopiert. Dieses Problem lässt sich nur umgehen, wenn man das StringBuffer-Objekt als Parameter an die Methode übergibt. Eine andere Möglichkeit, die noch flexibler ist, ermöglicht es Strings nicht explizit zu erzeugen, sondern in eine Datensenke zu schreiben. Hierzu dient die aus dem letzten Semester bekannte Klasse java.io.Writer. Von dieser gibt es unterschiedliche Implementierungen, die jeweils die Zeichen in unterschiedliche Datensenken schreiben. Häufig wird diese natürlich eine Datei sein, es kann aber auch über ein Netzwerk an einen Server geschrieben werden, oder aber auch wieder nur einfach in einen String. Um in ein Writer-Objekt zu schreiben, muss dieses wie am Ende des letzten Abschnitts erörtert, als Parameter übergeben werde. Zusätzlich ist zu beachten, dass die IO-Operationen zu Ausnahmen führen können: 93 p u b l i c v o i d w r i t e A s S t r i n g ( j a v a . i o . Writer out ) throws j a v a . i o . IOException { Listing 2.37: Tree.java 59 Kapitel 2 Hierarchische Strukturen Im Falle des leeren Baumes, wird dessen Darstellung geschrieben und die Methode verlassen: i f ( isEmptyTree ) { out . w r i t e ( ”Empty ( ) ” ) ; return ; } 94 95 96 97 Listing 2.38: Tree.java Wenn es sich um einen nichtleeren Baum handelt, können jetzt die einzelnen Teile nacheinander in den Writer geschrieben werden. Ähnlich wie in der vorherigen Lösung die einzelnen Teile dem StringBuffer angehängt wurden. out . w r i t e ( ” Branch ( ” ) ; out . w r i t e ( e l e m e n t . t o S t r i n g ( ) ) ; out . w r i t e ( ” ) [ ” ) ; 98 99 100 Listing 2.39: Tree.java Der Unterschied zu der vorherigen Lösung ist, dass jetzt die rekursiven Aufrufe den Writer als Parameter übergeben. f o r ( Tree c h i l d : c h i l d N o d e s ) { c h i l d . w r i t e A s S t r i n g ( out ) ; } out . w r i t e ( ” ] ” ) ; 101 102 103 104 } 105 Listing 2.40: Tree.java Um diese Implementierung jetzt auf gleiche Weise nutzen zu können wie die Standardmethode toString, kann ein StringWriter-Objekt erzeugt werden, in den der String geschrieben wird. public String asString () { try { j a v a . i o . S t r i n g W r i t e r out = new j a v a . i o . S t r i n g W r i t e r ( ) ; w r i t e A s S t r i n g ( out ) ; r e t u r n out . t o S t r i n g ( ) ; } c a t c h ( j a v a . i o . IOException e ) { return ”” ; } } 106 107 108 109 110 111 112 113 114 Listing 2.41: Tree.java Mit dieser Implementierung ist unnötiges Kopieren von Teilstrings komplett vermieden worden. zusätzlich ist sie flexibler, weil die Methode writeAsString nicht nur zum Erzeugen eines Strings genutzt werden kann, sondern auch dazu, die Stringdarstellung in unterschiedliche Datensenken zu schreiben. 60 2.2 Bäume als verallgemeinerte Listen Elemente in einer Liste gesammelt Ist man nicht mehr an der Baumstruktur interessiert, so kann man sich die Elemente eines Baums in einer Liste speichern. 115 116 117 118 119 p u b l i c j a v a . u t i l . L i s t a s L i s t ( ) { r e t u r n a s L i s t ( new j a v a . u t i l . L i n k e d L i s t <>() ) ; } p u b l i c L i s t a s L i s t ( L i s t r e s u l t ) { i f ( ! isEmptyTree ) r e s u l t . add ( e l e m e n t ) ; 120 f o r ( Tree c h i l d : c h i l d N o d e s ) c h i l d . a s L i s t ( r e s u l t ) ; 121 122 return r e s u l t ; 123 124 } Listing 2.42: Tree.java Ein einfacher Iterator über die Listendarstellung Mit der Listensammlung aller Elemente eines Baumes lässt sich schließlich leicht ein Baum über alle seine Elemente iterierbar machen. Es muss nur die Liste erzeugt werden und über diese iteriert werden. 125 126 127 128 @Override p u b l i c j a v a . u t i l . I t e r a t o r i t e r a t o r ( ) { return asList () . i t e r a t o r () ; } Listing 2.43: Tree.java Rekursive Methoden mit reduce auf Kindknoten Mit den Möglichkeiten von Java 8 lassen sich fast alle Algorithmen, die in den Baum absteigen, um dort Informationen zu sammeln, auch ohne explizite Schleifen sondern durch Methode höherer Ordnung auf die Kinderliste ausdrücken. Ob das immer besser ist, sei allerdings dahingestellt. Betrachten wir zunächst die Größe eines Baumes. Diese lässt sich als ein einziger Ausdruck formulieren. Zunächst wird durch den Bedingungsoperator der Spezialfall eines leeren Baumes behandelt. Ansonsten ist es 1 zur Summe der Größen aller Kinderbäume: 129 130 131 public int size () { r e t u r n isEmptyTree ? 0 : 1+c h i l d N o d e s 61 Kapitel 2 Hierarchische Strukturen . parallelStream () . r e d u c e ( 0 , ( r e s u l t , c h i l d ) −> r e s u l t+c h i l d . s i z e ( ) , Math : : addExact ) 132 133 ; } 134 Listing 2.44: Tree.java Die Summe der Kinderbäume ist mit der Methode reduce auf Stream gelöst. Diese entspricht der Methode reduce, wie wir sie selbst in dem eigenen Interface Iterable umgesetzt haben. Sie bekommt allerdings zwei Funktionsobjekte. Die erste Funktion beschreibt, wie ein einzelnen Element sein Ergebnis zum Gesamtergebnis hinzuzählt. In unserem Fall, wird von jedem Kind die Größe zum Gesamtergebnis addiert. Die zweite Funktion beschreibt, wie Teilergebnisse zu verknüpfen sind. In unserem Fall durch die Addition. Diese zwei Funktionen werden gebraucht, wenn der Stream, auf dem gearbeitet wird, parallelisiert wird. Dann wird z.B. vielleicht parallel das Teilergebnis der ersten Hälfte der Kinder und der zweiten Hälfte der Kinder berechnet. Diese Teilergebnisse sind zu addieren. Da wir unsere Bäume unser Interface Iterable haben implementieren lassen, können wir aber sehr einfach die dort als default definierte Methode reduce benutzen. Hier erhalten wir allerdings keine Parallelisierung und erzeugen zusätzlich über die Methode iterator() der Klasse Tree erst eine Liste aller Elemente. public int size2 () { r e t u r n r e d u c e ( 0 , ( r e s u l t , elem ) −> r e s u l t + 1 ) ; } 135 136 137 Listing 2.45: Tree.java Sehr sehr ähnlich sieht nun die Lösung für eine gänzlich andere Fragestellung aus. Was ist die maximale Tiefe des Baumes, also wie viele Generationen hat der Baum. Statt die Teilergebnisse aufzuaddieren, nehmen wir jetzt immer das Maximum der Teilergebnisse. Auch diese Aufgabe ist wunderbar parallelisierbar: public int generations () { r e t u r n isEmptyTree ? 0 : 1 + childNodes . parallelStream () . r e d u c e ( 0 , ( r e s u l t , c h i l d )−>Math . max( r e s u l t , c h i l d . g e n e r a t i o n s ( ) ) , Math : : max) ; } 138 139 140 141 142 143 144 145 } Listing 2.46: Tree.java Aufgabe 1 Schreiben Sie für die Klasse Tree eine Methode 62 2.2 Bäume als verallgemeinerte Listen List fringe(), die die Liste der Blätter des Baumes zurück gibt. Ein Blatt ist dabei ein Baumknoten, der keine Kinder mehr hat. Lösung Listing 2.47: Tree.java Aufgabe 1 Lösung in der Woche vom 19.5. in der Praktikumsstunde. Ergänzen Sie Ihre Klasse Tree aus dem letzten Übungsblatt um die folgende Methode: public void writeAsXML(java.io.Writer out) throws IOException; Es soll der Baum serialisiert als ein XML-Dokument in das Writer-Objekt geschrieben werden. Aufgabe 2 Schreiben Sie für die Klasse Tree eine Methode List pathTo(E elem), die die Elemente auf dem Pfad von der Wurzel zu dem Knoten mit der Element-Markierung elem zurück gibt. Sollte kein Knoten mit dem Element elem markiert sein, so ist die leer Liste das Ergebnis. Aufgabe 2 Lösung in der Woche vom 19.5. in der Praktikumsstunde. Schreiben Sie für die Klasse Tree eine Methode: public static Tree readFromXML(java.io.File xmlFile) throws Exception; Es soll ein neuen Baum erzeugt werden, der aus einer XML-Datei gelesen wird. Hierbei wird davon ausgegangen, dass die XML-Datei mit der Methode aus Aufgabe 1 geschrieben wurde. Benutzen Sie hierbei das DOM API. Aufgabe 3 Schreiben Sie für die Klasse Tree eine Methode boolean contains(java.util.function.Predicate pred), die genau dann wahr als Ergebnis hat, wenn für eines der Elemente im Baum das übergebene Prädikat wahr ist. 63 Kapitel 2 Hierarchische Strukturen Aufgabe 3 Nur für die Angewandte Informatik. Abgabe dieser Aufgabe bis Montag 26.5. per Mail an Leiter der Praktikumsstunde. Gegeben sei folgende Header Datei aus der Vorlesung: 1 2 #i f n d e f BIN_TREE__H #d e f i n e BIN_TREE__H 3 4 #i n c l u d e 5 6 typedef bool l e ( void * , void *) ; 7 8 9 10 11 12 13 14 s t r u c t TR{ /* im p r i n z i p i s t v o i d * s o etwas wie i r g e n d w a s a l s o : Object */ v o i d * head ; /* l i n k e s Kind ( d a r f NULL s e i n ) */ s t r u c t TR* l e f t ; /* l i n k e s Kind ( d a r f NULL s e i n ) */ s t r u c t TR* r i g h t ; 15 /* d i e O r d n u n g s r e l a t i o n . s o l l t e im j e d e n Knoten d e r s e l b e Z e i g e r s e i n */ le * kleinerGleich ; 16 17 18 }; 19 20 21 t y p e d e f s t r u c t TR Tree ; t y p e d e f u n s i g n e d i n t nat ; 22 23 b o o l isEmpty ( Tree * t h i s ) ; 24 25 26 /* mache e i n e l e e r e Menge */ Tree * newEmptyTree ( l e k l e i n e r G l e i c h ) ; 27 28 29 /* mache e i n e e i n e l e m e n t i g e Menge */ Tree * newLeafTree ( l e k l e i n e r G l e i c h , v o i d * elem ) ; 30 31 32 /* l ö s c h e a l l e Baumknoten , a b e r n i c h t d i e Elemente */ v o i d d e l e t e T r e e ( Tree * t h i s ) ; 33 34 /* u n s i g n e d i n t */ nat l e n g t h ( Tree * t h i s ) ; 35 36 37 /* Algorithmus f ü r das Hinzufügen e i n e s Elements : 38 39 40 41 42 43 44 45 64 1 . Schaue ob t h i s l e e r e r Baum : dann t h i s −>head = e l 2. sonst v e r g l e i c h e : t h i s −>k l e i n e r G l e i c h ( e l , head ) a ) Ja ! dann c h e c k e : t h i s −>k l e i n e r G l e i c h ( head , e l ) i ) Ja ! dann r e t u r n ( ohne w e i t e r e a k t i o n ) i i ) s o n s t add ( t h i s −>l e f t , e l ) ( wenn t h i s −> l e f t n i c h t NULL) ( o d e r t h i s −> l e f t = newLeafTree ( t h i s −> 2.2 Bäume als verallgemeinerte Listen kleinerGleich , el ) b ) a n a l o g wie oben nur r e c h t e S e i t e r e c h t s 46 47 48 */ v o i d add ( Tree * t h i s , v o i d * e l ) ; 49 50 51 /* k o p i e r e den Baum, a b e r n i c h t d i e Elemente */ Tree * copyTree ( Tree * t h i s ) ; 52 53 54 55 /* e n t h ä l t d e r Baum e i n bestimmtes Element . H i e r z u wird d i e O r d n u n g s r e l a t i o n d e s Baumes genommen . x==y b e d e u t e t : k l e i n e r G l e i c h ( x , y ) && k l e i n e r G l e i c h ( y , x ) . */ 56 57 b o o l c o n t a i n s ( Tree * t h i s , v o i d * elem ) ; 58 59 60 /* mache etwas f ü r a l l e Elemente , d i e vom Baum r e f e r e n z i e r t werden . */ v o i d macheFuerAlle ( Tree * t h i s , v o i d consumer ( v o i d * ) ) ; 61 62 /* B e i s p i e l f ü r i n t Z e i g e r : 63 64 65 66 b o o l k l G l ( v o i d * xp , v o i d * yp ) { r e t u r n * ( ( i n t * ) xp ) <= * ( ( i n t * ) yp ) ; } 67 68 69 70 void p r i n t I n t ( void * p) { p r i n t f (”%d ” , * ( ( i n t * ) p ) ) ; } 71 72 73 74 75 76 i n t main ( ) { i n t xs [ ] = { 3 4 , 5 , 2 3 , 6 , 5 3 4 5 , − 3 4 , 4 3 , − 4 3 1 , 1 , 4 3 , 5 4 4 5 , − 2 6 5 } ; Tree * t = newEmptyTree ( k l G l ) ; int i ; f o r ( i =0; i < 1 2 ; i ++) add ( t , xs+i ) ; 77 macheFuerAlle ( t , p r i n t I n t ) ; 78 79 deleteTree ( t ) ; 80 81 return 0; 82 83 } 84 85 86 */ #e n d i f Listing 2.48: BinTree.h Schreiben Sie die Implementierung dieser header Datei, so dass sie einen Binärbaum erhalten, der eine Menge realisiert. 1 2 #i n c l u d e ” BinTree . h” #i n c l u d e < s t d l i b . h> 65 Kapitel 2 Hierarchische Strukturen 3 #i n c l u d e 4 5 6 7 8 9 b o o l isEmpty ( Tree * t h i s ) { r e t u r n t h i s −>head==NULL && t h i s −> l e f t == NULL && t h i s −>r i g h t == NULL; } 10 11 12 13 Tree * newEmptyTree ( l e k l e i n e r G l e i c h ) { r e t u r n newLeafTree ( k l e i n e r G l e i c h ,NULL) ; } 14 15 16 17 18 19 20 21 22 23 /* mache e i n e e i n e l e m e n t i g e Menge */ Tree * newLeafTree ( l e k l e i n e r G l e i c h , v o i d * elem ) { Tree * t h i s = m a l l o c ( s i z e o f ( Tree ) ) ; t h i s −> l e f t = NULL; t h i s −> r i g h t = NULL; t h i s −> k l e i n e r G l e i c h = k l e i n e r G l e i c h ; t h i s −> head = elem ; return this ; } 24 25 26 27 28 29 30 /* l ö s c h e a l l e Baumknoten , a b e r n i c h t d i e Elemente */ v o i d d e l e t e T r e e ( Tree * t h i s ) { i f (NULL != t h i s −> l e f t ) d e l e t e T r e e ( t h i s −> l e f t ) ; i f (NULL != t h i s −>r i g h t ) d e l e t e T r e e ( t h i s −>r i g h t ) ; free ( this ) ; } 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 v o i d add ( Tree * t h i s , v o i d * e l ) { i f ( isEmpty ( t h i s ) ) { t h i s −> head = e l ; } else { i f ( t h i s −>k l e i n e r G l e i c h ( e l , t h i s −>head ) ) { i f ( t h i s −>k l e i n e r G l e i c h ( t h i s −>head , e l ) ) r e t u r n ; i f (NULL == t h i s −> l e f t ) { t h i s −> l e f t = newLeafTree ( t h i s −>k l e i n e r G l e i c h , e l ) ; }else { add ( t h i s −>l e f t , e l ) ; } } else { i f (NULL == t h i s −> r i g h t ) { t h i s −> r i g h t = newLeafTree ( t h i s −>k l e i n e r G l e i c h , e l ) ; }else { add ( t h i s −>r i g h t , e l ) ; } } } } 52 53 54 66 v o i d macheFuerAlle ( Tree * t h i s , v o i d consumer ( v o i d * ) ) { i f ( t h i s == NULL) r e t u r n ; 2.3 XML als serialisierte Baumstruktur i f ( isEmpty ( t h i s ) ) r e t u r n ; macheFuerAlle ( t h i s −> l e f t , consumer ) ; consumer ( t h i s −>head ) ; macheFuerAlle ( t h i s −> r i g h t , consumer ) ; 55 56 57 58 59 } 60 61 62 63 void p r i n t I n t ( void * p) { p r i n t f ( ”%d ” , * ( ( i n t * ) p ) ) ; } 64 65 66 67 68 69 70 71 72 73 b o o l c o n t a i n s ( Tree * t h i s , v o i d * e l ) { i f ( t h i s == NULL) r e t u r n f a l s e ; i f ( isEmpty ( t h i s ) ) r e t u r n f a l s e ; i f ( t h i s −>k l e i n e r G l e i c h ( e l , t h i s −> head )&&t h i s −>k l e i n e r G l e i c h ( t h i s −> head , e l ) ) return true ; i f ( t h i s −>k l e i n e r G l e i c h ( e l , t h i s −> head ) ) { r e t u r n c o n t a i n s ( t h i s −> l e f t , e l ) ; } r e t u r n c o n t a i n s ( t h i s −> r i g h t , e l ) ; 74 75 } 76 77 78 79 b o o l k l G l ( v o i d * xp , v o i d * yp ) { r e t u r n * ( ( i n t * ) xp ) <= * ( ( i n t * ) yp ) ; } Listing 2.49: BinTree.c Aufgabe 4 Schreiben Sie für die Klasse Tree eine Methode boolean contains(E el), die genau dann wahr als Ergebnis hat, wenn eines der Elemente im Baum gleich dem übergebenen Element ist. Aufgabe 5 Schreiben Sie für die Klasse Tree eine Methode Tree mapTree(java.util.function.Function f), die einen neuen Baum erzeugt, dessen Elemente aus den Elementen des Ursprungsbaums mit Hilfe der übergebenen Funktion erzeugt werden. 2.3 XML als serialisierte Baumstruktur XML ist eine Sprache, die es erlaubt Dokumente mit einer logischen Struktur zu beschreiben. Die Grundidee dahinter ist, die logische Struktur eines Dokuments 67 Kapitel 2 Hierarchische Strukturen von seiner Visualisierung zu trennen. Ein Dokument mit einer bestimmten logischen Struktur kann für verschiedene Medien unterschiedlich visualisiert werden, z.B. als HTML-Dokument für die Darstellung in einem Webbrowser, als pdf- oder postscript-Datei für den Druck des Dokuments und das für unterschiedliche Druckformate. Eventuell sollen nicht alle Teile eines Dokuments visualisiert werden. XML ist zunächst eine Sprache, die logisch strukturierte Dokumente zu schreiben, erlaubt. Dokumente bestehen hierbei aus den eigentlichen Dokumenttext und zusätzlich aus Markierungen dieses Textes. Die Markierungen sind in spitzen Klammern eingeschlossen. Beispiel 2.3.1 Der eigentliche Text des Dokuments sei: 1 The B e a t l e s White Album Die einzelnen Bestandteile dieses Textes können markiert werden: 1 2 3 4 < a r t i s t >The B e a t l e s < t i t l e >White Album Die XML-Sprache wird durch ein Industriekonsortium definiert, dem W3C. Dieses ist ein Zusammenschluß vieler Firmen, die ein gemeinsames Interesse eines allgemeinen Standards für eine Markierungssprache haben. Die eigentlichen Standards des W3C heißen nicht Standard, sondern Empfehlung (recommendation), weil es sich bei dem W3C nicht um eine staatliche oder überstaatliche Standartisiertungsbehörde handelt. Die aktuelle Empfehlung für XML liegt seit August 2006 als Empfehlung in der Version 1.1 vor . XML enstand Ende der 90er Jahre und ist abgeleitet von einer umfangreicheren Dokumentenbeschreibungssprache: SGML. Der SGML-Standard ist wesentlich komplizierter und krankt daran, daß es extrem schwer ist, Software für die Verarbeitung von SGML-Dokumenten zu entwickeln. Daher fasste SGML nur Fuß in Bereichen, wo gut strukturierte, leicht wartbare Dokumente von fundamentaler Bedeutung waren, so dass die Investition in teure Werkzeuge zur Erzeugung und Pflege von SGML-Dokumenten sich rentierte. Dies waren z.B. Dokumentationen im Luftfahrtbereich.3 Die Idee bei der Entwicklung von XML war: eine Sprache mit den Vorteilen von SGML zu Entwickeln, die klein, übersichtlich und leicht zu handhaben ist. 3 Man sagt, ein Pilot brauche den Copiloten, damit dieser die Handbücher für das Flugzeug trägt. 68 2.4 Das syntaktische XML-Format Wie wir im Laufe des Kapitels sehen werden, ist die logische Struktur eines XMLDokuments auch wieder eine hierarchische Baumstruktur, so dass wir alle unsere Überlegungen zu Bäumen direkt auf XML-Dokumente anwenden können. 2.4 Das syntaktische XML-Format Die grundlegendste Empfehlung des W3C legt fest, wann ein Dokument ein gültiges XML-Dokument ist, die Syntax eines XML-Dokuments. Die nächsten Abschnitte stellen die wichtigsten Bestandteile eines XML-Dokuments vor. Jedes Dokument beginnt mit einer Anfangszeile, in dem das Dokument angibt, daß es ein XML-Dokument nach einer bestimmten Version der XML Empfehlung ist: 1 Dieses ist die erste Zeile eines XML-Dokuments. Vor dieser Zeile darf kein Leerzeichen stehen. Die derzeitig aktuellste und einzige Version der XML-Empfehlung ist die Version 1.1. vom 16. August 2006. Nach Aussage eines Mitglieds des W3C ist es sehr unwahrscheinlich, dass es jemals eine Version 2.0 von XML geben wird. Zuviele weitere Techniken und Empfehlungen basieren auf XML, so daß die Definition von dem, was ein XML-Dokument ist kaum mehr in größeren Rahmen zu ändern ist. 2.4.1 Elementknoten Der Hauptbestandteil eines XML-Dokuments sind die Elemente. Dieses sind mit der Spitzenklammernotation um Teile des Dokuments gemachte Markierungen. Ein Element hat einen Tagnamen, der ein beliebiges Wort ohne Leerzeichen sein kann. Für einen Tagnamen name beginnt ein Element mit und endet mit . Zwischen dieser Start- und Endemarkierung eines Elements kann Text oder auch weitere Elemente stehen. Es wird für XML-Dokument verlangt, daß es genau ein einziges oberstes Element hat. Beispiel 2.4.1 Somit ist ein einfaches XML-Dokument ein solches Dokument, in dem der gesammte Text mit einem einzigen Element markiert ist: 1 2 3 4 D i e s e s i s t d e r Text d e s Dokuments . Er i s t mit genau einem Element m a r k i e r t . 69 Kapitel 2 Hierarchische Strukturen Im einführenden Beispiel haben wir schon ein XML-Dokument gesehen, das mehrere Elemente hat. Dort umschließt das Element zwei weitere Elemente, die Elemente und