3.8 Mit einem Iterator durch die Daten wandern

Wenn wir mit einer ArrayList oder LinkedList arbeiten, so haben wir zumindest eine gemeinsame Schnittstelle List, um an die Daten zu kommen. Doch was vereinigt eine Menge (Set) und eine Liste, sodass sich die Elemente der Sammlungen mit gleichem Programmcode erfragen lassen? Listen geben als Sequenz den Elementen zwar Positionen, aber in einer Menge hat kein Element eine Position. Hier bieten sich Iteratoren beziehungsweise Enumeratoren an, die unabhängig von der Datenstruktur alle Elemente auslesen – wir sagen dann, dass sie »über die Datenstruktur iterieren«. Und nicht nur eine Datenstruktur kann Daten liefern; eine Dateioperation könnte genauso gut Datengeber für alle Zeilen sein.

In Java gibt es für Iteratoren zum einen die Schnittstelle java.util.Iterator und zum anderen den älteren java.util.Enumeration. Der Enumerator ist nicht mehr aktuell, daher konzentrieren wir uns zunächst auf den Iterator.

Abbildung 3.10: Iterator und Enumeration

3.8.1 Die Schnittstelle Iterator

Ein Iterator ist ein Datengeber, der über eine Methode verfügen muss, um das nächste Element zu liefern. Dann muss es eine zweite Methode geben, die Auskunft darüber gibt, ob der Datengeber noch weitere Elemente zur Verfügung stellt. Zwei Operationen der Schnittstelle Iterator sind daher:

Die Methode hasNext() ermittelt, ob es überhaupt ein nächstes Element gibt, und wenn ja, ob next() das nächste Element erfragen darf. Bei jedem Aufruf von next() erhalten wir ein weiteres Element der Datenstruktur. So kann der Iterator einen Datengeber (in der Regel eine Datenstruktur) Element für Element ablaufen. Übergehen wir ein false von hasNext() und fragen trotzdem mit next() nach dem nächsten Element, bestraft uns eine NoSuchElementException.

Prinzipiell könnte die Methode, die das nächste Element liefert, auch per Definition null zurückgeben und so anzeigen, dass es keine weiteren Elemente mehr gibt. Allerdings kann null dann kein gültiger Iterator-Wert sein, und das wäre ungünstig.

interface java.util.Iterator<E>

• boolean hasNext()
  Liefert true, falls die Iteration weitere Elemente bietet.
• E next()
  Liefert das nächste Element in der Aufzählung oder NoSuchElementException, wenn keine weiteren Elemente mehr vorhanden sind.
• void remove()

Die Schnittstelle Iterator erweitert selbst keine weitere Schnittstelle.[24](Konkrete Enumeratoren (und Iteratoren) können nicht automatisch serialisiert werden; die realisierenden Klassen müssen hierzu die Schnittstelle Serializable implementieren.) Die Deklaration ist generisch, da das, was der Iterator liefert, immer von einem bekannten Typ ist.

Collection<String> set = new TreeSet<String>();
Collections.addAll( set, "Horst", "Schlämmer", "Hape" , "Kerkeling" );
for ( Iterator<String> iter = set.iterator(); iter.hasNext(); )
  System.out.println( iter.next() );

Beim Iterator geht es immer nur vorwärts

Im Gegensatz zum Index eines Felds können wir beim Iterator ein Objekt nicht noch einmal auslesen (next() geht automatisch zum nächsten Element), nicht vorspringen beziehungsweise hin und her springen. Ein Iterator gleicht anschaulich einem Datenstrom; wollten wir ein Element zweimal besuchen, zum Beispiel eine Datenstruktur von rechts nach links noch einmal durchwandern, dann müssen wir wieder ein neues Iterator-Objekt erzeugen oder uns die Elemente zwischendurch merken. Nur bei Listen und sortierten Datenstrukturen ist die Reihenfolge der Elemente vorhersehbar.

3.8.2 Der Iterator kann (eventuell auch) löschen

Die Schnittstelle Iterator bietet prinzipiell die Möglichkeit, das zuletzt aufgezählte Element aus dem zugrunde liegenden Container mit remove() zu entfernen. Vor dem Aufruf muss also next() das zu löschende Element als Ergebnis geliefert haben. Eine Enumeration kann die aufgezählte Datenstruktur grundsätzlich nicht verändern.

LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();
set.addAll( Arrays.asList( 3, 2, 1, 6, 5, 4 ) );
System.out.println( set );  // [3, 2, 1, 6, 5, 4]
for ( Iterator<Integer> iter = set.iterator(); iter.hasNext(); )
{
  iter.next();
  if ( set.size() > 2 )
    iter.remove();
}
System.out.println( set );  // [5, 4]

