package esami;

public class esami2 {

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[]a= {8, 1, 3, 1, 5, 10, 1, 3};
		stampaArray (a);
		ordinamentoRelativo (a, 4);
		stampaArray (a);
		int[]b={8, 1, 3, 1, 5, 10, 1, 3};
		stampaArray (b);
		stampaArray (ripetizioni(b));
		int[]c={8, 1, 3, 1, 5, 10, 1, 3};
		ordinamentoRelativoPD (c);
		stampaArray (c);
		int [] d ={1, 8, 3, 1, 5, 10, 1, 4};
		int [] e ={8, 1, 5, 10, 10,10,11, 4, 3, 3};
		System.out.println("equiv :" + equivalenti(d,e));
		System.out.println("equiv2 :" + equivalenti2(d,e));
		int [] f ={1, 8, 3, 1, 5, 10, 1, 4};
		System.out.println(sommaDiDue (f, 13));
		System.out.println(sommaDiDue (f, 17));
		stampaArray (f);
	}
	
	
static void stampaArray (int[]a) {      
		if (a==null) {
	           System.out.println("Array non inizializzato");         
	           return;
			}   
		System.out.print("{ ");
		for (int i=0; i<a.length; i++){
			System.out.print(a[i]);
			if (i<a.length-1) System.out.print(", ");
				
			}
		System.out.println(" }");
		}
	
static void mergeSort(int[]a){
		//dimensione input n=a.length
		if (a==null|| a.length==0) return;
		mergeSort(a,0, a.length -1);    
	}
	
static void mergeSort(int[]a, int l, int r){
		// dimensione input r-l+1
		//CASO BASE
		if (l==r) return;              
		int p=(r+l)/2; //  l<=p<r      
		mergeSort(a,l,p);             
		mergeSort(a, p+1,r);       
		merge(a,l,p,r);            
	}
	
static void merge(int[]a, int l, int p, int r)
	{//dimensione dell'input r-l+1
		int n1=p-l+2;
		int n2=r-p+1;
		int maxint=2147483647;    
		int[] sin= new int[n1];   
		int[] des= new int[n2];   
		for (int i=0; i<sin.length-1; i++) 
		{sin[i]=a[l+i];}                   
		sin[n1-1]=maxint;          
		for (int i=0; i<des.length-1; i++) 
		{des[i]=a[p+1+i];}     
		des[n2-1]=maxint;     
		int i=0;     
		int j=0;     
		for(int k=l; k<=r;k++)    
		{if (j==n2-1 || sin[i]< des[j])  
		     {a[k]=sin[i]; i++;}
		else {a[k]=des[j]; j++;}
		}
	}
	

static int binarySearch (int[] a, int v) 
//dimensione dell'input n=a.length complessità log n
		{ if (a==null || a.length==0) return -1; 
		return binarySearch(a,v,0,a.length-1);         
		}


static int binarySearch (int[] a, int v,int l,int r) 	{ 
		//CASO BASE
		if (l==r) {if (a[l]==v) return l; else return -1;} 
		int p=(l+r)/2;  //l<=p<r   
		if (a[p]>=v)    
			return binarySearch(a,v,l,p);  
		return binarySearch(a,v,p+1,r);    
		}
	

/*
	 * Esercizio 
	 * Scrivere un metodo in Java 
	 * static void ordinamentoRelativo (int[] a, int rif)  
	 * che, preso come parametro un array a di numeri interi 
	 * e un intero rif, ordina gli elementi di a in 
	 * modo non decrescente rispetto alla loro distanza 
	 * (in valore assoluto) dall’intero rif. 
	 * Ad esempio, se a={8, 1, 3, 1, 5, 10, 1, 3} e rif=4, 
	 * a sarà ordinato così:{3, 5, 3, 1, 1, 1, 8, 10}. 
	 * Si analizzi la complessità temporale del metodo 
	 * proposto: tale metodo deve avere complessità temporale 
	 * O(n log n) nel caso peggiore (soluzioni con 
	 * complessità temporale peggiore danno luogo a una 
	 * valutazione minore), dove n è la lunghezza dell’array 
	 * a in input. 
	 */


static void ordinamentoRelativo (int[] a, int rif){
		//dimensione input n=a.length
		if (a==null|| a.length==0) return; //c0   | 1 volta
		ordinamentoRelativo(a, rif ,0, a.length -1);                              
                                             //C'(n) | 1 volta
	}
	
