/**
   array ordinato di numeri interi.
   @author Adriano Luchetta
   @version 7-Nov-2003
   @version 20-Nov-2004
*/

import java.util.NoSuchElementException;

public class ArrayOrdinato
{
   private int[] array;
   private int arraySize;
   
   public ArrayOrdinato()
   {
      array = new int[1];
      arraySize = 0;
   }

   /**
      verifica se l'array è vuoto<br>
      Andamento asintotico O(1)
      
      @return true se l'array e' vuoto, false altrimenti
   */
   public boolean vuoto()
   {
      return arraySize == 0;
   }

   /**
      Aggiunge un elemento all'array ordinato <br>
      Andamento asintotico O(n) (Prima dell'inserimento l'array e' ordinato!)

      @param n il numero intero da aggiungere
   */
   public void aggiungi(int n)
   {
      // ridimensionamento dell'array
      if (arraySize == array.length)
      {
         int[] nuovoArray = new int[2 * array.length];
         for (int i = 0; i < arraySize; i++)
            nuovoArray[i] = array[i];
         array = nuovoArray;
      }

      // inserimento e ordinamento dell'array
      // (basta il ciclo interno dell'algoritmo di ordinamento per inserimento)
      int j;
      for (j = arraySize; j > 0 && n < array[j-1]; j--)
         array[j] = array[j - 1];
         
      array[j] = n;
      arraySize++;
   }
   
   /**
      ritorna il valore massimo nell'array, cancellandolo dall'array<br>
      Andamento asintotico O(1)

      @return il valore massimo
      @throws NoSuchElementException se l'array e' vuoto
   */
   public int togliMax() throws NoSuchElementException
   {
      if (vuoto())
         throw new NoSuchElementException();

      arraySize--;
      return array[arraySize];
   }

   /**
      restituisce la media dei valori dell'array<br>
      Andamento asintotico O(n)

      @return la media
   */
   public double media()
   {
      int somma = 0;
   	
      for (int i = 0; i < arraySize; i++)
         somma += array[i];

      return somma / (double) arraySize;
   }

   /**
      trova un numero nell'array ordinato (ricerca binaria)<br>
      Andamento asintotico O(log n)

      @param n l'intero da trovare
      @return l'indice nell'array dell'intero n se presente, -1 se assente
   */
   public int trova(int n)
   {
      int da = 0;
      int a = arraySize - 1;

      while (da <= a)
      {
         int medio = (da + a) / 2;
         if (n == array[medio])
            return medio;
         else if (n < array[medio])
            a = medio - 1;
         else
            da = medio + 1;
      }
      
      return -1;
   }
}