1 astrazioni sui dati : specifica ed implementazione di tipi di dato astratti in java
TRANSCRIPT
![Page 1: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/1.jpg)
1
Astrazioni sui dati :Specifica ed Implementazione di Tipi di Dato Astratti in Java
![Page 2: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/2.jpg)
2
Sommario
cos’è un tipo di dato astratto astrazione tramite specifica:
1. specifica
2. implementazione
3. relazione tra specifica ed implementazione (nel seguito)
![Page 3: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/3.jpg)
3
Perché l’astrazione sui dati
il più importante tipo di astrazione il nucleo della programmazione orientata ad oggetti lo scopo è quello di estendere il linguaggio
– nel nostro caso, Java
con nuovi tipi di dato (oltre a quelli primitivi int, String…)
quali, dipende dall’applicazione• interprete: stacks e tabelle di simboli (frame, ambiente dei
metodi)• applicazione bancaria: conti• applicazioni numeriche: matrici
![Page 4: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/4.jpg)
4
Cos’è un tipo di dato astratto
in ogni caso è– un insieme di dati
• stacks, conti, matrici– un insieme di operazioni
• per crearli e manipolarli
Cosa sta nella specifica?
• La descrizione astratta dei dati• La descrizione delle relative operazioni
![Page 5: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/5.jpg)
5
Implementazione
Cosa sta nell’ implementazione?
• La rappresentazione (o implementazione) dei dati
• L’implementazione delle relative operazioni
![Page 6: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/6.jpg)
6
Astrazione tramite specifica con la specifica vogliamo astrarre
dall’implementazione del tipo di dato– l’utente deve operare sul tipo di dato
indipendendentemente dalla sua rappresentazione (non la deve vedere)
Le modifiche della rappresentazione non devono modifiche dei moduli che usano il tipo di dato
![Page 7: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/7.jpg)
7
Come procediamo?
Prima definiamo la specifica del tipo di dato astratto– interfaccia pubblica per l’utente
Poi la implementiamo– puo’ al solito essere fatto in un momento successivo, in
modo indipendente dai moduli che usano il tipo di dato
![Page 8: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/8.jpg)
8
La specifica di un tipo di dato astratto Java (parte sintattica della specifica)
– classe o interfaccia• per ora solo classi
– nome per il tipo • nome della classe
– operazioni• metodi di istanza• incluso il(i) costruttore(i)
la specifica del tipo descrive proprietà generali degli oggetti– per esempio la modicabilità
per il resto la specifica è essenzialmente una specifica dei metodi– strutturata come già abbiamo visto per le astrazioni procedurali– l’oggetto su cui i metodi operano è indicato nella specifica da this
![Page 9: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/9.jpg)
9
Formato della specificapublic class NuovoTipo { // OVERVIEW: Gli oggetti di tipo NuovoTipo // sono collezioni modificabili di ..
// costruttori public NuovoTipo ()
// EFFECTS: ...
// metodi // specifiche degli altri metodi}
![Page 10: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/10.jpg)
10
L’insieme di interi 1public class IntSet { // OVERVIEW: un IntSet è un insieme modificabile // di interi di dimensione qualunque // 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 ...}
![Page 11: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/11.jpg)
11
L’insieme di interi 2public 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}
![Page 12: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/12.jpg)
12
IntSet: commenti 1public class IntSet { // OVERVIEW: un IntSet è un insieme modificabile // di interi di dimensione qualunque ....}
descrizione astratta dei dati gli oggetti della classe sono descritti nella specifica in
termini di concetti noti– in questo caso, gli insiemi matematici
gli stessi concetti sono anche utilizzati nella specifica dei metodi
![Page 13: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/13.jpg)
13
IntSet: commenti 2public class IntSet { // OVERVIEW: ... // costruttore public IntSet ()
// EFFECTS: inizializza this a vuoto...}
un solo costruttore (senza parametri)– inizializza this (l’oggetto nuovo)– non è possibile vedere lo stato dell’oggetto tra la creazione e
l’inizializzazione• la specifica non ha una clausola MODIFIES
![Page 14: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/14.jpg)
14
IntSet: commenti 3public class IntSet {... // 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
...} modificatori
– modificano lo stato del proprio oggetto (MODIFIES: this)– notare che nè insert nè remove sollevano eccezioni
• se si inserisce un elemento che c’è già• se si rimuove un elemento che non c’è
![Page 15: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/15.jpg)
15
IntSet: commenti 4
public boolean isIn (int x) // EFFECTS: se x appartiene a this ritorna
// true, altrimenti false 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...} osservatori
– non modificano lo stato del proprio oggetto – choose può sollevare un’eccezione (se l’insieme è vuoto)
• EmptyException può essere unchecked, perché l’utente può utilizzare size per evitare di farla sollevare
![Page 16: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/16.jpg)
16
Astrazione tramite specifica
• La specifica contiene tutte e sole le informazioni per utilizzare il tipo di dato in altri moduli
• Possiamo (dobbiamo) scrivere codice che crea oggetti di tipo Intset e li modifica tramite metodi e costruttori guardando solo la specifica
![Page 17: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/17.jpg)
17
Esempio di un metodo che usa IntSetpublic static IntSet getElements (int[] a) throws NullPointerException // EFFECTS:se a=null solleva NullPointerException// altrimenti, restituisce un insieme che
//contiene tutti e soli gli interi di a
{IntSet s = new IntSet(); for (int i = 0; i < a.length; i++)
s.insert(a[i]); return s;}
scritta solo conoscendo la specifica di IntSet
![Page 18: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/18.jpg)
18
Notate che
– non accede all’implementazione • non esiste ancora• anche se ci fosse non potrebbe “vederla”
– costruisce, accede e modifica l’oggetto solo attraverso i metodi (incluso il costruttore)
![Page 19: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/19.jpg)
19
Specifica di un tipo “primitivo”
le specifiche sono ovviamente utili per capire ed utilizzare correttamente i tipi di dato “primitivi” di Java
vedremo, come esempio, il caso dei vettori– Vector
– arrays dinamici che possono cambiare dimensione
– contengono Object (per il principio di sostituzione possiamo memorizzarci qualsiasi sottotipo di Object)
![Page 20: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/20.jpg)
20
Vector 1public class Vector { // OVERVIEW: un Vector è un array modificabile // di dimensione variabile i cui elementi sono // di tipo Object: indici tra 0 e size - 1 // costruttore public Vector ()
// EFFECTS: inizializza this a vuoto // metodi public void add (Object x)
// MODIFIES: this // EFFECTS: aggiunge una nuova posizione a
// this inserendovi x public int size ()
// EFFECTS: ritorna il numero di elementi di // this ...}
![Page 21: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/21.jpg)
21
Vector 2... public Object get (int n) throws
IndexOutOfBoundsException // EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti // ritorna l’oggetto in posizione n in this public void set (int n, Object x) throws
IndexOutOfBoundsException // MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva // IndexOutOfBoundsException, altrimenti // modifica this sostituendovi l’oggetto x in // posizione n}
![Page 22: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/22.jpg)
22
Vector 3...public void remove (int n) throws
IndexOutOfBoundsException // MODIFIES: this // EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti // modifica this eliminando l’oggetto in // posizione n
public void insert (Object o, int n) throws IndexOutOfBoundsException // MODIFIES: this // EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti // modifica this inserendo o nella posizione n
}
![Page 23: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/23.jpg)
23
Vector: commenti 1public class Vector { // OVERVIEW: un Vector è un array modificabile // di dimensione variabile i cui elementi sono // di tipo Object: indici tra 0 e size - 1 ....} gli oggetti della classe sono descritti nella specifica in
termini di concetti noti– in questo caso, gli arrays
gli stessi concetti sono anche utilizzati nella specifica dei metodi– indice, elemento identificato dall’indice
il tipo è modificabile (come l’array) notare che gli elementi sono di tipo Object
![Page 24: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/24.jpg)
24
Vector: commenti 2public class Vector { // OVERVIEW: un Vector è un array modificabile // di dimensione variabile i cui elementi sono // di tipo Object: indici tra 0 e size - 1 // costruttore public Vector ()
// EFFECTS: inizializza this a vuoto...}
un solo costruttore (senza parametri)– inizializza this (l’oggetto nuovo) ad un “array” vuoto
![Page 25: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/25.jpg)
25
Vector: commenti 3public void add (Object x)
// MODIFIES: this // EFFECTS: aggiunge una nuova posizione a
// this inserendovi xpublic void set (int n, Object x) throws
IndexOutOfBoundsException // MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva // IndexOutOfBoundsException, altrimenti modifica // this sostituendovi l’oggetto x in posizione n
sono modificatori– modificano lo stato del proprio oggetto (MODIFIES: this)– set e remove possono sollevare un’eccezione primitiva
unchecked
![Page 26: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/26.jpg)
26
Vector: commenti 3public void remove (int n) throws IndexOutOfBoundsException
// MODIFIES: this // EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti modifica // this eliminando l’oggetto in posizione n
public void insert (Object o, int n) throws IndexOutOfBoundsException // MODIFIES: this // EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti // modifica this inserendo o nella posizione n
sono modificatori In entrambi i casi vengono shiftati gli elementi che occorrono dopo la
posizione n, in indietro o avanti
![Page 27: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/27.jpg)
27
Vector: commenti 4public int size ()
// EFFECTS: ritorna il numero di elementi di // thispublic Object get (int n) throws
IndexOutOfBoundsException // EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti // ritorna l’oggetto in posizione n in thispublic Object lastElement ()
// EFFECTS: ritorna l’ultimo oggetto in this sono osservatori
– non modificano lo stato del proprio oggetto – get può sollevare un’eccezione primitiva unchecked
![Page 28: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/28.jpg)
28
Specifica di un tipo “primitivo”
– La specifica e’ di fatto la descrizione che troviamo nel manuale (a parte il formato dei commenti)
– Quando usiamo il tipo di dato primitivo non sappiamo come e’ realizzato, ovvero come e’ implementato il Vector e come sono realizzate le operazioni relative
– Lo stesso meccanismo di astrazione tramite specifica deve valere per i tipi di dato astratti che definiamo
![Page 29: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/29.jpg)
29
Implementazione
scelta fondamentale è quella della rappresentazione (rep)– come i valori del tipo astratto sono
implementati in termini di altri tipi• tipi primitivi o già implementati• nuovi tipi astratti che facilitano l’implementazione
del nostro
segue l’implementazione dei costruttori e dei metodi (più eventuali altri metodi ausiliari privati)
![Page 30: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/30.jpg)
30
La rappresentazione
in Java, gli oggetti del nuovo tipo sono semplicemente collezioni di valori di altri tipi– definite da un insieme di variabili di istanza
private• accessibili solo dai costruttori e dai metodi della
classe
• questo e’ necessario per evitare l’accesso diretto alla rappresentazione dell’oggetto da parte degli utenti
![Page 31: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/31.jpg)
31
Implementazione di IntSet 1
public class IntSet { // OVERVIEW: un IntSet è un insieme modificabile // di interi di dimensione qualunque private Vector els; // la rappresentazione // costruttore public IntSet ()
// EFFECTS: inizializza this a vuoto {els = new Vector();}...} un insieme di interi è rappresentato da un Vector
– più adatto dell’Array, perché l’insieme ha dimensione variabile gli elementi di un Vector sono di tipo Object
– non possiamo memorizzarci valori di tipo int– usiamo oggetti di tipo Integer
![Page 32: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/32.jpg)
32
Implementazione di IntSet 2
public void insert (int x) // MODIFIES: this // EFFECTS: aggiunge x a this
{Integer y = new Integer(x); if (getIndex(y) < 0) els.add(y); }
Inseriamo l’elemento solo se non occorre gia’ nell’insieme Vogliamo che non ci siano occorrenze multiple di elementi
– implementazione piu’ efficiente (vedi remove e size) A tale fine si utilizza un metodo ausiliario getIndex , che ritorna -1 se
l’elemento non occorre
![Page 33: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/33.jpg)
33
Implementazione di IntSet 2
private int getIndex (Integer x) // EFFECTS: se x occorre in this //ritorna la posizione in cui si trova, //altrimenti -1
{for (int i = 0; i < els.size(); i++) if (x.equals(els.get(i))) return i; return -1; }
il metodo privato ausiliario getIndex ritorna un valore speciale e non solleva eccezioni
non sta nella specifica (perché è privato) notare l’uso del metodo equals su Integer
![Page 34: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/34.jpg)
34
Implementazione di IntSet 3
public void remove (int x) // MODIFIES: this// EFFECTS: toglie x da this
{int i = getIndex(new Integer(x)); if (i < 0) return; els.set(i, els.lastElement()); els.remove(els.size() - 1);}
nella rimozione, se l’elemento c’è, ci scrivo sopra l’ultimo corrente ed elimino l’ultimo elemento
E’ corretto sse l’elemento occorre in una sola posizione del vettore………
![Page 35: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/35.jpg)
35
Implementazione di IntSet 3
public boolean isIn (int x) // EFFECTS: se x appartiene a this ritorna
// true, altrimenti false { return getIndex(new Integer(x)) >= 0; }
Usa il solito metodo ausiliario
![Page 36: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/36.jpg)
36
Implementazione di IntSet 4
public int size () // EFFECTS: ritorna la cardinalità di this {return els.size(); }
E’ corretto dato che non ci possono essere occorrenze multiple di elementi nel vettore
![Page 37: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/37.jpg)
37
Implementazione di IntSet 4
public int choose () throws EmptyException // EFFECTS: se this è vuoto, solleva // EmptyException, altrimenti ritorna un // elemento qualunque contenuto in this {if (els.size() == 0) throw new EmptyException(“IntSet.choose”); return ((Integer) els.lastElement()).intValue();
}
lastElement non puo’ sollevare eccezioni dato che si effettua un controllo che non sia vuoto
ritorna un Object (come tipo apparente), quindi per trasformarlo in int tramite intValue() bisogna fare il cast
![Page 38: 1 Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb4c497959361e8b9998/html5/thumbnails/38.jpg)
38
Sommario
Abbiamo realizzato tipi di dato astratto usando l’astrazione fornita dalla specifica
La specifica e l’implementazione stanno nella stessa classe la specifica funge da interfaccia con chi usa il tipo di dato,
puo’ anche essere compilata senza avere l’implementazione insieme ai moduli che la usano
Specifica ed implementazione sono di conseguenza legate da un concetto di correttezza (che vedremo)