interface java.util.Iterator<E>

• boolean hasNext()
• E next()
• void remove()
  Entfernt das Element, das der Iterator zuletzt bei next() geliefert hat. Kann ein Iterator keine Elemente löschen, so löst er eine UnsupportedOperationException aus.

In der Dokumentation ist die Methode remove() als optional gekennzeichnet. Das heißt, dass ein konkreter Iterator kein remove() können muss – auch eine UnsupportedOperationException ist möglich. Das ist etwa dann der Fall, wenn ein Iterator von einer unveränderbaren Datenstruktur kommt.

3.8.3 Einen Zufallszahleniterator schreiben

Zur Übung wollen wir einen Iterator schreiben, der Zufallszahlen liefert. Der Konstruktor soll dazu die maximale Zufallszahl entgegennehmen (exklusiv), die Methode next() liefert anschließend immer die Zufallszahl und hasNext() immer true. Da auch remove() von der Schnittstelle Iterator vorgeschrieben ist, müssen wir die Methode implementieren, lösen jedoch eine Ausnahme aus, da es nichts zu löschen gibt.

Listing 3.23: com/tutego/insel/util/RandomIterator.java

package com.tutego.insel.util;

import java.util.*;

/**
 * Iterator for pseudorandom numbers.
 */
public class RandomIterator implements Iterator<Integer>
{
  private final Random random = new Random();
  private final int bound;

  /**
   * Initializes this iterator with a maximum value (exclusive) for
   * pseudorandom numbers.
   * @param bound  Maximum (exclusive) pseudorandom
   */
  public RandomIterator( int bound )
  {
    this.bound = bound;
  }

  /**
   * Always true.
   * @return {@code true}.
   */
  @Override
  public boolean hasNext()
  {
    return true;
  }

  /**
   * Returns a pseudorandom, uniformly distributed {@code Integer} value
   * between 0 (inclusive) and the specified value (exclusive).
   * @return Next pseudorandom.
   */
  @Override
  public Integer next()
  {
    return random.nextInt( bound );
  }

  /**
   * Not supported.
   * @throws UnsupportedOperationException
   */
  @Override
  public void remove()
  {
    throw new UnsupportedOperationException();
  }
}

Ein Beispiel:

Listing 3.24: com/tutego/insel/util/RandomIteratorDemo.java, main()

Iterator<Integer> random = new RandomIterator( 6 );
int dice1 = random.next();
int dice2 = random.next();
System.out.println( dice1 );
System.out.println( dice2 );

Als Übung kann jeder den Iterator so verändern, dass auch ein Startwert definiert werden kann (jetzt ist er 0).

3.8.4 Iteratoren von Sammlungen, das erweiterte for und Iterable

Jede Collection wie ArrayList oder HashSet liefert mit iterator() einen Iterator.

interface java.util.Collection<E>
extends Iterable<E>

• Iterator<E> iterator()
  Liefert den Iterator der Datenstruktur.

Collection erweitert eine Schnittstelle Iterable, die unter Java 5 eingeführt wurde; sie schreibt die Methode vor, die einen Iterator liefert.

interface java.util.Iterable<T>

• Iterator<T> iterator()
  Liefert den Iterator für eine Sammlung.

Der typisierte Iterator

Von einer typisierten Collection liefert iterator() ebenfalls einen typisierten Iterator. Das heißt, die Datenstruktur überträgt den generischen Typ auf den Iterator. Nehmen wir eine mit String typisierte Sammlung an:

Collection<String> c = new LinkedList<String>();

Ein Aufruf von c.iterator() liefert nun Iterator<String>, und beim Durchlaufen über den Iterator kann die explizite Typanpassung beim next() entfallen:

for ( Iterator<String> i = c.iterator(); i.hasNext(); )
{
  String s = i.next();
  ...
}

Iterator und erweitertes for

Stößt der Compiler auf ein erweitertes for, und erkennt er rechts vom Doppelpunkt den Typ Iterable, so erzeugt er Bytecode für eine Schleife, die den Iterator und seine bekannten Methoden hasNext() und next() nutzt. Nehmen wir eine statische Methode totalStringLength(List) an, die ermitteln soll, wie viele Zeichen alle Strings zusammen besitzen. Aus

static int totalStringLength( List<String> strings )
{
  int result = 0;

  for ( String s : strings )
    result += s.length();

  return result;
}

erzeugt der Compiler selbstständig:

static int totalStringLength( List<String> strings )
{
  int result = 0;

  for ( Iterator<String> iter = strings.iterator(); iter.hasNext(); )
    result += iter.next().length();

  return result;
}

