I Comparatori in Java

Comparatori

Sia TreeSet che TreeMap memorizzano gli elementi in modo ordinato.

Tuttavia, è il comparatore che definisce precisamente quale sia questo ordine. Per impostazione predefinita, queste classi memorizzano i loro elementi utilizzando quello che Java chiama ordinamento naturale, che di solito è l'ordinamento che ci si aspetta per i numeri e per le lettere (A prima di B, 1 prima di 2, e così via).

Se sorge l'esigenza di ordinare gli elementi in modo diverso, allora bisogna specificare un Comparator quando si costruisce il set o la mappa. Facendo ciò si ottiene la possibilità di governare precisamente come gli elementi vengono memorizzati all'interno di collezioni e mappe ordinate.

Un Comparator è un'interfaccia generica che ha questa dichiarazione:

interface Comparator<T>

Qui, T specifica il tipo di oggetti che vengono confrontati.

Prima di JDK 8, l'interfaccia Comparator definiva solo due metodi: compare() e equals(). Il metodo compare(), mostrato qui, confronta due elementi per l'ordine:

int compare(T obj1, T obj2)

Qui, obj1 e obj2 sono gli oggetti da confrontare. Normalmente, questo metodo restituisce zero se gli oggetti sono uguali. Restituisce un valore positivo se obj1 è maggiore di obj2. Altrimenti, viene restituito un valore negativo. Il metodo può lanciare una ClassCastException se i tipi degli oggetti non sono compatibili per il confronto. Implementando compare(), si può alterare il modo in cui gli oggetti vengono ordinati. Ad esempio, per ordinare in ordine inverso, si può creare un comparatore che inverte l'esito di un confronto.

Il metodo equals(), mostrato qui, testa se un oggetto è uguale al comparatore invocante:

boolean equals(Object obj)

Qui, obj è l'oggetto da testare per l'uguaglianza. Il metodo restituisce true se obj e l'oggetto invocante sono entrambi oggetti Comparator e usano lo stesso ordinamento. Altrimenti, restituisce false. Sovrascrivere equals() non è necessario, e la maggior parte dei comparatori semplici non lo farà.

Per molti anni, i due metodi precedenti erano gli unici metodi definiti da Comparator. Con il rilascio di JDK 8, la situazione è cambiata drasticamente. JDK 8 ha aggiunto nuove funzionalità significative a Comparator attraverso l'uso di metodi di interfaccia predefiniti e statici. Ognuno è descritto qui.

Si può ottenere un comparatore che inverte l'ordinamento del comparatore su cui è chiamato utilizzando reversed(), mostrato qui:

default Comparator<T> reversed()

Restituisce il comparatore invertito. Ad esempio, assumendo un comparatore che usa l'ordinamento naturale per i caratteri da A a Z, un comparatore in ordine inverso metterebbe B prima di A, C prima di B, e così via.

Un metodo correlato a reversed() è reverseOrder(), mostrato di seguito:

static <T extends Comparable<? super T>> Comparator<T> reverseOrder()

Restituisce un comparatore che inverte l'ordine naturale degli elementi. Al contrario, si può ottenere un comparatore che usa l'ordinamento naturale chiamando il metodo statico naturalOrder(), mostrato di seguito:

static <T extends Comparable<? super T>> Comparator<T> naturalOrder()

Se si vuole un comparatore che può gestire valori null, si può adoperare nullsFirst() o nullsLast(), mostrati qui:

static <T> Comparator<T> nullsFirst(Comparator<? super T> comp)
static <T> Comparator<T> nullsLast(Comparator<? super T> comp)

Il metodo nullsFirst() restituisce un comparatore che considera i valori null come minori di altri valori. Il metodo nullsLast() restituisce un comparatore che considera i valori null come maggiori di altri valori. In entrambi i casi, se i due valori confrontati sono non-null, comp esegue il confronto. Se a comp è passato null, allora tutti i valori non-null sono considerati equivalenti.

