Esercitazione
Problema
• Vogliamo definire in modo gerachico un tipo di dato che
definisce Tabelle multi-dimensionali con un numero di
righe variabili e numero di colonne fissato
• Il supertipo Tab definisce le caratteristiche ed operazioni
comuni
• I sottotipi aggiungono caratteristiche particolari delle
Tabelle, p.e. varie forme di ordinamento
Supertipo
• Il supertipo Tab definisce le caratteristiche ed operazioni
comuni
-tabelle multi-dimensionali di dimensione variabile (per il
numero di righe)
-operazioni per scandirle e modificarle
• E’ una classe astratta (dato che il numero di colonne e’
fissato si puo’ memorizzare in una variabile d’istanza)
Super Tipo
public abstract class Tab{
//OVERVIEW: un Tab e’ una tabella di interi con un numero
//fissato di colonne ed un numero variabile di righe. E’ modificabile
public Tab(int x){
\\ EFFECTS: inizializza this alla tabella vuota con x colonne}
public abstract void insert(int [] a) throws
NullPointerException, DimException;
\\MODIFIES:this
\\ EFFECTS: se a e’ null solleva NullPointerException,
\\se la dimensione di a e’ diversa dal numero di colonne di this
\\ solleva DimException, altrimenti aggiunge a come riga di this
public abstract void set(int i, int j, int el) throws DimException;
\\MODIFIES:this
\\ EFFECTS: se this contiene la casella i, j sostituisce il valore
\\corrente con el, altrmenti solleva DimException
Super Tipo
public abstract int rows();
\\ EFFECTS: restituisce il numero di righe di this
public int colums(){
\\ EFFECTS: restituisce il numero di colonne di this}
public abstract int read(int i, int j) throws DimException;
\\ EFFECTS: se this contiene la casella i, j restituisce il valore
\ corrente, altrimenti solleva l’eccezione DimException
Super Tipo
public Iterator elements(){
\\ EFFECTS: restituisce un generatore che fornisce gli elementi
\\ di this scandendo la tabella riga per riga}
Concreto===> si puo’ definire usando il metodo astratto read
Implementazione
• Per implementare la classe astratta (variabile
colums protected)
• Implementare il costruttore ed i metodi concreti
• Non c’e’ invariante ne’ funzione di astrazione
(tipico delle classi astratte)
Esercizio
• Definire un sottotipo concreto di Tab (OrdTab)
• Definisce un caso particolare di Tab, in cui le
righe della tabella sono ordinate in base alla prima
colonna (in modo crescente)
Ex :
148
321
725
Parte I
• Definire la specifica del sottotipo:
proprieta’ dati+ metodi
• La specifica puo’ cambiare (essere raffinata)
a patto che valga il principio di sostituzione
Parte II: implementazione
• Definire la rappresentazione del sottotipo
• Invariante e funzione di astrazione
Parte III
• Implementare costruttori e metodi
• Dimostrare che soddisfano l’invariante e le
loro specifiche
public abstract class Tab{
//OVERVIEW: un Tab e’ una tabella di interi con un numero
//fissato di colonne ed un numero variabile di righe. E’ modificabile
protected int colums;
public Tab(int x){
\\ EFFECTS: inizializza this alla tabella vuota con x colonne
colums=x;}
public abstract void insert(int [] a) throws
NullPointerException, DimException;
\\MODIFIES:this
\\ EFFECTS: se a e’ null solleva NullPointerException,
\\se la dimensione di a e’ diversa dal numero di colonne di this
\\ solleva DimException, altrimenti aggiunge a come riga di this
public abstract void set(int i, int j, int el) throws DimException;
\\MODIFIES:this
\\ EFFECTS: se this contiene la casella i, j sostituisce il valore
\\corrente con el, altrmenti solleva DimException
public abstract int rows();
\\ EFFECTS: restituisce il numero di righe di this
public int colums(){
\\ EFFECTS: restituisce il numero di colonne di this
return colums;}
public abstract int read(int i, int j) throws DimException;
\\ EFFECTS: se this contiene la casella i, j restituisce il valore corrente
public Iterator elements(){
\\ EFFECTS: restituisce un generatore che fornisce gli elementi
\\ di this scandendo la tabella riga per riga
return new TabGen(this);
}
private static class TabGen implements Iterator{
private Tab tabella; // tabella da scandire
private int rig; //riga corrente
private int col; // colonna corrente
public TabGen( Tab t){
\\REQUIRES: t non e’ null
tabella=t; col=1; rig=1;}
public boolean hasnext(){
if (rig <= tabella.rows() & & col <= tabella.colums())
{return true;} else {return false;} }
NOTA: se e’ vuota rows e colums sono 0
public Object next() throws NoSuchElementException{
try{
Integer el= new Integer( tabella.read(rig,col));
if (col=tabella.colums()) {rig++; col=1;}
else {col++;}
return el;}}
catch (DimException e)
{throw new NoSuchElementException(“Tab.next”);}
}
NOTA: si sfrutta l’eccezione lanciata dal metodo read
Specifica della Sottoclasse
public class OrdTab extends Tab{
//OVERVIEW: un Tab e’ una tabella di interi con un numero
//fissato di colonne ed un numero variabile di righe. Le righe
//sono mantenute ordinate in base al primo elemento
//E’ modificabile
public OrdTab(int x){
\\ EFFECTS: inizializza this alla tabella vuota con x colonne}
public void insert(int [] a) throws
NullPointerException, DimException{
\\MODIFIES:this
\\ EFFECTS: se a e’ null solleva NullPointerException,
\\se la dimensione di a e’ diversa dal numero di colonne di this
\\ solleva DimException, altrimenti aggiunge a come riga di this
\\ rispettando l’ordinamento}
public void set(int i, int j, int el) throws DimException{
\\MODIFIES:this
\\ EFFECTS: se this contiene la casella i, j sostituisce il valore
\\corrente con el, altrimenti solleva DimException}
public int rows(){
\\ EFFECTS: restituisce il numero di righe di this}
public int read(int i, int j) throws DimException{
\\ EFFECTS: se this contiene la casella i, j restituisce il valore
\\ corrente, altrimenti solleva Dimexception}
•Contiene solo costruttore e i metodi concreti (mancanti),
colums e elements sono ereditati
•Le specifiche sono raffinate per alcuni metodi (solo per l’inserimento)
Principio di sostituzione
• Le proprieta’ dei dati del sottotipo sono piu’
forti (una tabella ordinata e’ un tipo
particolare di tabella)
• Le specifiche di tutti i metodi sono uguali (
a parte insert)
• La post-condizione di insert del sottotipo
implica quella del supertipo (regola dei
metodi)
Implementazione
private Vector rap;
•Utilizziamo un Vector per memorizzare le righe le
righe (deve essere possibile aggiungere righe)
•rap.get(i) contiene un array di interi che rappresenta
la riga in posizione i
•La variabile colums della superclasse e’ ereditata e
visibile (protected), tipico delle classi astratte
Funzione di astrazione ed
Invariante
Alpha(c) = tabella che ha c.colums colonne e
c.rap.size() righe
e contiene nella casella i,j
c.rap.get(i-1)[j-1]
Funzione di astrazione ed
Invariante
I(c) = c.rap != null & &
per ogni 0 < = i,j < c.rap.size()
(c.rap.get(i) != null ed e’ un array di interi
&
c.rap.get(i).length==c.colums)
& (c.colums>=1 & i< j =====>
c.rap.get(i)[0] <= c.rap.get(j)[0] )
Implementazione
public class OrdTab extends Tab{
private Vector rap;
public OrdTab(int x){
\\ EFFECTS: inizializza this alla tabella vuota con x
colonne
super(x); rap=new Vector();}
•Chiama il costruttore della superclasse (potrebbe anche
modificare colums direttamente)
•Inizializza il Vector
public void insert(int [] a) throws
NullPointerException, DimException{
\\MODIFIES:this
\\ EFFECTS: se a e’ null solleva NullPointerException,
\\se la dimensione di a e’ diversa dal numero di colonne di this
\\ solleva DimException, altrimenti aggiunge a come riga di this
\\ rispettando l’ordinamento
if (a.length != colums) throw new DimException(“Tab.insert”);
if (colums ==0) {return;} else
{int i= 0; boolean inserito=false;
while (i < rap.size() & & ! inserito)
{ int [] riga= (int[] ) rap.get(i);
if (a[0] < = riga[0] ) {rap.insert(i,a); inserito=true;}
else {i++;}}
if (! inserito) {rap.add(a);}
}
public void set(int i, int j, int el) throws DimException{
\\MODIFIES:this
\\ EFFECTS: se this contiene la casella i, j sotituisce il valore
corrente con el ( e la riordina), altrimenti solleva DimException
if ( ! (1< = i < = rap.size() & & 1 <= j < = colums) )
throw new DimException(“Tab.set”);
if (j==1) {int[] riga= (int[] ) rap.get(i-1) ;
riga[0]=el; rap.remove(i-1); insert(riga);}
else
{int[] riga= (int[] ) rap.get(i-1) ; //i-esima riga
riga[j-1]=el;}
//j-esima colonna
}
public int rows(){
\\ EFFECTS: restituisce il numero di righe di this
return rap.size();}
public int read(int i, int j) throws DimException{
\\ EFFECTS: se this contiene la casella i, j restituisce il valore corrente
if (!( 1< = i < = rap.size() & & 1 <= j < = colums))
throw new DimException(“Tab.read”);
int[] riga= (int[] ) rap.get(i-1) ; //i-esima riga
returna riga[j-1];}
//j-esima colonna
Nota: l’invariante garantisce le proprieta’ del Vector, e garantisce che
non si acceda ad oggetti null