KuroKami69 ha scritto:
vorrei fare un BST (binary searching tree) con i generics, e se ho capito bene, si deve usare il comparator. Ora, ho provato a capirci qualcosa del comparator, ma non ci ho capito assolutamente nulla. Quindi quel che chiedo io, come va usato? Come funziona?
Partiamo da un presupposto: in Java la comparazione degli oggetti è stata affrontata con l'uso di due interfacce specifiche: Comparable e Comparator. Comparable va implementato nella classe degli oggetti da comparare; Comparator si implementa in classi esterne, slegate dalla classe degli oggetti da comparare.
Riguardo il BST (vedi
qui su Wikipedia), la comparazione si applica ovviamente agli elementi dell'albero, per la ricerca ma ovviamente ANCHE per l'inserimento.
Guarda l'esempio di BST su Wikipedia, lì ci sono dei numeri. Con i numeri è abbastanza intuitivo. Ma si può applicare a qualunque altro tipo di dato, stabilendo un criterio di ordinamento. Se ho delle stringhe es. "arancia", "cocco", "mandarino", "mela", "uva" e voglio ordinarle con un BST secondo la lunghezza (ripeto:
lunghezza, non alfabeticamente), allora il BST può risultare così:
"arancia"
/ \
/ \
/ \
"mela" "mandarino"
/ \
/ \
/ \
"uva" "cocco"
"uva" è a sx di "mela" perché più corto; "cocco" è a dx di "mela" perché più lungo.
"mela" è a sx di "arancia" perché più corto; "mandarino" è a dx di "arancia" perché più lungo.
Tutto questo in sostanza vuol dire che il criterio di ordinamento deve
far parte del BST. Ovvero, quando crei un BST gli devi assegnare un criterio di ordinamento e quello deve restare tale per tutta la "vita" del BST.
Il criterio non può cambiare né per l'inserimento né per la ricerca, perché è il criterio di ordinamento che struttura l'albero!
Detto questo, la tua ultima definizione, ovvero:
public class BST<T implements Comparator<T>{...}>
semplicemente NON ha senso (è anche sbagliata, si usa
extends non implements con i bound). Il T è il "segnaposto" per il tipo degli oggetti nell'albero. Applicare un bound (limite) con Comparator, non ha senso perché come detto prima, Comparator NON si implementa negli oggetti da comparare!
Tecnicamente sarebbe più sensato se fosse:
public class BST<T extends Comparable<T>>
o in forma leggermente un po' più ampia
public class BST<T extends Comparable<? super T>>
Ma c'è una questione di concetto: io potrei voler mettere nel BST degli oggetti che NON implementano Comparable (es. dei java.net.URL) volendo però usare un Comparator. Ma gli oggetti, con quel bound, NON ci entrerebbero proprio! (per meglio dire: è il compilatore che non lo accetterebbe)
Quindi ricapitoliamo:
- si vuole stabilire il criterio di ordinamento SOLO con un Comparator esplicito (non è il caso più flessibile ma è lecito)
- come detto prima, il criterio DEVE far parte del BST.
Pertanto la cosa logica da fare è tenere il Comparator come attributo nel BST.
public class BST<T> {
private Comparator<? super T> comparatore;
public BST(Comparator<? super T> comparatore) {
this.comparatore = comparatore;
}
// .......
}