/**
  * SortedContainer
  * contenitore ordinato di generici oggetti comparabili
  * @author Adriano Luchetta
  * @version 8-Nov-2003
  * @version 27-Nov-2004
  * @version 20-Nov-2006
  */

import java.util.NoSuchElementException;

public class SortedContainer implements Container
{
   static final int INITIAL_SIZE = 1;

   private Object[] objects;
   private int objectsSize;

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

   /**
      rende vuoto il contenitore
   */
   public void makeEmpty()
   {
      objects = new Object[INITIAL_SIZE];
      objectsSize = 0;
   }
   
   /**
      @return il numero di elementi nel contenitore
   */
   public int size()
   {
      return objectsSize;
   }

   /**
      Aggiunge un elemento comparabile, ridimensionando l'array se necessario.
      Il contenitore e' mantenuto ordinato in senso crescente. Attenzione,
      prima dell'inserimento l'array e' ordinato! Andamento asintotico O(n).
      @param compObj oggetto comparabile da aggiungere
   */
   public void add(Comparable compObj)
   {
      //ridimensionamento se necessario
      if (objectsSize >= objects.length)
        objects = resize(objects, 2 * objects.length);

      // ricerca indice i per inserimento ordinato e spostamento a destra
      // ciclo interno dell'algoritmo di ordinamento per inserimento!
      int i;
      for (i = objectsSize; i > 0 && compObj.compareTo(objects[i - 1]) < 0; i--)
         objects[i] = objects[i-1];

      //inserimento oggetto
      objects[i] = compObj;
      objectsSize++;
   }
   
   /**
      ritorna il valore massimo del contenitore (massimo nel senso
      dell'ordinamento naturale della classe di oggetti comparabili)
      cancellandolo dal contenitore. Andamento asintotico O(1).
      @return il valore massimo
      @throws NoSuchElementException se l'array e' vuoto
   */
   public Object removeMax()
   {
      if (isEmpty())
         throw new NoSuchElementException("contenitore vuoto");

      Object obj = objects[objectsSize - 1];
      objects[objectsSize - 1] = null;          // garbage collector
      objectsSize--;

      return obj;
   }

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

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