La classe Collections

La classe java.util.Collections fornisce una serie di metodi statici che operano sul set di collezioni definiti all'interno del Java Collections Framework. Alcuni di questi metodi vengono definiti wrapper, cioè operano sulle collezione modificandone il loro stato. Un tipico esempio è quello di rendere una lista sincronizzata, oppure immutabile, cioè dove non si può apportare più nessuna modifica. Mentre l'altra serie di metodi implementa alcuni algoritmi che sono di per se molto complessi in particolare nella loro definizione ottimizzata. Tra questi abbiamo l'ordinamento, la ricerca binaria, minimo e massimo etc. Analizzeremo in questa sede alcune delle funzioni fondamentali che la classe Collections ci mette a disposizione, mostrando qualche semplice esempio per mettere in evidenza le potenzialità ed il meccanismo di funzionamento.

Ordinamento

Un insieme di oggetti per poter essere ordinato tramite un algoritmo, deve seguire una certa relazione d'ordine. Questa può essere specificata implicitamente nel tipo d'oggetto contenuto nell'insieme oppure può essere fornita esternamente all'algoritmo. In questo caso java ci mette a dispozione due semplici interfacce per conseguire questo scopo: java.lang.Comparable e java.util.Comparator. Queste due interfaccie ci permettono di 'esprimere' la relazione d'ordine di un determinato oggetto in due maniere strutturalmente diverse. Infatti abbiamo due tipologie di ordinamento tramite la classe Collections:

• static void sort(List list)
• static void sort(List list, Comparator c)

Il primo metodo si avvale dell'interfaccia Comparable definita negli oggetti contenuti nella List per ordinare l'insieme, mentre il secondo metodo si avvale del Comparator passato come secondo parametro. Vediamo in maniera specifica queste due interfacce, che sono tra l'altro alla base di tutte le funzionalità degli algoritmi implementati nella classe Collections.

Comparable

L'interfaccia Comparable ci permette di implementare il cosiddetto ordinamento naturale di un oggetto. Infatti oggetti come String, Double, Integer implementano l'interfaccia Comparable che definisce la normale relazione d'ordine di questi tipi. L'interfaccia fornisce un solo metodo:

public int compareTo(Object obj);

La specifica prevede che il metodo deve ritornare 1 nel caso in cui l'oggetto this (la classe che implementa l'interfaccia) è maggiore dell' oggetto obj, ritorna 0 se sono uguali, -1 altrimenti.

Comparator

Immaginiamo il caso in cui abbiamo una lista di stringhe e vogliamo cambiare il tipo di ordinamento, cioè invece di utilizzare l'ordinamento alfabetico desideriamo ordinare questa lista per lunghezza della stringa. Come facciamo? Possiamo ridefinire il compareTo() della classe String? Di certo no, non possiamo in quanto questa classe è final quindi non ereditabile. Allora questo è uno di quei casi in cui possiamo avvalerci di un altro meccanismo, cioè utilizzare l'interfaccia Comparator. Questa interfaccia fornisce un unico metodo molto simile al compareTo() dell'interfaccia Comparable:

public int compare(Object a, Object b);

Vediamo subito un esempio per il nostro caso, specificando una relazione d'ordine sulle stringhe che non sia per ordine alfabetico ma per ordine di lunghezza. Solo a parità di lunghezza ordiniamo alfabeticamente:

class MyComparatorString implements Comparator {
    public int compare(Object a, Object b) {
      if (!(a istanceof String) || !(b istanceof String)) {}
      String a1 = (String)a;
      String b1 = (String)b;
      if (a1.length()>b1.length()) return 1;
      else if (a1.length()==b1.length())
      	return a1.compareTo(b1);//A parità di lunghezza ordiniamo alfabeticamente
      else return -1;
    }
}

Facciamo un esempio con una lista di stringhe :

List <String> lista = new LinkedList<String>();
lista.add("z");
lista.add("aaa");
lista.add("ff");
lista.add("ggggg");

Adesso ordiniamola alfabeticamente tramite il metodo Collections.sort() che si avvale quindi del Comparable:

Collections.sort(list)

Avremo come output:

aaa
ff
ggggg
z

Mentre se dobbiamo effettuare l'ordinamento con la relazione d'ordine che abbiamo definito noi tramite la classe MyComparatorString basta utilizzare un'altro metodo sort che in questo caso riceve due parametri, la lista (interfaccia java.util.List) e il Comparator :

Collections.sort(lista, new MyComparatorString());
...
output:
z
ff
aaaa
ggggg

Il metodo sort, per ordinare l'insieme, si avvale a sua volta del metodo Arrays.sort() che implementa come algoritmo di ordinamento il merge sort con una complessità computazionale pari a O(n log n).

Ricerca binaria

La ricerca binaria è un particolare tipo di ricerca che si può effettuare solo su un insieme ordinato di elementi. Nella classe Collections sono definiti due metodi statici per questo tipo di ricerca, rispettivamente per il Comparable e per il Comparator. Ambedue i metodi ritornano un'intero che indica l'indice dell'elemento nella lista. Nel primo metodo basta inserire la lista e il valore chiave che vogliamo ricercare:

Colleactions.sort(lista);
int n = Collections.binarySearch(lista,"z");
System.out.println(n);
output:
3

Nel secondo metodo invece possiamo utilizzare il Comparator:

Collections.sort(lista, new MyComparatorString());
int n = Collections.binarySearch(lista, "z", new MyComparatorString());
System.out.println(n);
output:
0

Notate che ogni chiamata al metodo binarySearch() è preceduta dalla chimata al metodo sort() in quanto, ripeto, la lista deve essere ordinata per effettuare la ricerca binaria.

Min e Max

Un'altro problema molto ricorrente nella programmazione e quella di ricercare il minimo o il massimo all'interno di un vettore o in questo caso in una collezione. Per carcare il minimo possiamo utilizzare il metodo statico Collections.min(), sempre disponibile in due versioni. La prima riceve solo la collezione e quindi si avvalerà del compareTo():

String el = Collections.min(lista);
System.out.println(el);
output:
aaaa

Mentre nel secondo metodo è possibile specificare il Comparator:

String el = Collections.min(lista, new MyComparatorString());
System.out.println(el);
output:
z

Lo stesso identico discorso vale per la ricerca del massimo tramite il metodo static Collections.max().