Comparazione e ordinamento degli oggetti in Java

Questo articolo descrive come è stato affrontato l’argomento della comparazione e ordinamento degli oggetti in Java.

il
Senior Java developer, Collaboratore di IProgrammatori

Nel linguaggio Java i valori dei tipi primitivi numerici (compreso il char) si possono confrontare usando i ben noti operatori “relazionali” che sono < (minore), > (maggiore), <= (minore/uguale) e >= (maggiore/uguale). Questi operatori, tra l’altro, sono esattamente gli stessi (e con il medesimo significato) che si trovano anche in molti altri linguaggi di programmazione come il C, C++, C#, Javascript e sicuramente anche altri. Inoltre, tutti i tipi primitivi (compreso il boolean) si possono anche confrontare con gli operatori di “(dis)uguaglianza” che sono == (uguale) e != (diverso).

E per i tipi reference, ovvero gli oggetti? Per i tipi reference gli operatori == e != si basano solo sulla “identità” degli oggetti (non sul loro contenuto) quindi sono raramente utili, eccetto in certi casi particolari. Invece, purtroppo, gli operatori relazionali non si possono usare con gli oggetti. Il linguaggio Java oltretutto non prevede neanche la possibilità di “sovraccaricare” (overloading) gli operatori in generale, quindi non è possibile ridefinire arbitrariamente il loro comportamento come si può fare ad esempio in C++ e C#.

La possibilità di confrontare gli oggetti in Java però esiste, semplicemente è stata affrontata fin dall’inizio in una maniera ben differente seguendo un approccio molto più “object oriented”.

1) Premesse

Prima di vedere più in dettaglio la comparazione degli oggetti in Java, è necessario fare alcune premesse per chiarire due aspetti concettuali fondamentali: cosa vuol dire comparare due oggetti e dove si usa tipicamente la comparazione degli oggetti.

Quando si confrontano due valori numerici, il criterio del confronto è (direi) ovvio/scontato in quanto è un concetto matematico: 6 è maggiore di 5, -3 è minore di -2, ecc... Al massimo si può invertire l’ordine, cioè da crescente a decrescente. Per gli oggetti in generale invece la questione è ben differente. Infatti gli oggetti sono delle entità che possono anche essere complesse e dotate di molti attributi. Prendiamo come esempio una versione molto basilare di una classe Persona con gli attributi nome, cognome e annoNascita:

public class Persona {
    private String nome;
    private String cognome;
    private int annoNascita;

    // metodi getter/setter, ecc... (omessi per brevità)
}

Se ci sono due oggetti Persona da confrontare, con quale criterio si vuole confrontarli? Solo per nome? Per cognome/nome? Per anno di nascita decrescente e a parità di anno per cognome/nome? Per cognome/nome/anno di nascita? Nessuno di questi criteri è di per sé “sbagliato”, semplicemente sono criteri differenti ma tutti ragionevolmente sensati e potrebbero anche essere utilizzati insieme all’interno di una singola applicazione.

Il concetto alla base di tutto questo è molto semplice: con gli oggetti ci dovrebbe essere, in teoria, la possibilità di definire più criteri di comparazione differenti per un certo tipo di oggetti, da utilizzare in base al contesto e alle necessità specifiche. Come si vedrà in seguito, questa possibilità in Java fortunatamente esiste ed è stata prevista da molto tempo.

Un altro aspetto da valutare è dove si usa tipicamente la comparazione degli oggetti. Si può certamente applicare in qualunque situazione in cui si hanno due oggetti da comparare, ad esempio una stringa fornita in input dall’utente che deve essere confrontata con una singola stringa fissa es. "hotel". Ma questi sono casi ovviamente molto specifici (e forse poco realistici). Esiste invece un altro contesto dove in generale la comparazione degli oggetti è fondamentale: quando si deve ordinare una sequenza di elementi. In Java una sequenza di elementi si gestisce tipicamente con un array oppure con una collezione “lista” (implementazione della interfaccia java.util.List).

Per ordinare una sequenza di elementi si utilizza normalmente un apposito “algoritmo di ordinamento”. Ne esistono molti nella letteratura informatica, giusto per citarne alcuni: Bubble sort, Heap sort, Merge sort, Quicksort, Shell sort e svariati altri (sono tutti chiamati genericamente Xyz sort o Xyzsort). Ciascuno di questi algoritmi si basa su concetti e tecniche anche molto differenti dagli altri e offre prestazioni che possono variare in base all’algoritmo stesso e anche in base ai dati presenti inizialmente nella sequenza. Si va dagli algoritmi più “scarsi” come il Bubble sort fino a quelli molto buoni come il Merge sort.

