esercizi multiset, liste ordinate. progettare specifica ed implementazione (e relativa invariante ed...
TRANSCRIPT
![Page 1: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/1.jpg)
Esercizi
MultiSet, Liste Ordinate
![Page 2: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/2.jpg)
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
![Page 3: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/3.jpg)
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
![Page 4: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/4.jpg)
Specifica Multisetpublic 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)
![Page 5: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/5.jpg)
Specificapublic 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
![Page 6: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/6.jpg)
Specificapublic 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
![Page 7: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/7.jpg)
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)
![Page 8: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/8.jpg)
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}
![Page 9: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/9.jpg)
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)
![Page 10: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/10.jpg)
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)
![Page 11: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/11.jpg)
La rappresentazionepublic 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
![Page 12: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/12.jpg)
Invariante
IMultiset(c) = c.els null &
(c.els.size()>0 c.type null) & i,j 0 ij < 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
![Page 13: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/13.jpg)
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:0i<c.els.size()
•mappa un MultiSet in un multiinsieme:
(a,3),(b,1)------> {a,a,a,b}
![Page 14: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/14.jpg)
Metodipublic 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;}
![Page 15: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/15.jpg)
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
![Page 16: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/16.jpg)
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
![Page 17: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/17.jpg)
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 mantenevale occorrenze di x
![Page 18: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/18.jpg)
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); }} }
Remove
![Page 19: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/19.jpg)
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)
![Page 20: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/20.jpg)
public Iterator elements() {
//EFFECTS: restituisce un generatore che produce gli elementi // del multiinsieme this nella forma di coppie //(elemento,molteplicita')
return new MultisetGen(this); }
Classe Multiset, Iterator elements
•L’iteratore e’ facile da progettare perche’ larappresentazione e’ adeguata
![Page 21: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/21.jpg)
Classe MultisetGenprivate 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; }
![Page 22: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/22.jpg)
Classe MultisetGenpublic 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); } }
![Page 23: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/23.jpg)
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()
![Page 24: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/24.jpg)
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)
![Page 25: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/25.jpg)
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
![Page 26: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/26.jpg)
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; }
![Page 27: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/27.jpg)
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;} }
Overriding di Insert
•Aggiorna il massimo (l’elemento inserito
potrebbe avere ora la molteplicita’ max)
•Le post condizioni sono uguali
![Page 28: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/28.jpg)
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();} }
Overriding di Remove
•Le post condizioni sono uguali
•Se x aveva il numero max di occorrenze,
lo devo ricalcolare
![Page 29: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/29.jpg)
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;
}
}
![Page 30: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/30.jpg)
Funzione di astrazione e invariante
aMaxMultiset(c) = aMultiset(c)
IMaxMultiset(c) =
c.max 0 & c.max>0 xaMultiset(c)|x occorre c.max volte &
xaMultiset(c) la molteplicita' di x e' c.max
•E l’invariante della superclasse?
![Page 31: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/31.jpg)
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)
![Page 32: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/32.jpg)
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
![Page 33: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/33.jpg)
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
![Page 34: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/34.jpg)
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
![Page 35: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/35.jpg)
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
![Page 36: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/36.jpg)
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
![Page 37: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/37.jpg)
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)]
![Page 38: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/38.jpg)
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 elementopublic 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
![Page 39: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/39.jpg)
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;}
![Page 40: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/40.jpg)
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
![Page 41: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/41.jpg)
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 pre-esistenti?
![Page 42: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/42.jpg)
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
![Page 43: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/43.jpg)
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
}
![Page 44: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/44.jpg)
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
![Page 45: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/45.jpg)
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)
![Page 46: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/46.jpg)
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;}
}
![Page 47: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/47.jpg)
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
![Page 48: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/48.jpg)
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}
![Page 49: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/49.jpg)
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 }
![Page 50: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/50.jpg)
Implementazionepublic class OrderedList {
private Object val;
private boolean vuota;
private OrderedList next;
private Comparator conf;
public OrderedList (Comparator c ) {
vuota=true; conf=c;}
![Page 51: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/51.jpg)
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
)
![Page 52: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/52.jpg)
Implementazionepublic 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;}
}}
![Page 53: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/53.jpg)
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);
}
![Page 54: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/54.jpg)
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);}
![Page 55: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/55.jpg)
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)
![Page 56: Esercizi MultiSet, Liste Ordinate. Progettare specifica ed implementazione (e relativa invariante ed astrazione) del tipo di dato Multiset, multiinsieme](https://reader038.vdocumenti.com/reader038/viewer/2022110305/5542eb4c497959361e8b99a7/html5/thumbnails/56.jpg)
Differenza nell’uso
IPair p= new IPair (1,3); //sottotipo di ComparableIPair q=new IPair (2,4);OrderedList l=new OrderedList();l.add(p); l.add(q); //ordina con compareTol.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 comparel.toString();
Ritorna la lista ordinata (come String): [(1,3),(2,4)]