Un altro metodo predefinito è thenComparing(). Restituisce un comparatore che esegue un secondo confronto quando l'esito del primo confronto indica che gli oggetti confrontati sono uguali. Quindi, può essere usato per creare una sequenza "confronta per X poi confronta per Y". Ad esempio, quando si confrontano persone, il primo confronto potrebbe confrontare i cognomi, con il secondo confronto che confronta i nomi. Quindi, ad esempio, Rossi Mario verrebbe dopo Rossi Luigi.

Il metodo thenComparing() ha tre forme. La prima, mostrata qui, permette di specificare il secondo comparatore passando un'istanza di Comparator:

default Comparator<T> thenComparing(Comparator<? super T> thenByComp)

Qui, thenByComp specifica il comparatore che viene chiamato se il primo confronto restituisce uguale.

Le prossime versioni di thenComparing() permettono di specificare l'interfaccia funzionale standard Function (definita da java.util.function). Sono mostrate qui:

default <U extends Comparable<? super U>> Comparator<T>
    thenComparing(Function<? super T, ? extends U> getKey)

default <U> Comparator<T>
    thenComparing(Function<? super T, ? extends U> getKey, Comparator<? super U> keyComp)

In entrambi, getKey si riferisce a una funzione che ottiene la prossima chiave di confronto, che viene usata se il primo confronto restituisce uguale. Nella seconda versione, keyComp specifica il comparatore usato per confrontare le chiavi. Qui, e negli usi successivi, U specifica il tipo della chiave.

Comparator aggiunge anche le seguenti versioni specializzate dei metodi "then comparing" per i tipi primitivi:

default Comparator<T>
    thenComparingDouble(ToDoubleFunction<? super T> getKey)

default Comparator<T>
    thenComparingInt(ToIntFunction<? super T> getKey)

default Comparator<T>
    thenComparingLong(ToLongFunction<? super T> getKey)

In tutti i metodi, getKey si riferisce a una funzione che ottiene la prossima chiave di confronto.

Infine, Comparator ha un metodo chiamato comparing(). Restituisce un comparatore che ottiene la sua chiave di confronto da una funzione passata al metodo. Ci sono due versioni di comparing(), mostrate qui:

static <T, U extends Comparable<? super U>> Comparator<T>
    comparing(Function<? super T, ? extends U> getKey)

static <T, U> Comparator<T>
    comparing(Function<? super T, ? extends U> getKey,
                Comparator<? super U> keyComp)

In entrambi, getKey si riferisce a una funzione che ottiene la prossima chiave di confronto. Nella seconda versione, keyComp specifica il comparatore usato per confrontare le chiavi. Comparator aggiunge anche le seguenti versioni specializzate di questi metodi per i tipi primitivi:

static <T> Comparator<T>
    comparingDouble(ToDoubleFunction<? super T> getKey)

static <T> Comparator<T>
    comparingInt(ToIntFunction<? super T> getKey)

static <T> Comparator<T>
    comparingLong(ToLongFunction<? super T> getKey)

In tutti i metodi, getKey si riferisce a una funzione che ottiene la prossima chiave di confronto.

Usare un Comparator

Il seguente è un esempio che dimostra la potenza di un comparatore personalizzato.

Implementa il metodo compare() per stringhe che opera in modo inverso rispetto al normale. Pertanto, causa l'ordinamento di un tree set in ordine inverso.

// Usa un comparatore personalizzato.
import java.util.*;

// Un comparatore inverso per stringhe.
class MioComp implements Comparator<String> {

    public int compare(String stringaA, String stringaB) {
        // Inverte il confronto.
        return stringaB.compareTo(stringaA);
    }

    // Non è necessario sovrascrivere equals o i metodi predefiniti.

}

class DemoComp {

    public static void main(String[] args) {
        // Crea un tree set.
        TreeSet<String> ts = new TreeSet<String>(new MioComp());

        // Aggiungi elementi al tree set.
        ts.add("C");
        ts.add("A");
        ts.add("B");
        ts.add("E");
        ts.add("F");
        ts.add("D");

        // Visualizza gli elementi.
        for (String elemento : ts)
            System.out.print(elemento + " ");
        System.out.println();
    }

}

Come mostra il seguente output, l'albero ora è ordinato in ordine inverso:

F E D C B A

