Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java Sommario cos’è un tipo di dato astratto



Scaricare 164.5 Kb.
10.12.2017
Dimensione del file164.5 Kb.


Astrazioni sui dati : Specifica ed Implementazione di Tipi di Dato Astratti in Java


Sommario

  • cos’è un tipo di dato astratto

  • astrazione tramite specifica:

  • specifica

  • implementazione

  • relazione tra specifica ed implementazione (nel seguito)



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


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


Implementazione

  • Cosa sta nell’ implementazione?

      • La rappresentazione (o implementazione) dei dati
      • L’implementazione delle relative operazioni


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



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


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


Formato della specifica

  • public class NuovoTipo {

  • // OVERVIEW: Gli oggetti di tipo NuovoTipo

  • // sono collezioni modificabili di ..

  • // costruttori

  • public NuovoTipo ()

  • // EFFECTS: ...

  • // metodi

  • // specifiche degli altri metodi

  • }



L’insieme di interi 1

  • public 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

  • ...}



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

  • }



IntSet: commenti 1

  • public 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



IntSet: commenti 2

  • public 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


IntSet: commenti 3

  • public 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’è


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)








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)


Vector 1

  • public 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

  • ...}



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}



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

  • }



Vector: commenti 1

  • public 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



Vector: commenti 2

  • public 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


Vector: commenti 3

  • public void add (Object x)

  • // MODIFIES: this

  • // EFFECTS: aggiunge una nuova posizione a

  • // this inserendovi x

  • 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

  • sono modificatori

    • modificano lo stato del proprio oggetto (MODIFIES: this)
    • set e remove possono sollevare un’eccezione primitiva unchecked


Vector: commenti 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

  • sono modificatori

  • In entrambi i casi vengono shiftati gli elementi che occorrono dopo la posizione n, in indietro o avanti



Vector: commenti 4

  • public int size ()

  • // EFFECTS: ritorna il numero di elementi di

  • // this

  • 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 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




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)



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


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


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



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



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………



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



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



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



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)





Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale