Comparable e Comparator

Abbiamo visto come alcune Collections memorizzano gli elementi secondo un ordine, sappiamo che ad esempio sulle String l’ordinamento viene fatto sui caratteri che la compongono, o sui numeri che seguono un ordinamento naturale.

Possiamo però ordinare anche gli oggetti che definiamo noi, Java ti fornisce un interfaccia chiamata Comparable, se la tua classe implementa questa interfaccia, può essere memorizzata in strutture dati che prevedono l’ordinamento, altrimenti prenderai un eccezione quando tenterai di aggiungerle.

Java ti fornisce anche una classe per eseguire ordinamenti senza che le tue classi implementino Comparable, questa classe di chiama Comparator.

Comparable

vediamo come è definita questa interfaccia :

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

Ovviamente utilizza i generics, vediamo come definire una classe che implementa Comparable :

public class Aereo implements Comparable<Aereo> {
  private String nome;
  public Aereo(String nome) {
    this.nome = nome;
  }
  public int compareTo(Aereo o) {
    return this.nome.compareTo(o.nome);
  }
}

Molto semplice, vediamo che nella nostra implementazione, non facciamo altro che delegare a compareTo di String, comunque, il metodo compareTo ha la seguente logica.

  • restituisce 0 se gli oggetti sono uguali
  • restituisce un valore minore di 0 se l’oggetto corrente è minore di quello passato
  • restituisce un valore maggiore di 0 se l’oggetto corrente è maggiore di quello passato

Nel nostro caso abbiamo utilizzato i generics, ma se ci troviamo a dover lavorare con codice vecchio, compareTo vorrà un Object e sarà necessario eseguire il cast esplicito :

public class VecchioAereo implements Comparable {
  public int compareTo(Object o) {
    Aereo aereo = (Aereo)o;
    return this.nome.compareTo(o.nome);
  }
}

Consistenza di compareTo con equals

Introducendo il metodo compareTo stai introducendo altra logica per l’eguaglianza del tuo oggetto, e devi stare attento se hai già implementato equals, la logica deve essere congruente

  • se x.equals(y) == true allora x.compareTo(y) == 0

Comparator

A volte puoi avere la necessità di ordinare oggetti che non implementano Comparable, immaginiamo di avere la nostra classe Aereo che implementa Comparable e il metodo compareTo confronta per il nome ma noi vogliamo ordinarli secondo il peso in tonnellate :

public class Aereo implements Comparable<Aereo> {
  private int peso;
  private String nome;
  public int compareTo(Aereo o) {
    return this.nome.compareTo(o.nome));
  }
}

Per ordinarli con il peso non possiamo utilizzare compareTo, Java ci permette di specificare una logica di ordinamento differente tramite la classe Comparator :

public static void main(String... args) {
  Comparator<Aereo> comparator = new Comparator<Aereo> {
    public int compare(Aereo a1, Aereo a2) {
      return a1.peso - a2.peso;
    }
  };
  List<Aereo> aerei = new ArrayList<>();
  aerei.add(new Aereo("Boeing",700));
  aerei.add(new Aereo("Cessna",100));
  Collections.sort(aerei); 
  System.out.println(aerei); //Boeing, Cessna
  Collections.sort(aerei, comparator);
  System.out.println(aerei); //Cessna, Boeing
}

Tutto molto semplice, abbiamo definito una inner class di tipo Comparator e fornito l’implementazione del metodo compare, notiamo che Comparator è una Interfaccia funzionale, quindi possiamo implementarla mediante lambda expression :

Comparator<Aereo> comparator = (a1, a2) -> a1.peso - a2.peso;
Comparator<Aereo> comparator = (Aereo a1, Aereo a2) -> { return a1.peso - a2.peso; }

Anche Comparable è un interfaccia funzionale, ma utilizzarla con le lambda non è corretto in questo deve essere un metodo implementato nella definizione della classe.

Notiamo le differenza tra Comparable e Comparator

Differenza Comparable Comparator
Package java.lang java.util
Deve essere implementata nella classe ? Si No
Nome del metodo compareTo compare
Numero di parametri 1 2
Si dichiara con le lambda ? No Si

 

Per l’esame ricordiamoci che Comparable ha il metodo compareTo e Comparator ha compare !

Ricerca e Ordinamento

Sappiamo già come eseguire ricerche tramite la classe Array o Collection, Ora introdurremo l’interfaccia Comparable e la classe Comparator.

Il sort utilizza il metodo compareTo , si aspetta che gli oggetti implementino l’interfaccia Comparable : 

import java.util.*;
public class OrdinaAerei {
  static class Aereo { int id; }
  public static void main(String... args) {
    List<Aerei> aerei = new ArrayList<>();
    aerei.add(new Aereo());
    Collections.sort(aerei); //ERRORE
  }
}

Perchè va in errore di compilazione ? perchè la nostra classe Aereo non implementa l’interfaccia Comparable, di fatto Collections non può procedere all’ordinamento, vediamo come risolvere utilizzando Comparator

import java.util.*;
public class OrdinaAerei {
 static class Aereo { int id; }
 public static void main(String... args) {
 List<Aerei> aerei = new ArrayList<>();
 Comparator comp = (a1, a2) -> a1.id - a2-id;
 aerei.add(new Aereo());
 Collections.sort(aerei, comp); 
 }
}

Ora funziona correttamente.

il metodo sort e binarySearch permettono di passare un comparator come parametro, quando non si vuole utilizzare il sort naturale o specificato nella definizione della classe, ma facciamo attenzione, è abbastanza pericoloso e nasconde dei trabocchetti :

List<String> nomi = Arrays.asList("Fluffy","Hoppy");
Comparator<String> c = Comparator.reverseOrder();
int index = Collections.binarySearch(names, "Hoppy", c);
System.out.println(index);

questo codice restituisce -1, perchè ?, perchè la nostra lista è ordinata in maniera ascendente, con il nostro comparator abbiamo invertito l’ordinamento in maniera discendente, abbiamo chiesto poi un binarySearch in ordine discendente ma il nostro array è ordinato in ordine ascendente, di fatto Java non riesce a verificare

Cosa succede se tentiamo di aggiungere un oggetto che non implementa Comparable ad un TreeSet ?

public class AereoTreeSet {
  static class Aereo { int id; }
  public static void main(String... args) {
    Set<Aereo> aerei = new TreeSet<>();
    aerei.add(new Aereo("Boeing")); //throws exception
  }
}

Otterrai un ClassCastException : comparing.Aereo cannot be cast to java.lang.Comparable

Possiamo per fornire ad una collection che implementa l’ordinamento, un modo per ordinare gli oggetti se questi non implementano Comparable :

Set<Aereo> aerei = new TreeSet<>(new Comparator<Aerei>() {
  public int compare(Aereo a1, Aereo a2) {
    return a1.id - a2.id;
  }
});

ora possiamo fare tranquillamente :

aerei.add(new Aereo());