Astrazione sul controllo:
gli iteratori
1
Perché vogliamo iterarare “in modo
astratto”
 problema: iterare su tipi di dato arbitrari
 esempio: procedura stand-alone per calcolare la
somma di tutti gli elementi di un IntSet
public static int setSum (IntSet s) throws
NullPointerException
// EFFECTS: se s è null solleva
// NullPointerException altrimenti
// ritorna la somma degli elementi di s
2
Problema
 Non vediamo la rappresentazione (p.e. quella realizzata dal
vettore els)
 Dobbiamo usare i metodi pubblici forniti dalla classe
IntSet (la specifica)
 Unico modo per accedere agli elementi: choose
3
L’insieme di interi 1
public class IntSet {
// costruttore
public IntSet ()
// EFFECTS: inizializza this a vuoto
// metodi
public void insert (int x)
// MODIFIES: this
// EFFECTS: aggiunge x a this
public void remove (int x)
// MODIFIES: this
// EFFECTS: toglie x da this
public boolean isIn (int x)
//EFFECTS: se x appartiene a this ritorna
// true, altrimenti false
4
...}
L’insieme di interi 2
public class IntSet {
...
// metodi
...
public int size ()
// EFFECTS: ritorna la cardinalità di this
public int choose () throws EmptyException
// EFFECTS: se this è vuoto, solleva
// EmptyException, altrimenti ritorna un
// elemento qualunque contenuto in this
}
5
Una soluzione
 Prendiamo un elemento a caso con il metodo
choose
 Lo rimuoviamo
 Ripetiamo fino a svuotare l’insieme
 La procedura non deve modificare
l’insieme (non e’ riportato in MODIFIES)
 Quindi ci vuole una struttura di supporto per
memorizzare gli elementi
6
Soluzione insoddisfacente 1
public static int setSum (IntSet s) throws
NullPointerException {
// EFFECTS: se s è null solleva
// NullPointerException altrimenti
// ritorna la somma degli elementi di s
int[ ] a = new int [s.size( )];
int sum = 0;
for (int i = 0; i < a.length; i++)
{a[i] = s.choose( );
sum = sum + a[i];
s.remove(a[i]); }
// risistema s
for (int i = 0; i < a.length; i++)
s.insert(a[i]);
return sum;}
 ad ogni iterazione vengono chiamate choose e remove
 gli elementi rimossi li mettiamo in un array, poi li reinseriamo
7
Soluzione Sbagliata
 Un modo di risolvere il problema (accedere
alla rappresentazione)
 Per esempio, in IntSet accedere agli
elementi memorizzati nel vettore els
(mettendo els pubblico)
 Da evitare: rompe l’astrazione rendendo
dipendenti gli altri moduli
dall’implementazione
8
Soluzione insoddisfacente 2
 Il tipo di dato astratto non e’ progettato bene (metodi
pubblici forniti sono limitati….)
 potremmo aggiungere setSum come metodo d’istanza
della classe IntSet
– in modo più efficiente
• accedendo la rappresentazione
– non è direttamente collegata al concetto di IntSet
– quante altre operazioni simili dovremmo mettere in IntSet?
• trovare il massimo elemento.....
 Meglio sarebbe modificare la specifica mettendo delle
operazioni che siano un po’piu’ generali
9
Cosa non fare
 dotiamo IntSet di una operazione che ritorna la
rappresentazione (metodo d’istanza)
public Vector members ()
// EFFECTS: restituisce il Vector contenente gli
// elementi di this
 Soluzione assolutamente sbagliata: rende accessibile la
rappresentazione (rompe l’astrazione)
 Il codice del metodo dipende dalla rappresentazione
 Non possiamo piu’ garantire le proprieta’ di IntSet (la
rappresentazione puo’ essere modificata dall’esterno)
10
Soluzione leggermente diversa
public int [ ] members ()
// EFFECTS: restituisce un array contenente gli
// elementi di this, ciascuno esattamente una volta,
// in un ordine arbitrario
public static int setSum (IntSet s) {
int[ ] a = s.members();
int sum = 0;
for (int i = 0; i < a.length; i++) sum = sum + a[i];
return sum;}
 inefficiente
– due strutture dati
11
Di cosa abbiamo bisogno?
 un meccanismo generale di iterazione, che
permette di iterare sugli elementi di IntSet
– facile da usare
– efficiente
– che preservi l’astrazione (ovvero che non riveli
a chi lo usa il modo in cui l’insieme e’
implementato)
12
Vorremmo un generatore
 un generatore g produce in modo incrementale (uno alla
volta) tutti gli elementi i della collezione corrispondente
all’oggetto
 Utilizzando un generatore e’ possibile realizzare