Tutti gli algoritmi di ordinamento però hanno una cosa in comune: all’interno dell’algoritmo c’è un punto specifico in cui viene fatto un confronto tra due elementi. In pratica questi algoritmi fanno tanti confronti su coppie di elementi prese di volta in volta dalla sequenza e in base al risultato di tutti i confronti effettuati arrivano a determinare e imporre l’ordinamento complessivo della sequenza spostando/scambiando opportunamente gli elementi. Quante siano, quali siano e in che ordine vengono prese queste coppie di elementi dipende dalla logica dell’algoritmo ed è appunto questo che ne determina la bontà e l’efficienza.

L’ordinamento di una sequenza di elementi quindi si basa sempre su due concetti distinti:

  • L’algoritmo di ordinamento, che stabilisce con quale logica effettuare tutti i confronti su coppie di elementi della sequenza
  • Il criterio di comparazione, che effettua solo il confronto tra due elementi indicando se uno è minore/uguale/maggiore dell’altro

Se ad esempio si implementa “da zero” il classico Bubble sort, il criterio di comparazione generalmente è incapsulato, “annegato”, all’interno dell’algoritmo. Se si vogliono trattare più criteri differenti, si deve replicare completamente tutto il codice dell’algoritmo, cambiando solo il criterio di comparazione. Questo ovviamente è molto poco pratico oltre che ripetitivo e poco manutenibile.

La soluzione ideale sarebbe tenere i due concetti ben separati, cioè avere l’algoritmo di ordinamento a sé stante, implementato una volta sola, e poi poter passare un criterio di comparazione come “parametro” dell’algoritmo. Questo è proprio l’approccio che è stato scelto per gestire la comparazione e l’ordinamento degli oggetti in Java.

Il framework della piattaforma Java Standard Edition (Java SE) contiene già gli algoritmi per effettuare tutte le seguenti operazioni:

  • ordinare gli elementi di un array o una lista
  • mantenere ordinati gli elementi in collezioni specifiche (es. TreeSet)
  • cercare un elemento in un array o una lista tramite la tecnica del binary search (a condizione che la sequenza sia già ordinata)
  • determinare il valore “min” o “max” di una qualunque collezione

Tutti questi algoritmi richiedono solo di ricevere in un qualche modo, implicitamente o esplicitamente, un criterio di comparazione al fine di far funzionare correttamente l’algoritmo. Per rappresentare un criterio di comparazione in Java sono state usate le interfacce.

Una interfaccia viene sovente e tipicamente utilizzata per definire un “contratto” tra due parti perché (ignorando un momento le novità di Java 8) rappresenta una “astrazione pura” che permette di descrivere quali metodi deve avere un oggetto ma non come devono essere implementati. Una classe “concreta” (non astratta) che implementa una interfaccia sarà quindi obbligata ad avere tutti i metodi della interfaccia implementati mentre invece chi riceve un oggetto come tipo di una interfaccia sa a priori che l’oggetto ricevuto ha sicuramente i metodi della interfaccia implementati.

Per la comparazione degli oggetti in Java sono state definite due interfacce specifiche chiamate Comparable e Comparator. Il perché sono due verrà chiarito più avanti ma in breve si può dire che questa dualità serve per poter implementare un criterio di comparazione principale e poi un numero arbitrario di criteri alternativi.

Queste due interfacce non esistono esattamente dalla primissima versione di Java (JDK 1.0) ma fanno parte del “Java Collections Framework” che è stato introdotto solo nel JDK 1.2. Si tratta comunque di tantissimo tempo fa, quindi si può benissimo dire che l’argomento della comparazione e ordinamento degli oggetti in Java è stato affrontato praticamente “quasi” dall’inizio.

2) La interfaccia Comparable

La interfaccia java.lang.Comparable ha sostanzialmente la seguente definizione:

public interface Comparable<T> {
    public int compareTo(T other);
}

Prima di Java 5 era una normale interfaccia, a partire da Java 5 invece è una interfaccia “generica” nel senso che sfrutta i generics introdotti in Java 5. Si può trovare ancora oggi del codice che usa Comparable senza parametrizzazione (il raw type) e in tal caso il metodo compareTo deve avere come parametro un Object ed è necessario fare un cast esplicito al tipo specifico da trattare. L’utilizzo di Comparable non parametrizzato comunque è sconsigliato, perché richiede più codice, è più scomodo e causa dei warning emessi dal compilatore.

Comparable possiede un solo metodo astratto che riceve un singolo valore. Quale è quindi l’altro valore da utilizzare per il confronto? È molto semplice: l’altro valore è il this, ovvero l’oggetto su cui il metodo compareTo viene invocato.