static void ordinamentoRelativo(int[]a, int rif, int l, int r) 
	{
	// dimensione input r-l+1
	//CASO BASE
	if (l==r) return;                    // c1  | 1 volta
	int p=(r+l)/2;      //  l<=p<r         c2 | 1 volta
	ordinamentoRelativo (a, rif ,l,p);   // C'(n/2) | 1 volta
	ordinamentoRelativo (a, rif, p+1,r); // C'(n/2) | 1 volta
	ordina(a,rif,l,p,r);             // C''(n) = c*n| 1 volta
	}
	
static void ordina(int[]a, int rif, int l, int p, int r)
	{//dimensione dell'input r-l+1
	 int n1=p-l+1;  
	 int n2=r-p;    
	 int[] sin= new int[n1];   
	 int[] des= new int[n2];   
	 for (int i=0; i<n1; i++) {sin[i]=a[l+i];}                   
	 for (int i=0; i<n2; i++) {des[i]=a[p+1+i];}
	 int i=0;  // per scorrere sin   
	 int j=0;  // per scorrere des  
	 for(int k=l; k<=r;k++)    
		{
		if (i==n1)  {a[k]=des[j]; j++;}
		else {
		    	if (j==n2) {a[k]=sin[i]; i++;}
		      else {int v1=sin[i]-rif; if (v1<0) v1=-v1;
		            int v2=des[j]-rif; if (v2<0) v2=-v2;
		        	 if (v1<v2) {a[k]=sin[i]; i++;} 
		      	 else {a[k]=des[j]; j++;} 
		            }
		      }
             }
	} 
	
/*
 * L’array delle ripetizioni di un dato array a di numeri 
 * interi è definito come un array avente come lunghezza 
 * il numero di elementi distinti dell’array a, e 
 * contenente in posizione i (i=0,1,…) il numero di 
 * ripetizioni nell’array a dell’(i+1)-esimo elemento più 
 * piccolo di a. 
 * Ad esempio, se a={8, 1, 3, 1, 5, 10, 1, 3}, 
 * il suo array di ripetizioni è {3,2,1,1,1} in quanto in 
 * a ci sono 5 elementi distinti, e l’elemento più 
 * piccolo di a (1) compare 3 volte, il secondo elemento  
 * più piccolo(3) compare 2 volte, e i rimanenti elementi 
 * compaiono solo una volta. 
 * Scrivere un metodo in Java 
 *    static int[] ripetezioni (int[] a) 
 * che, preso come parametro un array a di numeri interi, 
 * crea e restituisce il suo array delle ripetizioni. 
 * Se a vale null, viene restituito null; se a è vuoto, 
 * viene restituito un array vuoto. 
 * Si analizzi la complessità temporale del metodo 
 * proposto: tale metodo può richiamare qualsiasi 
 * algoritmo di ordinamento e/o di ricerca visto a 
 * lezione e deve avere complessità temporale O(n log n) 
 * nel caso peggiore (soluzioni con complessità temporale 
 * peggiore danno luogo a una valutazione minore), 
 * dove n è la lunghezza dell’array a in input. 
 */

	
static int[] ripetizioni (int[] a){
	//dimensione input n=a.length
	if (a==null|| a.length==0) return a;
	mergeSort (a);
	int cont=1;
	int ultimo=a[0];
	for (int i=1; i<a.length; i++) 
		{if (a[i]!= ultimo){cont++; ultimo=a[i];}}
	int[]risultato=new int[cont];
	ultimo=a[0];
	int k=0;
	risultato[k]=1;
	for (int i=1; i<a.length; i++) 
		{if (a[i]!= ultimo){k=k+1; ultimo=a[i];}
		 risultato[k]++;
		}
	return risultato;
}
	

/*Esercizio 
 * Scrivere un metodo in Java 
 *     static void ordinamentoRelativoPD (int[] a) 
 * che, preso come parametro un array a di numeri interi, 
 * ordina gli elementi di a in modo non decrescente 
 * dando però precedenza agli elementi pari rispetto a quelli 
 * dispari. In altre parole, nell’array ordinato dovranno 
 * comparire prima tutti gli elementi pari (ordinati in ordine 
 * non decrescente) e poi tutti i dispari (ordinati in 
 * ordine non decrescente).  
 * Ad esempio, se a={8, 1, 3, 1, 5, 10, 1, 3}, dovrà essere 
 * ordinato così: {8, 10, 1, 1, 1, 3, 3, 5}. 
 * Si analizzi la complessità temporale del metodo proposto: 
 * tale metodo deve avere complessità temporale O(n log n) nel 
 * caso peggiore (soluzioni con complessità temporale peggiore 
 * danno luogo a una valutazione minore), 
 * dove n è la lunghezza dell’array a in input. 
 */		

	
