import javabooklet.*;
import java.util.Random;
import java.awt.Font;

/**
  raccolta di metodi statici
  per il trattamento di array ordinati
*/

public class OrdIntArrayUtil {

/**
  effettua l'input di una sequenza di int da tastiera,
  costruisce il corrispondente array e lo restituisce
  come risultato
*/

/**
  presi come argomenti un intero,
  un array parzialmente riempito e ORDINATO,
  e la lunghezza della parte occupata dell'array,
  inserisce l'intero al posto giusto nell'array
*/
  private static void inserisci(int x, int[] v, int m) {
    int j = m;
    while( j > 0 && x < v[j-1]) {
      v[j] = v[j-1];
      j--;
    }
    v[j] = x;
  }

/**
  effettua l'input (da tastiera)
  di una sequenza non ordinata di interi,
  costruisce il corrispondente array ORDINATO
  e lo restituisce come risultato
*/
  public static int[] leggi() {
    int n = Input.readInt("Di che lunghezza vuoi l'array?");
    int[] a = new int[n];
    int valoreLetto;
    for(int i=0; i<n; i++) {
      valoreLetto = Input.readInt("immetti elemento n. " + i + " (int)");
      inserisci(valoreLetto, a, i);
    }
    return a;
  }

/**
  scrive sulla consolle gli elementi dell'array
  in sequenza
*/
  public static void scriviSuConsolle(int[] a) {
    System.out.println("l'array e': ");
    for(int i=0; i < a.length; i++) {
      System.out.println(a[i]);
    }
  }

/**
  scrive in un MessageDialog gli elementi dell'array
  in sequenza
*/
  public static void scriviSuMessageDialog(int[] a) {
    String output = "l'array č:  ";
    for(int i=0; i < a.length; i++) {
      output = output + a[i] + "  ";
    }
    OptionIO.showMessageDialog(output);
  }

/**
  scrive in un OutputBox gli elementi dell'array
  in sequenza
*/
  public static void scriviSuOutputBox(int[] a) {
    OutputBox output = new OutputBox();
    output.print("l'array č: ");
    for(int i=0; i < a.length; i++) {
      output.print(a[i] + "  ");
    }
    output.waitUntilClose();
  }


/**
  restituisce (dopo averla costruita) la stringa
  costituente la scrittura della sequenza degli
  elementi dell'array
*/
  public static String arrayToString(int[] a) {
    StringBuffer stringBuf = new StringBuffer();
    for(int i=0; i < a.length; i++) {
      stringBuf.append(a[i]+" ");
    }
    return stringBuf.toString();
  }

