import java.io.*;
import java.util.*;

public class Arrays {
/*SCOPO: Questa classe fornisce un certo numero di 
procedure utili per manipolare array di interi */

public static void readArray (int [] a, ConsoleReader c) {
//SCOPO lettura di array inserendo i valorei da tastiera
     for (int i=0;i<a.length;i++) {
       System.out.println("Scrivi un valore intero ");
         a[i]=c.readInt();}}

public static String toString (int [] a) {
/*SCOPO: calcola una stringa contenente tutti gli elementi
di a separati da uno spazio. Invoca il metodo ricorsivo InSt*/
   return InSt(a,0);}

private static String InSt (int [] a, int i) {
//SCOPO: calcola la stringa corrispondente ad a 
   if (i==a.length) return "";
   else return (a[i]+" "+InSt(a, i+1));}
   
public static int SommaArr(int [] a){
//Calcola la somma degli elementi dell'array a
    return SommaArrRic(a,0);}
    
private static int SommaArrRic(int [] a, int from){
    if ((from >= a.length)| (from < 0)) return 0; //from fuori dal range
    else return a[from]+SommaArrRic(a, from+1);}
    
   public static String toStringIt(int [] a){
   //toString iterativo per array di interi 
       String s="{";
       for (int i=0;i<a.length-1;i++) s=s+a[i]+",";
           s=s+a[a.length-1]+"}";
       return s;}

   public static void writeArray (int [] a) {
//SCOPO: stampa degli elementi dell'array in output
   for (int i=0; i<a.length;i++) System.out.print(a[i]+" ");
   System.out.println();}

public static boolean search (int [] a, int x) { 
//SCOPO: ricerca di un elemento array NON ordinato
//Usa iterazione
    boolean Trovato=false;
    int i=0;
    while ((!Trovato) &(i<a.length)) {
        if (a[i]==x) Trovato=true;
    else i++;   }
    return(Trovato);} 

public static boolean searchRic (int [] a, int x,int i) { 
//SCOPO: ricerca di un elemento array NON ordinato
//Usa ricorsione
    if(i>=a.length) return false;
    else if (a[i]==x) return true;
    else return searchRic(a,x,i+1);
}

public static boolean searchSortRic (int [] a, int x,int i) { 
//SCOPO: ricerca di un elemento array  ordinato
//Usa ricorsione
    if(i>=a.length) return false;
    else if (a[i]==x) return true;
    else if (x<a[i]) return false;
    else return searchRic(a,x,i+1);
}

public static boolean searchSorted (int [] a, int x) { 
//SCOPO: ricerca di un elemento array ordinato
//Usa iterazione
    boolean continua=true;
    int i=0;
    while ((continua) &(i<a.length)){
        if (a[i]==x) continua=false;
    else if (x>a[i]) i++;
    else continua=false;}
    if (i<a.length) return a[i]==x;
    else return false;   
} 
    
  public static int binSearch (int [] a, int v) {
      /*Ricerca binaria nell'array a dell'elemento v. Calcola la posizione di v
    se lo trova altrimenti calcola -1
      Prerequisiti: a deve essere ordinato */
            return binS(a,v,0,a.length);
  }
  private static int binS(int [] a, int v, int min, int max) {
   /*Ricerca binaria nella porzione tra min e max dell'array a dell'elemento v. Calcola la posizione di v
    se lo trova altrimenti calcola -1
      Prerequisiti: a deve essere ordinato */   
      int mid;
    if (min<max) {
        mid=(max+min)/2;
        System.out.println("mid "+mid);
        
        if (a[mid]==v) return mid;
        else if (a[mid]>v) return binS(a,v,min,mid);
        else return binS(a,v,mid+1,max);
        
    }
    else return -1;
  }


public static int minPos(int [] a, int from) {
    /* Calcola la posizione dell'elemento piu` piccolo presente in a 
    partendo dalla posizione from*/
 int min=from;
 for (int i=from+1;i<a.length;i++) {
     if (a[min]>a[i]) min=i;}
     return min;}
public static void swap(int [] a, int i,int j) {
//System.out.println("swap scambia "+i+"e "+j); 
    int temp =a[i];
    a[i]=a[j];
    a[j]=temp;}
public static void selSort (int [] a) {
    /* MODIFICA: a*/
    /* EFFETTI: ordinamento di a in senso crescente, a viene modificata in modo che i suoi elementi risultino 
    ordinati in senso crescente. Es: se a=[3,4,1,0] prima dell'invocazione, dopo 
    l'invocazione a-post =[0,1,3,4] 
    algoritmo d'ordinamento per selezione dei minimi*/
    for (int i=0; i<a.length-1;i++) {
    int min=Arrays.minPos(a,i);
        if (min != i) Arrays.swap(a,i,min);}}


public static void mergeSort (int [] a) {
    /* MODIFICA: a*/
    /* EFFETTI: ordinamento di a in senso crescente, a viene modificata in modo che i suoi elementi risultino 
    ordinati in senso crescente. Es: se a=[3,4,1,0] prima dell'invocazione, dopo 
    l'invocazione a-post =[0,1,3,4] 
    algoritmo d'ordinamento merge sort*/
    if (a.length > 1) {
     msort(a,0,a.length);
    }  
}

private static void msort(int [] a, int min, int max) {
    /*ordina la porzione di array compreso tra min e max usando 
    l'algoritmo di merge sort*/
    int mid;
    if (min < max-1) {
         mid= (min+max)/2;
//         System.out.println("invoc. ricorsiva intervallo "+min+" , "+mid);
         msort(a, min, mid);
//      System.out.println("invoc. ricorsiva intervallo "+mid+" , "+max);
         msort(a, mid, max);
         merge(a, min, mid, max);
 //       System.out.println("array risultante");
//        System.out.println("ordinato nella porzione "+min+" a "+(max-1));
//        writeArray(a);
    }
}


private static void merge (int [] a, int min, int mid, int max) {
    //fai merge delle due porzioni ordinate di array comprese tra min e mid e mid e max
    int [] r=new int [max-min];
    int i=0;
    int j=min;
    int h=mid;
    while (i<r.length) {
        if ((j<mid) &(h<max))
       if (a[j]<a[h]) {         
            r[i]=a[j];
            j++;
        } else {
        r[i]=a[h];
        h++;        
        } else if (j<mid) {
        r[i]=a[j];
        j++;
       }
    else {
        r[i]=a[h];  
        h++;
    }
   i++;
    }
    for (i=0;i<r.length;i++) a[min+i]=r[i];
}

     }