package esami;

public class gennaio14lezione {


	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};
		int [] e ={10, 13, 11};
		System.out.println(equiposizionali(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 complessità n log n
		if (a==null|| a.length==0) return;
		mergeSort(a,0, a.length -1);    
	}
	static void mergeSort(int[]a, int l, int r){
		// dimensione input n= r-l+1 complessità n log n
		//CASO BASE
		if (l==r) return;              
		int p=(r+l)/2; 
		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 n= r-l+1 complessità n
		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) 
	{ //dimensione dell'input n=r-l+1 complessità log n
		//CASO BASE
		if (l==r) {if (a[l]==v) return l; else return -1;} 
		int p=(l+r)/2;  
		if (a[p]>=v)    
			return binarySearch(a,v,l,p);  
		return binarySearch(a,v,p+1,r);    
		}
	
	static void countingSort (int[] a, int k)
	// dimensione dell'input n= a.length
	{if (a==null|| a.length==0) return;   //costante
		int [] c= new int [k+1];          // dell'ordine di k
	    int []b =new int [a.length];      // dell'ordine di n
	    for (int i=0; i<a.length; i++)    //dell'ordine di n
	    	{c[a[i]]++;}
	    for (int i=1; i<c.length; i++)    //dell'ordine di k
    	{c[i]=c[i]+ c[i-1];}
	    for (int i=0; i<a.length; i++)    //dell'ordine di n
    	{b[c[a[i]]-1]=a[i]; c[a[i]]--;}
	    for (int i=0; i<a.length; i++)    //dell'ordine di n
    	     {a[i]=b[i];}
	}
	/* dell'ordine di n+k. 
     * Se k è una costante fissata a priori 
	* (non parametro in input), oppure se si sa che k<=n, 
	* allora il metodo complessità temporale O(n) 
	/*
	
/*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 (in 
	 * ordine non decrescente) e poi tutti i dispari (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 complessità n log n
		if (a==null|| a.length==0) return;
		ordinamentoRelativoPD(a,0, a.length -1);    
	}
	static void ordinamentoRelativoPD(int[]a, int l, int r){
		// dimensione input n= r-l+1 complessità n log n
		//CASO BASE
		if (l==r) return;              
		int p=(r+l)/2; 
		ordinamentoRelativoPD(a,l,p);             
		ordinamentoRelativoPD(a, p+1,r);       
		mergePD(a,l,p,r);            
	}
	
	static void mergePD(int[]a, int l, int p, int r)
	{//dimensione dell'input n= r-l+1 complessità n
		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++)    
		{int p1= sin[i]%2;    
		 int p2= des[j]%2;
			if (i==n1-1) {a[k]=des[j]; j++;}
			else {if (j==n2-1) {a[k]=sin[i]; i++;}    
			      else {if (p1<p2){a[k]=sin[i]; i++;}  
			      else {if (p1>p2){a[k]=des[j]; j++;}  
			      else {if (sin[i]<des[j]){a[k]=sin[i];                
                                                i++;}  
			      else {a[k]=des[j]; j++;}
			           } 
			           } 
			      } 
			}  
		}     
	}
	
	    /* 
	     * 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.
		 */
		
static boolean equiposizionali (int[] a, int[] b) {
			//dimensione dell'input n=a.length
		if (a==null && b==null) return true;
		if (a==null || b==null) return false;
		if (a.length!= b.length) return false;
		int[] c= new int [a.length]; 
		int[] d= new int [b.length];
		for (int i=0; i<a.length; i++) c[i]=a[i];
		for (int i=0; i<b.length; i++) d[i]=b[i];
		mergeSort(c);
		mergeSort(d);
		for (int i=0; i<a.length; i++)
		{ int h= binarySearch(a,c[i]);
		int k= binarySearch(b,d[i]);
		if (h!=k) return false; }
		return true;
			
		}
		/*
		 * Esercizio 
		 * Scrivere un metodo (in Java o in pseudocodice) 
		 * 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){
			if (a==null|| a.length==0) return false;
			int[] c= new int [a.length]; 
			for (int i=0; i<a.length; i++) c[i]=a[i];
			mergeSort (c);
			for(int i=0; i<a.length; i++)
			{int k=binarySearch (c, x-a[i]);
			if (k!= -1) return true;
			}
			return false;
		}
	}