/**
   contenitore di oggetti.
   Si possono inserire solo oggetti di classi che realizzano java.lang.Comparable.
   @author Adriano Luchetta
   @version 8-Nov-2003
   @version 27-Nov-2004
*/

import java.util.NoSuchElementException;

public class ContenitoreOrdinatoObj implements Container
{
   private Object[] obj;
   private int objSize;
   
   public ContenitoreOrdinatoObj()
   {
      obj = new Object[1];
      makeEmpty();
   }

   /**
      @return true se l'array e' vuoto, false altrimenti
   */
   public boolean isEmpty()
   {
      return objSize == 0;
   }

   /**
      rende vuoto il contenitore
   */
   public void makeEmpty()
   {
      objSize = 0;
   }
   
   /**
      @return il numero di elementi nel contenitore
   */
   public int size()
   {
      return objSize;
   }
   
   /**
      Aggiunge un elemento comparabile, ridimensionando l'array se necessario.
      L'elemento sia inserito in coda all'array e successivamente l'array
      sia ordinato. Attenzione, prima dell'inserimento l'array e' ordinato!
      Andamento asintotico O(n).
      @param object oggetto comparabile da aggiungere
   */
   public void aggiungi(Object object)
   {
      //ridimensionamento se necessario
      if (objSize == obj.length)
        obj = resize(obj, 2 * obj.length);

      // ricerca indice i per inserimento ordinato e spostamento a destra
      // ciclo interno dell'algoritmo di ordinamento per inserimento!
      Comparable compObj = (Comparable) object; //*** Conversione esplicita
      int i;
      for (i = objSize; i > 0 && compObj.compareTo(obj[i - 1]) > 0; i--)
         obj[i] = obj[i-1];
   	   
      //inserimento oggetto
      obj[i] = obj;
      objSize++;
   }
   
   /**
      ritorna il valore massimo del contenitore (massimo nel senso di compareTo()),
      cancellandolo dal contenitore. Andamento asintotico O(1).
      @return il valore massimo
      @throws NoSuchElementException se l'array e' vuoto
   */
   public Object togliMax() throws NoSuchElementException
   {
      if (isEmpty())
         throw new NoSuchElementException("obj vuoto");

      Object tmpObj = obj[objSize - 1];
      obj[objSize - 1] = null;
      objSize--;

      return tmpObj;
   }
   
   private Object[] resize(Object[] oldAr, int newLength)
   {
     Object[] newAr = new Comparable[newLength];
     int minLength = oldAr.length;
     if (newLength < oldAr.length)
        minLength = newLength;

     for (int i = 0; i < minLength; i++)
        newAr[i] = oldAr[i];
        
     return newAr;
   }
}