l’iterazione astratta:
per ogni i prodotto da g esegui a su i
 l’azione a da compiere sugli elementi è separata dalla
generazione degli elementi stessi
13
Generatori in Java
 i generatori sono oggetti di particolari classi
 sono sottotipi di una Interfaccia Iterator
– il tipo Iterator è definito dalla seguente
interfaccia Java (java.utilpackage)
14
Cos’e’ una Interfaccia
 una Interfaccia e’ un particolare tipo di
classe
 contiene solo la specifica
 non ha implementazione
 contiene solo metodi d’istanza (astratti)
 non ha costruttori
15
Cos’e’ una Interfaccia
 Non si possono creare oggetti
 L’implementazione e’ definita dai sottotipi,
che implementano i metodi ereditati
 serve per definire implementazioni multiple
di un tipo o per definire operazioni comuni
a vari tipi
16
Iterator (versione semplificata)
public interface Iterator {
//OVERVIEW: i sottotipi definiscono generatori
//metodi astratti
public boolean hasNext ( );
// EFFECTS: restituisce true se ci sono altri
// elementi da generare altrimenti false
public Object next throws NoSuchElementException;
// MODIFIES: this
// EFFECTS: se ci sono altri elementi da generare
//dà il successivo e modifica lo stato di this,
//altrimenti
//solleva NoSuchElementException (unchecked)}
}
17
Sottotipi di una interfaccia
 Si definiscono usando la parola chiave
implements (al posto di extends)
 Ereditano i metodi dall’interfaccia e li
implementano
 In questo modo si puo’ definire una famiglia
di sottotipi che hanno un’insieme di
operazioni comuni
18
Esempio
–un generatore su una data collezione si definisce
implementando l’interfaccia Iterator
–un generatore si crea, creando un oggetto
di quel tipo
–tutti i generatori hanno i metodi next ed
hasnext che si comportano nello stesso
modo (come dichiarato nella superclasse)
19
Cosa vedremo?
 Come si usa un generatore per realizzare
l’iterazione astratta su un tipo di dato
 Come si implementa l’interfaccia Iterator
20
Iterazione astratta
 Per utilizzare generatori per iterare in modo
astratto su una collezione, bisogna aggiungere un
metodo che ritorna un generatore nella specifica
 Metodi che ritornano un generatore, spesso
chiamati iteratori
– da non confondere con il tipo Iterator che
restituiscono
 possono essere anche procedure stand-alone
