Software-Entwurfsmuster

Iterator

(mit Typ-Parameter)

Ein Iterator ist ein Objekt, das eine bestimmte Datenstruktur sequenziell durchläuft (Bild 1). Mit jedem Aufruf seiner Methode next liefert der Iterator jeweils das nächstfolgende 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. Der Datentyp des Arrays wird dem Iterator als Typ-Parameter übergeben, das Array selbst wird dem Iterator im Konstruktor 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ückgegeben 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 empfehlenswert, die Schnittstelle java.util.Iterator zu verwenden. So ist der ArrayIterator überall einsetzbar, wo ein Iterator im Programm vorkommt.

 

public class ArrayIterator<Type> implements Iterator<Type>
{
    private Type[] a;
    private int n, i;

    public ArrayIterator(Type[] a_)
    {
        a=a_;
        n=a.length;
        i=0;
    }

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

    public Type next()
    {
        return a[i++];
    }

}    // end class ArrayIterator

 

Der Iterator wird typischerweise wie folgt angewendet, z.B. um alle Elemente eines String-Arrays s auszugeben.

 

public class TestArrayIterator
{
    public static void main(String[] args)
    {
        String[] s=new String[3];
        s[0]="ene";
        s[1]="mene";
        s[2]="muh";
        Iterator<String> it=new ArrayIterator<String>(s);
        while (it.hasNext())
            System.out.print(it.next()+" ");
        System.out.println();
    }
}

 

Die Verwendung eines Iterators ist immer dann besonders elegant, wenn eine komplexere Datenstrukturen durchlaufen werden soll oder wenn der Durchlauf nach einem besonderen Muster vonstatten gehen soll. Beispielsweise soll eine Matrix diagonalenweise 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 jedes Mal 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. Beispielsweise kann ein Iterator die Primfaktoren einer natürlichen Zahl erzeugen, die Permutationen einer Menge, oder die Zusammenhangskomponenten eines Graphen.

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

public class ModIterator implements Iterator<Integer>
{
    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 Integer next()
    {
        i++;
        return (i+j)%n;
    }

}

 

Der ModIterator wird beispielsweise wie folgt verwendet, um die Zahlen von 0 bis 9, beginnend bei einem zufälligen Anfangswert, zu erzeugen.

public class TestModIterator
{
    public static void main(String[] args)
    {
        int i;
        Iterator<Integer> it=new ModIterator(10);
        while (it.hasNext())
        {
            i=it.next();
            System.out.print(i+" ");
        }
        System.out.println();
    }
}

 

Aufgaben

Aufgabe 1:  Schreiben Sie einen Iterator, der eine m×n-Matrix mit Einträgen vom Typ Type zeilenweise durchläuft. Implementieren Sie den Konstruktor und die Methoden hasNext und next.

public class MatrixIterator<Type> implements Iterator<Type>
{
    // ...

    public MatrixIterator(Type[][] a)
    {
        // ...
    }

    public boolean hasNext()
    {
        // ...
    }

    public Type next()
    {
        // ...
    }
}

Testen Sie den Iterator mit einer Matrix vom Typ Double.

 

Weiter mit:  [Filteriterator]   oder   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 05.11.2006   Updated: 18.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden