Esercizi
MultiSet, Liste Ordinate
Progettare specifica ed implementazione (e
relativa invariante ed astrazione) del tipo di dato
Multiset, multiinsieme di dati del medesimo tipo.
In aggiunta al costruttore si abbiano come
operazioni primitive: inserimento, rimozione,
ricerca.
•Insieme: collezione di elementi, non esiste il concetto di numero
di occorrenze (Ex. {1,7,8})
•Multiinsieme: collezione di elementi, che possono occorrere zero
o piu’ volte (Ex. {1,7,8,7,1,1}). Le operazioni aggiungono e
rimuovono una occorrenza
Si progetti poi il tipo di dato MaxMultiset che
estende Multiset fornendo un metodo che ritorna
il valore che rappresenta la massima molteplicità
degli elementi del multiinsieme.
{1,1,3,5,5,5} e’ 3
Provare che i metodi realizzati soddisfano
l'invariante e la loro specifica.
Discutere il principio di sostituzione
Specifica Multiset
public 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' modificabile
//metodi
public Multiset () {
//EFFECTS: inizializza this al multiinsieme vuoto
public int isin(Object x) {
//EFFECTS: restituisce il numero di occorrenze di x (0
se non compare)
Specifica
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 un’occorrenza di x in this
//MODIFIES: this}
public void remove(Object x){
//EFFECTS: rimuove una occorrenza di x da this
//MODIFIES: this
Specifica
public Iterator elements(){
//EFFECTS: restituisce un generatore che restituisce
//gli elementi di this, fornendo per ogni elemento, el
//ed il numero di occorrenze}
•Si vuole che restuisca (1,3) se appaiono 3 occorrenze di 1, e non 1, 1, 1
•Tipo ausiliario Pair
Implementazione
• La scelta fondamentale e’ quella della
rappresentazione
• deve permettere di implementare i metodi
in modo efficiente
• Deve permettere la definizione di sottoclassi
(possibilmente senza rende accessibile la
rappresentazione)
Una possibilita’
• Utilizzare un vettore come per l’insieme
• Differenza: occorrenze multiple
• Non molto efficiente: metodo IsIn
[1,6,8,6,8,1,1] rappresenta {1,6,8,6,8,1,1}
Implementazione
• Vettore di coppie (valore, numero di occorrenze)
• Tipo record ausiliario Pair, due variabili d’istanza
left e right di tipo Object e int, che contengono
l’oggetto ed il numero di occorrenze
(molteplicita’)
• Piu’ efficiente isIn (rispetto al caso in cui inserisco
gli elementi direttamente nel vettore)
Insieme omogeneo
• Manteniamo in una variabile di tipo Class il tipo
del primo oggetto inserito (si usa getClass())
• Nota: una variabile di tipo Class prende come
valori tutti I tipi (gli posso assegnare direttamente
Integer, String…vedi costruttore che prende il
tipo)
La rappresentazione
public 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' modificabile
private Vector els;
private Class type;
•La variabile type memorizza il tipo
•Il vettore els memorizza le coppie
•Quali devono essere le loro proprieta’ ?
•L’ invariante esprime le proprieta’ delle due variabili d’istanza
che servono a garantire la correttezza
Invariante
IMultiset(c) = c.els  null &
(c.els.size()>0  c.type  null) &
i,j 0  ij < c.els.size() (
c.els.get(i) e’ un Pair &
c.els.get(i).left.getClass()=c.type &
c.els.get(i).right>0
&
c.els.get(i).left  c.els.get(j).left
•Le ultime condizioni vietano casi tipo: (a,3),(b,1),(b,3) o (c,0)
•Rendono l’implementazione piu’ efficiente
Funzione di astrazione: mappa in
multiinsiemi
aMultiset(c) = S tale c.els.get(i).left occorre c.els.get(i).right
volte in S i:0i<c.els.size()
•mappa un MultiSet in un multiinsieme:
(a,3),(b,1)------> {a,a,a,b}
Metodi
public Multiset (){
//EFFECTS: inizializza this al multiinsieme vuoto
{els=new Vector();}
public int isIn(Object x){
//EFFECTS: ritorna il numero di occorrenze di x in
//this, eventualmente o
{if (x==null} {return 0;}
for (int i=0; i<els.size(); i++) {
Pair q=(Pair) els.get(i);
if (x.equals(q.left)) {
return q.right;}}
return 0;}
Correttezza
• Soddisfano l’invariante (banale)
• Soddisfano la specifica?
• Notiamo per isIn sono necessarie le
proprieta’ dell’invariante, che garantisce che
non ci siano situazioni tipo (a,3),(b,1),(b,3)
• Altrimenti potrebbe riportare per b una sola occorrenza
Insert 1
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
un’occorrenza di x in this
//MODIFIES: this
if (x==null)
throw NullPointerException(" ");
if (els.size()==0)
type=x.getClass();
else {
if (!type.isinstance(x))
throw ClassCastException(" "); }
………………………… poi inserisce
• Prima effettua la verifica del tipo, se e’ vuoto inizializza il tipo con quello di
x, tramite getclass
• Preserva l’invariante (per quanto riguarda l’omogeneita’)
• Solleva l’eccezione in accordo alla specifica
Insert 2
……….
if (isin(x)==0) {
Pair p=new Pair(x,1);
els.add(p); }
else {
for (int i=0; i<els.size(); i++) {
Pair q=(Pair) els.get(i);
if (x.equals(q.left)) {
q.right++;}
}
•Preserva l’invariante e soddisfa la specifica
•Inserisce l’elemento rispettando i vincoli dell’invariante
•Se non c’era crea una nuova coppia
•Altrimenti aggiorna la molteplicita’ nella coppia che manteneva
le occorrenze di x
Remove
public void remove(Object x) {
//EFFECTS: rimuove un'occorrenza di x da this
//MODIFIES: this
if (isin(x)==0) return;
for (int i=0; i<els.size(); i++) {
Pair p=(Pair) els.get(i);
if (x.equals(p.left)) {
p.right--; if (p.right=0)
{els.remove(i); }}
}
Commenti a remove
•Preserva l’invariante e soddisfa la specifica
•Elimina l’elemento rispettando i vincoli dell’invariante
•Se c’era decrementa il numero di occorrenze
•Se sono zero rimuove proprio la coppia
•L’invariante non ammette (a,0) (piu’ efficiente)
Classe Multiset, Iterator elements
public Iterator elements() {
//EFFECTS: restituisce un generatore che produce gli elementi
// del multiinsieme this nella forma di coppie
//(elemento,molteplicita')
return new MultisetGen(this);
}
•L’iteratore e’ facile da progettare perche’ la
rappresentazione e’ adeguata
Classe MultisetGen
private static class MultisetGen implements Iterator {
//OVERVIEW: restituisce come Pair tutte le coppie (element0,
// molteplicita’) del multiinsieme che le viene passato
private Multiset set;
\\ il multinsieme
private int current; \\ prossimo elemento
//metodi
public MultisetGen(Multiset m) {
//EFFECTS: inizializza set a m e current a 0
set=m; current=0;
}
Classe MultisetGen
public boolean hasnext() {
//EFFECTS: se ci sono ancora elementi nel multiinsieme
// da generare 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; int loc=current;
current++; return set.els.get(loc);
}
}
Funzione di astrazione e invariante
aMultisetGen(c) = [c.set.els.get(current),
……..,c.set.els.get(c.set.els.size()-1) ]
IMultisetGen(c) =
0  c.current <= c.set.els.size()
Sottoclasse
• Estende col metodo maxmul, ritorna la
molteplicita’ massima presente nell’insieme
• Si puo’ implementare col generatore (ad
ogni chiamata scorre gli elementi e trova il
massimo)
• Si puo’ mettere una variabile d’istanza e
mantenerla aggiornata (tramite l’overriding
di insert e remove)
In ogni caso
• La rappresentazione della superclasse e’
mascherata
• Vantaggio: il codice delle sottoclassi e’
indipendente da quello della superclasse
• Facciamo vedere la seconda soluzione:
sfrutta la gerarchia
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: inizializza this al MaxMultiSet vuoto
{super(); max=0;
}
public int maxmul() {
//EFFECTS: restituisce il valore della molteplicita'
massima
return max; }
Overriding di Insert
public void insert (object x)
throws NullPointerException, ClassCastException
//EFFECTS: aggiunge una occorrenza di x in this
//MODIFIES: this
super.insert(x); int numero=isIn(x); if
(numero>max) {max=numero;} }
•Aggiorna il massimo (l’elemento inserito
potrebbe avere ora la molteplicita’ max)
•Le post condizioni sono uguali
{
Overriding di Remove
public void remove (object x)
{
//EFFECTS: rimuove una occorrenza di x da this
//MODIFIES: this
int numero=isIn(x);
super.remove(x); if (numero < max) {return;} else
{aggiornamax();}
}
•Le post condizioni sono uguali
•Se x aveva il numero max di occorrenze,
lo devo ricalcolare
Classe MaxMultiset, metodo aggiornamax
private void aggiornamax()
{
//EFFECTS: aggiorna la molteplicita' massima
//MODIFIES: this
max=0;
Iterator g = elements();
while (g.hasnext()) {
Pair p = (Pair)g.next();
if (p.right()>max)
max =p.right;
}
}
Funzione di astrazione e invariante
aMaxMultiset(c) = aMultiset(c)
IMaxMultiset(c) =
c.max  0 &
c.max>0 xaMultiset(c)|x occorre c.max volte &
xaMultiset(c) la molteplicita' di x e'  c.max
•E l’invariante della superclasse?
Commenti
• Nel progetto della superclasse deve essere previsto come si
puo’ estendere (accesso diretto o metodi)
• Abbiamo fornito il generatore alle possibili sottoclassi per
mantenere la rappresentazione privata
• Alternativa rappresentazione della superclasse protected
(accesso diretto)
• Piu’ efficiente, ma la sottoclasse diventerebbe dipendente
dall’implementazione della superclasse
• Inoltre la correttezza sarebbe piu’ complessa: la sottoclasse
potrebbe invalidare la correttezza della superclasse
(potrebbe violarne l’invariante)
Consiglio
• Le soluzioni migliori (piu’ efficienti e\o ben
strutturate) sono piu’ complicate: piu’
condizioni nell’invariante, nei metodi
bisogna fare attenzione a piu’ proprieta’
(per esempio a non inserire (a,8),(a,1))
• Cercate di non scegliere la via piu’ facile
*solo* per fare prima
Altro Esercizio
• Problema: vogliamo progettare un tipo di
dato Lista Ordinata Generica
• In grado di memorizzare interi, stringhe
etc…, ognuno con il relativo ordinamento
• Bisogna essere parametrici rispetto al tipo
degli elementi e anche rispetto alla relativa
nozione di ordinamento
• Due approcci basati sull’uso delle interfacce
Primo Approccio: element
subtype
• definiamo l’interfaccia I che definisce le
proprietà richieste (in questo caso
l’ordinamento), Comparable
• definiamo il tipo di dato (in questo caso la lista)
con elementi di tipo I (Comparable)
• definiamo gli oggetti come sottotipi
dell’interfaccia I
La classe OrderedList
• Generalizza OrderedIntList
• Permette di definire liste piu’ generali, che hanno come
elementi, sottotipi dell’interfaccia Comparable
• specifica e implementazione simili a quelle di
OrderedIntList solo che
– argomenti e risultati delle operazioni sono
Comparable invece che int
– l’ordinamento è fatto usando compareTo
La classe OrderedList
• Possiamo usarlo solo per memorizzare liste ordinate di
elementi sottotipi di Comparable, ovvero che
implementano l’interfaccia fornendo il metodi
compareTo
• String, Integer
• Nuovi tipi predefiniti
Esempio
• Supponiamo di volere mantenere ordinate
delle coppie di interi
• Ordinamento richiesto: in modo crescente in
base al primo elemento, se il primo
elemento e’ uguale in base al secondo in
ordine crescente
• Ex: [(1,2),(1,3),(2,1,),(2,4),(4,1)]
Per usare OrderedList
• E’ pero’ necessario definire a priori le coppie di
interi come sottotipo di Comparable
public class IPair implements Comparable{
//OVERVIEW: sono coppie di interi su cui e’ definito un ordine
// totale
public int left; \\ il primo elemento
public int right;\\ il secondo elemento
public IPair(int x,int y){right=x,left=y;}
public int compareTo (Object x) throws ClassCastException,
NullPointerException {
…….verifica se this e’ minore o uguale o maggiore di x secondo
l’ordinamento descritto in precedenza tra coppie
Per usare OrderedList
public int compareTo (Object x) throws ClassCastException,
NullPointerException {
IPair
y=(IPair) x;
if (left < x.left) {return -1};
if (x.left < left) {return 1};
else
{if (right < x.right) {return -1};
if (x.right < rigth) {return 1};}
return 0;}
Esempio di uso
IPair p= new IPair (1,3);
IPair q=new IPair (2,4);
OrderedList l=new OrderedList();
l.add(p); l.add(q);
l.toString();
• Ritorna la lista ordinata (come String):
[(1,3),(2,4)]
• I metodi di OrderedList usano compareTo per
ordinare gli oggetti, in questo caso quello fornito
dal tipo di dato IPair
Svantaggi
• Definendo il tipo IPair come sottotipo di
Comparable le coppie hanno direttamente la
relativa operazione di ordinamento (implementata
da compareTo)
• E se avessi gia’ definito un tipo Pair che
rappresenta le coppie di interi ma non implementa
Comparable?
• Si puo’ definire un tipo di dato “polimorfo”
OrderedList che funziona anche per tipi preesistenti?
Alternativa OrderedList
• Ha come elementi Object
• Il confronto e’ fatto usando il metodo compare, fornito da
una interfaccia Comparator (anche questa pre-definita in
Java)
• L’implementazione dell’interfaccia viene passata come
parametro al costruttore e memorizzata per usare la relativa
nozione di ordinamento
• Per usare la lista per un certo tipo di dato T basta definire
(anche a posteriori) l’implementazione di Comparator
relativa a T
L’interfaccia Comparator
public interface Comparator {
// OVERVIEW: tutti i sottotipi di Comparator forniscono
//metodi per confontare gli elementi di un “tipo
// collegato”
public int compare (Object x, Object y) throws
NullPointerException, ClassCastException;
// EFFECTS: se uno tra x o y è null, solleva
// NullPointerException; se x e y non sono
// confrontabili solleva ClassCastException; altrimenti,
// se x è minore di y ritorna -1; se y = x ritorna 0;
//se x è maggiore di y, ritorna 1
}
Come usare OrderedList?
•Vogliamo fare una lista ordinata di Pair (pre-definito)
•Pair non implementa direttamente l’interfaccia
Comparator non hanno incluso l’ordinamento
•Dobbiamo invece definire un ’implementazione di
Comparator, collegata a Pair, che realizza il confronto
tra coppie (quello richiesto)
•Dobbiamo passare ad OrderedList
l’ implementazione di Comparator, collegata a Pair
Esercizio
• Definire il sottotipo di Comparator,
PairComparator che realizza il confronto tra
le coppie
• Se i parametri passati a compare non sono
coppie deve sollevare ClassCastException,
non sono confrontabili (basta usare il cast)
public class PairCompator implements Comparator {
// OVERVIEW: definisce un sottotipo di Comparator relativo
//al tipo Pair
public int compare (Object x, Object y) throws
NullPointerException, ClassCastException{
// EFFECTS: se uno tra x o y è null, solleva
// NullPointerException; se x e y non sono
// confrontabili solleva ClassCastException; altrimenti,
// se x è minore di y ritorna -1; se y = x ritorna 0;
//se x è maggiore di y, ritorna 1
if (x==null || y==null) throw new NullPointerException();
Pair p1= (Pair) x; Pair p2=(Pair) y;
if (p1.left < p2.left) {return -1};
if (p1.left < p2.left) {return 1};
else
{if (p1.right < p2.right) {return -1};
if (p1.right < p2.rigth) {return 1};}
return 0;}
Specifica di OrderedList
public class OrderedList {
// OVERVIEW: `e una lista modificabile ordinata
// e omogenea di Object.
// Oggetto tipico [x1, . . . , xn] con xi < xj se
// i < j. Il confronto fra gli elementi è
// effettuato con il metodo compare di una
// interfaccia Comparator relativa
// costruttore
public OrderedList (Comparator c )
// EFFECTS: inizializza this alla lista
// ordinata vuota che ha elementi del tipo
//collegato c
Specifica di OrderedList 2
// metodi
public void addEl (Object el) throws
NullPointerException,
DuplicateException, ClassCastException {
// MODIFIES: this
// EFFECTS: se el è in this, solleva
//DuplicateException; se el è null solleva
//NuIlPointerException; se el non è confrontabile
//con gli altri elementi in this solleva
//ClassCastException; altrimenti, aggiunge el a this}
public void remove (Object el)
{
// MODIFIES: this
// EFFECTS: se el è in this, lo rimuove altrimenti,
//non fa nulla}
Specifica di OrderedList 2
// metodi
public Object first() throws EmptyException {
// EFFECTS: se el è vuota solleva
EmptyException, altrimenti restituisce il primo
elemento}
public OrederedList next() throws EmptyException {
// EFFECTS: se el è vuota solleva
EmptyException, altrimenti restituisce resto della
lista}
public boolean IsIn (Object el) {
// EFFECTS: se el è in this restituisce true,
//altrimenti false }
Implementazione
public class OrderedList {
private
private
private
private
Object val;
boolean vuota;
OrderedList next;
Comparator conf;
public OrderedList (Comparator c ) {
vuota=true; conf=c;}
Invariante e funzione di
astrazione
• Funzione di astrazione: la solita
• Invariante:
I(c)= c.conf!=null e
!c.vuota =====>
(c.next e c.val!=null e
c.conf.compare(c.val,c.val) non solleva ecc. e
c.conf=c.next.conf e I(c.next) e
c.conf.compare( c.val,c.next.val ) <0
)
Implementazione
public void addEl (Object el) throws
NullPointerException,DuplicateException, ClassCastException {
if (el==null) throw new NullPointerException(“”);
if (vuota){int n=conf.compare(el,el);
val=el; vuota=false; next=new OrderedList(conf);}
else
{int n=conf.compare(val,el);
if (n==0) throw new DuplicateException(“”);
if (n <0) {next.addEl(el);}
else
{OrderedList l=new OrderedList(conf); l.val=val;l.vuota=vuota;
l.next=next; l.conf=conf;
val=el;next=l;}
}}
Implementazione
public void remove (Object el)
{
if (vuota) return;
int n=conf.compare(val,el);
if (n==0) { if (next.vuota)
{vuota=true;}
else
{val=next.val; vuota=next.vuota; next=next.next;}
}
else {next.remove(el);
}
Implementazione di OrderedList
public Object first() throws EmptyException {
if (vuota) throw new Emptyexception(“first”);
return val;
}
public OrederedList next() throws EmptyException {
if (vuota) throw new Emptyexception(“first”);
return next;
public boolean IsIn (Object el) {
if (vuota) return false;
in n= conf.compare(val,el); if (n==0)
return true;
else return next.IsIn(el);}
Differenza rispetto all’altro
metodo
• Per confrontare el con l’elemento del vettore chiama il metodo
compare del Comparator
int n=conf.compare(o,el);
• Per confrontare el con l’elemento del vettore chiama il metodo
compareto sull’elemento (sono Comparable)
int n=o.compareto(el);
• Nel primo approccio gli elementi non hanno direttamente il metodo di
confronto (glielo passo col Comparator relativo)
• Nel secondo approccio gli elementi hanno direttamente il metodo di
confronto (implementano Comparable)
Differenza nell’uso
IPair p= new IPair (1,3); //sottotipo di Comparable
IPair q=new IPair (2,4);
OrderedList l=new OrderedList();
l.add(p); l.add(q); //ordina con compareTo
l.toString();
Pair p= new Pair (1,3);
Pair q=new Pair (2,4);
OrderedList l=new OrderedList(new PairComparator());
l.add(p); l.add(q); //ordina con compare
l.toString();
Ritorna la lista ordinata (come String): [(1,3),(2,4)]