Iteratori

Astrazioni sul controllo Nuove iterazioni •  Deﬁnendo un nuovo 4po come collezione di ogge8 (p. es., set) si vorrebbe disporre anche di un’operazione che consenta iterazioni •  Se la collezione è un Vector, un array o un ArrayList, è facile –  Organizzazione lineare degli elemen4 –  Con altri contenitori/collezioni? –  Informa4on hiding non consente (giustamente!) l’accesso direLo al rep di un contenitore! Iterare su collezioni •  Il for generalizzato non basta –  Fornisce una sola poli4ca di scansione –  Come fare a prevedere in an4cipo tu8 gli usi •  Soluzione ineﬃciente: avere un metodo che res4tuisce un array con tu8 gli elemen4 –  A volte però è u4le •  Soluzione ineﬃciente: deﬁnire size e get –  for (int i = 0; i < set.size(); i++) System.out.println(set.get(i)); –  con IntSet funzionerebbe bene, ma se poi si cambiasse implementazione? –  Su molte struLure da4 l’accesso casuale all’i-‐esimo elemento può essere molto ineﬃciente! Soluzione generale •  Introdurre ogge8 de8 iteratori in grado di “spostarsi” sugli elemen4 dei contenitori –  L’iteratore rappresenta un'astrazione del conceLo di “puntatore a un elemento del contenitore” e permeLe di scorrere il contenitore senza bisogno di conoscere l'eﬀe8vo 4po degli elemen4 –  Es. IntSet: oggeLo “iteratore su IntSet” con metodi: next(), per res4tuire il prossimo elemento della collezione, e hasNext() per veriﬁcare se siamo sull’ul4mo elemento public sta4c boolean insiemePosi4vo(IntSet set) { “genera Iteratore itr per set (posizionato al primo elemento)”; while (itr.hasNext()) if (itr.next() <0) return false; return true; } da Thinking in Java •  There’s not much you can do with the Java Iterator except: –  Ask a container to hand you an Iterator using a method called iterator() –  This Iterator will be ready to return the ﬁrst element in the sequence on your ﬁrst call to its next() method –  Get the next object in the sequence with next() –  See if there are any more objects in the sequence with hasNext() –  Remove the last element returned by the iterator with remove() Iteratori in Java •  Una collezione deve deﬁnire (almeno) un metodo che ritorna un oggeLo di 4po Iterator •  Alcuni nomi: iterator(), elements() e mol4 altri public Iterator<Integer> elements() boolean hasNext(); Integer next(); Interface Iterator •  In java.u4l public interface Iterator<E> { public boolean hasNext(); public E next() throws NoSuchElementExcep4on; public void remove(); // OPZIONALE } Interfaccia Iterable (1) •  Per standardizzare l’uso degli iteratori, in Java esiste anche l’interfaccia Iterable (in java.lang) •  Le classi che implementano l’interfaccia Iterable sono 4picamente collezioni che forniscono un metodo di nome standard iterator() per oLenere un oggeLo iteratore, con cui scandirne gli elemen4 Interfaccia Iterable (2) •  E’ necessario implementare Iterable se si vuole costruire una collezione da usare con for generalizzato –  Il prezzo della sempliﬁcazione lo paga l’implementatore, che deve codiﬁcare il metodo iterator() Iteratore per IntSet public static boolean stampa(IntSet set){
for (Iterator<Integer> itr = set.elements(); itr.hasNext();)
System.out.println(itr.next());
}
public static boolean insiemePositivo(IntSet set){
for (Iterator<Integer> itr = set.elements(); itr.hasNext();) if (itr.next()<0) return false;
return true;
}
•  Il metodo può essere deﬁnito solo in base all’iteratore! Iterare su collezioni qualunque •  È un’astrazione sul controllo molto potente: “the true power of the Iterator: the ability to separate the opera4on of traversing a sequence from the underlying structure of that sequence” public class Iterations {
public static void printAll(Iterator<E> itr){
while(itr.hasNext())
System.out.println(itr.next()); //NB: conv. automatica a String
} public static boolean cerca(Iterator<E> itr, <E> o){
while (itr.hasNext())
if (o.equals(itr.next())) return true;
return false;
}
}
Metodi iteratori per Poly e IntSet public class Poly { //come visto prima, e in più: public Iterator<Integer> terms() \result è un iteratore che res4tuisce gli esponen4 dei termini non zero di this public class IntSet { //come visto prima, e in più: public Iterator<Integer> elements() \result è un iteratore che res4tuisce i valori contenu4 in this, uno alla volta La classe per l’iteratore import java.util.Iterator;
import java.util.NoSuchElementException;
class PolyGen implements Iterator<Integer> {
private Poly p; // il Poly da iterare
private int n;
// primo elemento non “consumato”
//@ requires lui!=null; PolyGen(Poly lui) { p=lui; n = 0; }
public boolean hasNext(){
while(n <= p.deg) {
if(p.trms[n] != 0) return true;
else n++;
}
return false;
}
public Integer next() throws NoSuchElementException {
if(hasNext()) return n++; // restituisce il grado e passa al successivo
else throw new NoSuchElementException("Poly.terms");
}
}
Implementazione con classe interna public class Poly implements Iterable{
private int[] trms; private int deg; public Iterator<Integer> terms() {
return new PolyGen(this);
}
//classe interna
private static class PolyGen implements Iterator<Integer> {
…
//tutte le altre operazioni della classe
}
}
Iteratori "stand alone" •  Un iteratore potrebbe NON far parte di una classe, ma essere una procedura sta4ca “stand alone” •  Per esempio, iteratore allFibos che genera tu8 i numeri di Fibonacci –  o generatore di numeri primi •  Per questo mo4vo, serve deﬁnire la classe interna come sta4c: un metodo sta4c di una classe non può accedere a un costruLore di una classe interna non sta4c Esempio public class Nums {
public static Iterator<Integer> allFibos( ) {
return new FibosGen( );
}
//classe interna
private static class FibosGen implements Iterator<Integer> {
private int prev1, prev2; //i due ultimi generati
private int nextFib; //nuovo # Fibonacci generato
FibosGen() {prev2=1; prev1=0;}
public boolean hasNext() {return true;}
public Integer next() {
nextFib=prev1+prev2;
prev2=prev1; prev1=nextFib; return nextFib;
}
}
}
Uso dell’iteratore per Fibonacci public static void printFibos(int m) {
Iterator<Integer> g = Nums.allFibos();
while (g.hasNext()) {//sempre true…
int p = g.next();
if (p > m) return;
System.out.println("prox Fibonacci e` " + p);
}
}
Osservazioni •  “An iterator is an object whose job is to move through a sequence of objects and select each object in that sequence without the client programmer knowing or caring about the underlying structure of that sequence. In addi4on, an iterator is usually what’s called a “light-‐weight” object: one that’s cheap to create” •  Collezione può avere più 4pi di iteratori (e quindi più metodi per generarli) •  Esempio: una collezione potrebbe avere: public Iterator<T> smallToBig() {} public Iterator<T> bigToSmall() {} public Iterator<T> ﬁrst() {} Collezioni mutabili e metodo remove •  Remove è un’operazione “opzionale”: se non è implementata, quando invocata viene lanciata UnsupportedOpera4onExcep4on •  In eﬀe8, raramente è u4le modiﬁcare una collezione durante un’iterazione: più spesso si modiﬁca alla ﬁne (e.g., trovo elemento e lo elimino, poi iteratore non più usato) •  Seman4ca di remove() assicurata dal “contraLo” dell’interfaccia: –  elimina dalla collezione l’ul4mo elemento res4tuito da next(), a paLo che •  venga chiamata una sola volta per ogni chiamata di next() •  La collezione non venga modiﬁcata in qualsiasi altro modo (diverso dalla remove) durante l’iterazione –  altrimen4 •  Viene lanciata un’eccezione IllegalStateExcep4on se il metodo next() non è mai chiamato o se remove() già invocata dopo ul4ma chiamata di next() •  seman4ca della remove() non speciﬁcata se la collezione modiﬁcata in altro modo (diverso dalla remove) durante l’iterazione Sta4c Nested Classes •  As with class methods and variables, a sta4c nested class is associated with its outer class. And like sta4c class methods, a sta4c nested class cannot refer directly to instance variables or methods deﬁned in its enclosing class — it can use them only through an object reference. •  A sta4c nested class interacts with the instance members of its outer class (and other classes) just like any other top-‐level class. In eﬀect, a sta4c nested class is behaviorally a top-‐level class that has been nested in another top-‐level class for packaging convenience.

Download Report