Progettazione software, esercizi

Si definisca un modulo TDN per il tipo di dato astratto Memoria avente le seguenti operazioni:

Inserisci: inserisce in memoria un elemento di tipo intero restituendo un intero rappresentante la

posizione in dell’elemento in memoria. Qualora tutte le celle risultino occupate l’operazione non

può essere eseguita

Cancella: dato un valore rappresentante una posizione in memoria, ne cancella il contenuto. Qualora

non vi sia un elemento associato alla posizione, l’operazione non può essere eseguita

Libero: restituisce il numero di posizioni libere in memoria

Leggi: dato un valore rappresentante una posizione in memoria l’operazione restituisce l’elemento

memorizzato. Qualora non via sia tale elemento l’operazione non può essere effettuata

Reset: Cancella tutto il contenuto della memoria.

Esercizio 2

Si definisca un interfaccia Java per il modulo Memoria

Esercizio 3

Si realizzi una classe Java che implementa l’interfaccia Memoria

-1 TDN

Module MEMORIA<T>

exports

type

memoria = ?

procedure

insert(in e:T, out int pos, inout m: memoria)

raises memoriaPiena

pre: libero(m) > 0

post: libero(m) = libero(m’) -1 and leggi(pos,m) = e, and

occupato(pos,m)

cancella(in pos:int, inout m:memoria)

raises posInvalida, posVuota

pre: pos >= 0 and pos < max(m) and occupato(pos,m)

post: libero(m) = libero(m’) + 1 and not occupato(pos,m)

reset(inout m:memoria)

pre: true

post: libero(m) = max(m)

create(in size:int, out m:memoria)

raises wrongDim

pre: size > 0

post: libero(m) = max(m) and max(m) = size

function

libero(in m:memoria) : int

pre: true

leggi(in pos:int, in m:memoria) : T

raises posInvalida, posVuota

pre: pos >= 0 and pos < max(m) and occupato(pos,m)

max(in m:memoria) : int

pre: true

occupato(in pos: int, in m:memoria) : Boolean

raises posInvalida

pre: pos >= 0 and pos < max(m)

End MEMORIA

-2 INTERFACCIA

public interface memoria<T> {

int inserisci(T e) throws memoriaPiena;

void cancella(int pos) throws posInvalida, posVuota;

int libero();

T leggi(int pos) throws posInvalida, posVuota;

void reset();

int max();

boolean occupato(int pos) throws posInvalida;

}

-3 CLASSE

public class memoriaImpl<T> implements memoria<T> {

private Object[] mem;

private boolean[] libero;

private int size;

private int numLib;

private memoriaImpl(int s) throws wrongDim {

if (s < 1) throw new wrongDim();

size=s;

mem=new Object[size];

libero=new boolean[size];

numLib = size;

assert this.libero() == this.max() && this.max() == s;

}

public int inserisci(T e) throws memoriaPiena {

if(numLib == 0) throw new memoriaPiena();

int n = this.libero();

for (int i=0;i<size;i++)

if(libero[i]){

mem[i]=e;

libero[i]=false;

numLib--;

try {

assert this.libero() == n-1 && this.leggi(i) == e && this.occupato(i);

}

catch(posInvalida p) {;} //TMCH

catch(posVuota p) {;} //TMCH

return i;

}

return -1; //TMCH

}

public void cancella(int pos) throws posInvalida, posVuota {

if(pos<0 || pos>=size) throw new posInvalida();

if(libero[pos]) throw new posVuota();

int n = this.libero();

libero[pos]=true;

numLib++;

assert this.libero() == n+1 && !occupato(pos);

}

public void reset() {

for(int i=0;i<size;i++)

libero[i]=true;

numLib = size;

assert this.libero() == this.max();

}

public int libero() {

return numLib;

}

public T leggi(int pos) throws posInvalida, posVuota {

if(pos<0 || pos>=size) throw new posInvalida();

if(libero[pos]) throw new posVuota();

return ((T)mem[pos]);

}

public int max() {return size;}

public boolean occupato(int pos) throws posInvalida {

if(pos<0 || pos>=size) throw new posInvalida();

return !libero[pos];

}

}

public class posVuota extends Exception { }

public class posInvalida extends Exception { }

public class memoriaPiena extends Exception { }

public class wrongDim extends Exception { }

Parte 1

Si definisca un’interfaccia TDN per il tipo di dato astratto multi-insieme di interi avente le seguenti

funzionalità:

 Inserimento di un intero nel multi-insieme;

 Cancellazione di un intero di un dato valore dal multi-insieme;

 Cancellazione di tutti gli interi aventi un dato valore dal multi-insieme;

 Restituzione del numero di interi aventi un dato valore dal multi-insieme;

 Restituzione di una valore di verità indicante se un dato intero è presente all’interno del multi-

insieme.

module MULTIINSIEME

exports

type multiInsieme = ?

procedures

insert(in e:Int, inout m:multiInsieme) raises bagFull

pre: not full(m)

post: not empty(m) and howMany(e,m) = howMany(e,m’) + 1;

delete(in e:Int, inout m:multiInsieme)

raises bagEmpty, notFound

pre: not empty(m) and isin(e,m)

post: not full(m) and howMany(e,m) = howMany(e,m’) – 1

deleteAll(in e:Int, inout m:multiInsieme)

raises bagEmpty, notFound

pre: not empty(m) and isin(e,m)

post: not full(m) and howMany(e,m) = 0

create(out m:multiInsieme, in d:Int) raises dimErr

pre: dimErr > 0

post: empty(m);

functions

empty(in m:multiInsieme):boolean

