[JAVA] merge sort: il codice è corretto (compilato senza errori)?

[zanardi84]

Premesso che viene compilato correttamente e che esegue l'ordine (provato con gli Integer sfruttando l'autoboxing), dichiarare come Comparable gli array temporanei è corretto o c'è una scelta migliore per il metodo generico? Cioè, non capisco se dichiararli Comparable garantisca quanto ho scritto nella firma dichiarazione della classe.

public class DivideEtImpera <T extends Comparable<? super T>>
{
private Comparable a[];

// costruttore
public DivideEtImpera(T array[])
{
a = array;
}

public void sort()
{
if(a.length <=1)
return;

Comparable primo[] = new Comparable[a.length/2];

Comparable secondo[] = new Comparable[a.length - primo.length];


// riempio i due array
for(int i = 0; i<primo.length; i++)
{
primo[i] = a[i];
}
for(int i = 0; i<secondo.length; i++)
{
secondo[i] = a[primo.length+i];
}

DivideEtImpera <T> dividePrimo = new DivideEtImpera(primo);
DivideEtImpera<T> divideSecondo = new DivideEtImpera(secondo);

dividePrimo.sort();
divideSecondo.sort();
// metto assieme in un nuovo array, ordinando.
merge(primo, secondo);
}

private void merge(Comparable primo[], Comparable secondo[])
{
int iPrimo = 0;
int iSecondo = 0;
int i = 0;

while(iPrimo < primo.length && iSecondo < secondo.length)
{
if(primo[iPrimo].compareTo(secondo[iSecondo])<0)
{
a[i] = primo[iPrimo];
iPrimo++;
}
else
{
a[i] = secondo[iSecondo];
iSecondo++;
}
i++;
}
// completo il riempimento degli array.
while(iPrimo < primo.length)
{
a[i] = primo[iPrimo];
iPrimo++;
i++;
}
while(iSecondo < secondo.length)
{
a[i] = secondo[iSecondo];
iSecondo++;
i++;
}
}
}

[banryu79]

Premesso che viene compilato correttamente e che esegue l'ordine (provato con gli Integer sfruttando l'autoboxing), dichiarare come Comparable gli array temporanei è corretto o c'è una scelta migliore per il metodo generico? Cioè, non capisco se dichiararli Comparable garantisca quanto ho scritto nella firma dichiarazione della classe.


public class DivideEtImpera <T extends Comparable<? super T>>
{ ...snip }


Ciao, risposta breve:
1) se si può, è meglio usare le collection con i generics, non gli array.
2) se si deve usare gli arrays una soluzione è passare la Class per conservare l'informazione sul tipo a runtime e usarla con il metodo java.util.Arrays.newInstance per costruire array generici. Leggi qui: How do I generically create objects and arrays? (http://www.angelikalanger.com/GenericsFAQ/FAQSections/ProgrammingIdioms.html#FAQ603)
Altro link da leggere: Java how to: Generic Array creation (on StackOverflow) (http://stackoverflow.com/questions/529085/java-how-to-generic-array-creation)

Poi circa la tua domanda sulla type safety nel tuo caso: possiamo fare un ragionamento di massima.
Visto che la classe DivideEtImpera per essere istanzia richiede un array generico il cui tipo parametrico sia un <T extends Comparable<? super Comparable>> hai la garanzia che due elementi di detto array siano confrontabili tra di loro (nel contesto di merge), poco importa che poi, internamente alla classe, tu in realtà crei e manipoli dei sotto-array di tipo Comparable, fintanto che gli elementi che ci infili dentro sono le istanze che hai ricevuto in fase di costruzione (ovvero istanze che in effetti sono compatibili con <T extends Comparable<? super Comparable>>).

La faccenda sarebbe diversa se tu, invece di limitarti a creare dei nuovi riferimenti ad array in cui infili elementi rcevuti da chi ha istanziato la classe, che so, creassi ex-novo degli elementi di tipo compatibile con Comparable ma non compatibile con <T extends Comparable<? super Comparable>>.

Chiaro no? :D