Accesso sequenziale alle collezioni
Tipica operazione su di una collezione:
Esaminare tutti gli elementi, uno alla volta.
Esempio: stampa, somma, ricerca, minimo, massimo, ...

Per un vettore (o array) si usa un for:
 


for (int i = 0; i < vect.size(); i++)

    System.out.println(vect.elementAt(i));
 

Infatti sappiamo come accedere ad ogni elemento di un array o vettore con un indice.

In generale, non sappiamo come accedere agli elementi di una collezione (ad es., liste concatenate, tabelle hash, alberi binari,...).

Si introduce il concetto di iteratore, generalizzando la scansione lineare di un vettore.

Iteratori
Nel Java Collections Framework, gli iteratori sono definiti dall'iterfaccia Iterator, [locale, Medialab, Sun], dichiarata nella Java Collections API (package java.util):
 
 
 
public interface Iterator {
    boolean hasNext();
    Object next();
    void remove();
}
\psfig{figure=LinkedList/FigureLista/interfacciaIterator.eps,width=6.0in}

La API fornisce una precisa specifica dei metodi:

  • hasNext restituisce true se esiste ancora un elemento della collezione da esaminare, false altrimenti;
  • next restituisce il prossimo elemento da esaminare, e lancia un'eccezione se questo non esiste;
  • remove cancella dalla collezione l'elemento restituito dall'ultima chiamata al metodo next, e può essere invocato una sola volta dopo ogni next. [Opzionale.]

Un'interpretazione grafica (1)
Una collezione (non facciamo assunzioni su ordine e ripetizioni dei suoi elementi)
Collection coll = new ...;
coll.add(...);
...		 Un iteratore per coll ottenuto con
Iterator it = coll.iterator()
it.next() restituisce C it.next() restitusce A; 
l'elemento C viene messo nel "sacchetto" per non essere più considerato
 

Un'interpretazione grafica (2)
it.next() restitusce B;
it.hasNext() restituisce true perché c'è almeno un elemento "fuori dal sacchetto"		 it.remove() cancella dalla collezione B, l'elemento nella finestra (l'ultimo visitato).
Un'altra invocazione di it.remove() ora causerebbe un'eccezione, perché la finestra è vuota.
it.next() restituisce D it.next() restitusce A;
ora it.hasNext() restituisce false perché non ci sono altri elementi da visitare.
 

Uso degli iteratori
Come si ottiene un iteratore su una data collezione?
Invocando il metodo:
public Iterator iterator()
E' dichiarato nell'interfaccia Collection [locale, Medialab, Sun], e quindi ogni classe che implementa questa interfaccia ne deve fornire una realizzazione.

Esempio: Calcolo della dimensione di una qualunque collezione
 

public static int size(Collection coll){
    int numElem = 0;
    for (Iterator itr = coll.iterator( ); 
             itr.hasNext( ); itr.next( ))
        numElem++;
    return numElem;
}

Si noti che l'esecuzione di next() nella guardia ha due effetti:

  • restituisce il prossimo elemento della collezione da esaminare, ma questo risultato non viene utilizzato;
  • come effetto collaterale, l'elemento restituito venga marcato come "esaminato''.

Modifiche concorrenti
L'iteratore restituito dal metodo iterator ci consente di scandire e/o cancellare i dati della collezione. E' possibile avere più iteratori sulla stessa collezione (con l'uso delle classi interne).

Cosa succede se durante la scansione la collezione viene modificata (da un altro iteratore o da altri metodi sulla collezione?

Esempio: Modifica concorrente con due iteratori:

Iterator it1 = vect.iterator();
1
4
3
 
 Iterator it2 = vect.iterator();
n = it1.next();
// n == 1
1
4
3
 
n = it1.next();
// n == 4
1
4
3
 		 m = it2.next();
// m == 1
b = it1.hasNext();
// b == true
1
4
3
 		 m = it2.next();
m = it2.next();
// m == 3
? Stato inconsistente
1
4
 		 it2.remove();

Se eseguiamo it1.next() deve essere lanciata una eccezione di tipo ConcurrentModificationException, perché la vera causa del fallimento è una modifica concorrente (non qualcosa come NoSuchElementException).
 

Ordine di scansione
In che ordine vengono esaminati gli elementi di una collezione con un iteratore?
Dipende da come sono realizzati i metodi dell'iteratore.
L'iteratore standard della classe Vector scandisce gli elementi dalla posizione 0 fino alla posizione size()-1.
Un esempio: vettori con scansione in ordine inverso.
  1. Definire la classe RevVectIterator che implementa Iterator, e realizza un iteratore che scandisce gli elementi di un vettore in ordine inverso a quello standard. Il Vector da esaminare viene passato al momento della creazione ed è memorizzato dal costruttore in una variabile d'istanza. 

    2. Soluzione: RevVectIterator
  2. Scrivere la classe RevVector che estende Vector e ridefinisce il solo metodo iterator, restituendo un oggetto di RevVectIterator. 

    3. Soluzione: RevVector
  3. Scrivere la classe PrintCollection che contiene il metodo statico
      4. public static printCollection(Collection coll);
    che stampa tutti gli elementi della collezione coll usando un iteratore. 
    Nel main costruire un oggetto di Vector ed uno di RevVector, riempiendoli con gli stessi elementi, e invocare printCollection su entrambi, per verificare l'ordine in cui vengono stampati gli elementi. 
    Soluzione: PrintCollection