Metodologie di Programmazione: Lezione 7
Nella programmazione si presenta spesso la necessità di gestire un insieme, una lista, una coda, ovvero, qualche tipo di collezione di oggetti. Per rispondere a queste esigenze la piattaforma Java mette a disposizione dei programmatori il framework denominato Collections, nel package java.util. Si tratta di un insieme ben organizzato di interfacce, classi astratte e classi concrete che, anche grazie alla genericità, fornisce un valido aiuto in tutti i casi in cui c'è bisogno di usare qualche tipo di collezione di oggetti.
In questa lezione completiamo inoltre il discorso sulla genericità introducendo le wildcard e discutendo i vantaggi che offrono.
Il seguente diagramma mostra le principali classi ed interfacce del framework Collections:
Le interfacce sono quelle più chiare con contorno tratteggiato, le classi astratte sono un po' più scure ma sempre con contorno tratteggiato e infine le classi concrete hanno il contorno continuo e sono le più scure. Le frecce indicano le relazioni di estensione/implementazione, ovvero se c'è una freccia da B a A, allora B è un sotto-tipo di A. Ecco una breve panoramica di ognuna delle interfacce e poi delle classi del diagramma.
Iterable<E>Collection<E>add, contains, remove, size, etc. Rappresenta una collezione generica che può contenere anche ripetizioni dello stesso elemento e gli elementi non hanno alcun ordinamento.Set<E>SortedSet<E>List<E>Queue<E>Deque<E>1Map<K,V>Collection<E>. Le mappe sono analoghe ai dizionari di Python.AbstractCollection<E>, AbstractSet<E>, AbstractList<E>, AbstractMap<E>HashSet<E>Set<E> tramite tabelle hash.ArrayList<E>List<E> tramite array.TreeSet<E>SortedSet<E> tramite alberi binari di ricerca bilanciati.LinkedList<E>List<E>, Queue<E> e Deque<E> tramite liste bidirezionali (doubly-linked list). Quindi permette di rappresentare non solo strutture FIFO, cioè code, ma anche strutture LIFO, cioè pile e liste.ArrayDeque<E>Queue<E> e Deque<E> tramite array. Dovrebbe essere più veloce di LinkedList<E> quando è usata come coda.HashMap<K,V>Map<K,V> tramite tabelle hash.
Consideriamo ora più dettagliatamente quelle tra queste interfacce e classi che sono maggiormente usate.
Collection<E>Per prima cosa è bene ricordare che in tutte le collezioni (comprese le mappe) gli elementi sono sempre confrontati tramite il metodo equals. Vediamo i principali metodi, cioè i più importanti e i più usati, dell'interfaccia di base e che sono quindi implementati dalle classi concrete HashSet<E>, ArrayList<E>, TreeSet<E>, LinkedList<E>, ArrayDeque<E>.
boolean add(E elem)elem alla collezione. Se la collezione permette duplicati, il metodo ritorna sempre true. Se invece la collezione non permette duplicati (come Set), e un elemento equivalente ad elem è già presente, il metodo ritorna false.boolean contains(Object elem)true se la collezione contiene un elemento equivalente a elem. Altrimenti ritorna false.boolean remove(Object elem)elem dalla collezione e ritorna true se un'occorrenza di tale elemento è stata rimossa. Altrimenti ritorna false.int size()Iterator<E> iterator()
Si sarà notato che i metodi contains e remove, a differenza del metodo add, accettano un Object e questo contrasta, in un qualche modo, l'assunzione che la collezione contenga solamente elementi di tipo E. Tuttavia, ci sono due ragioni che hanno portato i progettisti del framework ad adottare tale scelta. La prima ha a che fare con l'agevolare la migrazione del codice scritto antecedentemente all'introduzione della genericità. La seconda è di evitare alcune difficoltà di utilizzo della definizione più stringente dei due metodi (con il tipo E al posto del tipo Object) che si possono presentare in certe circostanze2.
List<E>L'interfaccia List<E> estende l'interfaccia di base per rappresentare una collezione in cui ogni elemento è in una ben precisa posizione. Le posizioni di una lista list sono numerate da 0 fino a list.size() - 1. In altre parole la collezione rappresentata è una sequenza di elementi. Questo richiede che il contratto di alcuni metodi sia raffinato. Ad esempio, il metodo add aggiunge l'elemento alla fine della sequenza e il metodo iterator ritorna un iteratore che scandisce gli elementi secondo l'ordine della sequenza. I principali metodi aggiunti dall'interfaccia List<E> sono i seguenti:
void add(int index, E elem)elem in posizione index spostando di una posizione in avanti tutti gli elementi che si trovavano nelle posizioni da index in poi.E set(int index, E elem)index con elem e ritorna l'elemento sostituito.E get(int index)index.E remove(int index)index. Gli eventuali elementi successivi sono spostati di una posizione indietro.
In tutti i casi se l'indice non è compreso tra 0 e list.size() - 1, i metodi lanciano una eccezione.
La classe ArrayList<E> fornisce una semplice implementazione dell'interfaccia tramite array. Mentre LinkedList<E> è una implementazione tramite liste linkate.
Nel seguito useremo spesso List<E> e le sue implementazioni, sopratutto ArrayList<E>, perciò non vedremo esempi adesso.
Set<E>L'interfaccia Set<E> non aggiunge metodi all'interfaccia di base ma semplicemente rende più specifico il contratto di alcuni metodi. I metodi che aggiungono elementi (il metodo add e simili) non permettono di aggiungere duplicati.
La classe HashSet<E> implementa l'interfaccia tramite tabelle hash. Una tabella hash mantiene gli elementi suddivisi in tanti bucket in base ai valori hash degli elementi. Il valore hash (o codice hash) di un elemento determina quindi in quale bucket l'elemento sarà inserito. Sempre il valore hash permette quindi di velocizzare la ricerca di un elemento perché una volta calcolato si dovrà effettuare la ricerca dell'elemento solamente nel bucket relativo a quel valore hash. Il valore hash di un elemento è una specie di impronta dell'elemento. Una proprietà che si deve rispettare è che due elementi uguali, secondo il metodo equals, devono avere lo stesso valore hash, altrimenti si rischia che un elemento mantenuto in una tabella hash potrebbe non essere ritrovato. Il valore hash di un elemento è ottenuto dal seguente metodo della classe Object:
public int hashCode()
Se il metodo hashCode non è ridefinito ritorna un valore intero che è ricavato dall'indirizzo fisico dell'oggetto e che risulta, generalmente, differente per due oggetti che hanno indirizzi differenti. Perciò, una classe che ridefinisce il metodo equals dovrebbe anche ridefinire il metodo hashCode (se si prevede che gli oggetti della classe possano essere usati in una tabella hash) in modo da garantire che oggetti equivalenti abbiano lo stesso valore hash. Se ci sono elementi equivalenti che non hanno lo stesso valore hash questo può provocare un funzionamento non corretto della tabella hash e quindi anche della classe HashSet<E>. Lo stesso discorso vale per qualsiasi implementazione che usa le tabelle hash, come ad esempio HashMap<K,V>. Ad esempio, la classe String ridefinisce hashCode proprio per garantire che stringhe uguali abbiano lo stesso codice hash. Di solito il valore ritornato è una combinazione derivata dai valori dei campi che rappresentano lo stato di un oggetto. Per facilitare il calcolo di una tale combinazione si può usare il metodo Objects.hash.
A differenza di altri linguaggi come Python che non permettono che gli elementi di un insieme (o le chiavi di una mappa, dizionario) possano essere mutabili, Java lo permette. Però se un elemento mutabile viene modificato dopo che è stato inserito in un insieme, il buon comportamento dell'insieme non è più garantito.
Vediamo ora un semplice esempio d'uso di Set che sfrutta proprio la caratteristica di non contenere duplicati. Vogliamo scrivere un metodo che ritorna l'insieme delle sotto-stringhe di una di una stringa di testo che sono composte solamente da lettere. Definiamo i metodi che seguono nella classe mp.Utils perché potrebbero risultare utili in futuro. Prima di tutto ci serve un piccolo metodo per determinare se una stringa è composta solamente da lettere:
/** Ritorna {@code true} se la stringa contiene solamente lettere secondo il
* metodo {@link java.lang.Character#isLetter}.
* @param s una stringa
* @return {@code true} se la stringa contiene solamente lettere */
public static boolean isWord(String s) {
for (int i = 0 ; i < s.length() ; i++)
if (!Character.isLetter(s.charAt(i)))
return false;
return true;
}
/** Ritorna l'insieme delle sotto-stringhe di una data stringa che hanno una
* data lunghezza e sono composte solamente da lettere.
* @param s una stringa
* @param len lunghezza delle sotto-stringhe
* @return l'insieme delle sotto-stringhe */
public static Set<String> subwords(String s, int len) {
Set<String> subSet = new HashSet<>();
for (int i = 0 ; i <= s.length() - len ; i++) {
String sub = s.substring(i, i + len);
if (isWord(sub)) subSet.add(sub);
}
return subSet;
}
Si osservi che la variabile subSet è stata dichiarata di tipo Set<String> anche se il tipo effettivo è HashSet<String>. Questo non è casuale ed è invero una buona prassi quella di dichiarare una variabile del tipo più generale possibile compatibilmente con il suo utilizzo. Infatti così si evita di legare inutilmente il codice a una particolare implementazione, in questo caso a quella di HashSet.
Possiamo scrivere un metodo per mettere alla prova subwords:
private static void test_subwords() {
Scanner input = new Scanner(System.in);
out.print("Test metodo subwords(), digita una linea di testo: ");
String line = input.nextLine();
out.print("Digita la lunghezza delle sotto-stringhe: ");
int len = input.nextInt();
out.println(subwords(line, len));
}
Provandolo
Test metodo subwords(), digita una linea di testo: tre tigri contro tre tigri
Digita la lunghezza delle sotto-stringhe: 3
[tro, tig, con, ont, igr, tre, ntr, gri]
Come si vede non sono mantenute nell'insieme le ripetizioni delle sotto-stringhe. Inoltre, si noti che il metodo toString in HashSet è opportunamente ridefinito.
Map<K,V>L'interfaccia Map<K,V> non estende l'interfaccia di base Collection<E> perché ciò che è rappresentato, cioè una mappa, si differenzia da una collezione sotto vari aspetti. La differenza principale sta nel fatto che non si aggiungono elementi ad una mappa ma coppie chiave-valore. Inoltre, una mappa permette di ritrovare il valore associato ad una data chiave. Una chiave o non ha valori associati o ha esattamente un valore associato. Mentre un valore può essere associato a più chiavi. Si pensi, ad esempio, ad una associazione persona-indirizzo. Il nominativo (il codice fiscale) di una persona è una chiave a cui è associato il suo indirizzo di residenza. Chiaramente, ad ogni persona (chiave) possiamo associare al più un solo indirizzo (valore). Mentre, un indirizzo può essere associato a più persone. I principali metodi dell'interfaccia Map<K,V> sono i seguenti (K è il tipo delle chiavi e V è il tipo dei valori):
V put(K key, V value)key, value) alla mappa. Se la chiave key aveva già un valore associato questo è sostituito con il nuovo valore value e il vecchio valore è ritornato. Se non c'era una associazione precedente, aggiunge quella nuova e ritorna null.V get(Object key)key è associata o null se tale valore non c'è.boolean containsKey(Object key)true se la mappa contiene una associazione con la chiave key. A differenza del metodo get questo metodo permette di distinguere il caso in cui la chiave non ha un valore associato dal caso in cui ha associato il valore null.V remove(Object key)key e ritorna il valore che era associato alla chiave. Se la chiave non è associata a nessun valore, ritorna null.Set<K> keySet()remove dell'iteratore) il risultato dell'iterazione è indefinito. L'insieme ritornato supporta tutte le operazioni eccetto quelle di aggiunta di nuove chiavi.int size()
La classe HashMap<K,V> implementa l'interfaccia tramite tabelle hash. Quindi valgono le stesse considerazioni che sono state fatte in relazione a HashSet<E> per quanto riguarda i metodi hashCode e equals, in questo caso, relativamente agli oggetti chiave.
Vediamo un esempio che estende il metodo subwords (nella classe mp.Utils):
/** Ritorna una mappa che ad ogni sotto-stringa di lettere della stringa data e
* della lunghezza specificata associa il numero di occorrenze.
* @param s una stringa
* @param len lunghezza delle sotto-stringhe
* @return mappa che conta le occorrenze delle sotto-stringhe */
public static Map<String,Integer> subwordsCount(String s, int len) {
Map<String, Integer> count = new HashMap<>();
for (int i = 0 ; i <= s.length() - len ; i++) {
String sub = s.substring(i, i + len);
if (isWord(sub)) {
if (count.containsKey(sub))
count.put(sub, count.get(sub)+1);
else
count.put(sub, 1);
}
}
return count;
}
Per metterlo alla prova da tastiera possiamo scrivere il seguente metodo:
private static void test_subwordsCount() {
Scanner input = new Scanner(System.in);
out.print("Test metodo subwordsCount(), digita una linea di testo: ");
String line = input.nextLine();
out.print("Digita la lunghezza delle sotto-stringhe: ");
int len = input.nextInt();
out.println(subwordsCount(line, len));
}
Provandolo,
Test metodo subwordsCount(), digita una linea di testo: tre tigri contro tre tigri
Digita la lunghezza delle sotto-stringhe: 3
{tro=1, tig=2, con=1, ont=1, igr=2, tre=2, ntr=1, gri=2}
Come si vede, anche la classe HashMap<K,V> ridefinisce opportunamente il metodo toString.
Le mappe hanno una grande varietà di utilizzi. Sono ad esempio molto utili per implementare strutture come alberi o grafi. Il prossimo esempio mostra proprio un'implementazione di un albero i cui nodi possono essere di un tipo parametrico T. Per rappresentare un albero basta mantenere due mappe, una che associa ad ogni nodo la lista dei suoi figli e una che associa ad ogni nodo il suo genitore. Per concentrarci meglio sull'uso delle mappe nella seguente classe non abbiamo implementato i controlli relativi alle condizioni di errore.
package mp.util;
import java.util.*;
/** Un oggetto {@link HTree} rappresenta un albero. È implementato tramite
* {@link java.util.HashMap} e quindi gli oggetti che sono i nodi dell'albero
* dovrebbero avere un'adeguata definizione dei metodi {@link Object#equals} e
* {@link Object#hashCode}. Due oggetti che sono uguali (secondo
* {@link Object#equals}) non possono appartenere allo stesso albero.
* Per semplicità le condizioni di errore non sono state implementate.
* @param <T> tipo dei nodi dell'albero */
public class HTree<T> {
/** Crea un albero con la radice data.
* @param root la radice dell'albero */
public HTree(T root) {
this.root = root; // La radice
parent.put(root, null); // La radice ha come genitore null
children.put(root, new ArrayList<>()); // Figli della radice: la lista vuota
}
/** Aggiunge uno o più nodi a questo albero.
* @param p il nodo genitore dei nodi da aggiungere
* @param cc oggetti da aggiungere come nodi figli di p */
public void add(T p, T...cc) {
for (T c : cc) {
parent.put(c, p); // Imposta genitore del nuovo nodo
children.get(p).add(c); // Aggiunge nuovo nodo come figlio del genitore
children.put(c, new ArrayList<>()); // Figli nuovo nodo: la lista vuota
}
}
/** @return la radice di questo albero */
public T getRoot() { return root; }
/**Ritorna {@code true} se l'oggetto dato è un nodo di questo albero.
* @param u un oggetto
* @return {@code true} se l'oggetto è un nodo di questo albero */
public boolean isNode(T u) { return parent.containsKey(u); }
/** Ritorna il genitore del nodo dato.
* @param u un nodo di questo albero
* @return il genitore del nodo */
public T getParent(T u) { return parent.get(u); }
/** @return una vista non modificabile della lista dei figli del nodo dato */
public List<T> getChildren(T u) {
return Collections.unmodifiableList(children.get(u));
}
private T root; // Radice dell'albero
private final Map<T,T> parent = new HashMap<>(); // Mappa dei genitori
private final Map<T,List<T>> children = new HashMap<>(); // Mappa dei figli
}
Nel metodo getChildren per ritornare una vista non modificabile della lista dei figli di un nodo abbiamo usato il metodo Collections.unmodifiableList. La classe Collections, nel package java.util, offre molti metodi di utilità relativamente al framework Collections.
Abbiamo scritto la classe HTree<T> nel nuovo package mp.util perché è una classe di utilità generale e quindi dovrebbe essere in un package che è riservato a definizioni di questo tipo. Perciò anche la classe mp.Utils sarà spostata nel package mp.util.
Aggiungiamo alla classe anche un metodo che ritorna una stringa con una rappresentazione dell'intero albero:
/** @return una stringa che rappresenta l'intero albero */
public String toFullString() {
return toFullString(root, "");
}
private String toFullString(T u, String prefix) {
String s = (prefix.isEmpty() ? "" : prefix + "---");
s += u + "\n";
for (T c : getChildren(u))
s += toFullString(c, prefix + " |");
return s;
}
Abbiamo preferito non ridefinire toString con questo tipo di rappresentazione perché può ritornare una stringa molto grande.
Per provare la classe scriviamo un metodo che costruisce un albero di stringhe e lo stampa tramite toFullString:
private static void test_HTree() {
HTree<String> tree = new HTree<>("Computer Science");
tree.add("Computer Science", "Software", "Hardware");
tree.add("Hardware", "Memory", "Processor", "Architecture");
tree.add("Software", "Operating System", "Data Base", "Word Processing",
"Image Processing", "Algorithms", "Languages");
tree.add("Languages", "Procedural", "Functional", "Object Oriented");
tree.add("Procedural", "C", "Pascal");
tree.add("Object Oriented", "C++", "Java", "Smalltalk");
tree.add("Data Base", "SQL", "Data Mining");
tree.add("Operating System", "Unix", "Linux", "MacOS X");
out.println(tree.toFullString());
}
Se lo eseguiamo otteniamo,
Computer Science
|---Software
| |---Operating System
| | |---Unix
| | |---Linux
| | |---MacOS X
| |---Data Base
| | |---SQL
| | |---Data Mining
| |---Word Processing
| |---Image Processing
| |---Algorithms
| |---Languages
| | |---Procedural
| | | |---C
| | | |---Pascal
| | |---Functional
| | |---Object Oriented
| | | |---C++
| | | |---Java
| | | |---Smalltalk
|---Hardware
| |---Memory
| |---Processor
| |---Architecture
Le interfacce del framework Collections e le classi concrete che le implementano sono usatissime e le prossime lezioni non faranno eccezione.
Sappiamo che i tipi generici e più precisamente i tipi parametrici si comportano in modo diverso dagli array per quanto riguarda le relazioni di sotto-tipo e, simmetricamente, di super-tipo. Ricordiamo che se TypeB è un sotto-tipo di TypeA allora TypeB[] è un sotto-tipo di TypeA[], mentre GenType<TypeB> non è un sotto-tipo di GenType<TypeA> (a meno che TypeA non coincida con TypeB), dove GenType<T> è un qualsiasi tipo generico. Ciò è necessario affinché si possa garantire un controllo statico sui tipi parametrici. Però in alcune situazioni, come nel caso del metodo min visto nella lezione scorsa, sarebbe utile avere un modo, dato un tipo Type, per riferirsi a un qualsiasi tipo parametrico GenType<SubT> tale che SubT è un sotto-tipo di Type, o anche a un qualsiasi tipo parametrico GenType<SuperT> tale che SuperT è un super-tipo di Type. Il linguaggio Java permette di fare ciò con la sintassi delle wildcards:
<? extends Type>Type.<? super Type>Type.<?>Object, quindi un qualsiasi tipo riferimento senza restrizioni. È equivalente a <? extends Object>.
La wildcard è rappresentata dal carattere ? e Type può essere un tipo effettivo, una variabile di tipo o un tipo generico. La wildcard non è una variabile di tipo perché la sua visibilità è ristretta alle parentesi angolari in cui è usata. Le espressioni con wildcards possono essere usate ovunque si può usare il nome di un tipo, con alcune eccezioni che discuteremo fra poco.
Se ci occorre un metodo generico che stampa gli elementi di una lista di tipo List potremmo scriverlo così:
public static <T> void printList(List<T> list) {
for (T e : list) System.out.println(e);
}
Però la variabile di tipo T è usata solamente per denotare il tipo della lista. In questi casi può essere sostituita con una wildcard:
public static void printList(List<?> list) {
. . .
}
Questa versione è del tutto equivalente a quella che usa la variabile di tipo. In tutti i casi come questo, in cui una variabile di tipo è usata una sola volta (cioè, non ci sono dipendenze legate a tale variabile) si preferisce sostituirla con una wildcard.
Il metodo addAll dell'interfaccia Collection<E> e quindi ereditato da List<E> ha la seguente intestazione:
boolean addAll(Collection<? extends E> c)
Questa permette la massima generalità nell'aggiunta degli elementi di una collezione a una lista (o più in generale a una collezione) senza contravvenire al contratto. Mentre se l'intestazione fosse stata
boolean addAll(Collection<E> c)
Allora il seguente frammento di codice non sarebbe corretto
List<Dipendente> listD = . . .
List<Dirigente> listDir = . . .
listD.addAll(listDir); // ERRORE in compilazione
Infatti si avrebbe un errore in compilazione dovuto la fatto che List<Dirigente> non è un sotto-tipo di Collection<Dipendente>. Eppure se avessimo aggiunto alla lista listD gli elementi di listDir uno ad uno l'operazione sarebbe stata ammissibile. Invece con l'intestazione originale l'errore non c'è più.
Grazie alla possibilità della limitazione super della wildcard possiamo riscrivere il metodo generico min della scorsa lezione:
public static <T extends Comparable<? super T>> T min(T[] a) {
. . .
}
Con questa nuova definizione il seguente frammento di codice è legale:
Dirigente[] dirA = new Dirigente[] {new Dirigente("Carla Bo", 100),
new Dirigente("Luisa Lalla", 200)};
Dirigente minDir = min(dirA); // OK
È importante notare che, a differenza della limitazione extends che può essere applicata anche a variabili di tipo, la limitazione super può essere usata solamente con una wildcard.
Le espressioni che usano wildcard rappresentano dei tipi che sono chiamati tipi wildcard (wildcard types). I tipi wildcard hanno relazioni di sotto-tipo/super-tipo tra loro e con i tipi parametrici ordinari. Il seguente diagramma mostra alcuni esempi di queste relazioni per wildcard con la limitazione extends:
-----------
| Pair<?> |
-----------
Δ
|
------------------------------------------
| |
---------------- --------------------------
| Pair<Object> | | Pair<? extends Number> |
---------------- --------------------------
Δ
|
----------------------------------
| |
--------------------------- ----------------
| Pair<? extends Integer> | | Pair<Number> |
--------------------------- ----------------
Δ
|
-----------------
| Pair<Integer> |
-----------------
Il tipo Number in java.lang è un super-tipo di tutti i tipi numerici come Integer, Short, Double ecc.
Relazioni simmetriche valgono anche per wildcard con la limitazione super:
-----------
| Pair<?> |
-----------
Δ
|
-------------------------
| Pair<? super Integer> |
-------------------------
Δ
|
--------------------------------------
| |
----------------- ------------------------
| Pair<Integer> | | Pair<? super Number> |
----------------- ------------------------
Δ
|
-------------------------
| |
---------------- ----------------
| Pair<Number> | | Pair<Object> |
---------------- ----------------
Vediamo ora alcuni esempi che mostrano le conseguenze di tali relazioni nella dichiarazione di variabili e nell'assegnamento di valori a variabili:
List<?> da = new ArrayList<?>(); // ERRORE in compilazione
List<Pair<?>> pairL = new ArrayList<>();
pairL.add(new Pair<Integer>(1, 2));
pairL.add(new Pair<String>("a", "b"));
Pair<Integer> intPair = null;
intPair = pairL.get(0); // ERRORE in compilazione
Pair<Object> objPair = pairL.get(1); // ERRORE in compilazione
Pair<?> unknown = pairL.get(0); // OK
List<Pair<? extends Number>> numPairL = new ArrayList<>();
numPairL.add(new Pair<Integer>(1, 2));
numPairL.add(new Pair<String>("a", "b")); // ERRORE in compilazione
intPair = numPairL.get(0); // ERRORE in compilazione
Pair<Number> numPair = numPairL.get(0); // ERRORE in compilazione
Pair<? extends Number> extNumPair = numPairL.get(0); // OK
extNumPair = intPair;
Pair<? super Integer> supIntPair = numPair;
supIntPair = extNumPair; // ERRORE in compilazione
Pair<? super Number> supNumPair = null;
supIntPair = supNumPair;
supNumPair = supIntPair; // ERRORE in compilazione
unknown = supIntPair;
unknown = extNumPair;
supIntPair = objPair;
La prima riga mostra che i tipi wildcard non possono essere usati in espressioni creazionali però, come mostra la seconda riga, possono essere usati se sono nidificati. Tutti gli altri errori derivano dalla non validità di relazioni di sotto-tipo.
Le relazioni di sotto-tipo (e simmetricamente di super-tipo) per le diverse categorie di tipi, concreti, generici, parametrici, variabili e wildcard, non sono facili da capire. Si ricordi però il principio fondamentale che una relazione di sotto-tipo dovrebbe soddisfare:
se
Bè un sotto-tipo diA, allora in un qualsiasi contesto un oggetto di tipoApuò sempre essere sostituito con un oggetto di tipoB(senza che questo provochi errori dovuti ai tipi).
Tale principio è chiamato principio di sostituzione di Liskov, o brevemente LSP (Liskov Substitution Principle). Se c'è anche un solo contesto in cui tale principio non vale, il tipo B non dovrebbe3 essere un sotto-tipo di A. L'introduzione della genericità in Java è stata effettuata garantendo la validità di LSP.
Quando si hanno dei dubbi circa la relazione di sotto-tipo tra due tipi si può cercare di immaginare dei contesti d'uso per i due tipi e controllare la validità di LSP. Ad esempio, per Pair<Object> e Pair<String> si può considerare il contesto
Pair<Object> o = new Pair<>(null,null);
o.setFirst(12);
Se Pair<String> fosse un sotto-tipo di Pair<Object>, potremmo assegnare alla variabile o un oggetto di tipo Pair<String>, ma ciò renderebbe l'invocazione o.setFirst(12) errata. Per cui Pair<String> non può essere un sotto-tipo di Pair<Object>.
Per i tipi Pair<Object> e Pair<?> si può considerare il contesto
Pair<?> u = Pair<String>("","");
Pair<Object> o = new Pair<>(null,null);
o.setFirst(12);
Se Pair<?> fosse un sotto-tipo di Pair<Object>, potremmo assegnare alla variabile o l'oggetto in u, ma ciò renderebbe l'invocazione o.setFirst(12) errata. Si noti che Pair<?> può essere descritto come una coppia i cui valori sono di un qualsiasi tipo ma tale tipo è fissato e non può essere modificato, invece Pair<Object> è una coppia i cui valori possono avere qualsiasi tipo. Così ad una coppia di tipo Pair<Object> possiamo assegnare valori di qualsiasi tipo alle due componenti, invece ad una coppia di tipo Pair<?> possiamo assegnare, alle componenti, solamente il valore null, cioè l'unico valore compatibile con qualsiasi tipo (riferimento). Infatti
Pair<?> u = new Pair<Object>(null,null); // OK
u.setFirst(""); // ERRORE in compilazione
u.setFirst(12); // ERRORE in compilazione
u.setFirst(null); // OK
[ErroriW1] Il seguente codice Java contiene uno o più errori. Trovare gli errori e spiegarli. In particolare, dire per ogni errore se si verifica in compilazione o durante l'esecuzione.
public class Test {
public static void main(String[] args) {
List<String> strL = new ArrayList<>();
strL.add("a");
List<?> list = strL;
list.add("b");
Object o = list.get(0);
String s = list.get(0);
List<? extends String> sL = strL;
sL.add("c");
String s2 = sL.get(0);
}
}
[ErroriW2] Il seguente codice Java contiene uno o più errori. Trovare gli errori e spiegarli. In particolare, dire per ogni errore se si verifica in compilazione o durante l'esecuzione.
public class Test {
public static void main(String[] args) {
List<Integer> intL = new ArrayList<>();
intL.add(12);
List<? super Integer> supIL = intL;
supIL.add(1, 17);
Integer intO = supIDA.get(0);
List<?> da = new ArrayList<? extends Integer>();
List<?> da2 = new ArrayList<List<?>>();
}
}
[Unione] Definire un metodo generico che prende in input due insiemi di tipo Set crea e ritorna un nuovo insieme che contiene l'unione degli elementi dei due insiemi. Il metodo dovrebbe essere il più flessibile possibile.
[Intersezione] Definire un metodo generico che prende in input due insiemi di tipo Set crea e ritorna un nuovo insieme che contiene l'intersezione degli elementi dei due insiemi. Il metodo dovrebbe essere il più flessibile possibile.
[Max] Definire un metodo generico che preso in input una lista di tipo List ritorna il valore massimo della lista. Come al solito, massimizzare la flessibilità del metodo.
[ContaRipetizioni] Scrivere un metodo generico <E> Map<E,Integer> countRep(Collection<E> coll) che ritorna una mappa che associa ad ogni elemento distinto della collezione coll il numero di volte che occorre nella collezione.
[RimuoviArray] Definire un metodo generico che preso in input una collezione di tipo Collection e un array di elementi dello stesso tipo di quelli della collezione, rimuove dalla collezione tutti gli elementi presenti nell'array (comprese tutte le eventuali ripetizioni).
[Slice] Scrivere un metodo generico <E> void slice(List<E> list, int i, int j, E...elems) che sostituisce la sotto-lista di list compresa tra gli indici i e j escluso, con gli elementi elems. Gestire anche le condizioni di errore.
[RimuoviRipetizioni] Definire un metodo generico che prende in input una lista, di tipo List, e rimuove da essa tutte le eventuali ripetizioni di elementi, mantenendo l'ordine originale per gli elementi rimanenti.
[ListToMap] Definire un metodo generico che prende in input una lista generica (di tipo List) e crea e ritorna una mappa le cui chiavi sono gli elementi distinti della lista e il valore associato ad una chiave k è la lista degli indici della lista di input in cui l'elemento k compare. Il tipo ritornato non deve dipendere dall'implementazione della mappa o delle liste. Ecco un esempio:
Lista di input (lista di stringhe):
("A", "B", "A", "C", "C", "D")
Mappa di output:
{("A", (0, 2)), ("B", (1)), ("C", (3, 4)), ("D", (5))}
[ListaDiListe] Definire un metodo generico che prende in input una matrice e crea e ritorna una lista di liste (di tipo List) che rappresenta la matrice. Ogni sotto-lista contiene gli elementi della corrispondente riga della matrice di input. La matrice può avere righe di lunghezze differenti. Il tipo ritornato non deve dipendere dalla particolare implementazione usata per le liste.
[Threshold] Definire un metodo generico che prende in input una mappa generica m (di tipo Map<...>) e un valore t dello stesso tipo dei valori della mappa e ritorna una nuova mappa dello stesso tipo di m che contiene esattamente tutte le associazioni di m che hanno valore maggiore od uguale alla soglia t. Ecco un esempio:
Mappa di input Map<String, Integer> e soglia 5:
{("A", 2), ("B", 5), ("C", 4), ("D", 6), ("F", 6)}
Mappa di output:
{("B", 5), ("D", 6), ("F", 6)}
Ovviamente, il metodo deve richiedere che il tipo dei valori implementi in modo opportuno l'interfaccia Comparable.
[HTreeCheck] Aggiungere alla classe HTree<T> tutti i controlli relativi alle condizioni di errore, ad esempio non si può ottenere la lista dei figli di un oggetto che non è un nodo dell'albero.
[AziendaAppList] Modificare l'implementazione di AziendaApp usando una lista (di tipo List) invece che un array per mantenere i dipendenti.
[Grafi] Definire una classe generica DGraph<T> per rappresentare grafi diretti i cui nodi sono di tipo parametrico T. Definire metodi per aggiungere nodi, archi, per scandire gli adiacenti (uscenti) di un nodo, per rimuovere archi e nodi.
Suggerimento: usare una mappa per rappresentare il grafo tramite liste di adiacenza: le chiavi sono i nodi e il valore associato ad un nodo è l'insieme dei suoi adiacenti (uscenti).
15 Mar 2016
Si pronuncia come deck.↩
Ad esempio se abbiamo una collezione Collection<Dirigente> e il metodo contains fosse definito con l'intestazione più stringente contains(E elem), non si potrebbe fare una ricerca passando al metodo una variabile d di tipo Dipendente. Però potrebbe essere utile poterlo fare dato che la variabile d può contenere anche oggetti di tipo Dirigente.↩
Abbiamo scritto “dovrebbe” invece di “deve” perchè, come sappiamo, LSP è violato in Java dalla covarianza degli array. ↩