Avendo quindi ad esempio una variabile oggetto1 di un tipo che implementa la interfaccia Comparable, il metodo compareTo si può invocare nel seguente modo:

int risultato = oggetto1.compareTo(oggetto2);

Secondo la documentazione ufficiale di Comparable, il risultato del metodo compareTo deve essere un valore intero con i seguenti significati:

  • un valore < 0 per indicare che oggetto1 è minore di oggetto2
  • un valore = 0 per indicare che oggetto1 è uguale a oggetto2
  • un valore > 0 per indicare che oggetto1 è maggiore di oggetto2

Da notare che il valore restituito può essere tecnicamente qualunque valore intero: 10, -25, 123, ecc... Chi implementa il compareTo ha la facoltà di restituire qualsiasi valore voglia per indicare “minore” o “maggiore” mentre invece chi usa il risultato del compareTo non dovrebbe mai aspettarsi un valore specifico ma solo testare il valore in maniera generalizzata per minore, uguale o maggiore di 0.

Il concetto più importante e fondamentale è che la interfaccia Comparable deve essere implementata nella stessa classe degli oggetti da comparare. Per tale motivo ci può quindi essere un solo criterio di comparazione definito con Comparable per un certo tipo di oggetti.

Secondo la specifica di Comparable, questo criterio dovrebbe rappresentare l’ordinamento “naturale” degli oggetti. Quale sia esattamente questo criterio dipende ovviamente dal significato e dal contenuto della classe di oggetti. Si possono fare diversi esempi pratici per chiarire meglio:

  • per una classe Libro l’ordinamento “naturale” può ragionevolmente essere per titolo (o eventualmente editore/titolo se fosse presente anche l’attributo editore)
  • per una classe Persona l’ordinamento “naturale” può ragionevolmente essere per cognome/nome
  • per una classe Veicolo l’ordinamento “naturale” può ragionevolmente essere per marca/modello

In altre parole, l’ordinamento “naturale” dovrebbe essere quello più logico, sensato e tipico per una certa classe di oggetti.

La documentazione di Comparable inoltre precisa che è “fortemente raccomandato”, ma non obbligatorio, che questo ordinamento naturale sia consistente con il equals. Ovvero fare in modo che:

  • se e1.compareTo(e2) == 0 è true allora e1.equals(e2) dà true
  • se e1.compareTo(e2) == 0 è false allora e1.equals(e2) dà false

Questo è particolarmente importante ad esempio quando si usano delle collezioni “sorted” come TreeSet e TreeMap senza aver specificato un comparatore esplicito (e quindi usano implicitamente Comparable). Usare con queste collezioni un ordinamento naturale che non è consistente con equals significa sostanzialmente “violare” il contratto generale delle collezioni set/map che si basa sul concetto del equals.

Se si ha una classe Persona, come quella mostrata all’inizio e si vuole renderla “comparabile” tramite Comparable, il codice minimale (abbozzato, l’esempio completo sarà più avanti) è il seguente:

public class Persona implements Comparable<Persona> {
    // ...campi, metodi, ecc...

    @Override
    public int compareTo(Persona altraPersona) {
        // .... logica di confronto tra:  this <---> altraPersona
    }
}

Si dichiara che la classe implementa Comparable<Persona> e si definisce il metodo compareTo, che per effetto della parametrizzazione <Persona> deve avere un parametro di tipo Persona. All’interno del compareTo ci dovrà essere la logica per confrontare l’oggetto Persona this (quello su cui il compareTo è invocato) con l’altro oggetto Persona ricevuto in argomento.

3) La interfaccia Comparator

La interfaccia java.util.Comparator è un po’ il “duale” di Comparable ma ha una definizione e un utilizzo differente:

public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
}

In maniera similare a Comparable, anche Comparator prima di Java 5 era una normale interfaccia, mentre a partire da Java 5 è invece una interfaccia “generica” nel senso che sfrutta i generics introdotti in Java 5. Si può trovare ancora oggi del codice che usa Comparator senza parametrizzazione (il raw type) e in tal caso il metodo compare deve avere due parametri di tipo Object ed è necessario fare un cast esplicito al tipo specifico da trattare. L’utilizzo di Comparator non parametrizzato comunque è sconsigliato, perché richiede più codice, è più scomodo e causa dei warning emessi dal compilatore.

Anche se dichiara due metodi, in realtà il solo metodo astratto da implementare è il compare. Il metodo equals invece è una ridefinizione del equals di Object e quindi in una implementazione “concreta” di Comparator sarà sicuramente già implementato, come minimo proprio da Object.

