Il tipo di dato Insieme (Set)

Un insieme è una collezione in cui gli elementi compaiono senza ripetizioni, e non sono organizzati in un ordine prefissato.

Le principali operazioni su insiemi sono le seguenti:

test sulla presenza di un elemento;

inserzione di una nuovo elemento;

eliminazione di un elemento.

Esistono inoltre le classiche operazioni insiemistiche (unione, intersezione, complemento), che non sempre sono presenti in una interfaccia minimalista.

Nella pratica, vi sono molti modi per realizzare un insieme ognuno con i suoi vantaggi e svantaggi.

La classe Vector può essere adattata allo scopo ma sorgono grossi problemi di efficienza (tipicamente la ricerca ha un costo lineare nel numero degli elementi).

Insiemi di numeri interi con un campo di variabilità limitato (fino a qualche miliardo).
Può essere consigliabile l'implementazione con un array di valori di verità (possibilmente utilizzando i singoli bit). Si richiede un elevata quantità di memoria. L'inserzione, la ricerca e la cancellazione hanno complessità costante; le operazioni insiemistiche sono costose.

Insiemi di oggetti con un campo di variabilità molto vasto (per esempio stringhe) e per cui non è importante una scansione in un ordine particolare, e non sono previste molte cancellazioni di elementi.
Può essere consigliabile l'implementazione con le tabelle hash. L'inserzione e la ricerca hanno complessità costante; le operazioni insiemistiche hanno complessità lineare.

Insiemi di oggetti con un campo di variabilità molto vasto (per esempio stringhe) e per cui è importante una scansione in un ordine particolare.
Può essere consigliabile l'implementazione con gli alberi binari di ricerca. L'inserzione, la ricerca e la cancellazione hanno complessità logaritmica nel numero di elementi; le operazioni insiemistiche hanno complessità lineare.

La classe BitSet

La classe java.util.BitSet implementa vettori di bit che aumentano se necessario. Ogni componente del BitSet è individuata da un intero nonnegativo ed è associata ad un valore booleano, memorizzato in un bit, a cui si può accedere individualmente.

Per una descrizione esauriente si rimanda alla documentazione ufficiale, qui ci limitiamo a segnalare i metodi principali.

I metodi
```
   void set(int i) 
   void clear(int i) 
```
rispettivamente pongono a true o a false il bit di indice i.
I metodi
```
   void set(int i, int j) 
   void clear(int i, int j) 
```
rispettivamente pongono a true o a false i bit tra l'indice i compreso e j escluso.
Il metodo
```
   boolean get(int i) 
```
restituisce il valore del bit di indice i.
Il metodo
```
   int nextSetBit(int i) 
```
restituisce il valore dell'indice del primo bit true dopo quello di indice i-1.

Attenzione BitSet non implementa l'interfaccia Set descritta nel seguito.

L'esempio che segue mostra come BitSet può essere usata per realizzare il crivello di Eratostene per il calcolo dei numeri primi.

/** * Calcola il numero di primi minori di n */ int crivello(int n){ BitSet primi = new BitSet(n); primi.set(2,n); int i=1; while (i*i<n) { i=primi.nextSetBit(i+1); for(int k=i*i; k<n; k+=i) primi.clear(k); } return primi.cardinality(); }

L'Interfaccia Set<T>

L'interfaccia java.util.Set<T> specifica il tipo Set con elementi di tipo .

Per una descrizione esauriente si rimanda alla documentazione ufficiale, qui ci limitiamo a segnalare i metodi principali.

Il metodo
```
   boolean contains(Object element) 
```
restituisce true se l'elemento è presente, false altrimenti.
Il metodo (opzionale)
```
   boolean add(T element) 
```
inserisce l'elemento element, viene reso true se l'elemento è stato aggiunto, false se era già presente.
Il metodo (opzionale)
```
   boolean remove(Object element) 
```
rimuove l'elemento element se presente, viene reso true se l'elemento è stato eliminato, false se non era presente.
Il metodo (opzionale)
```
   boolean addAll(Collection C),   
```
aggiunge gli elementi della Collection C se non presenti, (implementando così una variante della unione), viene reso true se l'insieme è stato modificato.
Il metodo (opzionale)
```
   boolean removeAll(Collection C),  
```
rimuove gli elementi della Collection C se presenti, (implementando così una variante della differenza), viene reso true se l'insieme è stato modificato.
Il metodo (opzionale)
```
   boolean retainAll(Collection C),  
```
conserva solo gli elementi della Collection C che sono presenti, (implementando così una variante della intersezione), viene reso true se l'insieme è stato modificato.
Inoltre, tra gli altri, vi sono i metodi: clear(), isEmpty(), size(), equals(), iterator(), dall'ovvio significato.