Da die erweiterte Schleife das Ablaufen einer Datenstruktur vereinfacht, wird ein explizit ausprogrammierter Iterator selten benötigt. Doch der Iterator kann ein Element über die remove()-Methode des Iterators löschen, was über das erweiterte for nicht möglich ist.

Einen eigenen Iterator und Iterable-Implementierung

Die Konzepte Iterator und Iterable müssen sauber getrennt werden: ein Iterator ist das Objekt, das durch eine Datensammlung läuft, während ein Iterable das Objekt ist, das einen anderen Iterator liefert. Eine Klasse kann beide Schnittstellen implementieren, doch oft kommt das nicht vor. Für unser nächstes Beispiel ergibt das aber Sinn – es nutzt einem Iterator, der durch eine Sammlung läuft und immer dann, wenn er an das Ende kommt, wieder von vorne beginnt. Zunächst der Einsatz:

Listing 3.25: com/tutego/insel/util/RotatingIteratorDemo.java, main

int i = 0;
for ( String s : new RotatingIterator<String>( "Bohnen", "Eintopf" ) )
{
  System.out.println( "Toll, heute gibt es " + s );
  if ( i++ == 7 )
    break;
}

Zur Implementierung:

Listing 3.26: com/tutego/insel/util/RotatingIterator.java

package com.tutego.insel.util;

