Liste di Interi
Esercitazione
Liste Concatenate
• Tipo di dato utile per memorizzare sequenze di
elementi di dimensioni variabile
• Definizione tipicamente ricorsiva
Un nodo
val next
Lista non vuota:
Primo elemento
11
64
Lista vuota
Lista concatenata
• CASO BASE: la lista vuota
• CASO INDUTTIVO: e’un nodo che
contiene un valore (di tipo Integer in questo
caso) e un puntatore al resto della lista
• Nota: definizione ricorsiva
Un esempio
• Liste concatenate di Integers
• Non modificabile
• Costruttori per creare la lista vuota o un
nodo
• Metodi d’istanza: operazioni base (non si
accede direttamente a tutti gli elementi, ma
solo al primo)
Specifica di IntList
public class IntList {
OVERVIEW: un IntList è una lista non
modificabile di Integers.
Elemento tipico [x1,...,xn]
public IntList () {
EFFECTS: inizializza this alla lista vuota }
public IntList (Integer x) throws
NullPointerException {
EFFECTS: se x e’ null solleva
NullPointerException, altrimenti inizializza
this alla lista che contiene esattamente x }
Metodi Produttori
public IntList addEl (Integer x) throws
NullPointerException{
EFFECTS: se x e’ null solleva
NullPointerException, altrimenti restituisce la
lista ottenuta aggiungendo x all’inizio di this
}
public IntList removeEl (Integer x) throws
NullPointerException{
EFFECTS: se x e’ null solleva
NullPointerException, altrimenti restituisce la
lista ottenuta rimuovendo tutte le occorrenze
di x in this }
Metodi per accedere agli elementi
public Integer first () throws EmptyException{
EFFECTS: se this è vuoto solleva EmptyException,
altrimenti ritorna il primo elemento di this}
public IntList rest () throws EmptyException{
EFFECTS: se this è vuoto solleva EmptyException
altrimenti ritorna la lista ottenuta da this
togliendo il primo elemento}
Specifica di IntList
public int size () {
EFFECTS: ritorna il numero di elementi di this}
public Iterator elements () {
EFFECTS: ritorna un generatore che produrrà tutti
gli elementi di this (come Integers) nell’ordine
che hanno in this }
public
boolean repOk (){// EFFECTS:standard}
public String toString (){// EFFECTS: standard }
}
Come si implementa?
• Ci sono vari modi (a LSD altre soluzioni)
• Dobbiamo scegliere delle variabili d’istanza che
permettano di rappresentare sia la lista vuota che
quella non vuota (definizione ricorsiva pulita)
• Deve essere possibile distinguere i due casi in
modo chiaro
La rappresentazione
private boolean vuota;
//indica se e’ vuota
private Integer val;
//contiene il valore
private IntList next;
//puntatore al resto
Rappresentazione Lista
val
next
vuota
Lista vuota:
Lista non vuota:
any
any
154
24
any
any
true
false
false
true
Rappresentazione
public class IntList {
// OVERVIEW: un IntList è una lista non modificabile di I
// Elemento tipico [x1,...,xn]
private
private
private
private
boolean vuota;
Integer val;
IntList next;
int sz;
la variabile sz mantiene il numero di elementi
della lista, non e’ necessaria ma rende
l’implementazione piu’ efficiente
(va pero’ tenuta aggiornata)
Prima di implementare i metodi
• Invariante di rappresentazione: esprime le
proprieta’ della rappresentazione, il
significato delle variabili ed il legame tra I
loro valori
• Funzione di astrazione: spiega il modo
scelto per implementare la lista mettendo in
relazione gli oggetti concreti con quelli
astratti
Invariante (ricorsiva)
I(c) = c.vuota
e c.sz=0
oppure
(c.next != null e c.val !=null
e
I(c.next) e
c.sz= 1 + c.next.size() )
•O e’vuota (non c’e’ nessuna condizione)
•Oppure next e val devono essere definiti ed il valore di sz
deve essere uguale al numero di elementi del next +1
Funzione di astrazione
a(c) = se c.vuota allora [], altrimenti
a(c) = [c.val] + a(c.next)
Mappa gli oggetti concreti, implementati con una lista concatenata,
nella corrispondente lista, del tipo [x1,
..., xn]
La funzione di astrazione ricorsiva riflette il fatto che
l’ordinamento implementato e’ di fatto quello astratto, il primo
elemento e’ quello contenuto in val, poi seguono gli
elementi del next
Implementazione dei metodi
• Deve preservare l’invariante di
rappresentazione
• Allo stesso tempo sfruttando le proprieta’
garantite dall’invariante
• Facciamo in parallelo il ragionamento di
correttezza
• Il tipo di dato e’ non modificabile e
ricorsivo
Per ogni metodo:
• Assumendo che this e tutti i parametri del
tipo soddisfino l’invariante
• Che i valori di tipo IntList prodotti dagli
altri metodi soddisfino l’invariante
• Bisogna fare vedere che gli oggetti di tipo
IntList eventualmente prodotti soddisfano
l’invariante
Metodi ricorsivi
• si usa l’induzione sulla dimensione della
lista
• si fa vedere che la lista vuota prodotta dal
metodo soddisfa inv
• assumendo che l’inv. sia soddisfatta per le
liste di dimensione n, si fa vedere che vale
per quelle di dimensione n+1
Costruttori 1
public IntList () {
// EFFECTS: inizializza this alla lista vuota
vuota=true;sz=0;}
•
L’invariante e’ banalmente soddisfatta
(la lista e’ vuota e sz=0)
•Inoltre la specifica e’ soddisfatta (la lista rappresentata
da this e’ vuota tramite funzione astrazione)
Costruttori 2
public IntList (Integer x) throws NPE{
// EFFECTS: se x e’ null solleva NPE, altrimenti
//inizializza this alla lista che contiene esattamente x
if (x==null) throw new NullPointerException(“IntList”);
vuota=false; val=x; next=new IntList();sz=1;}
•L’invariante e’ soddisfatta (notate che sia val che next
devono essere non null)
•Inoltre la specifica e’ soddisfatta (la lista rappresentata
da this contiene esattamente un elemento)
a(c) =[c.val] +a(c.next)=[x]+[]=[x]
Costruttori
val
next
vuota
Lista vuota:
Lista con un elemento:
any
any
24
any
any
true
false
true
Inserimento
public IntList addEl (Integer x) throws NPE {
// EFFECTS: se x e’ null solleva NPE, altrimenti
aggiunge x all’inizio di this
if (x==null) throw new NPE(“addEl”)
IntList n = new IntList(x);
n.next = this;
n.sz = this.sz + 1; return n; }
Mettiamo l’elemento in testa, creando una lista che
contiene x e aggiorniamo sz
Correttezza
L’invariante e’ soddisfatta perche’:
il costruttore produce un oggetto che soddisfa
l’invariante
il next (this) soddisfa l’invariante
il valore di sz e’ soddisfatto
Corretto: a(c_pre) =L
a(c) =[c.val] +
a(c.next)=[x]+L
public IntList removeEl (Integer x) throws NPE{
//EFFECTS: se x e’ null solleva NPE, altrimenti
//restituisce la lista ottenuta rimuovendo tutte
//le occorrenze di x in this
if (x==null) throw new NPE(“removeEl”);
if (vuota) return new IntList();
IntList newnext=next.removeEl(x);
if (x.equals(val)) {return newnext;}
else
{IntList n = new IntList(val);
n.next =newnext;
n.sz = 1 + newnext.sz;
return n;}
}
Invariante
caso base: lista vuota (dalla correttezza del costruttore)
caso induttivo: assumendo che this soddisfi l’invariante e il
metodo removeEl (chiamato sul next) produca una lista che
soddisfa l’invariante, allora
removeEl su this soddisfa l’invariante
Correttezza
L’invariante e’ soddisfatta perche’:
caso base: lista vuota(ok)
caso induttivo: assumendo che il metodo removeEl
(chiamato sul next) sia corretto (rimuova le occorrenze di x
nel next)
removeEl su this rimuove tutte le occorrenze di x
First e rest
public Integer first () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException
altrimenti ritorna il primo elemento di this
if (vuota) throw new
EmptyException(“IntList.first”);
return val;}
public IntList rest () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException,
altrimenti ritorna la lista ottenuta da this
togliendo il primo elemento
if (vuota) throw new
EmptyException(“IntList.first”);
return next;}
Size
public int size () {
// EFFECTS: ritorna il numero di elementi di this
return sz;}
Corretto: l’invariante assicura che sz contenga proprio
il numero di elementi della lista
Piu’ efficiente: altrimenti dovrei usare un metodo ricorsivo
per calcolare il numero degli elementi (da fare per esercizio)
ToString()
public String toString (){
if (vuota) {return “”;}
return
val.intValue() + next.toString();}
Metodo Ricorsivo
Notate che l’invariante garantisce che next e value non siano null
quando vuota e’ falso
Altrimenti ci potrebbero essere delle eccezioni non previste nella
specifica
Iteratore
public Iterator elements () {
// EFFECTS: ritorna un generatore che produrrà tutti
gli elementi di this (come Integers) nell’ordine che
hanno in this
return new IntListGen(this); }
•Restituisce un generatore, istanza di un sottotipo di Iterator
•IntlistGen e’ una classe interna di IntList privata e statica
Generatore
• Dobbiamo generare tutti gli elementi della
lista dal primo all’ultimo
• Generatore: deve essere induttivo
• Se e’ vuota terminiamo subito
• Per iterare su l: prima generiamo l.val
• Poi, passiamo a considerare il next
public class IntList {
private static class IntListGen implements Iterator {
private IntList me; // nodo corrente
si noti l’uso di me per memorizzare la lista su cui iteriamo
Il nodo corrente deve essere aggiornato
Metodi
public IntListGen(IntList o) {
// REQUIRES: o != null
me=o;}
public boolean hasNext () {
if (me.vuota) {return false; }
return true;}
public Object next() throws NoSuchElementException{
if (me.vuota) throw
NoSuchElementException(“IntList.elements”);
Integer temp=me.val; me=me.next;
return temp;}
Importanza del generatore
• Dal punto di vista dei moduli che usano
IntList e’ fondamentale per realizzare
l’iterazione astratta
• Permette di accedere a tutti gli elementi
della lista senza sapere come e’
implementata
• Per esercizio: procedure statiche
Specifica
public class IntListProc {
// OVERVIEW: fornisce metodi statici per manipolare
//liste di stringhe
public static int min(IntList l) throws
EmptyException
{// REQUIRES: l non e’ null
//EFFECTS: se l e’ vuota solleva EmptyException,
altrimenti restituisce il minimo elemento di this}
public static IntList reverse (IntList l)
{// REQUIRES: l non e’ null
//EFFECTS: restituisce una lista che e’ l’inverso di this}
}
Metodi Statici
• Devono operare sul parametro di tipo
IntList tramite l’interfaccia pubblica
• Non hanno visibilita’ delle variabili
d’istanza val e next (i cui valori sono
accessibili tramite first e rest)
• Possono essere realizzati tramite il
generatore (piu’ facile) o in modo ricorsivo
usando first e rest per scorrere la lista
Reverse (senza iteratore)
public static IntList reverse(IntList l)
{// REQUIRES: l non e’ null
//EFFECTS: restituisce una lista che e’ l’inverso
if (l.size()==0) return new IntList();
else
{IntList next=reverse(l.rest());
return next.LaddEl(l.first());
}
}
Metodo min
• Si potrebbe fare ricorsivo tipo reverse (un
po’ complicato perche’ nel caso base lista
vuota viene sollevata una eccezione)
• Facciamolo invece con l’iteratore
elements(), e’ molto piu’ semplice
• L’unica cosa che ci serve per usare
l’iteratore e’ la specifica di elements
Metodo elements
• Per usare il generatore restituito da elements
basta guardare la specifica
• Il tipo particolare di Iterator restituito non
e’visibile
public Iterator elements () {
// EFFECTS: ritorna un generatore che produrrà
tutti
gli elementi di this (come Integers) nell’ordine
che
hanno in this
public static
int min(IntList l) throws
EmptyException{
if (l.size()==0) throw new EmptyException(“”);
int min=0;
Iterator g=l.elements();
while (g.hasNext())
{int el=(Integer) g.next().intValue();
if (el<min}{min=el;}
}
return min;
}
Dall’ultimo al primo
• E se dovessimo generare gli elementi in
ordine inverso dall’ultimo al primo?
• Dovremmo partire dall’ultimo nodo e
tornare indietro
• Come?
• Facile se ci sono anche i puntatori
all’indietro
• Farlo per esercizio (IntList prev)
Soluzione alternativa
• Usiamo un generatore su next per generare
tutti gli elementi successivi
• Quando sono finiti (next solleva
un’eccezione), generiamo val
• Bisogna memorizzare il sottogeneratore
(per mantenere il suo stato)
Generatore
private static class LGen{
private IntList io; // il nodo
private Lgen g; //generatore del next
private quanti; //quanti nodi mancano
DA FINIRE