Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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)


Interfacce legate a Collection

Il diagramma in figura illustra le interfacce direttamente collegate con Collection.
Abbiamo già detto che Collection estende Iterable, e quindi fornisce un metodo che restituisce un iteratore.
La prossima slide illustra gli altri metodi elencati nella figura.

Collection viene estesa dalle tre interfacce parametriche Set, List e Queue.

  • Set rappresenta un insieme in senso matematico
    • non sono ammessi duplicati
    • gli elementi al suo interno non vengono mantenuti in ordine;
  • List rappresenta un vettore
    • sono ammessi duplicati
    • gli elementi al suo interno vengono mantenuti nello stesso ordine in cui sono stati inseriti;
  • Queue rappresenta una coda.
Le interfacce direttamente collegate con Collection.

Le interfacce direttamente collegate con Collection.


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.

L’interfaccia Set e le sue implementazioni

L’interfaccia Set non aggiunge metodi a Collection. Tuttavia, restringe, ovvero rende più specifici, i contratti di alcuni metodi, come add.
La specificità di un Set, rispetto ad una Collection generica, è che un Set non può contenere elementi duplicati.
Quindi, se si tenta di aggiungere con add un elemento che è già presente (ovvero, un oggetto che risulta uguale, secondo equals, ad uno già presente), la collezione non viene modificata e add restituisce false.

L’interfaccia SortedSet, che estende Set, rappresenta un insieme sui cui elementi è definita una relazione d’ordine (totale).
L’iteratore di un SortedSet garantisce che gli elementi saranno visitati in ordine, dal più piccolo al più grande.
Inoltre, un tale insieme dispone di due metodi extra:

  • first restituisce l’elemento minimo tra quelli presenti nella collezione;
  • last restituisce l’elemento massimo;
  • questi due metodi non modificano la collezione.
Le classi e interfacce che derivano da Set.

Le classi e interfacce che derivano da Set.


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.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion