/**
  * ArrayAlgorithms.java
  *
  * riunisce algoritmi applicabili agli array di numeri interi
  *
  * @version 8-Nov-2006
  * @author Horstmann
  *
  */
public class ArrayAlgorithms
{
   /**
      ordinamento per selezione degli elementi di un array di numeri interi. O(n*n).
      @param a l'array da ordinare
   */

   public static void selectionSort(int[] a)
   {  
      for (int i = 0; i < a.length - 1; i++)
      {
         int minPos = findMinPos(a, i);
         if (minPos != i) swap(a, minPos, i);
      }
   }

   /*
      scambia due elementi nell'array
      @param a l'array in cui vengono scambiati gli elementi
      @param i indice di uno degli elementi da scambiare
      @param j indice di uno degli elementi da scambiare
   */
   private static void swap(int[] a, int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }

   /*
      restituisce l'indice dell'elemento minimo nel sottoarray di a che inizia all'indice from
      @param a l'array in cui viene effettuata la ricerca del minimo
      @param from indice da cui inizia la ricerca
      @return l'indice dell'elemento minimo nel sottoarray di a che inizia dall'indice from
   */
   private static int findMinPos(int[] a, int from)
   {
      int pos = from;  int min = a[from];
      for (int i = from + 1; i < a.length; i++)
      {
         int temp = a[i]; // metodo complicato per
         if (temp < min)  // rendere piu' semplice la
         {  pos = i;      // valutazione delle
            min = temp;   // prestazioni (piu' avanti)
         }
      }

      return pos;
   }
   
   /**
      ordinamento per fusione degli elementi di un array di numeri interi. O(n*log n).
      @param a l'array da ordinare
   */
   public static void mergeSort(int[] a)
   {
      // caso base
      if (a.length < 2) return;

      // dividiamo (circa) a meta'
      int mid = a.length / 2;

      int[] left = new int[mid];
      int[] right = new int[a.length - mid];
      System.arraycopy(a, 0, left, 0, mid);
      System.arraycopy(a, mid, right, 0, a.length - mid);

      // passi ricorsivi: problemi piu' semplici
      // si tratta di doppia ricorsione
      mergeSort(left);
      mergeSort(right);
      // fusione
      merge(a, left, right);
   }

   /*
      fonde due sottoarray ordinati
      @param a l'array ordinato
      @param b sottoarray ordinato
      @param c sottoarray ordinato
   */
   private static void merge(int[] a, int[] b, int[] c)
   {
      int ia = 0, ib = 0, ic = 0;

      //finche' ci sono elementi in b e c
      while (ib < b.length && ic < c.length)
         if (b[ib] < c[ic])
            a[ia++] = b[ib++];
         else
            a[ia++] = c[ic++];

      //qui uno dei due array non ha piu'
      //elementi
      while (ib < b.length)
         a[ia++] = b[ib++];
      while (ic < c.length)
         a[ia++] = c[ic++];
   }

   /**
      ordinamento per inserimento degli elementi di un array di numeri interi. O(n) nel caso migliore. O(n*n) nei casi medio e peggiore..
      @param a l'array da ordinare
   */
   public static void insertionSort(int[] a)
   {
      // il ciclo inizia da 1 perche' il primo
      // elemento non richiede attenzione
      for (int i = 1; i < a.length; i++)
      {  // nuovo elemento da inserire
         int temp = a[i];
         // la variabile di ciclo j va definita
         // fuori dal ciclo perche' il suo valore
         // finale viene usato in seguito
         int j;
         // vengono spostati a destra di un posto
         // tutti gli elementi a sinistra di temp
         // che sono maggiori di temp, procedendo
         // da destra a sinistra
         for (j = i; j > 0 && temp < a[j-1]; j--)
            a[j] = a[j-1];
         // temp viene inserito in posizione
         a[j] = temp;
      }
   }
   
   /**
      ricerca lineare. O(n).
      @param a l'array in cui viene effettuata la ricerca
      @param target l'elemento da ricercare
      @return l'indice nell'array della prima occorrenza dell'elemento cercato, se presente, -1 altrimenti
   */
   public static int linearSearch(int[] a, int target)
   {
      for (int i = 0; i < a.length; i++)
         if (a[i] == target)
            return i; // TROVATO

      return -1;      // NON TROVATO
   }
   
   /**
      ricerca lineare con sentinella. O(n).
      l'array a non deve essere completamente riempito
      @param a l'array riempito solo in parte in cui viene effettuata la ricerca
      @param size il numero di elementi inseriti nell'array riempito solo in parte
      @param target l'elemento da ricercare
      @return l'indice nell'array della prima occorrenza dell'elemento cercato, se presente, -1 altrimenti
      @throws IllegalArgumentException se l'array a e' completamente riempito
   */
   public static int guardedLinearSearch(int[] a, int size, int target)
   {
      if (size == a.length)
         throw new IllegalArgumentException();
         
      a[size] = target;
      int i;
      for (i = 0; a[i] != target; i++)
         ;
      if (i != size)
         return i;     // TROVATO

      return -1;      // NON TROVATO
   }
   

   /**
      ricerca binaria. O(n). Algoritmo ricorsiva
      @param a l'array in cui viene effettuata la ricerca
      @param v l'elemento da ricercare
      @return l'indice nell'array della prima occorrenza dell'elemento cercato, se presente, -1 altrimenti
   */
   public static int recursiveBinarySearch(int[] a, int v)
   {
      return binSearch(a, 0, a.length - 1, v);
   }

   /*
   
      @param a l'array in cui viene effettuata la ricerca
      @param from indice nell'array a da cui inizia la ricerca
      @param to indice nell'array a a cui finisce la ricerca
      @param target l'elemento da ricercare
      @return l'indice nell'array della prima occorrenza dell'elemento cercato, se presente, -1 altrimenti
   */
   private static int binSearch(int[] a, int from, int to, int target)
   {
      if (from > to)
         return -1;  // NON TROVATO

      int mid = (from + to) / 2; // CIRCA IN MEZZO
      int middle = a[mid];

      if (middle == target)
         return mid;             // TROVATO
      else if (middle < target)
         return binSearch(a, mid + 1, to, target);   // CERCA A DESTRA
      else
         return binSearch(a, from, mid - 1, target); // CERCA A SINISTRA
   }

   /**
      ricerca binaria. O(n). Algoritmo iterativo
      @param a l'array in cui viene effettuata la ricerca
      @param v l'elemento da ricercare
      @return l'indice nell'array della prima occorrenza dell'elemento cercato, se presente, -1 altrimenti
   */
   public static int iterativeBinarySearch(int[] a, int v)
   {
      int from = 0;                  //Limite inferiore
      int to = a.length - 1;         //Limite superiore

      //fino a che l'array corrente ha almeno un elemento
      while(from <= to)
      {
         int mid = (from + to)/2;     //CIRCA IN MEZZO

         if (a[mid] == v)
            return mid;               //TROVATO
         else if (a[mid] < v)
            from = mid + 1;           //CERCA A DESTRA
         else
            to = mid - 1;             //CERCA A SINISTRA
      }

      return -1; //NON TROVATO
   }
}