Sul equals bisogna però precisare che non riguarda assolutamente i due oggetti da confrontare. Il senso di questo equals è di verificare se due diversi oggetti Comparator sono “equivalenti”, cioè rappresentano lo stesso criterio di comparazione. Questa possibilità comunque non viene praticamente quasi mai sfruttata, quindi si tende normalmente a non ridefinire il equals in una implementazione di Comparator.

Nota: la definizione di Comparator mostrata sopra è quella che esiste fino a Java 7. In Java 8 sono stati aggiunti all’interno di Comparator svariati nuovi metodi statici e di default (nuova funzionalità di Java 8). Tutti i nuovi metodi servono per comporre un Comparator in maniera più “funzionale” e soprattutto “fluente”. Per il momento queste novità si possono ignorare (vedere sezione al fondo “Comparazione con le novità di Java 8”).

Il concetto fondamentale è che, a differenza di Comparable, la interfaccia Comparator deve essere implementata in una classe distinta, separata, dalla classe degli oggetti da comparare. Questo significa che è possibile creare più classi per definire un numero arbitrario di criteri di comparazione alternativi o comunque più particolari rispetto all’ordinamento “naturale” espresso tramite Comparable.

Per una classe Persona si possono creare vari altri comparatori, ad esempio:

public class AnnoNomePersonaComparator implements Comparator<Persona> {
    @Override
    public int compare(Persona persona1, Persona persona2) {
        // .... logica di confronto tra:  persona1 <---> persona2
    }
}
public class CognomeNomeAnnoPersonaComparator implements Comparator<Persona> {
    // .........
}
public class AnnoDecrCognomeNomePersonaComparator implements Comparator<Persona> {
    // .........
}

ecc...

Per poter usare un Comparator bisogna innanzitutto creare un oggetto di una implementazione specifica di Comparator. A quel punto il metodo compare si può invocare nel seguente modo:

int risultato = unComparator.compare(oggetto1, oggetto2);

Il risultato di compare segue praticamente lo stesso concetto già descritto per il compareTo di Comparable, ovvero il metodo dovrà restituire un valore intero con i seguenti significati:

  • un valore < 0 per indicare che oggetto1 è minore di oggetto2
  • un valore = 0 per indicare che oggetto1 è uguale a oggetto2
  • un valore > 0 per indicare che oggetto1 è maggiore di oggetto2

Sul valore restituito valgono esattamente le stesse considerazioni già fatte in precedenza per Comparable.

4) Implementazione di compareTo/compare

Prima di vedere degli esempi concreti, è bene spiegare cosa si dovrebbe fare all’interno dei metodi compareTo e compare. Quando questi metodi vengono invocati, ci sono sempre e solo due oggetti da confrontare (nel caso di compareTo uno dei due oggetti è il this).

La implementazione di compareTo o compare non ha, di per sé, alcuna “visione” su una intera sequenza di elementi. Giusto per ribadire il concetto appena espresso: l’obiettivo di questi metodi non è di ragionare su un intero insieme di elementi ma solo su due elementi per volta. Quindi ad esempio stabilire secondo un certo criterio se un oggetto Persona «Mario Rossi, 1975» è minore/uguale/maggiore di un altro oggetto Persona «Roberto Verdi, 1963». Ci penserà l’algoritmo di ordinamento o di ricerca a fare tutte le necessarie comparazioni tra gli elementi per arrivare al risultato finale.

Quindi, in definitiva: ci sono sempre due oggetti su cui si devono confrontare uno o più attributi. Sugli attributi ci sono tre aspetti da considerare: il tipo, il numero e il trattamento dei valori null.

4.1) Tipo degli attributi

Riguardo il tipo degli attributi ci sono principalmente tre casistiche:

Caso 1: Attributo di tipo primitivo

In questo caso, tipicamente, si confronta l’attributo di tipo primitivo tra i due oggetti usando gli operatori relazionali:

if (persona1.getAnnoNascita() < persona2.getAnnoNascita()) {
    return -1;
} else if (persona1.getAnnoNascita() > persona2.getAnnoNascita()) {
    return +1;
} else {
    return 0;
}

oppure in maniera più compatta usando l’operatore “condizionale”:

return persona1.getAnnoNascita() < persona2.getAnnoNascita() ? -1 :
       persona1.getAnnoNascita() > persona2.getAnnoNascita() ? +1 : 0;

Nota: quando si restituisce esplicitamente un valore per minore/maggiore, è tipico usare il valore fisso -1 e +1.

A partire da Java 7 ci sono altre possibilità per fare questo tipo di comparazioni in modo più pratico, vedere la sezione al fondo “Comparazione con le novità di Java 7”.

È anche possibile trovare del codice che effettua il confronto tra due valori primitivi in questo modo:

return persona1.getAnnoNascita() - persona2.getAnnoNascita();

