Multiset. Progettare (specifica con identificazione delle eventuali astrazioni necessarie, incluse...

Multiset

Progettare (specifica con identificazione delle eventuali astrazioni necessarie, incluse eccezioni, e implementazione) del tipo di dato Multiset, multiinsieme di dati del medesimo tipo. In aggiunta al costruttore si abbiano come operazioni primitive insert, remove, isin. Si progetti poi il tipo di dato MaxMultiset che estende Multiset mantenendo aggiornato il valore che rappresenta la massima molteplicità degli elementi del multiinsieme. Provare che i metodi realizzati soddisfano l'invariante e la loro specifica.

Classe Multiset, Metodo isinpublic class Multiset {//OVERVIEW: un Multiset e' un insieme di elementi omogenei in//cui ogni elemento puo' occorrere piu' volte, es. {1,5,4,1,4}.//E' modficabile private vector els; private class type;//metodi public Multiset () {//EFFECTS: inizializza un multiinsieme vuoto els=new vector(); } public boolean isin(Object x) {//EFFECTS: se x e' un elemento di this restituisce true, altrimenti//false if (x==null) return false; for (int i=0; i<els.size(); i++) { Pair p=(Pair)els.get(i); if (x.equals(p.left())) return true; } return false; }

Classe Multiset, Metodo insert public void insert(Object x) throws NullPointerException, ClassCastException {//EFFECTS: se x e' null solleva NullPointerException, se x non e' omogeneo//agli elementi di this solleva ClassCastException, altrimenti inserisce x in//this//MODIFIES: this if (x==null) throw NullPointerException(" "); if (els.size()==0) type=x.getclass(); else { if (!type.isinstance(x)) throw ClassCastException(" "); } if (!isin(x)) { Pair p=new Pair(x,new Integer(1)); els.add(p); } else { for (int i=0; i<els.size(); i++) { Pair q=(Pair) els.get(i); if (x.equals(q.left())) { int y=(Integer) q.right.intValue(); y++; Pair p=new Pair(x, new Integer(y)); els.set(i,p); } } }

public void remove(Object x) {

//EFFECTS: rimuove un'occorrenza di x da this

//MODIFIES: this

if (!isin(x)) return;

for (int i=0; i<els.size(); i++) {

Pair p=(Pair) els.get(i);

if (x.equals(p.left())) {

int y=(Integer) p.right().intvalue();

y--;

if (y>0)

els.set(i, newPair(x,new Integer(y)));

else

els.remove(i); } }

Classe Multiset, Metodo remove

protected Iterator elements() {

//EFFECTS: ritorna gli elementi del multiinsieme this nella

//forma di coppie (elemento,molteplicita')

return new MultisetGen(this); }

Classe Multiset, Iterator elements

Classe MultisetGenprivate static class MultisetGen implements Iterator {//OVERVIEW: restituisce come Pair tutti gli elementi di un//multiinsieme che le viene passato private Multiset set; private int current;//metodi public MultisetGen(Multiset m) {//EFFECTS: inizializza set a m e current a 0 set=m; current=0; } public boolean hasnext() {//EFFECTS: se ci sono ancora elementi nel multiinsieme da//ritornare ritorna true, altrimenti false return (current<set.els.size()); } public Object next() throws NoSuchElementException {//EFFECTS: restituisce il prossimo elemento del multiinsieme//se ce ne sono, altrimenti solleva un'eccezione if (current=set.els.size()) throw NoSuchElementException; Pair p=(Pair) set.els.get(current); current++; return p; } }

Classe MaxMultiset, metodo maxmul

public class MaxMultiset extends Multiset{

//OVERVIEW: un MaxMultiset e' un Multiset che mantiene traccia

//della massima molteplicita' dei suoi elementi

private int max;

//metodi

public MaxMultiset () {

//EFFECTS: richiama il costruttore di Multiset e inizializza la

//molteplicita' massima a 0

super(); max=0; }

public int maxmul() {

//EFFECTS: restituisce il valore della molteplicita' massima

return max; }

public void insert (object x)

throws NullPointerException, ClassCastException {

//EFFECTS: richiama la insert di Multiset ed aggiorna la

//molteplicita' massima

//MODIFIES: this

super.insert(x); max=0; aggiornamax(); }

public void remove (object x) {

//EFFECTS: richiama la remove di Multiset ed aggiorna la

//molteplicita' massima

//MODIFIES: this

super.remove(x); max=0; aggiornamax(); }

Classe MaxMultiset, metodi insert e remove

Classe MaxMultiset, metodo aggiornamax

private void aggiornamax() {

//EFFECTS: aggiorna la molteplicita' massima degli elementi

//di this

//MODIFIES: this

Iterator g = elements();

while (g.hasnext()) {

Pair p = (Pair)g.next();

if ((Integer) p.right.intvalue()>max)

max = (Integer) p.right.intvalue();

}

}

Funzione di astrazione e invariante

Multiset(c) = S :

c.els.get(i).left() occorre c.els.get(i).right.intvalue()

volte in S i:0i<c.els.size

IMultiset(c) = c.els null &

(c.els.size()>0 c.type null) & i,j 0 ij < c.els.size() ( c.els.get(i).left().getClass()=c.type &

c.els.get(i).right.intvalue()>0 &

c.els.get(i).left() c.els.get(j).left() )


MultisetGen(c) = [c.els.get(current).left().. c.els.get(c.set.els.size()-1).left() ]

IMultisetGen(c) =

c.set Multiset(c) &

0 c.current < c.set.els.size()


MaxMultiset(c) = Multiset(c)

IMaxMultiset(c) =

c.max 0 & c.max>0 xMultiset(c)|x occorre c.max volte &

xMultiset(c) la molteplicita' di x e' c.max

Costruttore public Multiset () {

//EFFECTS: inizializza un multiinsieme vuoto

els=new vector(); }

Il costruttore della classe Multiset soddisfa l'invariante e la specifica (banalmente), infatti:

IMultiset(c) =

c.els null & (c.els.size()>0 c.type null) & i,j 0 ij < c.els.size() ( c.els.get(i).left().getClass()=c.type &

c.els.get(i).right.intvalue()>0 &

c.els.get(i).left() c.els.get(j).left() )

Metodo isin public boolean isin(Object x) {//EFFECTS: se x e' un elemento di this restituisce true, altrimenti//false if (x==null) return false; for (int i=0; i<els.size(); i++) { Pair p=(Pair)els.get(i); if (x.equals(p.left())) return true; } return false; }

Il metodo isin soddisfa l'invariante (non modifica nulla) e la specifica:- se x=null x (this) ed isin ritorna false- se xnull e x (this) allora nel ciclo for viene individuata la coppia (x,n) e isin ritorna true- se xnull e x (this) allora il ciclo for termina la sua esecuzione senza trovare alcuna coppia utile e isin ritorna false

Metodo insert

Il metodo insert soddisfa l'invariante:- se x=null solleva un'eccezione ed esce- se xnull ma x non e' omogeneo al tipo di this, il metodo solleva un'eccezione ed esce

Il metodo non effettua nessuna modifica.Assumendo vera l'invariante prima di invocare il metodo, l'invariante rimane soddisfatta anche dopo l'esecuzione del metodo.

public void insert(Object x) throws NullPointerException, ClassCastException {//EFFECTS: se x e' null solleva NullPointerException, se x non e' omogeneo//agli elementi di this solleva ClassCastException, altrimenti inserisce x in//this//MODIFIES: this if (x==null) throw NullPointerException(" "); if (els.size()==0) type=x.getclass(); else { if (!type.isinstance(x)) throw ClassCastException(" "); } if (!isin(x)) { Pair p=new Pair(x,new Integer(1)); els.add(p); } else { for (int i=0; i<els.size(); i++) { Pair q=(Pair) els.get(i); if (x.equals(q.left())) { int y=(Integer) q.right.intValue(); y++; Pair p=new Pair(x, new Integer(y)); els.set(i,p); } } }

Metodo insert

Il metodo insert soddisfa l'invariante:- se xnull e this e' vuoto inizializza this alla classe di x. c.els.size()>0 c.type nulle' soddisfatta, nel momento in cui un elemento e' inserito in this (c.els.size()>0) il tipo di this viene inizializzato (c.type null).

- se xnull e this e' del tipo di x inserisce x in (this)

Tutte le condizioni dell'invariante rimangono banalmente soddisfatte anche dopo l'esecuzione del metodo.


Metodo insert

Il metodo insert soddisfa la specifica:- se x=null solleva un'eccezione ed esce- se xnull e this e' di tipo diverso dal tipo di x solleva un'eccezione ed esce- se xnull e this e' vuoto inizializza this alla classe di x.- se xnull e this e' del tipo di x: - se x this trova (x,y) e la aggiorna in (x,y+1) - se x this crea una nuova coppia (x,1) e la inserisce nel multiinsieme


Metodo remove

Il metodo remove soddisfa l'invariante:- se x (this) il metodo esegue una return senza fare nulla

Assumendo vera l'invariante prima di invocare il metodo, l'invariante rimane soddisfatta anche dopo l'esecuzione del metodo.

public void remove(Object x) {//EFFECTS: rimuove un'occorrenza di x da this//MODIFIES: this if (!isin(x)) return; for (int i=0; i<els.size(); i++) { Pair p=(Pair) els.get(i); if (x.equals(p.left())) { int y=(Integer) p.right().intvalue(); y--; if (y>0) els.set(i, newPair(x,new Integer(y))); else els.remove(i); } }

Metodo remove

Il metodo remove soddisfa l'invariante:- se x (this) il metodo rimuove x da (this)

Tutte le condizioni dell'invariante rimangono banalmente soddisfatte anche dopo l'esecuzione del metodo. Si noti che le condizioni sono soddisfatte anche nel caso in cui x sia l'unico elemento di (this), il tipo di this resta immutato e verra' cambiato solo ad una nuova chiamata di insert, poiche' this.set.els.size() sara' uguale a 0.


Metodo remove

Il metodo remove soddisfa la specifica:- se x (this) il metodo esegue una return senza fare nulla- se x (this) il metodo cerca la coppia (x,y) e decrementa y - se y-1> 0 aggiorna la coppia (x,y) al valore (x,y-1) - se y-1=0 elimina la coppia (x,y) dal multiinsieme


Multiset. Progettare (specifica con identificazione delle eventuali astrazioni necessarie, incluse...

Documents

Transcript of Multiset. Progettare (specifica con identificazione delle eventuali astrazioni necessarie, incluse...