/**
  * archivio ordinato realizzato con un array riempito solo in parte.
  * Classe didattica.
  *
  * @author A. Luchetta
  * @version 14-Nov-2006
  */

import java.util.NoSuchElementException;

public class ArchivioOrdinato
{
  // variabili di esemplare
  private Comparable[] array;
  private int arraySize;
     
  public ArchivioOrdinato()
  {
     array = new Comparable[1];
     arraySize = 0;
  }

  /**
     Aggiunge un elemento all'archivio ordinato
     Andamento asintotico O(n)
     Prima dell'inserimento l'array e' ordinato!
     @param n il numero intero da aggiungere
  */
  public void aggiungi(Comparable c)
  { // ridimensionamento dell'array
  
   if (arraySize >= array.length)
   { Comparable[] newArray = new Comparable[2*array.length];
     for (int i = 0; i < arraySize; i++)
       newArray[i] = array[i];
     array = newArray;
   }
  
   /* inserimento e ordinamento dell'archivio
      (basta il ciclo interno dell'algoritmo di
      ordinamento per inserimento)
   */
   int j;
   for (j = arraySize; j>0 && c.compareTo(array[j-1]) < 0; j--)
     array[j] = array[j - 1];
  
   array[j] = c;
   arraySize++;
}

   /**
      ritorna il valore massimo nell'archivio,
      cancellandolo dall'arrchivio.
      Andamento asintotico O(1)
      @return il valore massimo
      @throws NoSuchElementException se l'array e' vuoto
   */
   public Object togli()
   {
      if (vuoto())
         throw new NoSuchElementException();

      Object tmp = array[arraySize - 1];
      array[arraySize - 1] = null; // garbage collector

      arraySize--;

      return tmp;
   }

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