La sottrazione tra due valori primitivi è proprio la situazione che porta ad avere come risultato un “qualunque” valore intero, che di per sé è lecito secondo quanto descritto in precedenza.

Per un confronto sull’anno di nascita, la sottrazione ragionevolmente è “innocua” e non dovrebbe causare problemi. Ma in generale sarebbe da evitare, perché in base ai valori c’è la possibilità che avvenga un overflow.

Esempio (come tipo int): -1500000000   -   +900000000

Risultato teorico: -2400000000 (vorrebbe dire che -1500000000 < +900000000 , corretto)
Risultato reale: +1894967296 (vorrebbe dire che -1500000000 > +900000000 , sbagliato!)

Questa sottrazione ha causato un overflow perché -2400000000 non è rappresentabile in una variabile di tipo int e il valore ha fatto il “giro” nella rappresentazione in complemento a due, diventando un valore positivo che non ha più senso/utilità. La sottrazione ai fini della comparazione quindi sarebbe sempre da evitare, a meno di avere ottima conoscenza e/o controllo sull’intervallo dei valori dell’attributo.

Caso 2: Attributo di tipo reference che implementa Comparable

Esistono classi come String, Integer, java.math.BigInteger, java.util.Date e molte altre che implementano già la interfaccia Comparable. La classe String implementa Comparable<String> quindi possiede il compareTo(String) che si può sfruttare per confrontare due stringhe.

Pertanto si può fare ad esempio:

return persona1.getCognome().compareTo(persona2.getCognome());

Caso 3: Attributo di tipo reference che NON implementa Comparable

Ci possono essere attributi da confrontare che sono oggetti che non implementano Comparable. In questi casi si può comunque tentare di fare qualcosa. L’ideale sarebbe fare in modo che la classe di questi oggetti implementi Comparable. Se non è possibile (non ci sono i sorgenti, non si può modificare il sorgente, ecc...) si può comunque fare una valutazione sul contenuto della classe per vedere se e quali attributi si possono confrontare singolarmente.

Ci potrebbero essere delle classi che offrono modalità alternative/non-standard per la comparazione, ad esempio metodi chiamati after e/o before che potrebbero essere sfruttati. Comunque, fortunatamente, questo scenario capita abbastanza raramente.

4.2) Numero degli attributi

Riguardo il numero degli attributi, se ci sono 2 o più attributi si fanno solitamente i confronti sugli attributi in “cascata”, terminando appena si riesce ad ottenere un risultato inequivocabile e ignorando tutti gli altri attributi il cui confronto non sarebbe più determinante.

Si parte generalmente da un attributo che è stato scelto per avere “peso” maggiore e si confronta questo tra i due oggetti. Se uno dei due è minore/maggiore dell’altro, si ha già il risultato finale. Se invece sono uguali allora si passa a confrontare l’attributo di “peso” inferiore e si continua così fino all’ultimo attributo.

L’esempio classico è quando si confrontano degli oggetti Persona per cognome/nome:

  • prima si confrontano i due cognomi. Se uno dei due è minore o maggiore dell’altro, si ha già il risultato finale (non c’è alcun bisogno di confrontare i nomi!)
  • solo se i due cognomi sono uguali, allora in questo caso si confrontano i nomi

Questa logica si realizza ad esempio così:

int r = persona1.getCognome().compareTo(persona2.getCognome());

if (r == 0) {
    r = persona1.getNome().compareTo(persona2.getNome());
}

return r;

4.3) Trattamento dei valori null

In un confronto come il seguente:

int r = persona1.getCognome().compareTo(persona2.getCognome());

appare abbastanza evidente che se persona1.getCognome() restituisce un null, la invocazione di compareTo causa un NullPointerException. Generalmente gli attributi di tipo reference che si confrontano sarebbe bene che non siano mai null. Se invece è possibile/lecito che un attributo sia null, allora bisogna prestare ovviamente un po’ di attenzione. E si deve stabilire innanzitutto una cosa importante: se un valore null deve venire prima o dopo di un valore non-null.

Supponendo che nel confronto del cognome un null deve venire prima di un non-null, allora il confronto si può realizzare così:

int r;

if (persona1.getCognome() != null) {
    if (persona2.getCognome() != null) {
        r = persona1.getCognome().compareTo(persona2.getCognome());
    } else {
        r = +1;   // persona1.getCognome() non-null viene DOPO un null
    }
} else {
    if (persona2.getCognome() != null) {
        r = -1;   // persona1.getCognome() null viene PRIMA di un non-null
    } else {
        r = 0;    // un null è uguale ad un null
    }
}

// ......

Effettivamente scritto così è un po’ lungo e si potrebbe in parte anche compattare o magari “girare” in altro modo ma sostanzialmente la logica è quella, cioè bisogna considerare tutti i casi in cui il valore dell’attributo è null.