Si osservi attentamente la classe MioComp, che implementa Comparator implementando compare(). Come spiegato in precedenza, sovrascrivere equals() non è né necessario né comune. Non è nemmeno necessario sovrascrivere i metodi predefiniti. All'interno di compare(), il metodo String compareTo() confronta le due stringhe. Tuttavia, stringaB, e non stringaA, invoca compareTo(). Questo causa l'inversione del risultato del confronto.

Sebbene il modo in cui il comparatore di ordine inverso è implementato dal programma precedente sia perfettamente adeguato, c'è un altro modo per affrontare una soluzione. Ora è possibile semplicemente chiamare reversed() su un comparatore di ordine naturale. Restituirà un comparatore equivalente, tranne che funziona in modo inverso. Ad esempio, assumendo il programma precedente, si può riscrivere MioComp come un comparatore di ordine naturale, come mostrato qui:

class MioComp implements Comparator<String> {

    public int compare(String stringaA, String stringaB) { 
        return stringaA.compareTo(stringaB); 
    }

}

Successivamente, si può usare la seguente sequenza per creare un TreeSet che ordina i suoi elementi stringa in modo inverso:

// Crea un comparatore che usa l'ordine naturale delle stringhe.
MioComp mc = new MioComp();

// Passa una versione di ordine inverso di MioComp a TreeSet.
TreeSet<String> ts = new TreeSet<String>(mc.reversed());

Se si inserisce questo nuovo codice nel programma precedente, produrrà gli stessi risultati di prima. In questo caso, non c'è alcun vantaggio ottenuto usando reversed(). Tuttavia, nei casi in cui bisogna creare sia un comparatore di ordine naturale che un comparatore invertito, allora usare reversed() è un modo facile per ottenere il comparatore di ordine inverso senza doverlo codificare esplicitamente.

Espressioni Lambda come Comparator

Non è effettivamente necessario creare la classe MioComp negli esempi precedenti perché un'espressione lambda può essere facilmente usata al suo posto.

Ad esempio, si può rimuovere completamente la classe MioComp e creare il comparatore di stringhe usando questa istruzione:

// Usa un'espressione lambda per implementare Comparator<String>.
Comparator<String> mc = (stringaA, stringaB) -> stringaA.compareTo(stringaB);

Un altro punto: in questo semplice esempio, sarebbe anche possibile specificare un comparatore inverso tramite un'espressione lambda direttamente nella chiamata al costruttore TreeSet(), come mostrato qui:

// Passa un comparatore invertito a TreeSet() tramite un'
// espressione lambda.
TreeSet<String> ts = new TreeSet<String>(
    (stringaA, stringaB) -> stringaB.compareTo(stringaA));

Apportando queste modifiche, il programma è sostanzialmente accorciato, come illustra la sua versione finale mostrata qui:

// Usa un'espressione lambda per creare un comparatore inverso. 
import java.util.*;

class DemoComp2 {

    public static void main(String[] args) {
        // Passa un comparatore inverso a TreeSet() tramite un'
        // espressione lambda.
        TreeSet<String> ts = new TreeSet<String>(
                (stringaA, stringaB) -> stringaB.compareTo(stringaA));

        // Aggiunge elementi al tree set.
        ts.add("C");
        ts.add("A");
        ts.add("B");
        ts.add("E");
        ts.add("F");
        ts.add("D");

        // Visualizza gli elementi.
        for (String elemento : ts)
            System.out.print(elemento + " ");
        System.out.println();
    }

}

Comparatori più complessi

Per un esempio più pratico che usa un comparatore personalizzato, il seguente programma è una versione aggiornata del programma TreeMap mostrato nelle lezioni precedenti che memorizza saldi di alcuni conti correnti. In questo caso, il nome e cognome della persona rappresenta la chiave della mappa mentre il saldo del conto ne rappresenta il valore.

Nella versione precedente, i conti erano ordinati per nome, ma l'ordinamento iniziava con il nome di battesimo. Il seguente programma ordina i conti per cognome. Per farlo, adoperiamo un comparatore che confronta il cognome di ogni conto. Questo risulta nella mappa ordinata per cognome.

// Usa un comparatore per ordinare i conti per cognome.
import java.util.*;