import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * An {@link Iterator} that goes over a given {@link Collection}
 * but rolls back to the start when it reaches the end.
 * If the underling {@link Collection} contains no elements the method
 * {@link #hasNext()} will return {@code false}. Removing elements is
 * supported if the Iterator of the underlying Collection
 * supports {@link Iterator#remove()}. Iterating over the underling
 * Collection and modifying it at the same time will probably result in a
 * {@link ConcurrentModificationException}.
 */
public class RotatingIterator<E> implements Iterator<E>, Iterable<E>
{
  private final Collection<? extends E> collection;
  private Iterator<? extends E>         iterator;

  public RotatingIterator( Collection<? extends E> collection )
  {
    if ( collection == null )
      throw new IllegalArgumentException( "Collection darf nicht null sein" );

    this.collection = collection;
    iterator = collection.iterator();
  }

  public RotatingIterator( E... elements )
  {
    this( Arrays.asList( elements ) );
  }

  @Override
  public boolean hasNext()
  {
    return ! collection.isEmpty();
  }

  @Override
  public E next()
  {
    if ( ! hasNext() )
      throw new NoSuchElementException( "Keine Elemente in der Collection" );

    if ( ! iterator.hasNext() )
      iterator = collection.iterator();

    return iterator.next();
  }

  @Override
  public void remove()
  {
    iterator.remove();
  }

  @Override
  public Iterator<E> iterator()
  {
    return this;
  }
}

3.8.5 Fail-Fast-Iterator und die ConcurrentModificationException

Beackern zwei Programmstellen gleichzeitig eine Datenstruktur, so kann es zu Schwierigkeiten kommen, wenn sich die Datenstruktur strukturell verändert, also neue Elemente hinzukommen oder wegfallen. Probleme treten leicht auf, wenn ein Verweis auf die Datenstruktur im Programm an verschiedenen Stellen weitergegeben wird. Führt nun eine Stelle strukturelle Änderungen mit Methoden wie remove() oder add() durch und verändert sich damit die Größe der Liste, dann kann das zu Zugriffsfehlern führen, wenn die andere Stelle von der Änderung nichts mitbekommt.

Nehmen wir an, zwei Programmteile greifen auf eine gemeinsame Liste zurück. Ein Programmteil merkt sich eine Suchstelle und will anschließend auf das gefundene Element zurückgreifen. Zwischen diesen beiden Operationen verändert jedoch ein anderer Programmteil die Liste, und die Position des Elements verschiebt sich:

Listing 3.27: com/tutego/insel/util/ConcurrentModification.java, main()

List<String> list = new ArrayList<String>( Arrays.asList( "Trullo", "Zippus" ) );
int posOfZippus = list.indexOf( "Zippus" );
System.out.println( list.get( posOfZippus ) );  // Zippus
list.add( 0, "Apulien" );
System.out.println( list.get( posOfZippus ) );  // Trullo

Nach dem Einfügen von "Apulien" ist posOfZippus also veraltet. Es wäre eine Hilfe, wenn get() die strukturelle Veränderung bemerken würde.

Beim Erfragen über Listen-Iteratoren ist das anders. Die Entwickler der Java-Bibliothek haben einen Entwurf gewählt, bei dem konfliktträchtige Änderungen über die Listen-Iteratoren auffallen und zu einer ConcurrentModificationException führen.

Listing 3.28: com/tutego/insel/util/ConcurrentModificationExceptionDemo.java, main()

List<String> list = new ArrayList<String>( Arrays.asList( "Stunden", "der" ) );
Iterator<String> iterator = list.iterator();  // modCount = 0, expectedModCount = 0
list.get( 0 );                                // Anfragen ändert modCount nicht
list.add( "Entspannung" );                    // modCount = 1, expectedModCount = 0
iterator.next();                              // modCount != expectedModCount => CME

Das funktioniert so, dass sich die Liste die Anzahl struktureller Änderungen merkt – bei der Standardimplementierung vom JDK intern in der Variablen modCount. Der Iterator registriert also die Änderungen, da sich der modCount in der Zwischenzeit durch das add() verändert hat. Wird der Iterator initialisiert, erfragt er den modCount der Liste und speichert den Wert in expectedModCount. Jede strukturelle Änderung in der Liste führt zum Inkrement vom modCount. Wird später eine Operation über den Iterator durchgeführt, testet er, ob der gemerkte expectedModCount mit dem aktuellen modCount übereinstimmt. In unserem Fall tut er das nicht, denn add() ist eine strukturelle Änderung und modCount wird 1. Beim nachfolgenden next() kommt es zu einer ConcurrentModificationException.

CurrentModificationException vermeiden

Die CurrentModificationException lässt sich in der Regel durch Umbau des Programmcodes vermeiden. Rekapitulieren wir, woher die Ausnahme eigentlich kommt: Sie kommt vom parallelen Verändern, also dem Einfügen oder Löschen der Datenstruktur, während ein Lesedurchlauf über den Iterator stattfindet. Die Lösung besteht darin, die Veränderungen über den Iterator vorzunehmen, denn dieser besitzt Einfüge-/Löschoperationen. Der Standard-Iterator bietet nur remove(), doch der ListIterator bietet auch eine set() bzw. add()-Methode.

Beispiel: Die folgenden Zeilen sollen eine Datenstruktur result ablaufen und alle Personen rausschmeißen, die verrückt sind. Lösung eins führt zur CurrentModificationException:

for ( Person p : result )
  if ( p.isWired() )
    result.remove( p );    //   CurrentModificationException

Übertragen wir das Löschen dem Iterator, funktioniert es:

for ( Iterator<Person> iterator = result.iterator(); iterator.hasNext(); )
  if ( iterator.next().isWired() )
    iterator.remove();

3.8.6 Die Schnittstelle Enumerator *

Für Iteratoren deklariert die Java-Bibliothek zwei unterschiedliche Schnittstellen. Das hat historische Gründe: Die Schnittstelle Enumeration[25](Nicht Enumerable!) gibt es seit den ersten Java-Tagen; die Schnittstelle Iterator gibt es seit Java 1.2, seit der Collection-API. Der Typ Iterator ist jedoch deutlich weiter verbreitet. Die Namen der Operationen unterscheiden sich in den Schnittstellen ein wenig und sind beim neuen Iterator kürzer.

interface java.util.Enumeration<E>

• boolean hasMoreElements()
  Testet, ob ein weiteres Element aufgezählt werden kann.
• E nextElement()
  Liefert das nächste Element der Enumeration zurück. Diese Methode kann später eine NoSuchElementException (eine RuntimeException) auslösen, wenn nextElement() aufgerufen und das Ergebnis false beim Aufruf von hasMoreElements() ignoriert wird.

Wie auch Iterable erweitert Enumeration keine weitere Schnittstelle.

Konvertieren von Enumeration, Iterator, Iterable *

Es gibt keine direkte Methode, die eine Enumeration in einen Iterator oder einen Iterator in eine Enumeration konvertiert. Nur über Umwege lässt sich das erreichen. Es helfen dabei zwei Methoden in der Utility-Klasse Collections:

class java.util.Collections

• static <T> Enumeration<T> enumeration(Collection<T> c)
• static <T> ArrayList<T> list(Enumeration<T> e)

Die Methode enumeration() liefert zu einer Collection eine Aufzählung vom Typ Enumeration. (Für einen gewünschten Iterator ist keine Hilfsmethode nötig, da jede Collection die Methode iterator() besitzt.) Ist eine Collection gegeben, so bleibt nichts anderes übrig, als eine temporäre Datenstruktur aufzubauen, Element für Element den Iterator abzulaufen und diese Elemente in die temporäre Datenstruktur zu setzen, die dann Argument der Methode enumeration() wird.

Der zweite Fall ist einfacher. Ist eine Enumeration gegeben, liefert list() eine ArrayList – der Rückgabetyp ist wirklich sehr erstaunlich, da er ungewöhnlich konkret ist. Die ArrayList ist eine Collection und somit Iterable, kann also rechts vom Doppelpunkt beim erweiterten for stehen bzw. liefert mit iterator() einen Iterator.

Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.