Comparable e Comparator

[newutente]

Non mi è chiaro il funzionamento di questo frammento di codice:

import java.util.Comparator;

public class StringComparator implements Comparator<String> {
    public int compare (String s1, String s2) {
        StringBuilder sb1 = new StringBuilder(s1);
        StringBuilder sb2 = new StringBuilder(s2);
        s1 = sb1.reverse().toString();
        s2 = sb2.reverse().toString();
        return s1.compareTo(s2);
    }
}

List<String> nomiList = new ArrayList<String>(Arrays.asList(nomi));
System.out.println("List non ordinata");
stampaList(nomiList);
Collections.sort(nomiList, new StringComparator());
System.out.println("List ordinata a stringhe al contrario");
stampaList(nomiList);

In modo particolare non capisco il funzionamento di questa istruzione:

Collections.sort(nomiList, new StringComparator());

e della classe StringComparator. Come funziona il metodo compare all'interno di quella classe? Non capisco il nesso visto che restituisce un intero (-1, 0, 1 a seconda del risultato del confronto).

Mi aiutate a capire?

[andbin]

Come funziona il metodo compare all'interno di quella classe? Non capisco il nesso visto che restituisce un intero (-1, 0, 1 a seconda del risultato del confronto).

Mi aiutate a capire?

In Java la comparazione degli oggetti è stata affrontata con le due interfacce Comparable/Comparator (gli operatori relazionali < > <= >= non funzionano con gli oggetti!). Le due interfacce servono a definire un criterio di ordinamento ma in contesti e modi differenti.
Comparable va implementato nella classe degli oggetti da comparare es.:

class Persona implements Comparable<Persona> { .... }

Di Comparable quindi ce ne può essere uno solo per una tipologia di oggetti. Questo criterio di ordinamento "dovrebbe" essere quello naturale per quel tipo di oggetti.

Comparator invece va implementato in una classe separata e ce ne possono essere quindi quanti ne vuoi es.:

class PersonaPerAnnoNascitaComparator implements Comparator<Persona> { .... }
class PersonaPerNomeDiscendenteComparator implements Comparator<Persona> { .... }
.....

Comparable ha int compareTo(T o) e la comparazione è tra il this e l'oggetto ricevuto dal metodo. Comparator ha int compare(T o1, T o2) che riceve i due oggetti.

La comparazione è quindi sempre e solo tra due oggetti. Chi implementa una di queste interfacce deve solo dire se un oggetto è minore/maggiore/uguale all'altro, restituendo appunto <0, >0 o 0.

Il Collections.sort ha due forme, una si basa su Comparable, l'altra su un Comparator esplicito. Ma il succo non cambia. L'algoritmo implementato in sort farà tante combinazioni di oggetti presi a due per volta dalla lista e invocherà compareTo/compare per sapere come considerare i due oggetti. In base al risultato di tanti compareTo/compare, sort ordinerà l'intera lista secondo quel criterio di ordinamento.

[newutente]

Ho capito il discorso, tuttavia non riesco a capire dove avviene l'invocazione del metodo compare. Cioè, dove avviene esattamente il confronto tra gli oggetti? Nel momento in cui viene creato un oggetto StringComparator passandolo in input al metodo sort?

[andbin]

Ho capito il discorso, tuttavia non riesco a capire dove avviene l'invocazione del metodo compare. Cioè, dove avviene esattamente il confronto tra gli oggetti? Nel momento in cui viene creato un oggetto StringComparator passandolo in input al metodo sort?

È all'interno del metodo sort che avviene la invocazione di compareTo (per la forma di sort che "presuppone" che gli oggetti siano Comparable) oppure di compare (per la forma che riceve il Comparator esplicito).

E come ho detto, il sort fa tante comparazioni e dai risultati deduce come riordinare la lista affinché segua quel criterio di ordinamento passato (con Comparable implicito o Comparator esplicito).

[newutente]

Forse inizio a capire però mi sfugge ancora una cosa.
Cerco di spiegarmi con un esercizio che ho fatto e che richiedeva l'ordinamento al contrario degli elementi interi di un array.
Vi posto sia la mia soluzione, così come l'ho pensata, sia quella del manuale:

SOLUZIONE MIA:

import java.util.*;

public class Vettore {
        public static void main(String args[]) {
            
            int[] vettore = {168,789,167,125,698};
            Arrays.sort(vettore);
            
            
            List<Integer> vettore2 = new ArrayList<Integer>();
            
            for(int i=0; i<vettore.length; i++) {
                vettore2.add(vettore[i]);
            }
            
            Collections.reverse(vettore2);
            
            
            System.out.println("Array ordinato al contrario:");
            
            Iterator<Integer> i = vettore2.iterator();
            while(i.hasNext()) {            
                 Integer numero = i.next();
                 System.out.println(numero);
             }
            
            
        }    
}

SOLUZIONE MANUALE:

import java.util.Arrays;

public class TestIntegerComparator {
    public static void main(String args[]) {
        Integer []array = {1942, 1947, 1971, 1984, 1976, 1974};
        Arrays.sort(array, new IntegerComparator());
        for (int intero : array) {
            System.out.println(intero);
        }
    }
}

import java.util.Comparator;

public class IntegerComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return -(o1.compareTo(o2));
    }   
}