// Confronta le ultime parole intere in due stringhe.
class TComp implements Comparator<String> {

    public int compare(String stringaA, String stringaB) {
        int i, j, k;
        // Trova l'indice dell'inizio del cognome.
        i = stringaA.lastIndexOf(' ');
        j = stringaB.lastIndexOf(' ');

        // Confronta i cognomi ignorando le maiuscole.
        k = stringaA.substring(i).compareToIgnoreCase(stringaB.substring(j));

        // Se i cognomi sono uguali, confronta l'intero nome.
        if (k == 0)
            return stringaA.compareToIgnoreCase(stringaB);
        else
            return k;
    }

    // Non è necessario sovrascrivere equals.

}

class DemoTreeMap2 {

    public static void main(String[] args) {
        // Crea una tree map usando il Comparator TComp.
        TreeMap<String, Double> tm =
            new TreeMap<String, Double>(new TComp());

        // Inserisce elementi nella map.
        tm.put("Giovanni Rossi", 3434.34);
        tm.put("Tommaso Bianchi", 123.22);
        tm.put("Giulia Fornaio", 1378.00);
        tm.put("Teodoro Sala", 99.22);
        tm.put("Raffaele Bianchi", -19.08);

        // Ottiene un set delle entries.
        Set<Map.Entry<String, Double>> set = tm.entrySet();

        // Visualizza gli elementi.
        for (Map.Entry<String, Double> me : set) {
            System.out.print(me.getKey() + ": ");
            System.out.println(me.getValue());
        }
        System.out.println();

        // Deposita 1000 nel conto di Giovanni Rossi.
        double saldo = tm.get("Giovanni Rossi");
        tm.put("Giovanni Rossi", saldo + 1000);
        System.out.println("Nuovo saldo di Giovanni Rossi: " +
                tm.get("Giovanni Rossi"));
    }

}

Di seguito è riportato l'output prodotto dal programma. Si noti che ora i conti sono ordinati per cognome, e all'interno del cognome, per nome di battesimo:

Raffaele Bianchi: -19.08
Tommaso Bianchi: 123.22
Giulia Fornaio: 1378.0
Giovanni Rossi: 3434.34
Teodoro Sala: 99.22

Nuovo saldo di Giovanni Rossi: 4434.34

La classe comparatore TComp confronta due stringhe che contengono nomi e cognomi. Lo fa confrontando prima i cognomi. Per fare questo, trova l'indice dell'ultimo spazio in ogni stringa e poi confronta le sotto-stringhe di ogni elemento che iniziano da quel punto. Nei casi in cui i cognomi sono equivalenti, vengono poi confrontati i nomi di battesimo. Questo produce una tree map che è ordinata per cognome, e all'interno del cognome per nome di battesimo. Si può vedere questo perché "Raffaele Bianchi" viene prima di "Tommaso Bianchi" nell'output.

Comparatori Concatenati

C'è un altro modo in cui si potrebbe codificare il programma precedente in modo che la map sia ordinata per cognome e poi per nome di battesimo. Questo approccio usa il metodo thenComparing(). Si ricordi che thenComparing() permette di specificare un secondo comparatore che verrà usato se il comparatore che lo invoca restituisce uguale. Questo approccio è messo in azione dal seguente programma, che rielabora l'esempio precedente per usare thenComparing():

// Usa thenComparing() per ordinare per cognome,
// poi per nome di battesimo.
import java.util.*;

// Un comparatore che confronta i cognomi.
class CompCognomi implements Comparator<String> {

    public int compare(String stringaA, String stringaB) {
        int i, j;
        // Trova l'indice dell'inizio del cognome.
        i = stringaA.lastIndexOf(' ');
        j = stringaB.lastIndexOf(' ');

        // Confronta i cognomi ignorando le maiuscole.
        return stringaA.substring(i).compareToIgnoreCase(
            stringaB.substring(j));
    }

}

// Un comparatore che confronta i nomi di battesimo.
// Questo viene usato se i cognomi corrispondono.
class CompPoiPerNomeDiBattesimo implements Comparator<String> {

    public int compare(String stringaA, String stringaB) {
        // Confronta il nome completo ignorando le maiuscole.
        return stringaA.compareToIgnoreCase(stringaB);
    }

}

