Marco Faella » 14.La libreria Java Collection Framework: le interfacce Iterable, Collection e Set

Il Java Collection Framework

Java Collection Framework (JCF) è una parte della libreria standard dedicata alle collezioni, intese come classi deputate a contenere altri oggetti.
Questa libreria offre strutture dati di supporto, molto utili alla programmazione, come liste, array di dimensione dinamica, insiemi, mappe associative (anche chiamate dizionari) e code.

Le classi e interfacce del JCF si dividono in due gerarchie:

1. quella che si diparte dall’interfaccia Collection;
2. e quella che si diparte da Map.

Inoltre, la classe Collections (si noti la “s” finale) contiene numerosi algoritmi di supporto, ad esempio, metodi che effettuano l’ordinamento.

L’interfaccia Collection estende la versione parametrica di Iterable, che andiamo ad introdurre.

La versione parametrica di Iterator e Iterable

Ora che abbiamo introdotto la programmazione parametrica, possiamo svelare che le interfacce Iterator e Iterable sono, in realtà, parametriche.
La loro definizione è la seguente:

public interface Iterator {
public E next();
public boolean hasNext();
public void remove();
}

public interface Iterable {
public Iterator iterator();
}

Lo scopo ultimo del parametro di tipo consiste nel permettere al metodo next di restituire un oggetto del tipo appropriato, evitando che il chiamante debba ricorrere ad un cast.

Il ciclo for-each

Java 1.5 ha introdotto anche un nuovo tipo di ciclo for, chiamato ciclo “for each”.
Cominciamo con un esempio:

String[] array = {"uno", "due", "tre"};
for (String s: array)
System.out.println(s);

Il ciclo di sopra stampa tutte le stringhe contenute nell’array, una per rigo.
Questa nuova forma di ciclo permette di iterare su un array senza dover esplicitamente utilizzare un indice, quindi senza il rischio di sbagliare gli estremi dell’iterazione.

Oltre che per gli array, il ciclo for-each funziona anche su tutti gli oggetti che implementano Iterable<E>, come illustrato nella prossima slide.

Il ciclo for-each (segue)

Se un oggetto x appartiene ad una classe che implementa Iterable< A >, per una data classe A, è possibile scrivere il seguente ciclo:

for (A a: x) {
// corpo del ciclo
...
}

Il ciclo di sopra è equivalente al blocco seguente:

Iterator< A > it = x.iterator();
while (it.hasNext()) {
A a = it.next();
// corpo del ciclo
...
}

È evidente che la nuova forma di ciclo semplifica molto la vita al programmatore, allo stesso tempo riducendo drasticamente il rischio di scrivere codice errato.

Esercizio (esame 23/2/2007)

Definire una classe Primes che rappresenta l’insieme dei numeri primi.
Il campo statico “all” fornisce un oggetto su cui si può iterare, ottenendo l’elenco di tutti i numeri primi.
Non deve essere possibile creare oggetti di tipo Primes.

L’implementazione deve rispettare il seguente esempio d’uso:

for (Integer i: Primes.all) {
if (i > 20) break;
System.out.println(i);
}

Output dell’esempio d’uso:
1
3
5
7
11
13
17
19

Esercizio (esame 23/2/2007) (segue)

Prima di presentare una soluzione, discutiamo brevemente della sua progettazione.

La traccia richiede che “all” sia un campo statico.
È naturale che sia anche “public”, per essere visto dall’esterno, e “final”, in modo che non possa essere modificato.
Inoltre, in base al caso d’uso, deve puntare ad un oggetto che implementi Iterable<Integer>.

Per quanto riguarda la richiesta che la classe Primes non sia instanziabile, si può ottenere questo risultato dichiarandola astratta, oppure dotandola di un solo costruttore, privato.

La prossima slide presenta una possibile implementazione.

Si noti l’utilizzo di due classi anonime annidate, una per implementare Iterable e l’altra per implementare Iterator.

Esercizio (esame 23/2/2007) (segue)

L’interfaccia Collection<E>

Come dice il nome, una collection rappresenta un insieme di oggetti. L’interfaccia ha un parametro di tipo che indica il tipo degli oggetti contenuti. I metodi principali dell’interfaccia sono i seguenti:

• int size()
  • restituisce il numero di oggetti contenuti.
• boolean isEmpty()
  • restituisce vero se e solo se la collezione è vuota.
• boolean add(E x)
  • aggiunge x alla collezione, se possibile;
  • restituisce vero se e solo se x è stato aggiunto con successo.
• boolean contains(Object x)
  • restituisce vero se e solo se la collezione contiene un oggetto uguale (nel senso di equals) ad x.
• boolean remove(Object x)
  • rimuove l’oggetto x (o un oggetto uguale ad x secondo equals) dalla collezione;
  • restituisce vero se e solo se un tale elemento era presente nella collezione.

Osservazioni

Come si vede, le collezioni fanno affidamento al metodo equals per identificare gli elementi, le implementazioni concrete di Collection usano anche altri metodi, come vedremo tra breve.

Per quanto riguarda il metodo add, il motivo per cui restituisce un valore booleano diventerà chiaro quando esamineremo alcune implementazioni concrete di Collection

Può sorprendere che i metodi contains e remove accettino Object invece del tipo parametrico E:

• lo fanno perché non si corre alcun rischio a passare a questi due metodi un oggetto di tipo sbagliato;
• semplicemente, entrambi i metodi restituiranno false, senza nessun effetto sulla collezione stessa;
• inoltre, in certi casi la possibilità di passare oggetti qualsiasi potrebbe tornare utile;
• ad esempio, potremmo trovarci in un metodo che ha a disposizione una Collection e che riceve dall’esterno un Object, che potrebbe essere una stringa;
• la firma di contains ci consente di passargli quest’oggetto, senza doverci preoccupare preventivamente di controllare se si tratta di una stringa o meno.

La classe TreeSet

TreeSet è un Set implementato internamente come albero di ricerca bilanciato.
Gli elementi devono essere dotati di una relazione d’ordine, in uno dei seguenti modi:

• gli elementi devono implementare l’interfaccia Comparable; in questo caso, si può utilizzare il costruttore di TreeSet senza argomenti;

oppure

• bisogna passare al costruttore di TreeSet un opportuno oggetto Comparator; il parametro di tipo “? super E” che compare nella firma del costruttore che accetta Comparator sarà spiegato nelle lezioni successive.

Le operazioni principali di TreeSet hanno la seguente complessità di tempo, tipica degli alberi di ricerca bilanciati:

size    O(1)
isEmpty    O(1)
add    O(log n)
contains    O(log n)
remove    O(log n)

Coerenza tra ordinamento ed uguaglianza

TreeSet utilizza un ordinamento, fornito da Comparable o da Comparator, per smistare e poi ritrovare gli elementi all’interno dell’albero.
Allo stesso tempo, come previsto dall’interfaccia Set, viene usato il metodo equals per identificare gli elementi.
Se l’ordinamento non è coerente con l’uguaglianza definita da equals, la struttura dati può comportarsi in modo imprevedibile.

Consideriamo il caso di Comparable.
Per ogni coppia di elementi x e y, in aggiunta alle normali proprietà di equals e compareTo, deve valere la seguente condizione:

x.equals(y) è vero se e solo se x.compareTo(y) == 0

Una condizione analoga deve valere nel caso venga fornito un oggetto di tipo Comparator.