Astrazioni Polimorfe e Tipi Generici
Polimorfismo
• Dal Greco  molte forme
• Una variabile polimorfa può riferirsi a oggetti di classi diverse
• Un metodo polimorfo può avere parametri di tipi diversi
• Un tipo polimorfo può essere un contenitore di dati di tipi diversi
(per esempio stack di oggetti di tipo qualunque…)
2
Polimorfismo
• Polimorfismo per procedure e iteratori:
astrazioni parametriche rispetto al tipo di uno o piu` argomenti
– Es. e motivazione: invece di costruire una procedura di ordinamento per un
vettore di interi, una per per un vettore di stringhe, ecc.,è preferibile unica
astrazione procedurale che ordina un vettore, e che sia utilizzabile sia per gli
interi che per le stringhe,
• Polimorfismo per data abstraction:
astrazione parametrica rispetto a tipo degli elementi contenuti
negli oggetti
– Es. Invece di un’astrazione per insiemi di numeri interi (IntSet) e una per
insiemi di stringhe (StrSet), preferibile unica astrazione del concetto di
insieme (astrazione Set) utilizzabile sia per gli interi che per le stringhe
3
Esempio: Ricerca sequenziale
….
public static int cerca(Object x, Vector a) {
//@requires x != null && a !=null && (\forall int i; 0<=i<a.size();
//@ a.get(i)!=null);
//@ensures \result == -1 && (*non esiste in a elemento equals a x *)
//@ || x.equals(a.get(\result))
for(int i=0; i<a.size(); i++) {
if(x.equals(a.get(i)) return i;
return –1;
}
}
• Il codice per Object è un’astrazione di quello, ad esempio, per int.
• Similmente, si potrebbe definire cerca(Object, Iterator) o cerca(Object,
Collection) per astrarre ricerca sequenziale a qualunque contenitore
4
Es. Specifica di set polimorfo
public class PolimSet {
// OVERVIEW: PolimSet sono insiemi mutabili illimitati
// oggetto null non può appartenere a un oggetto PolimSet
// usato equals per determinare uguaglianza di elementi
public PolimSet()
// costruttore
public void insert (Object x) throws NullPointerException {…}
//@ signals x == null
//@ ensures x!=null && (*inserisce x (non un suo clone) in this *)
public void remove (Object x)
public boolean IsIn (Object x)
public boolean subset (PolimSet s)
}
5
Implementazione (parziale) di PolimSet
public class PolimSet{
private ArrayList els; //oppure Vector
public PolimSet(){els=new ArrayList();} // oppure Vector()
public void insert (Object x) throws NullPointerException {
if (getIndex(x) < 0) els.add(x);
}
private int getIndex(Object x){
for(int i=0; i<els.size(); i++)
if(x.equals(els.get(i)) return i;
return –1;
}
public void remove (Object x){
if (x==null) return;
els.remove(x);
}
public boolean IsIn (object x){…}
public boolean subset (PolimSet s){…}
}
6
Attenzione all’implementazione del metodo equals
• Appartenenza di un elemento a oggetto PolimSet determinata usando equals, quindi
anche contenuto di un PolimSet dipende da esso
• Spesso (ad es. per Vector e tutte le classi delle librerie Sun) equals restituisce true se
due vettori hanno lo stesso stato: attenzione a immettere oggetti Vector in un PolimSet!
PolimSet s = new PolimSet();
Vector x = new Vector();
Vector y = new Vector();
s.insert(x);
y non viene aggiunto
s.insert(y);
a causa di equals
x.add(new Integer(3));
if(s.isIn(y)) // qsta condizione vale false
• Questo può essere inatteso (dopo s.insert(y); senza un remove ci si aspetta
che y sia ancora in s)
– soluzione insoddisfacente: usare == invece di equals : non funziona per oggetti
immutabili (es: due stringhe identiche nello stesso PolimSet)
– Soluzione: racchiudere elementi (es. Vector) che si vogliono distinguere in oggetti
di una classe contenitore (wrapper) che ridefinisca il metodo equals in maniera
opportuna
7
Usare un contenitore per gli oggetti
mutabili della collezione
public class Container{
private Object el;
public Container(Object x){el = x;}
public Object get () {return el;}
public boolean equals (Object x){
if(! x instanceOf Container) return false;
return (el == ((Container) x).get());
}
}
• Adesso il codice (con qualche modifica) funziona come ci aspettiamo
PolimSet s = new PolimSet();
Vector x = new Vector();
Vector y = new Vector();
s.insert(new Container(x));
s.insert(new Container(y));
x.add(new Integer(3));
if(s.isIn(new Container (y))) // condizione vera
8
Accorgimenti nell’uso di collezioni polimorfe
• Le collezioni polimorfe (e.g., PolimSet) sono definite rispetto a elementi di
classe Object, quindi
– bisogna incapsulare (wrap) i tipi primitivi: int  Integer
– i metodi osservatori che restituiscono elementi della collezione restituiranno oggetti
di tipo Object, quindi occorre fare il casting e nel caso di tipi primitivi “estrarre”
(unwrap)
– a volte wrap e unwrap evitati grazie ad autoboxing e autounboxing
PolimSet s = new PolimSet();
incapsulamento del tipo primitivo
s.insert(new Integer(3));
………
casting
Iterator g = s.elements();
while (g.hasNext()){
int i = (Integer) g.next(); //NB: autounboxing
…………
}
9
Problema con astrazioni polimorfe
• Il vincolo che gli elementi di una collezione siano tutti dello stesso tipo non può essere
controllato dal compilatore! quindi possono verificarsi errori di classe a run-time (che
non si verificano, e.g., con IntSet).
• Esempio
List myIntList = new LinkedList(); // 1
myIntList.add(new Integer(0)); // 2
Integer x = (Integer) myIntList.iterator().next(); // 3
– Il cast in linea 3 è “noioso”: il programmatore sa cosa c’è nella lista.
– Se pero’ la riga (2) fosse:
myIntList.add(new String(0)); // 2
– allora l’oggetto restituito in linea 3 non sarebbe un Integer, causando un
errore run time!
• Come fare a evitarlo? Noi vorremmo type safety!
• Questo è un problema ineliminabile fino al JDK 1.4 incluso, in quanto è
necessario usare il casting
• Risolto in Java 1.5 con i tipi generici
10
Classi Generiche
• Generici forniscono un’astrazione sui tipi, simile alle
astrazioni polimorfe ma più “sicure” (type-safety è
sempre garantita)
– Esempio di lista di interi con i generici
List<Integer> myIntList = new LinkedList<Integer>(); // 1’
myIntList.add(new Integer(0)); //2’
Integer x = myIntList.iterator().next(); // 3’
– alla riga 3’non serve più il cast: il compilatore “sa” che la lista
contiene solo oggetti Integer
– se la riga 2’ fosse:
myIntList.add(new String(0)); // 2
– non ci sarebbe bisogno di mandare in esecuzione il programma per
accorgersi dell’errore: ce lo segnalerebbe il compilatore
11
Classi Generiche
• Esempi di classi generiche: le interfacce List e Iterator
public interface List<E> {
void add(E x);
Iterator<E> iterator();
}
public interface Iterator<E> {
E next();
boolean hasNext();
}
public interface IntegerList {
void add(Integer x)
Iterator<Integer> iterator();
}
- parti tra parentesi angolate sono parametri formali della classe
generica; tipico identificatore: singola lettera maiuscola
- List<Integer> e Iterator<Integer> sono invocazioni della classe
generica, con parametro attuale Integer
- NB: non si crea una classe nuova (nessuna duplicazione di codice)
così come non si crea nuovo codice quando si invoca un metodo
passandogli i parametri attuali
12
Genericità e Sottotipi
• Attenzione: alcune cose sembrano andare contro l’intuizione
List<String> ls = new ArrayList<String>();
List<Object> lo = ls;
// ERRORE IN COMPILAZIONE
lo.add(new Object());
String s = ls.get(0); // ERRORE: tenta di assegnare un Object a una String!
• Domanda fondamentale: una lista di String è una lista di Object?
– NO! Altrimenti tramite una variabile lista di Object si può inserire un Object
in una lista di String e quando si tenta di estrarre, tramite una variabile lista
di String, un oggetto String, si verifica un errore
• In generale, se Gen<T> è una classe generica e se ClassB è
sottoclasse di ClassA allora Gen<ClassB> NON è sottoclasse di
Gen<ClassA>
• (NB: a maggior ragione una lista di Object NON è sottoclasse di una lista di
String)
13
Genericità e Sottotipi: i tipi jolly (1)
• Rimane problema di definire sottoclassi di classi ottenute per
invocazione di classi generiche, per realizzare polimorfismo, e.g.,
nei metodi che hanno parametri contenitori
• Esempio: un metodo che stampi tutti gli elementi di una collezione
void printCollection(Collection<Object> c) {
for (Object e : c) { System.out.println(e);}
}
– Non va: parametro attuale deve essere stesso tipo o sottotipo, ma
Collection<Object> non ha alcun sottotipo  nessun polimorfismo
• Occorre definire il tipo supertipo di tutte le collezioni ottenute per
invocazione di Collection<E>
– questo è Collection<?> (leggi: “Collection di sconosciuto”)
void printCollection(Collection<?> c) {
for (Object e : c) { System.out.println(e);}
}
14
Genericità e Sottotipi: i tipi jolly (2)
• L’inserzione di elementi NON è possibile!
Collection<?> c;
c = new ArrayList<String>();
c.add(new Object()); // errore di compilazione
– NB: il tipo statico di c dice che il tipo dell’elemento della collezione è sconosciuto
(può essere qualsiasi)  tipo del parametro attuale di add deve essere sottotipo di
qualsiasi altro tipo  non esiste tale tipo; unico valore attuale ammissibile è null
– NB: è comunque possibile fare una c.get() e assegnare il risultato a una variabile di
tipo Object, perchè qualsiasi cosa estratto dalla get è un Object.
15
Tipi jolly limitati
•
Ad esempio
– Per definire un metodo drawAll che accetti liste di qualsiasi sottotipo di Shape
public void drawAll(List<? extends Shape> shapes) { ... }
•
<? extends Shape> è un esempio di jolly limitato
– Rappresenta un tipo sconosciuto, di cui si sa che estende Shape
– Shape è il suo limite superiore (upper bound)
classe Shape
•
Solito problema con gli inserimenti
public void addRectangle(List<? extends Shape> shapes) {
shapes.add(0, new Rectangle()); // Errore: shapes di fatto
// è in sola lettura
}
– perchè il tipo del componente del parametro shapes è un sottotipo sconosciuto di
Shape: non è garantito che sia un supertipo di Rectangle
16
Metodi Generici (1)
• Es: Metodo che travasa tutti gli oggetti di un array in una collezione
static void fromArrayToCollection(Object[] a, Collection<Object> c) {
for (Object o : a) { c.add(o); }
}
– Non funziona: Perchè?
static void fromArrayToCollection(Object[] a, Collection<?> c) {
for (Object o : a) { c.add(o); }
}
– Non funziona neanche questo: Perchè?
• Il modo giusto è usare metodi generici, che hanno uno o più parametri che rappresentano
tipi.
static <T> void fromArrayToCollection(T[] a, Collection<T> c) {
for (T o : a) { c.add(o); }
}
– per rendere corretta l’inserzione c.add(o) dobbiamo chiamare fromArrayToCollection con
parametri in cui il tipo dell’elemento della collezione sia supertipo di quello dell’array
– NB: non occorre indicare esplicitamente parametri attuali in corrispondenza ai parametri
formali di un metodo generico:
• ci pensa il compilatore a inferire il tipo del parametro attuale scegliendo il tipo più
specifico (il minimo, nell’ordinamento tra tipi definito dalla gerarchia di ereditarietà, tra
tutti quelli che rendono legale l’invocazione del metodo generico)
17
Metodi Generici (2)
•Esempi di inferenza dei tipi da parte del
compilatore
String[] sa = new String[100];
Collection<String> cs = new ArrayList<String>();
fromArrayToCollection(sa, cs);// T inferred to be String
Collection<Object> co = new ArrayList<Object>();
fromArrayToCollection(sa, co);// T inferred to be Object
Integer[] ia = new Integer[100];
fromArrayToCollection(ia, cs);// compile-time error: String NON è
supertipo di Integer
18
Metodi generici vs jolly (1)
•
Possono apparire intercambiabili:
interface Collection<E> {
public boolean containsAll(Collection<?> c);
public boolean addAll(Collection<? extends E> c);
}
interface Collection<E> {
public <T> boolean containsAll(Collection<T> c);
public <T extends E> boolean addAll(Collection<T> c);
}
•
•
Quale dei due stili è preferibile?
Notiamo che
–
–
–
Nei due metodi il parametro T compare una sola volta, non vincola il valore restituito dal metodo e gli
altri parametri del metodo
T serve solo per il polimorfismo, ma per questo basterebbero i tipi Jolly
I metodi generici servono per esprimere dipendenze tra gli argomenti del metodo oppure tra gli
argomenti e il tipo restituito
19
Metodi generici vs jolly (2)
• Possibile anche l’uso combinato dei due
class Collections {
public static <T> void copy(List<T> destinazione,
List<? extends T> sorgente){...}
}
• alternativamente, senza tipi jolly
class Collections {
public static <T, S extends T> void copy(List<T> dest,
List<S> src){...}
}
20