/**
 * contenitore di testo
 *
 * @author Adriano Luchetta
 * @version 08-Nov-2003
 * @version 20-Nov-2004
 * @version 11-Nov-2005
 *
 */

import java.util.NoSuchElementException;

public class Text implements Container
{
   // variabili di esemplare
   private String[] words;
   private int wordsSize;

   public Text()
   {
      words = new String[1];
      makeEmpty();;
   }

   /**
      verifica se l'elenco di parole e' vuoto.
      @return true se vuoto, false altrimenti
   */
   public boolean isEmpty()
   {
      return wordsSize == 0;
   }
   
   /**
      rende vuoto il contenitore.
   */
   public void makeEmpty()
   {
      wordsSize = 0;
   }

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

   /**
      aggiunge in coda una parola all'elenco. Se l'elenco e' pieno,
      ridimensiona l'elenco.
      @param aWord la parola da aggiungere.
   */
   public void add(String aWord)
   {
      if (wordsSize == words.length)
        words = resize(words, 2 * words.length);

      words[wordsSize] = aWord;
      wordsSize++;
   }

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

      mergesort(words);
   }

   /**
      restituisce l'ultima parola dell'elenco, rimuovendola
      @return l'ultima parola dell'elenco
      @throws NoSuchElementException se l'elenco e' vuoto
   */
   public String removeLast() throws NoSuchElementException
   {
      if (isEmpty())
         throw new NoSuchElementException();

      String value = words[wordsSize-1];
      words[wordsSize - 1] = null;          // garbage collector
      wordsSize--;
      return value;
   }

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

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

      String[] right = new String[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(String[] a, String[] b, String[] c)
   {
      int ia = 0;
      int ib = 0;
      int ic = 0;

      //finché 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 String[] resize(String[] oldAr, int newLength)
   {
     int minLength = oldAr.length < newLength ? oldAr.length : newLength;
     String[] newAr = new String[newLength];
     
     for (int i = 0; i < minLength; i++)
       newAr[i] = oldAr[i];
       
     return newAr;
   }
}