LIP: 18 Aprile 2008
Interfacce
Rappresentazione Lista
val
next
vuota
Lista vuota:
Lista non vuota:
any
any
154
24
any
any
true
false
false
true
Implementazione di StringList
public class StringList {
// OVERVIEW: un StringList è una lista
//modificabile di stringhe.
// Elemento tipico [x1,...,xn]
private boolean vuota;
private String val;
private StringList next;
public StringList () {
// EFFECTS: inizializza this alla lista vuota
vuota=true;}
public StringList (String x) {
// EFFECTS: se x e’ null solleva
//NullPointerException, altrimenti inizializza
//this alla lista che contiene esattamente x
if (x==null) throw new
NullPointerException(“StringList.StringList”);
vuota=false; val=x; next=new StringList();}}
public void FaddEl (String x) {
//MODIFIES:this
// EFFECTS: se x e’ null solleva NullPointerexception,
//altrimenti aggiunge x all’inizio di this
if (x==null) throw new
NullPointerException(“IntList.IntList”);
{if (vuota) {val=x;next=new StringList();vuota=false;}
else
{StringList n = new StringList(val);
n.next = this.next; //copia di this
this.val =x;
this.vuota=false;
this.next=n;}
}}}
public void LaddEl (String x) {
//MODIFIES:this
// EFFECTS: se x e’ null solleva NullPointerexception,
//altrimenti aggiunge x alla fine di this
{if (vuota) {val=x;next=new StringList();vuota=false;}
else
next.LaddEl(x);}}
public void remove (String x) {
//MODIFIES:this
// EFFECTS: se x e’ null solleva NullPointerexception,
// altrimenti rimuove da this una occorrenza di x
{if (! vuota) { if (x.equals(val))
{vuota=next.vuota; if (! next.vuota)
{val=next.val;next=val.next;}}
else next.remove(x);}}
public String first () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException,
//altrimenti ritorna il primo elemento di this
if (vuota) throw new
EmptyException(“IntList.first”);
return val;}
public StringList rest () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException,
//altrimenti ritorna la lista ottenuta da this togliendo
//il primo elemento
if (vuota) throw new
EmptyException(“IntList.first”);
return next;}
public int size () {
// EFFECTS: ritorna il numero di elementi di this
if (vuota) return 0;
return 1 + next.size();
}
public String toString (){// EFFECTS: standard
String s=“”;
if (vuota) {return s;}
return val.intValue() + next.toString();}
public boolean equals(Object x) {
// EFFECTS: se x e’ null solleva
//NullpointerException, se this ed x sono uguali
//(sono liste che rappresentano la stessa
//sequenza di elementi) restituisce true,
//altrimenti false
if (! (x instanceOf StringList) return false;
StringList l= (StringList) x;
if (vuota) {if (l.vuota)
{return true;} else {return false;}
else
{if (l.vuota) {return false;}
else
{if (val.equals(l.val))
{return next.equals(l.next);}
else {return false;}
}
}
Ereditarieta’
• Abbiamo come estendere classi normali
tramite la definizione di sottoclassi
(extends)
• Definire una gerarchia di tipi
• In Java esistono altri meccanismi per
utilizzare gerarchie di tipi in cui la
superclasse e’ una classe definita in modo
parziale (classe astratta o interfaccia)
Cos’e’ una Interfaccia
• una interfaccia e’ un particolare tipo di
classe
• contiene solo la specifica
• non ha implementazione
• contiene solo metodi d’istanza (astratti)
• non ha costruttori
Di conseguenza
• non si possono creare oggetti, istanze di una
interfaccia
• L’implementazione e’ definita dai sottotipi,
che implementano lo stato, i costruttori ed i
metodi ereditati
A cosa servono?
• per definire implementazioni multiple di un
tipo di dato astratto (astraendo
dall’implementazione)
• per definire operazioni comuni a vari tipi
Prima Applicazione
• La specifica di un tipo di dato astratto puo’
essere definita da un’ interfaccia
• I sottotipi definiscono diverse
implementazioni del tipo di dato
• Esempio: stack di interi
public interface Stack {
\\OVERVIEW: uno Stack e’ una collezione di
\\elementi (interi) organizzati per ordine di inserimento con una politica
\\ LIFO. E’ modificabile
\\ metodi astratti
public boolean isEmpty();
\\EFFECTS: se this e’ vuoto restituisce true, altrimenti false
public int top() throws EmptyException;
\\EFFECTS: se this e’ vuoto solleva EmptyException, altrimenti
\\ritorna l’ultimo elemento inserito
public void pop() throws EmptyException;
\\ MODIFIES: this
\\ EFFECTS: se this non e’ vuoto rimuove l’ultimo elemento inserito,
\\altrimenti solleva EmptyException
public void push (int o);
\\ MODIFIES: this
\\ EFFECTS: inserisce o nella pila
}
Interfaccia
• Non ha implementazione
• Non si possono creare oggetti (non ci sono i
costruttori)
• I metodi astratti sono descritti da pre-post
condizioni in modo standard
Sottotipi
• I sottotipi forniscono l’implementazione
(implements)
• Tramite IntList
• Liste di Integer modificabili
public class ListStack implements Stack{
private IntList lista;
public ListStack(){
\\EFFECTS: inizializza this alla pila vuota
lista=new IntList();}
\\ metodi ereditati
public boolean isEmpty(){
return (lista.size()==0);}
public int top() throws EmptyException{
if (lista.size()==0) throw
new EmptyException(“Stack.top”);
return ((Integer) lista.first()).intValue();
}
public void pop() throws EmptyException{
if (lista.size()==0) throw
new EmptyException(“Stack.top”);
lista=lista.rest();}
public void push (int o){
lista.addEl(new Integer(o));}
}
•Il codice scritto rispetto al supertipo (interfaccia)
funziona correttamente per tutti i sottotipi
•Le differenze di implementazione restano invisibili
•Si forza ad astrarre tramite la specifica
Astrazione tramite specifica
• Frammento di codice che calcola la somma
degli elementi di uno Stack
• Scritto in base alla specifica (interfaccia)
• E’ indipendente dalla implementazione
• Funziona correttamente per ListStack
come per qualsiasi altra implementazione
(p.e. tramite Vector)
public static int somma(Stack p){
\\ REQUIRES: p non e’ null
\\EFFECTS: restituisce la somma degli elementi
\\di p
\\caso base
if (p.isEmpty()) {return 0;}
\\ caso ricorsivo
int first= p.top();
int sum= first + somma(p.pop())
p.push(first);
return sum;
}
Seconda Applicazione
• Permette di definire una famiglia di sottotipi
che hanno delle operazioni in comune
• Utile per astrarre dal tipo degli elementi di
una collezione
• Esempio: liste generiche ordinate
Astrarre dal tipo
• Abbiamo definito liste concatenate di interi,
stringhe
• Definite dai tipi StringList, IntList
• Non sarebbe meglio astrarre dal tipo degli
elementi e definire un tipo di dato lista
concatenata generico (polimorfo)?
Liste generiche
• Per definire un tipo generico si potrebbe
definire una lista che ha elementi di un supertipo,
ObjectList
• Il supertipo Object permetterebbe di
memorizzare Integer, String
• Svantaggio: non e’ garantito per costruzione che
gli elementi siano di tipo omogeneo
(analogo Vector)
Altro svantaggio
• Se volessimo una versione ordinata?
• Il supertipo Object non ha associata una
relazione di ordinamento (solo uguaglianza)
• Vorremmo una struttura dati parametrica
rispetto al tipo degli elementi e anche
rispetto all’ordinamento relativo
• Per memorizzare elementi di tipo diverso
ognuno con il suo ordinamento
Esempio
• Per String vorremmo usare l’ordinamento
lessicografico
• Per Integer vorremmo usare l’ordinamento
<=
Una soluzione
• Le interfacce possono essere usate per realizzare
una forma di lista generica ordinata
• In particolare l’interfaccia
Comparable (definito in java.util)
fornisce un supertipo i cui sottotipi hanno tutti un
metodo per il confronto (relazione di ordinamento
totale)
Interfaccia Comparable
–Ha un solo metodo compareTo che serve per realizzare confronti
–Tutti i sottotipi implementano il metodo compareTo
L’interfaccia Comparable
public interface Comparable {
// OVERVIEW: i sottotipi di Comparable forniscono un metodo
// per determinare la relazione di ordinamento fra i loro
// oggetti; l’ordinamento deve essere totale e, ovviamente,
// transitivo e simmetrico; infine
// x. compareTo (y) == 0 implica x. equals (y)
public int compareTo (Object x) throws ClassCastException,
NullPointerException;
// EFFECTS: se x è null, lancia NullPointerException;
// se this e x non sono confrontabili, solleva
ClassCastException;
// altrimenti, se this è minore di x ritorna -1;
// se this = x ritorna 0; se this è maggiore di x, ritorna 1
}
Nota
• Il metodo compareTo realizza
l’ordinamento
• String ed Integer sono sottotipi
primitivi di Comparable
• Se chiamato su oggetti che non sono
omogenei (tipo String ed Integer) allora
solleva ClassCastException
Uso di Comparable
• Facciamo una lista ordinata generica ed omogenea usando
Comparable
• Gli elementi della lista sono di tipo Comparable (invece
che Integer o String etc…)
• Il confronto e’ fatto in modo generico usando compareTo
• Questo permette di usare la lista per memorizzare
qualsiasi sottotipo di Comparable
• L’ordinamento giusto verra’ scelto a run-time in base al
tipo degli elementi
Cosa cambia nella Specifica?
• Bisogna indicare che gli elementi sono
Comparable
– argomenti e risultati sono Comparable invece che int
– bisogna indicare che gli elementi sono ordinati rispetto a
compareTo
• OrderedList assicura che gli elementi della lista siano
omogenei
– Si sfutta il fatto che compareTo solleva un’eccezione se gli
oggetti non sono confrontabili
• il tipo degli elementi nella lista è determinato
dall’inserimento del primo elemento
– se la lista diventa vuota il tipo può cambiare con l’aggiunta di un
nuovo elemento
Specifica di OrderedList
public class OrderedList {
// OVERVIEW: `e una lista modificabile ordinata di
// oggetti omogenei sottotipi di Comparable
// Oggetto tipico [x1, . . . , xn] con xi < xj se i < j
// Il confronto fra gli elementi è effettuato con il
// metodo compareTo
• Nota: xi < xj significa rispetto a compareTo
Costruttori e Metodi
public OrderedList ( ) {
// EFFECTS: inizializza this alla lista ordinata vuota}
public void addEl (Comparable 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}
Nota: in questo caso aggiunge vuol dire che lo
aggiunge in base all’ordinamento
Specifica
public Comparable first () throws EmptyException{
// EFFECTS: se this è vuoto solleva
EmptyException, //altrimenti ritorna il primo
elemento di this}
public OrderedList rest () throws EmptyException{
// EFFECTS: se this è vuoto solleva
EmptyException, //altrimenti ritorna la lista
ottenuta da this togliendo il primo elemento}
public int size () {
// EFFECTS: restituisce il numero di elementi di
this}
public boolean IsIn(Comparable c) {
// EFFECTS: restituisce true se c compare in this,
//false altrimenti}
public String toString (){\\EFFECTS: standard}
}
Esercizio 1
• Implementare la lista ordinata generica
• Generalizzare StringList
• Ordinamento
• Il metodo compareTo deve essere utilizzato
per realizzare i confronti e l’ordinamento
Testing
• Non esistono oggetti di tipo Comparable
(interfaccia)
• Esistono oggetti che sono sottotipi di
Comparable
• String,Integer (implementazioni
dell’interfaccia)
• Testare anche l’omogeneita’ (inserendo
elementi di tipo diverso)
Nuovi Sottotipi di Comparable
• E se volessimo usarlo per memorizzare un
sottotipo non primitivo?
• Es. Abbonato
• Dovremmo definirlo come implementazione
di Comparable
• Definire la relazione di ordinamento tramite
compareTo
public class Abbonato{
private String nome;
private int numero;
public Abbonato(String s,int n){
\\EFFECTS:crea un nuovo abbonato con nome s e numero n
numero=n; nome=s;}
public String nome(){
\\EFFECTS: restituisce il nome di this
return nome;}
public int numero(){
\\EFFECTS: restituisce il numero di this
return numero;}
\\ metodo overridden
public boolean equals(Object o){
\\EFFECTS :se o non e’ di tipo Abbonato solleva
\\ClassCastException, altrimenti restituisce true
\\se this ed o sono uguali, false altrimenti Libro
a= (Abbonato) o;
if (nome.equals(a.nome) &&
numero==a.numero)
return true;
return false;
}
}
Esercizio 2
• Vogliamo ordinare gli Abbonati
in base al nome
• Se il nome e’ uguale, in base al numero
• Progettare la specifica della modifica di abbonato
• Implementarla