Objektorientierte Entwurfsmuster - Architektur und Entwurfsmuster der Softwaretechnik - page 232

Infolge der Trennung der Datenstruktur und des Mechanismus
des Traversierens kann man Iteratoren für verschiedene Traver-
sierungsarten schreiben, ohne dabei die Schnittstelle der Daten-
struktur zu verändern
Die Realisierung der Traversierung wird aus der Datenstruktur herausgehalten. Da-
durch wird die Formulierung der Datenstruktur einfacher. Eine Traversierung kann im
Falle einer Liste zum Beispiel sequenziell vorwärts oder sequenziell rückwärts erfol-
gen. Bei einem Baum kann beispielsweise nach der Strategie Depth-First 67 traversiert
werden.
Man unterscheidet externe und interne Iteratoren. Bei einem ex-
ternen Iterator wird die Iteration vom Client selbst gesteuert,
d. h., der Client muss das Weiterrücken des Iterators veranlas-
sen. Ein interner Iterator rückt von selbst vor und kapselt so den
Aufbau einer Iteration. Dadurch wird die Iteration wiederverwend-
bar. Sie muss also nicht wie bei einem externen Iterator stets neu
programmiert werden.
Einem internen Iterator muss die Operation übergeben werden, die er während eines
Durchlaufs ausführen soll. Interne Iteratoren werden ausführlich in "Design Patterns -
Elements of Reusable Object-Oriented Software" [Gam95] der sogenannten " Gang of
Four " (GoF) vorgestellt. Da interne Iteratoren den Aufbau der Iteratoren kapseln, ist
von außen ihre Eigenschaft als Iterator nicht mehr erkennbar. Sie werden in dem vor-
liegenden Buch nicht weiter betrachtet.
Im Folgenden werden externe Iteratoren mit sequenziellem Zugriff behandelt. Solch
ein Iterator hat grundsätzlich die beiden Methoden next() und hasNext() . Diese
beiden Methoden sind typisch für externe Iteratoren. Die Methode hasNext() stellt
fest, ob es noch ein nächstes Element gibt oder nicht, die Methode next() beschafft
das nächste Element. Gibt es noch weitere Elemente in der Datenstruktur, gibt die
Methode hasNext() als Ergebnis true zurück. Das folgende Bild zeigt die Trennung
von Iterator und der zu durchquerenden Datenstruktur für den Fall eines externen
Iterators:
67 Depth-First bedeutet "Tiefe zuerst" - bildlich gesprochen geht man in einem Baum erst in die Tiefe,
dann in die Breite. Das bedeutet, dass bei der Depth-First Traversierung ausgehend vom Startknoten
ein Unterzweig eines jeden auftretenden Kindknotens bis zu dessen letzten Kindknoten durchlaufen
wird und erst anschließend zurückgekehrt wird, um einen Nachbarknoten zu besuchen.