static void ordinamentoRelativoPD (int[] a){
		//dimensione input n=a.length
		if (a==null|| a.length==0) return;
		ordinamentoRelativoPD (a,0, a.length -1);    
	}

static void ordinamentoRelativoPD (int[]a, int l, int r){
		// dimensione input r-l+1
		//CASO BASE
		if (l==r) return;              
		int p=(r+l)/2; //  l<=p<r      
		ordinamentoRelativoPD (a,l,p);             
		ordinamentoRelativoPD (a, p+1,r);       
		ordinaPD(a,l,p,r);        
	}

static void ordinaPD(int[]a, int l, int p, int r)
	{//dimensione dell'input r-l+1
 	int n1=p-l+1;  
	int n2=r-p;    
	int[] sin= new int[n1];   
	int[] des= new int[n2];   
	for (int i=0; i<n1; i++) {sin[i]=a[l+i];}                   
	for (int i=0; i<n2; i++) {des[i]=a[p+1+i];}
	int i=0;  // per scorrere sin   
	int j=0;  // per scorrere des  
	for(int k=l; k<=r;k++)    
	 {
	 if (i==n1)  {a[k]=des[j]; j++;}
	 else {int v1=sin[i] %2;
		 if (j==n2 || v1< des[j]%2) {a[k]=sin[i]; i++;}
		 else {int v2=des[j]%2; 
		       if (v2<v1) {a[k]=des[j]; j++;}
		       else {if (sin[i]<des[j]) {a[k]=sin[i]; i++;} 
		      	  else {a[k]=des[j]; j++;}
		      	 }
		        }
		   }
	   }
	} 
	
	
	
/*
 * Scrivere un metodo in Java
 * static boolean equivalenti (int[] a, int[] b)
 * che, presi come parametro due array a e b di numeri interi, 
 * restituisce true se e solo se a e b contengono gli stessi
 * elementi (non tenendo in conto le ripetizioni 
 * degli elementi e/o l’ordine in cui essi compaiono).
 * Se a e b valgono entrambi null, viene restituito true; 
 * se solo uno dei due array vale null, viene restituito 
 * false. Ad esempio, se a={1, 8, 3, 1, 5, 10, 1, 4} 
 * e b={8, 1, 5, 10, 4, 3, 3}, il metodo deve restituire true.
 * Si analizzi la complessità temporale del metodo proposto: 
 * tale metodo può richiamare qualsiasi algoritmo di
 * ordinamento e/o di ricerca visto a lezione e 
 * deve avere complessità temporale O(n log n) nel caso 
 * peggiore (soluzioni con complessità temporale peggiore 	
 * danno luogo a una valutazione minore),
 * dove n è la lunghezza dell’array a in input.
 */
	
static boolean equivalenti (int[] a, int[] b){
	//dimensione input n= max(a.length, b.length)
	if (a==null && b==null) return true;
	if (a==null || b==null) return false;
	if (a.length==0 && b.length==0) return true;
	if (a.length==0 || b.length==0) return false;
	mergeSort (a);
	mergeSort (b);
	int x=a[0];
	int y=b[0];
	int i=1; int j=1;
	if (x!=y) return false; 
	while (i<a.length && j< b.length)
	if (a[i]==x && b[j]==y) {i++; j++;}
	else {if (a[i]==x) i++;
		 else {if (b[j]==y) j++;
			 else {if (a[i]!=b[j]) return false;
				  x=a[i]; y=b[j];i++; j++;
				 }
			 }
		}
	if (x==a[a.length-1] && y== b[b.length-1]) return true;
	return false;
}


static boolean equivalenti2 (int[] a, int[] b){ 
	//altra versione fatta a lezione
	//dimensione input n= max(a.length, b.length)
	if (a==null && b==null) return true;
	if (a==null || b==null) return false;
	mergeSort (a);
	mergeSort (b);
	int x;
	for (int i=0; i< a.length; i++)
         {	x=binarySearch(b, a[i]);
		if (x==-1) return false;
	    }
	for (int i=0; i< b.length; i++)
         {	x=binarySearch(a, b[i]);
		if (x==-1) return false;
	    }
	return true;
	}
	