5) Esempio d’uso di Comparable

Se si ha ad esempio una classe Persona (come quella mostrata all’inizio) e la si vuole rendere “comparabile” tramite Comparable per confrontare cognome/nome, allora si può fare nel seguente modo:

public class Persona implements Comparable<Persona> {
    private String nome;
    private String cognome;
    private int annoNascita;

    public Persona(String nome, String cognome, int annoNascita) {
        this.nome = nome;
        this.cognome = cognome;
        this.annoNascita = annoNascita;
    }

    public String getNome() {
        return nome;
    }

    public void setNome(String nome) {
        this.nome = nome;
    }

    public String getCognome() {
        return cognome;
    }

    public void setCognome(String cognome) {
        this.cognome = cognome;
    }

    public int getAnnoNascita() {
        return annoNascita;
    }

    public void setAnnoNascita(int annoNascita) {
        this.annoNascita = annoNascita;
    }

    @Override
    public int compareTo(Persona altraPersona) {
        int r = getCognome().compareTo(altraPersona.getCognome());

        if (r == 0) {
            r = getNome().compareTo(altraPersona.getNome());
        }

        return r;
    }

    @Override
    public String toString() {
        return "Persona[" + nome + " " + cognome + ", " + annoNascita + "]";
    }

    // equals/hashCode omessi per brevità (non importanti ora)
}

Una prova di ordinamento si può effettuare con il seguente codice.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ProvaComparablePersone {
    public static void main(String[] args) {
        List<Persona> persone = new ArrayList<Persona>();
        persone.add(new Persona("Mario", "Rossi", 1982));
        persone.add(new Persona("Roberto", "Bianchi", 1979));
        persone.add(new Persona("Giacomo", "Verdi", 1965));
        persone.add(new Persona("Elena", "Rossi", 1982));
        persone.add(new Persona("Anna", "Neri", 1991));
        persone.add(new Persona("Luisa", "Marrone", 1979));

        Collections.sort(persone);

        for (Persona p : persone) {
            System.out.println(p);
        }
    }
}

L’output è il seguente:

Persona[Roberto Bianchi, 1979]
Persona[Luisa Marrone, 1979]
Persona[Anna Neri, 1991]
Persona[Elena Rossi, 1982]
Persona[Mario Rossi, 1982]
Persona[Giacomo Verdi, 1965]

Come si può vedere, i cognomi sono ordinati e a parità di cognome (es. Rossi) anche i nomi sono ordinati.

Il metodo sort di Collections usato nell’esempio è uno dei principali metodi di “utilità” del framework che implementa l’algoritmo per ordinare una lista di oggetti. Questo sort ha la seguente forma:

public static <T extends Comparable<? super T>> void sort(List<T> list)

Affinché il sort possa funzionare correttamente, la lista passata in argomento deve avere le seguenti caratteristiche:

1) Tutti gli oggetti nella lista devono implementare la interfaccia Comparable.

Questo è necessario perché l’algoritmo di ordinamento implementato nel sort delega la comparazione agli oggetti nella lista. In pratica questo sort si aspetta che il criterio di comparazione arrivi “implicitamente” dagli oggetti stessi contenuti nella lista.

2) Tutti gli oggetti nella lista devono essere “mutualmente comparabili”, ovvero per due qualunque elementi e1 e e2 presi dalla lista, la invocazione di e1.compareTo(e2) non deve causare un ClassCastException.

La motivazione di questo vincolo è anche abbastanza semplice da spiegare: normalmente le classi che sono Comparable sono fatte per permettere il confronto solo con altri oggetti di quella stessa classe. Un oggetto String si può confrontare solo con un altro oggetto String, un oggetto Integer si può confrontare solo con un altro oggetto Integer, ecc...

Pertanto se si ha un array o lista da ordinare, dovrebbe contenere solo oggetti dello stesso tipo, in modo che siano tutti “mutualmente comparabili”. Avere invece ad esempio una lista List<Object> che contiene vari oggetti di tipo eterogeneo può essere un grosso problema, anche perché bisognerebbe stabilire (con un Comparator!) delle regole apposite ben precise, del tipo: un oggetto String deve venire prima o dopo di un oggetto Integer??

3) La lista deve essere mutabile ma non è necessario che sia espandibile.

L’ordinamento di una sequenza di elementi ovviamente non espande (né riduce) la sequenza. Per l’algoritmo di ordinamento normalmente è sufficiente che gli elementi della lista siano settabili, quindi si può usare qualunque implementazione di List che sia “mutabile” in tal senso. Anche ad esempio una lista creata con il Arrays.asList(......) (che è mutabile ma non espandibile).

