Software-Entwurfsmuster

Iterator

 aufwärts

Ein Iterator ist ein Objekt, das eine bestimmte Daten­struktur sequenziell durchläuft (Bild 1). Mit jedem Aufruf seiner Methode next liefert der Iterator jeweils das nächst­folgende Element (bezeichnet als das Cursor-Objekt). Mithilfe der Methode hasNext stellt der Iterator fest, ob noch weitere Elemente vorhanden sind.

Bild 1: Durchlaufen einer Datenstruktur mit einem Iterator
Bild 1: Durchlaufen einer Datenstruktur mit einem Iterator

Array-Iterator

Der einfachste Iterator durchläuft ein Array. Dem Iterator wird im Konstruktor das Array als Parameter übergeben. In einer Variablen i merkt sich der Iterator die Position des Cursor-Elements, also desjenigen Array-Elements, das als nächstes zurück­gegeben werden soll. Die Methode next gibt dieses Element zurück und erhöht i um 1. Die Methode hasNext ergibt den Wert true, solange i kleiner als die Länge des Arrays ist.

Es ist empfehlens­wert, die Schnitt­stelle java.util.Iterator zu verwenden. So ist der ArrayIterator überall einsetzbar, wo ein Iterator im Programm vorkommt. 1)

import java.util.Iterator;

public class ArrayIterator implements Iterator
{
    private Object[] a;
    private int i;

    public ArrayIterator(Object[] a_)
    {
        a=a_;
        i=0;
    }

    public boolean hasNext()
    {
        return i<a.length;
    }

    public Object next()
    {
        int k=i;
        i++;
        return a[k];
    }

    public void remove()
    {
        // nicht implementiert
    }

}    // end class ArrayIterator

 

Diese Implementierung ver­anschaulicht die Technik bei der Pro­grammierung eines Iterators. Im Konstruktor wird der Cursor auf das erste gültige Element gesetzt. Gibt es kein gültiges Element, so liefert hasNext bereits jetzt den Wert false. Bevor next das jeweilige aktuelle Cursor­element zurückgibt, wird dort schon das nächste gültige Cursor­element gesucht.

Der ArrayIterator wird typischerweise wie folgt angewendet, z.B. um alle Elemente eines Arrays a auszugeben:

    Iterator it=new ArrayIterator(a);
    while (it.hasNext())
        System.out.println(it.next());

Die Verwendung eines Iterators ist immer dann besonders elegant, wenn eine komplexere Daten­strukturen durchlaufen werden soll oder wenn der Durchlauf nach einem besonderen Muster vonstatten gehen soll. Beispiels­weise soll eine Matrix diagonalen­weise durchlaufen werden oder die Nachbarn eines Knotens in einem Graphen sollen durchlaufen werden.

Der Vorteil einer solchen Lösung mit einem Iterator besteht darin, dass der Iterator

ist. So muss nicht jedesmal neu überlegt, programmiert und getestet werden, wenn eine entsprechende Daten­struktur durchlaufen werden soll.

Iterator als Generator

Ein Iterator kann auch verwendet werden, um die Elemente einer bestimmten Menge oder Folge zu erzeugen. Beispiels­weise kann ein Iterator die Primfaktoren einer natürlichen Zahl erzeugen, die Permutationen einer Menge, oder die Zusammenhangs­komponenten eines Graphen.

Als weiteres Beispiel ist im Folgenden der Iterator ModIterator angegeben, der die Elemente von ganze Zahlenn, beginnend bei einem zufällig gewählten Element, erzeugt 2).

import java.util.Iterator;

public class ModIterator implements Iterator
{
    private int i, j, n;

    public ModIterator(int n_)
    {
        n=n_;
        i=0;
        j=(int)(Math.random()*n);    // Zufallszahl aus {0, ..., n-1}
    }

    public boolean hasNext()
    {
        return i<n;
    }

    public Object next()
    {
        Integer k=(i+j)%n;
        i++;
        return k;
    }

    public void remove()
    {
        // nicht implementiert
    }

}    // end class ModIterator

 

Da die Methode next des Iterators ein Objekt vom Typ Object zurückgibt, muss dieses mit einem Cast in den Typ Integer umgewandelt werden, bevor es als Zahl verwendet werden kann.

    Integer i;
    Iterator it=new ModIterator(10);
    while (it.hasNext())
    {
        i=(Integer)it.next();
        // verwende Zahl i
    }

Aufgaben

Aufgabe 1:  Schreiben Sie einen Iterator

public class MatrixIterator implements IntIterator,

der eine m × n-Matrix mit Einträgen vom Typ int zeilenweise durchläuft. Implementieren Sie den Konstruktor

public MatrixIterator(int[][] a)

und die Methoden

public boolean hasNext()   und

public int next()


1)  Die Schnitt­stelle java.util.Iterator verlangt unsinniger­weise zusätzlich die Implementierung einer Methode remove (im Programm­beispiel nicht implementiert)

2)  Der Programmcode funktioniert ab Java 5 (automatische Typ­umwandlung von int in Integer).

 

Weiter mit:  [Iterator mit Typ-Parameter]   [Filteriterator]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.11.2006   Updated: 20.06.2016
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik