/**
  * SortableContainer.java
  * contenitore ordinabile di oggetti comparabili
  * @author Adriano Luchetta
  * @version 8-Nov-2003
  * @version 27-Nov-2004
  * @version 18-Nov-2006
  */

import java.util.NoSuchElementException;

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

   private Comparable[] objs;
   private int objsSize;

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

   /**
      rende vuoto il contenitore
   */
   public void makeEmpty()
   {
      objs = new Comparable[INITIAL_SIZE];
      objsSize = 0;
   }

   /**
      @return il numero di elementi nel contenitore
   */
   public int size()
   {
      return objsSize;
   }

   /**
      Aggiunge un elemento ridimensionando l'array se necessario.
      L'elemento sia inserito in coda all'array.
      Andamento asintotico O(1).
      @param compObj oggetto da aggiungere
   */
   public void add(Comparable compObj)
   {
      //ridimensionamento se necessario
      if (objsSize >= objs.length)
        objs = resize(objs, 2 * objs.length);

      //inserimento oggetto
      objs[objsSize++] = compObj;
   }
   
   /**
      cancella e ritorna l'ultimo elemento dal contenitore. Andamento asintotico O(1).
      @return il valore massimo
      @throws NoSuchElementException se l'array e' vuoto
   */
   public Object removeLast() throws NoSuchElementException
   {
      if (isEmpty())
         throw new NoSuchElementException("contenitore vuoto");

      Object tmpObj = objs[objsSize - 1];
      objs[objsSize - 1] = null;
      objsSize--;

      return tmpObj;
   }

   /**
      ordina l'archivio in modo che il metodo removeLast() restituisca il
      massimo. Andamento asintotico O(n log n).
   */
   public void sort()
   {
     // ridimensionamento per usare il metodo mergesort operante su array pieni
     objs = resize(objs, objsSize);

     ArrayAlgorithms.mergesort(objs);
   }
   
   private Comparable[] resize(Comparable[] oldAr, int newLength)
   {
     Comparable[] 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;
   }
}