Ovviamente il sort non si può usare con una lista ottenuta ad esempio dal Collections.unmodifiableList(lista) perché fornisce una visione completamente “immutabile” (read-only) della lista passata in argomento.

Nota: esiste nella classe java.util.Arrays un metodo statico di “utilità” equivalente per ordinare gli array di oggetti basandosi implicitamente su Comparable.

6) Esempio d’uso di Comparator

Come esempio d’uso si può fare un comparatore per la classe Persona che sia in grado di ordinare per anno di nascita decrescente e a parità di anno per cognome/nome.

import java.util.Comparator;

public class AnnoDecrCognomeNomePersonaComparator implements Comparator<Persona> {
    @Override
    public int compare(Persona persona1, Persona persona2) {
        int r;

        if (persona1.getAnnoNascita() < persona2.getAnnoNascita()) {
            r = +1;
        } else if (persona1.getAnnoNascita() > persona2.getAnnoNascita()) {
            r = -1;
        } else {
            r = persona1.getCognome().compareTo(persona2.getCognome());

            if (r == 0) {
                r = persona1.getNome().compareTo(persona2.getNome());
            }
        }

        return r;
    }
}

Con questo comparatore l’anno di nascita viene ordinato in senso decrescente. Infatti se la condizione:

persona1.getAnnoNascita() < persona2.getAnnoNascita()

è “vera” (quindi l’anno di persona1 è minore dell’anno di persona2) viene restituito +1 per indicare che persona1 deve venire dopo persona2, cosa che denota appunto il senso decrescente dell’anno di nascita.

Il comparatore si può quindi usare in una classe di prova nel seguente modo:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ProvaComparatorPersone {
    public static void main(String[] args) {
        List<Persona> persone = new ArrayList<Persona>();
        persone.add(new Persona("Mario", "Rossi", 1982));
        persone.add(new Persona("Roberto", "Bianchi", 1979));
        persone.add(new Persona("Giacomo", "Verdi", 1965));
        persone.add(new Persona("Elena", "Rossi", 1982));
        persone.add(new Persona("Anna", "Neri", 1991));
        persone.add(new Persona("Luisa", "Marrone", 1979));

        Collections.sort(persone, new AnnoDecrCognomeNomePersonaComparator());

        for (Persona p : persone) {
            System.out.println(p);
        }
    }
}

L’output è il seguente:

Persona[Anna Neri, 1991]
Persona[Elena Rossi, 1982]
Persona[Mario Rossi, 1982]
Persona[Roberto Bianchi, 1979]
Persona[Luisa Marrone, 1979]
Persona[Giacomo Verdi, 1965]

Come si può vedere, gli anni sono ordinati in senso decrescente e a parità di anno si ha il tradizionale ordine per cognome/nome.

L’unica differenza con il precedente ProvaComparablePersone è la invocazione del sort. Questa infatti è l’altra versione di sort presente in Collections che ha la seguente forma:

public static <T> void sort(List<T> list, Comparator<? super T> c)

Questo sort, a differenza del precedente, riceve esplicitamente un oggetto Comparator che utilizza per fare i confronti tra gli oggetti Persona.

In modo similare al precedente sort, anche questa versione richiede che la lista passata in argomento abbia alcune caratteristiche:

1) Tutti gli oggetti nella lista devono essere “mutualmente comparabili”, ovvero per due qualunque elementi e1 e e2 presi dalla lista, la invocazione di unComparator.compare(e1, e2) non deve causare un ClassCastException.

2) La lista deve essere mutabile ma non è necessario che sia espandibile.

Nota: esiste nella classe java.util.Arrays un metodo statico di “utilità” equivalente per ordinare gli array di oggetti basandosi esplicitamente su Comparator.

7) Comparazione con le novità di Java 7

In Java 7 nelle classi “wrapper” dei tipi primitivi (java.lang.Byte, java.lang.Short, ecc...) sono stati aggiunti dei metodi statici chiamati compare per semplificare la comparazione tra due valori primitivi in modo da evitare l’utilizzo esplicito degli operatori relazionali < (minore) e > (maggiore).

In pratica:

  • la classe Byte ha un: public static int compare(byte x, byte y)
  • la classe Short ha un: public static int compare(short x, short y)
  • la classe Integer ha un: public static int compare(int x, int y)

e così via in maniera similare anche per le altre classi “wrapper” dei primitivi (es. Long, ecc...).

Il valore restituito da questi metodi compare rispecchia esattamente lo stesso concetto dei metodi compareTo/compare delle interfacce Comparable/Comparator, ovvero:

  • un valore < 0 per indicare che x è minore di y
  • un valore = 0 per indicare che x è uguale a y
  • un valore > 0 per indicare che x è maggiore di y