/*
* Esercizio 
* Scrivere un metodo 
* static boolean sommaDiDue (int[] a, int x) 
* che, preso come parametro un array a di numeri interi 
* ed un intero x, restituisce true se e solo se esistono due 
* posizioni i e j di a tali che x=a[i]+a[j]. 
* Se a vale null, viene restituito false. 
* Il metodo non deve modificare l’array a.  
* Si analizzi la complessità temporale del metodo proposto: 
* tale metodo può richiamare qualsiasi algoritmo 
* visto a lezione e deve avere complessità 
* temporale O(n log n) nel caso peggiore 
* (soluzioni con complessità temporale peggiore 
* danno luogo a una valutazione minore), dove n è 
* la lunghezza dell’array a in input. 
* Ad esempio, se a={5, 7, 3, 2, 9, 8, 10, 8} 
* e x=9 il metodo deve restituire true, 
* mentre se x=-3 il metodo deve restituire false. 
 */
	
static boolean sommaDiDue (int[] a, int x){
	//dimensione input n= a.length
	if (a==null || a.length<=1) return false;
	int[] b= new int [a.length];
	for (int i=0; i< a.length; i++) b[i]=a[i];
	int j;
	for (int i=0; i< a.length-1; i++)
		{j=binarySearch(b,x-b[i], i+1, b.length -1);
		if (j!=-1) 
		  {System.out.println("indici: i=" +i+ " e j=" +j);
			//la stampa non è richiesta
		   return true;
		  }
		}
	return false;
	}
	
/*
 * Esercizio. Due array a e b della stessa lunghezza n 
 * (ognuno dei quali non contiene elementi ripetuti) si dicono
 * equiposizionali se per ogni posizione 
 * i=0,…,n-1, vale che a[i] è il j-esimo elemento più 
 * piccolo in a se e solo se b[i] è 
 * il j-esimo elemento più piccolo in b. 
 * Ad esempio, a={1, 8, 3} e b={10, 13, 11} 
 * sono equiposizionali.
 * Scrivere un metodo (in pseudocodice o in Java)
 * static boolean equiposizionali (int[] a, int[] b)
 * che, presi come parametro due array a e b di numeri interi, 
 * restituisce true se e solo se a e b sono della stessa
 * lunghezza e sono equiposizionali. 
 * Se entrambi valgono null, viene restituito true. 
 * Se solo uno dei due vale null, viene
 * restituito false. Il metodo non deve modificare gli array.
 * Si analizzi la complessità temporale del metodo proposto: 
 * tale metodo può richiamare qualsiasi algoritmo visto a
 * lezione e deve avere complessità temporale O(n log n) 
 * nel caso peggiore (soluzioni con complessità temporale
 * peggiore danno luogo a una valutazione minore), 
 * dove n è la lunghezza degli array a e b in input.
 */
	
	
	
  /*	Esercizio 
     * Scrivere un metodo 
     * static int selezione (int[] a, int k)
     * che, presi come parametro un array a di numeri interi
     * e un intero k, restituisce il k-esimo valore 
     * più piccolo presente tra gli elementi dell’array 
     * (senza contare gli elementi ripetuti). 
     * Se k è minore di 1, viene restituito
     * l’elemento più piccolo dell’array, 
     * mentre se k è maggiore del numero di 
     * elementi distinti presenti nell’array a, 
     * viene restituito l’elemento più grande 
     * dell’array. Il metodo non deve modificare l’array.
     * Ad esempio, se 
     *  a={1, 8, 3, 1, 5, 10, 1, 4} e k=2, 
     * il metodo deve restituire 3 
     * (poiché 3 è il secondo valore più
     * piccolo presente nell’array.
     * Si analizzi la complessità temporale del 
     * metodo proposto: 
     * tale metodo può richiamare qualsiasi algoritmo
     * di ordinamento e/o di ricerca 
     * visto a lezione e deve avere complessità 
     * temporale O(n log n) nel caso peggiore
     * (soluzioni con complessità temporale 
     * peggiore danno luogo a una valutazione minore), 
     * dove n è la lunghezza dell’array a in input.
     */
}