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

import java.util.Scanner;
import java.util.NoSuchElementException;

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

   // variabili di esemplare
   private String[] words;
   private int wordsSize;

   /**
      inizializza un contenitore vuoto
   */
   public TextContainer()
   {
      makeEmpty();
   }
   
   /**
      inizializza un contenitore, inserendo un insieme di parole, acquisite da un oggetto di classe Scanner.
      @param reader oggetto da cui acquisire un insieme di parole.
      @param delimiter stringa contenente i delimitatori
   */
   public TextContainer(Scanner reader, String delimiter)
   {
      this();

      reader.useDelimiter("[" + delimiter + "]+");
      while (reader.hasNext())
         add(reader.next());
   }

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

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

   /**
      aggiunge una parola in coda al contenitore. Se il contenitore 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++;
   }

   /**
      restituisce l'ultima parola del contenitore, rimuovendola
      @return l'ultima parola del contenitore
      @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;
   }
   
   /**
      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 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);
   }


   // 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;

      //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 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;
   }
}