/**
 * RawComparableContainer
 * contenitore di oggetti confrontabili
 *
 * @author Adriano Luchetta
 * @version 08-Nov-2003
 * @version 20-Nov-2004
 * @version 11-Nov-2005
 * @version 18-Nov-2006
 *
 */

import java.util.NoSuchElementException;

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

   // variabili di esemplare
   private Comparable[] c;
   private int cSize;

   public RawComparableContainer()
   {
      makeEmpty();;
   }

   /**
      verifica se il contenitore e' vuoto.
      @return true se vuoto, false altrimenti
   */
   public boolean isEmpty()
   {
      return cSize == 0;
   }
   
   /**
      rende vuoto il contenitore.
   */
   public void makeEmpty()
   {
      c = new Comparable[INITIAL_SIZE];
      cSize = 0;
   }

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

   /**
      aggiunge un oggetto in coda al contenitore. Se il contenitore e' pieno,
      ridimensiona l'elenco.
      @param obj riferimento all'oggetto da aggiungere.
   */
   public void add(Comparable obj)
   {
      if (cSize == c.length)
        c = resize(c, 2 * c.length);

      c[cSize] = obj;
      cSize++;
   }

   /**
      ordina per fusione il contenitore.
      Ridimensiona il contenitore prima di ordinarlo, in modo
      da usare i metodi noti per mergesort() che lavorano
      su array pieni.
   */
   public void sort()
   {
      // ridimensionamento di c prima di ordinarlo
      // in modo che sia pieno, cosi' possiamo usare i metodi
      // mergesort() e merge() come definiti
      c = resize(c, cSize);

      mergesort(c);
   }

   /**
      restituisce l'ultimo oggetto del contenitore, rimuovendolo
      @return l'ultimo oggetto del contenitore
      @throws NoSuchElementException se l'elenco e' vuoto
   */
   public Comparable removeLast() throws NoSuchElementException
   {
      if (isEmpty())
         throw new NoSuchElementException();

      Comparable value = c[cSize-1];
      c[cSize - 1] = null;          // garbage collector
      cSize--;
      return value;
   }

   // metodo privato mergesort()
   private void mergesort(Comparable[] a)
   {
      // caso base
      if (a.length < 2) return;

      // passi ricorsivi
      int mid = a.length / 2;
      Comparable[] left = new Comparable[mid];
      for (int i = 0; i < mid; i++)
         left[i] = a[i];

      Comparable[] right = new Comparable[a.length - mid];
      for (int i = 0; i < a.length - mid; i++)
         right[i] = a[mid + i];

      mergesort(left);
      mergesort(right);

      // fusione
      merge(a, left, right);
   }

   // metodo privato merge()
   private void merge(Comparable[] a, Comparable[] b, Comparable[] c)
   {
      int ia = 0;
      int ib = 0;
      int ic = 0;

      //finche' ci sono elementi in b e c
      while (ib < b.length && ic < c.length)
         if (b[ib].compareTo(c[ic]) < 0)
            a[ia++] = b[ib++];
         else
            a[ia++] = c[ic++];

      //qui uno dei due array non ha piu' elementi
      while (ib < b.length)
         a[ia++] = b[ib++];
      while (ic < c.length)
         a[ia++] = c[ic++];
   }
   
   // metodo privato resize()
   private Comparable[] resize(Comparable[] oldAr, int newLength)
   {
     int minLength = oldAr.length < newLength ? oldAr.length : newLength;
     Comparable[] newAr = new Comparable[newLength];
     
     for (int i = 0; i < minLength; i++)
       newAr[i] = oldAr[i];
       
     return newAr;
   }
}