siebler-2014-iterator-pattern.pdf

9 Iterator Pattern Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024...

9 Iterator Pattern Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 Java kennt verschiedene Sammlungen, beispielsweise die Klassen ArrayList und Linked- List. Die Daten werden in diesen Klassen intern unterschiedlich gespeichert. Für den ­Client ist es aber von Interesse, dass er ohne Kenntnis der internen Struktur über die Daten iterieren kann. In diesem Kapitel werden Sie sich ausführlich mit Sammlungen beschäf­ tigen und die Klassen ArrayList und LinkedList nachbilden. Sie werden außerdem eine Schnittstelle erstellen, mit der Sie über diese Klassen iterieren können. For personal use only. 9.1 Zwei Möglichkeiten, Daten zu speichern In den folgenden Abschnitten werde ich Ihnen zwei Möglichkeiten zeigen, wie Sie Samm­ lungen erzeugen können. 9.1.1 Daten in einem Array speichern Die erste Sammlung, die Sie irgendwann einmal kennengelernt haben, war sicher das Array. In einem Array speichern Sie beliebig viele Elemente eines bestimmten Datentyps. Mit der Deklaration int[] zahlen = new int legen Sie ein Array an, das fünf int-Zahlen speichern kann. Sie greifen sehr performant auf die einzelnen Speicherbereiche zu. Ein Array hat den Nachteil, dass es sich nicht vergrößern lässt. Das ist unpraktisch, wenn sich herausstellt, dass mehr Daten gespeichert werden sollen, als ursprünglich vorgesehen war. Basis für die erste Sammlung soll ein Array sein. Das Array wird vom allgemeinen Typ Object sein. Initial sollen fünf Objekte referenziert werden können. Um verschiedene Datentypen typsicher speichern zu können, legen Sie die Klasse generisch an. Listing 9.1 Datenbasis im Projekt „Sammlungen_1“ public class MyArray { private int zaehler = 0; private Object[] elemente = new Object; }  110 9 Iterator Pattern Um ein neues Element einzufügen, definieren Sie die Methode add(). Ihr wird ein Argu­ ment vom generischen Typ übergeben. Dieses Element wird an der nächsten freien Stelle im Array gespeichert. Das Datenfeld zaehler speichert diese Position. Wenn bereits fünf Elemente gespeichert werden und ein sechstes hinzukommen soll, muss die Datenbasis erweitert werden. Da ein Array nicht vergrößert werden kann, bleibt nur der Weg, das Array neu zu definieren. Allgemein: Wenn die nächstfreie Position gleich der Anzahl Elemente ist, muss die Größe des Arrays um einen bestimmten Wert vergrößert werden. Im Beispiel soll die Arraygröße um weitere fünf Elemente vergrößert werden. Listing 9.2 Elemente in der Sammlung speichern Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 public void add(E e) { if (zaehler == elemente.length) { Object[] tempArray = new Object[zaehler + 5]; System.arraycopy(elemente, 0, tempArray, 0, zaehler); elemente = tempArray; } elemente[zaehler] = e; zaehler++; } Der Client möchte vielleicht erfragen, wie viele Elemente in der Sammlung gespeichert sind. Dafür reicht es, dass Sie die Position des nächstfreien Elements zurückgeben. For personal use only. Listing 9.3 Anzahl gespeicherter Elemente bekanntgeben public int size() { return zaehler; } Die Sammlung erfüllt ihren Sinn erst dann, wenn die einzelnen Elemente zurückgegeben werden können. Hierzu legen Sie die Methode get() an, die als Parameter einen Index erwartet, der die Stelle des gesuchten Elements in der Datenbasis beschreibt. Vor der Rück­ gabe wird der gespeicherte Wert auf den generischen Typ gecastet. Listing 9.4 Ein Element an einer bestimmten Stelle zurückgeben public E get(int index) { return (E) elemente[index]; } Wenn Sie ein Element löschen möchten, muss zunächst der Zähler dekrementiert werden. Das Element wird dann dadurch gelöscht, dass Sie die nachfolgenden Elemente jeweils um eine Stelle nach vorne verschieben. Listing 9.5 Element an bestimmtem Index löschen public void remove(int index) { if (index == zaehler) zaehler--;  9.1 Zwei Möglichkeiten, Daten zu speichern 111 else { System.arraycopy( elemente, index + 1, elemente, index, elemente.length-1-index); elemente[zaehler--] = null; } } Die Sammlung, die Sie gerade entwickelt haben, entspricht der ArrayList der Klassenbibliothek. Sie ist optimal, wenn Sie auf einzelne Elemente über deren Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 Index zugreifen müssen. 9.1.2 Daten in einer Kette speichern Einen ganz anderen Ansatz verfolgen Sie, wenn Sie die einzelnen Elemente nicht in einem Array speichern, sondern in einer Kette. Jedes Element kennt seinen Nachfolger. Denkbar wäre auch, dass ein Element auch einen Vorgänger kennt; auf diese Möglichkeit gehe ich nicht weiter ein – das Projekt würde nur unnötig umfangreich, ohne das dahinterstehende Prinzip zu verändern. Strings und alle anderen Objekte, die Sie in Ihrer Liste speichern möchten, nenne ich Ele- For personal use only. ment. Sie werden nicht in der Sammlung gespeichert, sondern in der Instanz einer inneren Klasse, die ich Node nenne. Die Klasse Node hat zwei Datenfelder, die das zu speichernde Element und das nachfolgende Node-Objekt speichern. Die Sammlung kann sich dann da­­ rauf beschränken, das erste Objekt (das Datenfeld header) zu referenzieren. Listing 9.6 Die Klasse „MyList“ im Projekt „Sammlungen_1“ public class MyList { private int zaehler = 0; private Node header = null; private class Node { private final E ELEMENT; private Node nextNode; Node(E element, Node next) { this.ELEMENT = element; this.nextNode = next; } } } Daten werden in die Sammlung eingefügt, indem ein neues Node-Objekt erzeugt wird. Dieses Objekt wird von der Variablen header referenziert und verdrängt das vorher als header gespeicherte Objekt. Das Feld nextNode des neuen header-Objekts referenziert den früheren header. Und schließlich muss der Zähler inkrementiert werden. Wenn Sie die Größe der Sammlung abfragen, wird der Zähler zurückgegeben.  112 9 Iterator Pattern Listing 9.7 Elemente einfügen und Größe der Datenbasis zurückgeben public void add(E element) { header = new Node(element, header); zaehler++; } public int size() { return zaehler; } Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 Um ein Element aus der Sammlung zu löschen, gehen Sie die Sammlung mit einer while- Schleife durch und prüfen, ob das referenzierte Element gleich dem gesuchten Element ist. In diesem Fall übergeben Sie die Referenz des nachfolgenden Node-Objekts an den Vorgän­ ger des Node-Objekts, das das gesuchte Element referenziert. Anschließend dekrementie­ ren Sie den Zähler. Die lokale Variable previous referenziert jeweils den Vorgänger des Node-Objekts, dessen Element gerade geprüft wird. Listing 9.8 Ein bestimmtes Element löschen public boolean remove(E element) { Node previous = null; For personal use only. Node tempNode = header; while( tempNode != null ) { if( equals( element, tempNode.ELEMENT)) { if( previous == null ) header = tempNode.nextNode; else previous.nextNode = tempNode.nextNode; zaehler--; return true; } previous = tempNode; tempNode = previous.nextNode; } return false; } Die Methode get() soll die gleiche Aufgabe lösen wie die get-Methode der Klasse MyArray. Da die Datenbasis jedoch nicht indexbasiert ist, können Sie das x-te Element in der Samm­ lung nicht direkt erfragen. Sie müssen die gesamte Sammlung durchgehen, bis Sie das x-te Element gefunden haben. Listing 9.9 Ein indiziertes Element zurückgeben public E get(int index) { if (index < 0 || index >= zaehler) throw new NoSuchElementException();  9.2 Aufgabe eines Iterators 113 Node tempNode = header; for (int i = 0; i < index; i++) tempNode = tempNode.nextNode; return tempNode.ELEMENT; } Die Klasse, die Sie gerade entwickelt haben, entspricht der Klasse LinkedList aus der Klassenbibliothek. Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 9.2 Aufgabe eines Iterators Wenn Sie eine Sammlung anlegen, möchten Sie sicher auch über alle Elemente iterieren. Ein erster Ansatz könnte das Vorgehen der Testmethoden sein, die Sie zu beiden Klassen unter www.patternsBuch.de finden. Bitte analysieren Sie diese und lassen Sie sie laufen. In beiden Testmethoden iterieren Sie mit einer for-Schleife über die Datensammlung. for (int i = 0; i < myList.size(); i++) { For personal use only. System.out.println(myList.get(i)); } Sie greifen mit der Methode get() auf jedes Element der Sammlung zu. Bei der Klasse MyArray ist das durchaus sinnvoll. Die Performance der Klasse MyList bleibt bei einem indexbasierten Zugriff auf ihre Elemente jedoch weit unter ihren Möglichkeiten. Es ist also sinnvoll, den Algorithmus, wie über die Sammlung zu iterieren ist, in eine eigene Klasse, den Iterator, auszulagern. Den Iterator können Sie sich wie ein Lesezeichen vorstellen, das Seite für Seite durch ein Buch geschoben wird. Der Iterator kennt die spezifischen Merk­ male einer Sammlung und nutzt diese optimal. Sie können einen Iterator als internen Iterator oder als externen Iterator entwerfen. Intern bedeutet, dass Sie die Aktion des Iterierens an den Iterator übergeben, der „selbstständig“ über alle Objekte iteriert. Wenn Sie einen externen Iterator pro- grammieren, lassen Sie sich das jeweils nächste Element zurückgeben und fragen ab, ob noch weitere Elemente vorhanden sind, die Sie anfordern können; es ist also die Aufgabe des Client, den Iterator voranzutreiben. Die größte Flexibilität ­erhalten Sie sich mit einem externen Iterator. Im Folgenden werde ich mich nur mit externen Iteratoren beschäftigen. Sie werden einen internen Iterator gleich beim Composite Pattern wiederfinden.  114 9 Iterator Pattern 9.3 Das Interface „Iterator“ in Java Die Klassenbibliothek kennt das Interface Iterator, das eine Schnittstelle für alle er­­ denklichen Iteratoren darstellt. Mit hasNext() lassen Sie sich zurückgeben, ob noch weitere Elemente in der Datensammlung enthalten sind. Die Methode next() liefert das nächste Element in der Sammlung. Wenn der Client auf ein Element zugreifen möchte, das es nicht gibt, werfen Sie eine NoSuchElementException. Und remove() schließlich löscht das aktu­ elle Element aus der zugrunde liegenden Datensammlung. Die Methode remove() muss ge­­mäß der Spezifikation nicht implementiert werden, sie darf eine UnsupportedOperation Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 Exception werfen. 9.3.1 Der Iterator der Klasse „MyArray“ Die einfachste Form eines Iterators wird von der Methode iterator() zurückgegeben. Der Iterator speichert intern die Position, an der das Lesezeichen gesetzt wird. Die Methode next() gibt das jeweils nächste Element zurück, die Methode hasNext() liefert true zurück, wenn es weitere Elemente gibt. Listing 9.10 Iterator der Klasse „MyArray“ im Projekt „Sammlungen_2“ For personal use only. public Iterator iterator() { return new Iterator() { private int position = -1; @Override public boolean hasNext() { return (position < size()) && elemente[position + 1] != null; } @Override public E next() { position++; if(position >= size() || elemente[position] == null) throw new NoSuchElementException("..."); E value = (E) elemente[position]; return value; } @Override public void remove() { throw new UnsupportedOperationException("..."); } }; } Der nächste Abschnitt zeigt, wie Sie den Iterator verwenden.  9.3 Das Interface „Iterator“ in Java 115 9.3.1.1 Test des Iterators Sie legen in der main-Methode zunächst eine Sammlung vom Typ MyArray an und spei­ chern einige Strings darin. MyArray myArray = new MyArray(); myArray.add("String 1"); //... myArray.add("String 6"); Danach lassen Sie sich einen Iterator zurückgeben und fragen in einer while-Schleife so lange Daten ab, bis keine weiteren Daten mehr in der Sammlung enthalten sind. Um die Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 Exception zu provozieren, rufen Sie gezielt ein Element mehr ab, als gespeichert ist. Iterator iterator = myArray.iterator(); while(iterator.hasNext()) System.out.println( iterator.next() ); // provoziert eine Exception System.out.println(iterator.next()); Auf der Konsole wird nun jeder String ausgegeben. Anschließend wird die Exception ge­­ worfen. 9.3.1.2 Kritik am Iterator Die Iteration wird nun sehr viel einfacher und da der Client-Code sich nicht ändert, sind die For personal use only. Listen austauschbar. Sie lassen sich zunächst einen Iterator geben und rufen so lange die Methode next() auf, wie die Methode hasNext() ein true zurückgibt. Die Beispiele sind sehr einfach gehalten, die Methode iterator() gibt als Iterator die Instanz einer anonymen Klasse zurück. Dieser Iterator geht die Datenbasis elementweise von vorne nach hinten durch. Diese Vereinfachung darf nicht darüber hinwegtäuschen, dass Sie als Programmie­ rer frei sind, den Iterator so zu definieren, wie Sie es brauchen. Beispielsweise könnte der Iterator das Array von hinten nach vorne durchgehen. Alternativ wäre auch ein Iterator denkbar, der die Datenbasis zunächst kopiert und/oder sortiert, bevor er die einzelnen Ele­ mente zurückgibt. Natürlich müssen Sie den Iterator nicht als anonyme Klasse definieren – Sie könnten auch eine Klasse außerhalb des Namensraums der Sammlung entwerfen. 9.3.2 Der Iterator der Klasse „MyList“ Die Klasse MyList ist intern anders aufgebaut. Die einzelnen Elemente werden nicht in einem Array gespeichert, sondern verlinkt. Welche Konsequenz hat das für den Iterator? Es wird im Gegensatz zu MyArray kein Zähler als Lesezeichen gespeichert, sondern das aktu­ elle Element. Initial wird das aktuelle Element auf den Header der Liste gesetzt. Wenn Sie testen möchten, ob eine Sammlung weitere Elemente enthält, müssen Sie fragen, ob das aktuelle Element des Iterators ungleich null ist; in diesem Fall darf die Methode hasNext() ein true zurückgeben. Die Methode next() gibt den Inhalt des aktuellen Ele­ ments zurück und rückt den Zeiger auf das nächste Element um eine Stelle weiter.  116 9 Iterator Pattern Listing 9.11 Iterator der Klasse „MyList“ im Projekt „Sammlungen_2“ public Iterator iterator() { return new Iterator() { private Node current = header; @Override public boolean hasNext() { return (current != null); Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 } @Override public E next() { if(current == null) throw new NoSuchElementException("..."); E value = (E)current.ELEMENT; current = current.nextNode; return value; } @Override public void remove() For personal use only. { throw new UnsupportedOperationException(); } }; } Und wie wird dieser Iterator getestet? 9.3.2.1 Test des Iterators Um den Iterator zu testen, legen Sie eine Instanz der Klasse MyList an und speichern in ihr verschiedene Strings. Sie lassen sich einen Iterator zurückgeben und iterieren über die komplette Sammlung. Natürlich habe ich auch bei diesem Test eine Abfrage zu viel ein­ gebaut, um das Auslösen der Exception zu provozieren. MyList myList = new MyList(); myList.add("String 1"); //... myList.add("String 6"); Iterator iterator = myList.iterator(); while(iterator.hasNext()) System.out.println( iterator.next() ); System.out.println(iterator.next()); Wieder werden zunächst alle Strings und auf der Konsole ausgegeben; anschließend wird eine Exception geworfen.  9.4 Das Interface „Iterable“ 117 9.3.2.2 Nutzen des Iterators Den Besonderheiten der beiden Sammlungsklassen wird nun Rechnung getragen, ohne dass der Client das überhaupt mitbekommt. Sie erinnern sich, dass Sie beim Observer ­Pattern gesehen haben, dass Iteratoren anfällig sind für Probleme, die aus Nebenläufig­ keit resultieren. Da Sie mehrere Iteratoren erzeugen können, ist es gar nicht so unwahr­ scheinlich, dass während der Iteration ein Element gelöscht wird. Sie stehen dann schnell vor der Situation, dass ein Iterator auf ein Element zugreifen möchte, das es gar nicht mehr gibt. Die Sammlungsklassen der Klassenbibliothek werfen in solchen Fällen eine ConcurrentModificationException. Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 9.4 Das Interface „Iterable“ Eine while-Schleife ist mit der for-Schleife verwandt. Anstelle der while-Schleife while(iterator.hasNext()) { //... Aktion } könnten Sie auch eine for-Schleife verwenden: For personal use only. for(Iterator iterator = myList.iterator(); iterator.hasNext(); ;) { //... Aktion } Seit Java 5 haben Sie die for-each-Schleife. Iterieren wird sehr viel einfacher: for (String tempString : liste) System.out.println(tempString); Wie können Sie Ihre Sammlungen MyList und MyArray so vorbereiten, dass Sie sie in einer for-each-Schleife verwenden können? Sie müssen lediglich das Interface Iterable imple­ mentieren. Dieses Interface schreibt die Methode iterator() vor, deren Rückgabewert der Iterator der Sammlung ist. Listing 9.12 Rahmen der Klasse „MyArray“ im Projekt „Sammlungen_3“ public class MyArray implements Iterable { @Override public Iterator iterator() { //... wie vorher } //... gekürzt }  118 9 Iterator Pattern Jetzt können Sie die Klasse MyArray in einer erweiterten for-Schleife einsetzen: MyArray myArray = new MyArray(); myArray.add("String 1"); //... myArray.add("String 6"); for(String tempString : myArray) System.out.println(tempString); Bei der MyList funktioniert das entsprechend. Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 Suchen Sie in der API-Doku nach dem Interface Iterable. Ein Subinterface ­hiervon ist das Interface Collection. Dieses Interface wird von allen gängigen Sammlungen wie List und Set und von vielen weiteren implementiert. Daher ­dürfen Sie darauf vertrauen, dass alle Sammlungen die Methode iterator() ­definieren, die ein Iterator-Objekt zurückgibt. Bei einer Map ist das Thema etwas vertrackter. Nehmen Sie als Beispiel eine HashMap, die aus drei Sammlungen besteht: einem KeySet für die Schlüssel, ­einer Collection für die Werte und einem EntrySet für die Verbindung zwischen beiden Sammlungen. Niemand kann im Voraus wissen, ob der Anwender über die Schlüssel oder über die Werte iterieren möchte; daher kann die HashMap keinen „Standard“-Iterator entwerfen. For personal use only. Die for-each-Schleife ist für den Programmierer ein sehr nützliches Sprachkonstrukt. Doch obwohl dem Programmierer viel Arbeit abgenommen wird, hat der Compiler verhältnis­ mäßig wenig Arbeit damit. Er schreibt die for-each-Schleife vor dem Übersetzen in eine while-Schleife um (Code-Rewriting) und lässt sich den Iterator geben. Wenn Sie mit der for- each-Schleife über ein Array iterieren, wird die Schleife in eine herkömmliche for-next- Schleife umgeschrieben und dann übersetzt. Sie sehen an diesem Beispiel, wie Patterns Einzug in die Klassenbibliothek ­gefunden haben. Nicht nur der Name, sondern auch die Realisierung des Patterns entspricht der Beschreibung der GoF. 9.5 Zusammenfassung Gehen Sie das Kapitel noch mal stichwortartig durch. ƒƒ Sammlungen sind intern unterschiedlich aufgebaut. ƒƒ Iteratoren sind Lesezeichen, die von einem Element zum nächsten verschoben werden. ƒƒ Sie ermöglichen es, ohne Kenntnis der internen Struktur über die Sammlung zu iterieren.  9.5 Zusammenfassung 119 ƒƒ Interne Iteratoren sind für das Voranschreiten des Iterators selbst verantwortlich. ƒƒ Bei externen Iteratoren ist der Client für das Voranschreiten verantwortlich. ƒƒ Ein Iterator hat, wenn er sich an der Java-Spezifikation orientiert, drei Methoden: ƒƒ remove() löscht ein Element aus der Sammlung – die Methode muss nicht überschrie­ ben werden. ƒƒ hasNext() gibt true zurück, wenn die Sammlung weitere Elemente hat. ƒƒ next() liefert das nächste Element der Sammlung zurück; gibt es kein Element, wird eine NoSuchElementException geworfen. Design Patterns mit Java downloaded from www.hanser-elibrary.com by AKAD Hochschule Stuttgart on September 30, 2024 ƒƒ Der Iterator wird von der Methode iterator() zurückgegeben. ƒƒ Die Definition des Iterators ist Aufgabe des Programmierers. ƒƒ Es kann mehrere Iterator-Klassen und mehrere Iterator-Instanzen geben. ƒƒ Während mindestens ein Iterator aktiv ist, darf die Datenbasis nicht geändert werden. ƒƒ Wenn eine Sammlung das Interface Iterable implementiert, kann mit der for-each- Schleife über sie iteriert werden. Zweckbeschreibung: Die Gang of Four beschreibt den Zweck des Patterns wie folgt: „Bietet eine Möglichkeit, um auf die Elemente eines zusammengesetzten Objekts For personal use only. sequenziell zugreifen zu können, ohne die zugrunde liegende Repräsentation ­offenzulegen.“