[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]

Originariamente inviato da 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>> 
{ ...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?
Altro link da leggere: Java how to: Generic Array creation (on StackOverflow)

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?