  public static boolean čOrdinato(int[] a) {
    int n = a.length;
    int i = 1;
    while(i < n && a[i-1] <= a[i]) i++;
    return i==n;
  }

/**
  ricerca sequenziale in array ORDINATO
  restituente un booleano,
  versione con il for
*/
  public static boolean ricerca(int x, int[] a) {
    int n = a.length;
    for(int i=0; i < n; i++) {
      if(x == a[i]) return true;
      if(x < a[i]) return false;
    }
    return false;
  }

/**
  ricerca sequenziale in array ORDINATO
  restituente l'indice dell'elemento
  oppure -1 se il valore cercato non c'č,
  versione con il for
*/
  public static int ricercaIndiceDi(int x, int[] a) {
    int n = a.length;
    for(int i=0; i < n; i++) {
      if(a[i] == x) return i;
      if(x < a[i]) return -1;
    }
    return -1;
  }

/**
  ricerca sequenziale in array ORDINATO
  restituente un booleano,
  versione con il while
*/
  public static boolean ricercaWh(int x, int[] a) {
    int n = a.length;
    int i = 0;
    while(i < n && x > a[i]) i++;
    return i < n && x == a[i];
  }

/**
  ricerca sequenziale in array ORDINATO
  restituente un booleano,
  versione con il while ottimizzata
*/
  public static boolean ricercaWhOtt(int x, int[] a) {
    int n = a.length;
    int i = 0;
    while(i < n-1 && x > a[i]) i++;
    return x == a[i];
  }

/**
  ricerca sequenziale in array ORDINATO
  restituente l'indice dell'elemento
  oppure -1 se il valore cercato non c'č,
  versione con il while
*/
  public static int ricercaIndiceWh(int x, int[] a) {
    int n = a.length;
    int i = 0;
    while(i < n && x > a[i]) i++;
    //if(i < n && x == a[i]) return i;
    //else return -1;
    return i < n && x == a[i] ? i : -1;
  }

/**
  ricerca sequenziale in array ORDINATO
  restituente l'indice dell'elemento
  oppure -1 se il valore cercato non c'č,
  versione con il while ottimizzata
*/
  public static int ricercaIndiceWhOtt(int x, int[] a) {
    int n = a.length;
    int i = 0;
    while(i < n-1 && x > a[i]) i++;
    //if(x == a[i]) return i;
    //else return -1;
    return x == a[i] ? i : -1;
  }

/** ricerca binaria, restituente un booleano */
  public static boolean ricercaBin(int x, int[] a) {
    int i, inf = 0, sup = a.length - 1;
    while(inf <= sup) {
      i = (inf + sup)/2;
      if(x < a[i]) sup = i-1;
      else if(x > a[i]) inf = i+1;
      else return true;
    }
    return false;
  }

/** ricerca binaria, restituente l'indice */
  public static int binRicercaIndiceDi(int x, int[] a) {
    int i, inf = 0, sup = a.length - 1;
    while(inf <= sup) {
      i = (inf + sup)/2;
      if(x < a[i]) sup = i-1;
      else if(x > a[i]) inf = i+1;
      else return i;
    }
    return -1;
  }


/** presi come argomenti due array ordinati (che possono contenere elementi ripetuti),
    crea e restituisce un nuovo array ordinato (eventualmente contenente elementi ripetuti)
    dato dalla fusione ordinata
    dei due array-argomenti (senza modificare tali array-argomenti)
 */
  public static int[] fondi(int[] a, int[] b) {
    int m = a.length;
    int n = b.length;
    int[] c = new int[m+n];

    int i = 0, j = 0;
    while(i < m && j < n) {
      if(a[i] <= b[j]) {
        c[i+j] = a[i];
        i++;
      }
      else {
        c[i+j] = b[j];
        j++;
      }
    }
    while(i < m) {
      c[i+j] = a[i];
      i++;
    }
    while(j < n) {
      c[i+j] = b[j];
      j++;
    }
    return c;
  }

/** presi come argomenti due array ordinati privi di elementi ripetuti,
    crea e restituisce un nuovo array ordinato (privo di elementi ripetuti)
    che rappresenta l'intersezione insiemistica dei due argomenti,
    senza modificare tali array-argomenti
 */
  public static int[] intersezione(int[] a, int[] b) {
    int m = a.length;
    int n = b.length;
    int p;
    if(m < n) p = m; else p = n;
    int[] c = new int[p];

    int i = 0, j = 0, k = 0;
    while(i < m && j < n) {
      if(a[i] < b[j]) i++;
      else if(a[i] > b[j]) j++;
      else {
        c[k] = a[i];
        i++; j++; k++;
      }
    }

    int[] d = new int[k];
    for(i = 0; i < k; i++) d[i] = c[i];
    return d;
  }

/** presi come argomenti due array ordinati privi di elementi ripetuti,
    crea e restituisce un nuovo array ordinato (privo di elementi ripetuti)
    che rappresenta l'unione insiemistica dei due argomenti,
    senza modificare tali array-argomenti
 */
  public static int[] unione(int[] a, int[] b) {
    int m = a.length;
    int n = b.length;
    int p;
    int[] c = new int[m+n];

    int i = 0, j = 0, k = 0;
    while(i < m && j < n) {
      if(a[i] < b[j]) {
        c[k] = a[i];
        i++; k++;
      }
      else if(a[i] > b[j]) {
        c[k] = b[j];
        j++; k++;
      }
      else {
        c[k] = a[i];
        i++; j++; k++;
      }
    }
    while(i < m) {
      c[k] = a[i];
      i++; k++;
    }
    while(j < n) {
      c[k] = b[j];
      j++; k++;
    }

    int[] d = new int[k];
    for(i = 0; i < k; i++) d[i] = c[i];
    return d;
  }

  static final int N = 10000; // lunghezza dell'array da ordinare
  static final int K = 3*N; // N/3; // numero di valori diversi possibili

  public static void main(String args[]) {
    int[] ar1 = {3,5,21, 30,30, 65, 88, 90, 99};
    int[] ar2 = {-5, -2, 4, 11, 13, 21, 25, 30, 89, 90, 94, 97};
    scriviSuOutputBox(fondi(ar1, ar2));

    int[] ar3 = {3,5,21, 30, 65, 88, 90, 99};
    int[] ar4 = {-5, -2, 4, 11, 13, 21, 25, 30, 89, 90, 94, 97};
    scriviSuOutputBox(fondi(ar3, ar4));
    scriviSuOutputBox(unione(ar3, ar4));
    scriviSuOutputBox(intersezione(ar3, ar4));
    scriviSuOutputBox(IntArrayUtil.intersezione(ar3, ar4));

    int[] fuso = fondi(ar3,ar4);
    System.out.println("ricerca");
    System.out.println(fuso[ricercaIndiceWh(89, fuso)]);
    System.out.println(fuso[ricercaIndiceWhOtt(89, fuso)]);
    System.out.println(fuso[binRicercaIndiceDi(89, fuso)]);

    int[] arr1 = leggi();
    scriviSuOutputBox(arr1);

    Random generatore = new Random();

    int[] bigArray1 = new int[N];
    for(int i = 0; i < N; i++) {
      inserisci(generatore.nextInt(K), bigArray1, i);
    }
    System.out.println(čOrdinato(bigArray1));

    int[] bigArray2 = new int[N];
    for(int i = 0; i < N; i++) {
      inserisci(generatore.nextInt(K), bigArray2, i);
    }
    System.out.println(čOrdinato(bigArray2));

    int[] veryBigArray = fondi(bigArray1, bigArray2);
    System.out.println(čOrdinato(veryBigArray));

    int num = generatore.nextInt(K);
    int j = ricercaIndiceWh(num, veryBigArray);
    System.out.println(num + " "+ (j != -1 ? veryBigArray[j]+" " : "non trovato"));

    j = ricercaIndiceWhOtt(num, veryBigArray);
    System.out.println(num + " "+ (j != -1 ? veryBigArray[j]+" " : "non trovato"));

    j = ricercaIndiceDi(num, veryBigArray);
    System.out.println(num + " "+ (j != -1 ? veryBigArray[j]+" " : "non trovato"));

  }

}