Si noti che alcune operazioni sono opzionali, ovvero non necessariamente presenti in tutte le implementazioni. Nel contesto del linguaggio Java, dire che un metodo di una interfaccia è opzionale significa che tale metodo deve essere comunque implementato, limitandosi a lanciare una UnsupportedOperationException

La classe HashSet

La classe HashSet implementa insiemi con le tabelle hash.

L'esempio che segue mostra come HashSet può essere usata per implementare un'insieme di stopwords. Ricordiamo che le stopword sono parole usate frequentemente, come la congiunzione "e", che non vengono prese in considerazione durante le operazioni di indicizzazione (per esempio vengono ignorate nelle interrogazioni dei motori di ricerca).

... HashSet<String> stopSet = new HashSet<String>(600); for(String word : stopArray)stopSet.add(word); ... String word; ... if(stopSet.contains(word)) ... // ignora la parola ... private final static String[] stopArray={ "able", "about", "above", "according", ..., "without", "wonder", "would", "your","yours", "yourself", "yourselves", "zero" }; ...

La classe TreeSet

La classe TreeSet implementa tabelle con gli alberi binari di ricerca. L'esempio che segue mostra come TreeSet può essere usata per eliminare i duplicati da un iteratore su una struttura (di elementi che implementano Comparable<T>) rendendo un iteratore che scorre i dati secondo l'ordine indotto dal metodo compareTo().

public Iterator<T> NoDup(Iterator<T> it){ Set<T> set = new TreeSet<T>(); for (;it.hasNext();) set.add(it.next()); return set.iterator(); }

Esercizi

1) Si scriva la classe SetTheory.java, che contiene i seguenti metodi:

public void union (Set<T> s1, Set<T> s2, Set<T> r)

che restituisce in r l'unione degli insiemi passati per argomento.

public void intersection(Set<T> s1, Set<T> s2, Set<T> r)

che restituisce in r l'intersezione degli insiemi passati per argomento.

public void difference(Set<T> s1, Set<T> s2, Set<T> r)

che restituisce in r la differenza degli insiemi passati per argomento, cioè gli elementi di s1 che non sono elementi di s2.

public void abs(Set<Integer> s, Set<Integer> r)

r

Integer

Si scriva un programma di test che, senza modificare la classe, usi sia l'implementazione con HashSet che con TreeSet.

SOLUZIONE

2) Si scriva la classe StaticSetTheory.java, non istanziabile, che contiene i seguenti metodi:

public static <T> Set<T> union (Set<T> s1, Set<T> s2)

che restituisce l'unione degli insiemi passati per argomento.

public static <T> Set<T> intersection (Set<T> s1, Set<T> s2)

che restituisce l'intersezione degli insiemi passati per argomento.

public static <T> Set<T> difference (Set<T> s1, Set<T> s2)

che restituisce la differenza degli insiemi passati per argomento, cioè gli elementi di s1 che non sono elementi di s2.

public static Set<Integer> abs(Set<Integer> s)

Integer

Si scriva un programma di test che, senza modificare la classe, usi sia l'implementazione con HashSet che con TreeSet.

SOLUZIONE

3) Utilizzando la classe BitSet si scriva un programma che riceve come argomento (NB non legge da console) un numero positivo n e stampa quanti sono i numeri interi compresi tra 1 e n che sono rappresentabili come

somma di due cubi
somma di quattro cubi
somma di tre quadrati
somma di quattro cubi oppure somma di tre quadrati
somma di sette cubi

Si consiglia di provare più di un'implementazione alla ricerca delle più efficienti.

SOLUZIONE