/** Prova di Programmazione del 16-Lug-2008
  * Classe S - definisce una pila di elementi comparabili
  * @author A. Luchetta
  * @version 14-07-2008
  */  
public class S implements CStack
{
    private static final int DIM = 100;

    private Object v[] ;
    private int vSize;

    public S()
    {
        v = new Object[DIM];
        vSize = 0;
    }

    public boolean isEmpty()
    {
        return (vSize == 0);
    }


    public int size()
    {
        return vSize;
    }

    public void push(Comparable x)
    {
        if(vSize >= v.length)
        {
           Object[] a = new Object[v.length * 2];
           for (int i = 0; i < v.length; i++)
              a[i] = v[i];
              
           v = a;
        }

        v[vSize++] = x;
    }

    public Object pop() throws EmptyStackException
    {
       if( isEmpty() )
           throw new EmptyStackException();

      Object x = v[vSize - 1];
      v[vSize - 1] = null;
      vSize--;

      return x;
    }

    public Object[] toArray()
    {
        Object[] a = new Object[vSize];

        for(int i = 0; i < vSize; i++)
           a[i] = v[vSize - 1 - i];

        return a;
    }
    
    public Object[] toSortedArray()
    {
        Object[] a = toArray();
        mergesort(a);

        return a;
    }

   private static void mergesort(Object[] a)
   {
      // caso base
      if (a.length < 2) return;

      // dividiamo (circa) a meta’
      int mid = a.length / 2;

      Object[] left = new Object[mid];
      Object[] right = new Object[a.length - mid];
      System.arraycopy(a, 0, left, 0, mid);
      System.arraycopy(a, mid, right, 0, a.length - mid);

      // passi ricorsivi: problemi piu’ semplici
      // si tratta di doppia ricorsione
      mergesort(left);
      mergesort(right);
      // fusione
      merge(a, left, right);
   }

   /*
      fonde due sottoarray ordinati
      @param a l'array ordinato
      @param b sottoarray ordinato
      @param c sottoarray ordinato
   */
   private static void merge(Object[] a, Object[] b, Object[] c)
   {
      int ia = 0, ib = 0, ic = 0;

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

      //qui uno dei due array non ha più
      //elementi
      while (ib < b.length)
         a[ia++] = b[ib++];
      while (ic < c.length)
         a[ia++] = c[ic++];
   }
}