Quello che mi sfugge è il perchè ha utilizzato il metodo sort nella sua seconda forma (quindi quello dove è richiesto l'oggetto della classe che implementa Comparator) quando poteva utilizzare il metodo reverse per invertire l'ordine degli elementi.
Probabilmente l'ha fatto per evitare di dover creare un'altra struttura oltre alla array dichiarato all'inizio e quindi immagino per risparmiare memoria.

In ogni caso vorrei cercare di comprendere meglio la logica di funzionamento di compare. In poche parole, qualsiasi siano gli elementi (ovviamente Integer) confrontati lui restituisce sempre un valore negativo? In teoria questo dovrebbe indicare che l'elemento (o1) sul quale si invoca il metodo è minore dell'elemento (o2) passato in input. Ma a quel punto non capisco il nesso.

[andbin]

Quello che mi sfugge è il perchè ha utilizzato il metodo sort nella sua seconda forma (quindi quello dove è richiesto l'oggetto della classe che implementa Comparator) quando poteva utilizzare il metodo reverse per invertire l'ordine degli elementi.
Probabilmente l'ha fatto per evitare di dover creare un'altra struttura oltre alla array dichiarato all'inizio e quindi immagino per risparmiare memoria.

No. Dato un array di interi "disordinato", ordinarlo in senso crescente e poi rovesciarlo (come hai fatto tu) è concettualmente la stessa cosa che ordinarlo applicando già un criterio di ordinamento al contrario (come la soluzione del manuale)!

Le differenze tecniche tra le due soluzioni ovviamente ci sono: tu parti da un int[] e in Arrays c'è un sort(int[] a). Ma non c'è un reverse per gli array. Quindi hai dovuto passarlo in un List<Integer> e poi usare il reverse di Collections.
Il manuale invece è partito da un Integer[] ed essendo un array di oggetti, esiste un sort per cui specificare un Comparator esplicito.
Presumibilmente il manuale voleva proprio mostrare un esempio di comparatore esplicito.

In poche parole, qualsiasi siano gli elementi (ovviamente Integer) confrontati lui restituisce sempre un valore negativo?

No, semplicemente "gira" il segno del risultato di compareTo. compareTo può restituire un valore 0, <0 o >0.
Se o1 è minore di o2, compareTo restituisce <0 (ovvero appunto o1 è minore di o2). Girando il segno, il sort vede >0 e lo interpreta come "o1 deve venire dopo di o2". Che appunto significa ordinare i numeri in senso decrescente.

Tra l'altro la soluzione del manuale, con il '-' personalmente non mi piace. Quando devo fare io cose del genere faccio semplicemente:

return o2.compareTo(o1);

che rende più chiaro il fatto che l'ordinamento è in senso contrario.

[newutente]

ma una volta che il compareTo ad ogni confronto fatto dal sort (2 elementi alla volta) restituisce i suoi risultati cosa succede? Cioè, il compareTo avrà generato una serie di valori <0, 0, >0 ma come fa il sort a capire quali sono gli elementi da invertire come posizione? Considera solo alcuni risultati?

[andbin]

ma una volta che il compareTo ad ogni confronto fatto dal sort (2 elementi alla volta) restituisce i suoi risultati cosa succede?

Dipende dall'algoritmo specifico di ordinamento .... ne esistono tanti.
Guarda ad esempio il Bubble-sort in Java: http://it.wikibooks.org/wiki/Impleme...bble_sort#Java

Osserva dove fa la comparazione. Nell'esempio tratta dei int, quindi ovviamente può usare < o >. Immagina ora oggetti (< e > non funzionano) e quindi immagina di sostituirci la invocazione di un compareTo o compare.
Se la condizione è true, vengono scambiati i due elementi.

Per altri algoritmi è ... più complicato.

[newutente]

ah quindi utilizzando il metodo sort (che sia quello di Arrays oppure quello di Collections) io non "vedo" quello che accade, la cosa che devo fare è solo invocarlo passandogli in input l'array da ordinare e il comparatore (praticamente l'oggetto della classe che implementa Comparator).
Ad esempio:

import java.util.Arrays;

public class Classe {
    public static void main(String args[]) {
        Integer []array = {1942, 1947, 1971, 1984, 1976, 1974};
        Arrays.sort(array, new IntegerComparator());
        ...
        }
    }
}

Poi una volta fatto questo vado a creare la classe che implementarà Comparator e all'interno di questa classe andrò a fare l'override di compare.
Ad esempio:

import java.util.Comparator;

public class IntegerComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return ... ;
    }   
}

Il resto lo fa sort. Giusto?

[andbin]

ah quindi utilizzando il metodo sort io non "vedo" quello che accade

Non vedi nel senso che l'algoritmo può essere più o meno complesso e come è fatto alla fin fine poco importa (se è fatto bene, ovviamente). Per i sort del framework comunque i sorgenti ci sono.

la cosa che devo fare è solo invocarlo passandogli in input l'array da ordinare e il comparatore (praticamente l'oggetto della classe che implementa Comparator).

Esatto.

Poi una volta fatto questo vado a creare la classe che implementarà Comparator e all'interno di questa classe andrò a fare l'override di compare.

Il resto lo fa sort. Giusto?

Esatto. Non stai implementando l'intero algoritmo di ordinamento ma solo la logica di comparazione tra due elementi. La logica del sort è sostanzialmente spezzata in due parti: una parte fissa/nota che è dovuta all'algoritmo di ordinamento ben preciso che ragiona solo in quel modo. Ma ad un certo punto dovrà comparare qualcosa e da solo non lo sa fare con gli oggetti. Quindi delega ad altro (Comparable/Comparator) implementato esternamente all'algoritmo.