class DemoTreeMap2A {

    public static void main(String[] args) {
        // Usa thenComparing() per creare un comparatore che confronta
        // i cognomi, poi confronta l'intero nome quando i cognomi corrispondono.
        CompCognomi compCN = new CompCognomi();
        Comparator<String> compCognomePoiPrimo =
            compCN.thenComparing(
                new CompPoiPerNomeDiBattesimo());

        // Crea una tree map.
        TreeMap<String, Double> tm =
            new TreeMap<String, Double>(compCognomePoiPrimo);

        // Inserisce elementi nella map.
        tm.put("Giovanni Rossi", 3434.34);
        tm.put("Tommaso Bianchi", 123.22);
        tm.put("Giulia Fornaio", 1378.00);
        tm.put("Teodoro Sala", 99.22);
        tm.put("Raffaele Bianchi", -19.08);

        // Ottieni un set delle entries.
        Set<Map.Entry<String, Double>> set = tm.entrySet();

        // Visualizza gli elementi.
        for (Map.Entry<String, Double> me : set) {
            System.out.print(me.getKey() + ": ");
            System.out.println(me.getValue());
        }
        System.out.println();

        // Deposita 1000 nel conto di Giovanni Rossi.
        double saldo = tm.get("Giovanni Rossi");
        tm.put("Giovanni Rossi", saldo + 1000);
        System.out.println("Nuovo saldo di Giovanni Rossi: " +
                tm.get("Giovanni Rossi"));
    }

}

Questa versione produce lo stesso output di prima. Differisce solo nel modo in cui realizza il suo compito.

Per iniziare, si noti che viene creato un comparatore chiamato CompCognomi. Questo comparatore confronta solo i cognomi. Un secondo comparatore, chiamato CompPoiPerNomeDiBattesimo, confronta l'intero nome, iniziando con il nome di battesimo. Successivamente, la TreeMap viene creata dalla seguente sequenza:

CompCognomi compCN = new CompCognomi();
Comparator<String> compCognomePoiPrimo =
    compCN.thenComparing(new CompPoiPerNomeDiBattesimo());

Qui, il comparatore primario è compCN. È un'istanza di CompCognomi. Su di esso viene chiamato thenComparing(), passando un'istanza di CompPoiPerNomeDiBattesimo. Il risultato viene assegnato al comparatore chiamato compCognomePoiPrimo. Questo comparatore viene usato per costruire la TreeMap, come mostrato qui:

TreeMap<String, Double> tm =
    new TreeMap<String, Double>(compCognomePoiPrimo);

Ora, ogni volta che i cognomi degli elementi confrontati sono uguali, l'intero nome, iniziando con il nome di battesimo, viene usato per ordinare i due. Questo significa che i nomi sono ordinati basandosi sul cognome, e all'interno dei cognomi, per nomi di battesimo.

Un ultimo punto: nell'interesse della chiarezza, questo esempio crea esplicitamente due classi comparatore chiamate CompCognomi e CompPoiPerNomeDiBattesimo, ma avrebbero potuto essere usate espressioni lambda invece.

Ad esempio, potremmo creare la TreeMap con questo codice:

// Usa thenComparing() per creare un comparatore che confronta
// i cognomi, poi confronta l'intero nome quando i cognomi corrispondono.
Comparator<String> compCN = (A, B) -> {
    int i, j;
    // Trova l'indice dell'inizio del cognome.
    i = A.lastIndexOf(' ');
    j = B.lastIndexOf(' ');

    // Confronta i cognomi ignorando le maiuscole.
    return A.substring(i).compareToIgnoreCase(
        B.substring(j));
};

// Crea una tree map.
TreeMap<String, Double> tm =
    new TreeMap<String, Double>(compCN.thenComparing(
        (A, B) -> A.compareToIgnoreCase(B)));

In questo codice, creiamo il primo comparatore usando un'espressione lambda che confronta i cognomi. Poi, usiamo thenComparing() passando un'altra espressione lambda che confronta l'intero nome. Questo produce lo stesso effetto del programma precedente, ma senza dover creare le classi comparatore separate.