Il comparatore mostrato prima si può quindi riscrivere da Java 7 in questo modo:

// Da Java 7 in avanti
import java.util.Comparator;

public class AnnoDecrCognomeNomePersonaComparator implements Comparator<Persona> {
    @Override
    public int compare(Persona persona1, Persona persona2) {
        int r = Integer.compare(persona2.getAnnoNascita(), persona1.getAnnoNascita());

        if (r == 0) {
            r = persona1.getCognome().compareTo(persona2.getCognome());

            if (r == 0) {
                r = persona1.getNome().compareTo(persona2.getNome());
            }
        }

        return r;
    }
}

Una cosa importante da notare è che il primo argomento del Integer.compare è l’anno di nascita di persona2, non di persona1. Questo scambio serve per mantenere il senso decrescente dell’anno esattamente come è stato fatto per la precedente versione.

Se ad esempio persona2.getAnnoNascita() vale 1970 e persona1.getAnnoNascita() vale 1990, il Integer.compare restituirà un valore < 0 che sarà restituito a sua volta dal compare di AnnoDecrCognomeNomePersonaComparator. Ma in questo comparatore un valore < 0 significa che persona1 deve venire prima di persona2. Quindi il persona1 con anno 1990 viene effettivamente visto come “minore” rispetto al persona2 con anno 1970, dando appunto il senso decrescente dell’anno di nascita.

8) Comparazione con le novità di Java 8

Java 8 è la release che ha portato molte novità nel linguaggio Java tra cui: lambda expression, method references, metodi statici e di default nelle interfacce e altro.

Con tutte queste novità è possibile implementare un Comparator (che da Java 8 è una functional interface) in modo molto compatto utilizzando ad esempio una lambda expression. Se si vuole realizzare un Comparator su oggetti Persona per confrontare solo i nomi (che non siano null), si può fare in questo modo:

Collections.sort(persone, (p1, p2) -> p1.getNome().compareTo(p2.getNome()));

La interfaccia java.util.List da Java 8 ha anche un nuovo metodo di default chiamato sort che riceve esplicitamente un Comparator. Quindi a condizione che il reference della lista non sia null, è anche possibile fare:

persone.sort((p1, p2) -> p1.getNome().compareTo(p2.getNome()));

Le possibilità per creare dei Comparator in modo molto compatto però non finiscono qui. Come già anticipato in una sezione precedente, anche la interfaccia Comparator è stata aggiornata in Java 8 per avere dei nuovi metodi statici e di default. Tramite questi nuovi metodi è possibile comporre un Comparator che opera su più attributi in maniera compatta e soprattutto molto “fluente” e leggibile. Un esempio è il seguente (funzionalmente equivalente al precedente AnnoDecrCognomeNomePersonaComparator):

Comparator<Persona> comparatore = Comparator.comparingInt(Persona::getAnnoNascita).reversed()
        .thenComparing(Persona::getCognome)
        .thenComparing(Persona::getNome);

Collections.sort(persone, comparatore);     // oppure: persone.sort(comparatore);

Questi nuovi metodi comparing/comparingXyz/thenComparing/thenComparingXyz ricevono una “funzione” che funge da key extractor, cioè che estrae il valore dell’attributo dall’oggetto da confrontare. Per passare questa funzione è molto frequente e tipico usare un method reference che fa riferimento al metodo “getter”, come è stato fatto nell’esempio. Quindi per ciascun attributo questa funzione viene invocata due volte, una volta con il primo oggetto e un’altra volta con il secondo oggetto. Il comparatore di quell’attributo, avendo quindi i due valori a disposizione, applica la comparazione nel modo appropriato per il tipo di dato.

Il vantaggio evidente di questo modo di comporre un Comparator è che è molto compatto, “fluente” e soprattutto leggibile. C’è però uno svantaggio da tenere bene in considerazione: è più inefficiente.

Infatti non ci sono solo le funzioni di key extractor in mezzo a tutta questa logica di comparazione. Ogni volta che viene invocato uno dei thenComparing (o il reversed) viene creato un nuovo oggetto Comparator che “incapsula” il Comparator precedente a cui viene delegata in prima battuta la comparazione. Questo vuol dire che per ogni comparazione tra due oggetti c’è tutta una catena di invocazioni di metodi che rende la comparazione meno efficiente.

È ovviamente difficile fare stime precise ma indicativamente questo modo di comporre un Comparator può rendere più “pesante” l’ordinamento di una sequenza anche del 10~20% (se non di più) rispetto all’uso di un Comparator implementato “a mano” come è stato fatto nelle due versioni della classe AnnoDecrCognomeNomePersonaComparator.