pre: true

full(in m:multiInsieme):boolean

pre: true

isin(in e:Int, in m:multiInsieme):boolean

pre: true

howMany(in e:Int, in m:multiInsieme):Int

pre: true

invariant

true

end MULTIINSIEME

Parte 2 Si realizzi una interfaccia Java per l’interfaccia definita nell’Esercizio 1, che consenta la

1. serializzazione degli oggetti di tipo multiInsieme.

Si realizzi una classe Java che implementa l’interfaccia

2. Si estenda l’implementazione introducendo un sistema

3. di serializzazione che salvi per ogni

elemento presente una coppia rappresentata dall’elemento stesso e dal numero di occorrenze.

Soluzione contiene l’interfaccia

multiInsieme.java:

import java.io.*;

public interface multiInsieme extends Serializable {

void insert(int e) throws bagFull;

void delete(int e) throws bagEmpty, notFound;

void deleteAll(int e) throws bagEmpty, notFound;

boolean empty();

boolean full();

int howMany(int e);

boolean isin(int e);

} contiene la classe che implementa l’interfaccia

multiInsiemeImpl:

import java.io.*;

public class multiInsiemeImpl implements multiInsieme {

private int[] bag;

private int free;

private int max;

public multiInsiemeImpl(int size) throws dimErr {

if (size <= 0) throw new dimErr();

max = size;

bag = new int[max];

free = 0;

assert this.empty();

} public void insert(int e) throws bagFull {

if (this.full()) throw new bagFull();

int n = this.howMany(e);

bag[free++] = e;

assert !this.empty() && this.howMany(e) == n + 1;

} public void delete(int e) throws bagEmpty, notFound {

int i = 0;

if (this.empty()) throw new bagEmpty();

if (!isin(e)) throw new notFound();

int n = this.howMany(e);

while (bag[i] != e) i++;

for (int j=i; j<free-1;j++)

bag[j] = bag[j+1];

free--;

assert !this.full() && this.howMany(e) == n - 1;

}

public void deleteAll(int e) throws bagEmpty, notFound {

int num;

if (this.empty()) throw new bagEmpty();

if (!this.isin(e)) throw new notFound();

while(this.isin(e))

delete(e);

assert !this.full() && this.howMany(e) == 0;

}

public int howMany(int e) {

int num = 0;

for (int i=0; i<free; i++)

if (bag[i] == e)

num++;

return num;

}

public boolean isin(int e) {

for (int i=0; i<free; i++)

if (bag[i] == e)

return true;

return false;

}

public boolean empty() {return (free == 0);}

public boolean full() {return (free == max);}

private void writeObject(ObjectOutputStream out) throws IOException {

while (!this.empty()) {

int val = bag[0];

int n = this.howMany(val);

out.writeInt(val);

out.writeInt(n);

try {

this.deleteAll(val);

} catch(bagEmpty e) {e.printStackTrace();break;}

catch(notFound e) {e.printStackTrace();break;}

}

} private void readObject(ObjectInputStream in) throws IOException {

bag = new int[10];

free = 0;

max = 10;

while (in.available() > 0) {

int val = in.readInt();

int n = in.readInt();

System.out.println("Val " + val + " Num " + n);

for(int i=0;i<n;i++)

try {

this.insert(val);

}

catch(bagFull e) {throw new IOException("MultiSet Full");}

}

}

} Progettazione di Software

Esercizio n.1 (4pt)

Un Nastro è un tipo di dato astratto in grado di memorizzare in modo sequenziale dei generici elementi e che supporta il

concetto di posizione corrente.

Si definisca un modulo TDN per il tipo di dato astratto Nastro avente almeno le seguenti operazioni:

write: inserisce un elemento nel Nastro nella posizione corrente. La nuova posizione corrente al termine

dell’operazione è quella successiva all’elemento inserito. Qualora prima dell’operazione di write, vi fosse un elemento

in posizione corrente, oppure qualora il Nastro fosse pieno l’operazione non può essere eseguita.

restituisce l’elemento in posizione corrente. Al termine dell’operazione la posizione corrente si sposta

read:

all’elemento successivo a quello letto. Qualora in posizione corrente non vi fossero elementi, l’operazione non può

essere eseguita.

rewind: riporta la posizione corrente al primo elemento del Nastro. Qualora non vi siano elementi, la posizione corrente

non viene modificata.

empty: restituisce il valore Vero se e solo se il nastro non contiene elementi.

full: restituisce il valore Vero se e solo se il nastro non è in grado di memorizzare ulteriori elementi.

Esercizio n.2 (7 pt)

Si realizzi l’interfaccia Nastro in Java.

Esercizio n. 3

Si realizzi in Java una classe che implementa l’interfaccia di cui al precedente esercizio

Esercizio 3 (5pt)

Si realizzi una classe contenente un metodo main che acquisisce 10 numeri interi dallo standard input e li inserisce in un

Nastro, inizialmente vuoto.

module NASTRO[T]

exports

type

Nastro = ?;

procedures

write(in e:T, inout n:Nastro) raises nastroPieno, notEof

pre: not full(n) and eof(n)

post: eof(n) and length(n) = length(n’) +1 and

curr(n) = curr(n’) +1

read(out e:T, inout n:Nastro) raises Eof

pre: not eof(n)

post: curr(n) = curr(n’) + 1 and lenght(n) = length(n’)

rewind(inout n:Nastro)

pre: true

post: curr(n) = 1 and length(n) = length(n’)

create(out n:Nastro, in size:Int) raises dimErr

pre: size > 0

post: length(n) = 0 and eof(n) and max