21
Metodo d’istanza per IntSet
public class IntSet {
// come prima più
public Iterator elements (){
// EFFECTS: ritorna un generatore che produrrà tutti
// gli elementi di this (come Integers) ciascuno una
// sola volta, in ordine arbitrario
// REQUIRES: this non deve essere modificato
// finché il generatore è in uso
}
 la clausola REQUIRES impone condizioni sul
codice che utilizza il generatore
– tipica degli iteratori su tipi di dato modificabili
22
Un iteratore stand-alone 1
public class Num {
// come prima più
public static Iterator primesLT100 () {
// EFFECTS: restituisce un generatore,
// che genera incrementalmente tutti i
// numeri primi (Integer) minori di 100}
}
23
Specifica di un iteratore stand alone
public class Num {
// come prima più
public static Iterator allPrimes ()
// EFFECTS: ritorna un generatore che produrrà tutti
// i numeri primi (come Integers) ciascuno una
// sola volta, in ordine arbitrario
}
 il limite al numero di iterazioni deve essere
imposto dall’esterno
– il generatore può produrre infiniti elementi
24
Come si usano?
 Il metodo iteratore ed il relativo generatore si usano
guardando la specifica, che descrive il modo in cui produce
gli lementi
public static Iterator primesLT100 ()
// EFFECTS: restituisce un generatore,
// che genera incrementalmente tutti i
// numeri primi (Integer) minori di 100
25
Iterazione astratta
 Sappiamo che restituisce Integer dalla specifica
// ciclo controllato da hasnext
Iterator g = Num.primesLT100 ();
while (g.hasNext())
{int i = ((Integer) g.next( )).intValue( );
// esegui a su i }
26
Alternativa
// ciclo controllato da
exception
Iterator g = Num.primesLT100();
try {while (true) {int i =
((Integer) g.next()).intValue();
// esegue a su i
}
catch (NoSuchElementException e) { };
27
Iterazione astratta per IntSet
public Iterator elements ()
// EFFECTS: ritorna un generatore che produrrà tutti
// gli elementi di this (come Integers) ciascuno una
// sola volta, in ordine arbitrario
// REQUIRES: this non deve essere modificato
// finché il generatore è in uso
}
Lo usiamo per realizzare la procedura stand-alone
public static int setSum (IntSet s) throws
NullPointerException
// EFFECTS: se s è null solleva
// NullPointerException altrimenti
// ritorna la somma degli elementi di s
28
Procedura stand-alone
public static int setSum (IntSet s) throws
NullPointerException {
Iterator g= s.elements();
int sum = 0; try{while(true)
{sum=sum +(Integer) g.next().intvalue();} }
catch (NoSuchElementException e)
{}}
Scritta guardando solo la specifica di IntSet
Realizza l’iterazione astratta (indipendente dalla
rappresentazione) usando il generatore
29
Iteratori
 Abbiamo visto la specifica e l’uso dei
metodi che ritornano un generatore
(sottotipo di Iterator)
 Questi metodi li abbiamo chiamati iteratori
 Come e dove si definiscono i relativi
generatori?
30
Implementazione degli iteratori e dei
generatori
 i generatori sono oggetti che hanno come tipo un
sottotipo di Iterator
– istanze di una classe g che “implementa” l’interfaccia
Iterator
 un iteratore a è un metodo (stand alone o
associato ad un tipo astratto) che ritorna il
generatore istanza di g
 Vogliamo che g acceda alla rappresentazione (deve
iterare) senza renderla visibile
31
Esempio
 Il generatore di IntSet deve produrre tutti gli
elementi dell’insieme
 Deve necessariamente poter accedere alla
rappresentazione, ovvero al vettore els
32
Quindi
 Il generatore g deve avere una visibilità limitata al
package che contiene l’iteratore a
– oppure può essere contenuta nella classe che contiene a
• come inner class privata
 in questo modo i generatori sono visti dall’esterno
come oggetti di tipo Iterator
– perché il sottotipo g non è visibile
33
Classi nidificate
 una classe g dichiarata all’interno di una classe a
può essere
– static (di proprietà della classe a)
– di istanza (di proprietà degli oggetti istanze di a)
 se g è static come sempre non può accedere
direttamente le variabili di istanza ed i metodi di
istanza di a
– le classi che definiscono i generatori si possono quasi
sempre definire come inner classes statiche
34
Esempio
 La classe che definisce il generatore di
IntSet la definiamo come inner class privata
 Vede la rappresentazione
 Non e’ visibile ai moduli esterni al package
35
Intset: iteratore
public class IntSet {
private Vector els;
public Iterator elements () {
// EFFECTS: ritorna un generatore che produrrà tutti
// gli elementi di this (come Integers) ciascuno una
// sola volta, in ordine arbitrario
// REQUIRES: this non deve essere modificato
// finché il generatore è in uso
return new IntSetGen(this);}
Ritorna un oggetto di tipo IntSetGen, sottotipo di Iterator,
a cui passa l’oggetto corrente
Il tipo IntSetGen e’ definito come inner class privata di IntSet
36
Intset:generatore 1
private static class IntSetGen implements Iterator {
private IntSet s; // l’insieme su cui si itera
private int next; // prossimo indice del vettore da considerare
Manca l’OVERVIEW: il generatore e’ descritto nel corrispondente
Iteratore (elements)
Le variabili d’istanza mantengono le informazioni per iterare,
l’insieme e l’indice del vettore a cui siamo arrivati
Nota che la classe e’ interna ad IntSet, ha visione
delle variabili private di IntSet (in particolare del Vector)
37
Intset:generatore 1
private IntSet s; // l’insieme su cui si itera
private int next; // prossimo indice del vettore da considerare
public IntSetGen (IntSet it) {
// REQUIRES: it != null
s = it; next=0; }
Costruttore procedura parziale, usata solo all’interno
della classe
Prende come parametro l’IntSet su cui operare
(vedi elements())
38
Intset:generatore 2
public boolean hasNext () {if (next>= s.els.size())
{return false;} else {return true;} }
public Object next () throws NoSuchElementException {
if (next >= s.els.size()) {
throw new NoSuchElementException(”IntSet.elements"); }
return s.els.get(next);
next=next+1;}
La specifica dei metodi e’ quella descritta nell’interfaccia
(e’ sempre la stessa)
39
Implementazione degli iteratori 3
public class Num {
public static Iterator allPrimes (){return new PrimesGen();}
// EFFECTS: ritorna un generatore che produrrà tutti
// i numeri primi (come Integers) ciascuno una
// sola volta, in ordine arbitrario
private static class PrimeGen implements Iterator {
// inner class (classe annidata)
private Vector ps; // primi già dati
private int p; // prossimo candidato alla generazione
PrimesGen () {p = 2; ps = new Vector(); }
public boolean hasNext () {return true }
public Object next () {
if (p == 2) { p = 3; return new Integer(2);}
for (int n = p; true; n = n + 2)
for (int i = 0; i < ps.size(); i++){
int e1 = ((Integer) ps.get(i)).intValue();
if (n%e1 == 0) break; // non è primo
if (e1*e1 > n)
{ps.add(new Integer(n); p = n + 2;
return new Integer(n);}}} }}
40
Classi nidificate e generatori
 le classi i cui oggetti sono generatori definiscono
comunque dei tipi astratti
– sottotipi di Iterator
 in quanto tali devono essere dotati di
– una funzione di astrazione
– un invariante di rappresentazione
Necessarie per ragionare sulla loro correttezza
41
Funzione di astrazione per i
generatori
 dobbiamo sapere cosa sono gli stati astratti
 per tutti i generatori, lo stato astratto è
– la sequenza di elementi che devono ancora essere
generati
– la funzione di astrazione mappa la rappresentazione su
tale sequenza
42
Funzione di Astrazione:
IntSetGen
private static class IntSetGen implements Iterator {
private IntSet s; // l’insieme su cui si itera
private int next; // prossimo indice del vettore da considerare
a(c) = [] se c.next>=c.s.els.size()
oppure
a(c) =[x_i, x_i+1, ... ,x_n] tale che
c.next= i ed n=c.s.els.size()-1
e per ogni i <= j <=n
x_j = c.els.get(j)
•notare che si usano le rep sia di IntSet che di IntSetGen
43
Invariante di rappresentazione
I(c) = c.s != null e
(0 <= c.next <=
c.s.els.size())
 Il next varia tra 0 e la lunghezza del vettore
44
Correttezza dell’iteratore
 Facciamo vedere che l’invariante di
IntSetGen vale
 Costruttore
 Metodi per induzione sui dati
45
Invariante
private static class IntSetGen implements Iterator {
private IntSet s; // l’insieme su cui si itera
private int next; // prossimo indice del vettore da considerare
IntSetGen (IntSet it) {
// REQUIRES: it != null
s = it; next=0; }
public boolean hasNext () {if (next > = s.els.size())
{return false;} else {return true;}}
I(c) = c.s != null e
(0 <= c.next <= c.s.els.size())
46
Invariante
private static class IntSetGen implements Iterator {
private IntSet s; // l’insieme su cui si itera
private int next; // prossimo indice del vettore da considerare
public Object next () throws NoSuchElementException {
if (next >= s.els.size()) {
throw new NoSuchElementException(”IntSet.elements"); }
return s.els.get(next);
next=next+1;}
I(c) = c.s != null e
(0 <= c.next <= c.s.els.size())
Vale: se c.next era = c.s.els.size() allora ha
sollevato l’eccezione
47
Correttezza del generatore
 Valgono le invarianti di Intset e di
IntSetGen
 E’ facile convincersi che i metodi next e
hasnext() soddisfano la specifica
48
Correttezza dell’iteratore
 il generatore soddisfa anche la specifica (quella richiesta in elements)
// EFFECTS: ritorna un generatore che produrrà tutti
// gli elementi di this (come Integers) ciascuno una
// sola volta, in ordine arbitrario
 Il generatore ritorna gli elementi del vettore che rappresenta l’insieme
 E’ corretto perche’: (1) non ci sono occorrenze multiple nel vettore; (2)
gli elementi del vettore sono Integer
 Queste proprieta’ sono garantite dall’invariante di IntSet
49
Conclusioni sugli iteratori
 in molti tipi di dato astratti (collezioni) gli iteratori sono un
componente essenziale
–
–
–
–
–
supportano l’astrazione via specifica
portano a programmi efficienti in tempo e spazio
sono facili da usare
non distruggono la collezione
ce ne possono essere più d’uno
 se il tipo di dato astratto è modificabile ci dovrebbe sempre
essere il vincolo sulla non modificabilità del dato durante
l’uso dell’iteratore
– altrimenti è molto difficile specificarne il comportamento previsto
– in alcuni casi può essere utile combinare generazioni e modifiche
50