/**
  * ArrayVector Classe: laboratorio IX
  * realizza un vettore ridimensionabile usando un array
  * @author A. Luchetta
  * @version 24-Nov-2006
  * @see MyList
  */
import java.util.NoSuchElementException;

public class ArrayVector implements MyList
{
   static final int INITIAL_CAPACITY = 10;

   private Object[] v;
   private int vSize;

   /**
      costruttore
   */
   public ArrayVector()
   {
      v = new Object[INITIAL_CAPACITY];
      vSize = 0;
   }
   
   /**
      @return true se il contenitore e' vuoto, false altrimenti
   */
   public boolean isEmpty()
   {
      return vSize == 0;
   }
   
   /**
      rende vuoto il contenitore
      mantiene immutata la capacita' del contenitore
   */
   public void makeEmpty()
   {
      v = new Object[v.length];
      vSize = 0;
   }
   
   /**
      @return numero di elementi nel contenitore
   */
   public int size()
   {
      return vSize;
   }
   
   /**
      aggiunge l'elemento specificato alla fine di questo Vettore
      O(1) nel caso migliore, O(n) nel caso peggiore
      @param obj nuovo elemento da aggiungere
   */
   public void add(Object obj)
   {
      if (vSize >= v.length)
         v = resize(v, 2 * v.length);
         
      v[vSize++] = obj;
   }

   /**
      inserisce l'elemento specificato alla posizione specificata in questo Vettore.
      Sposta a destra l'elemento attualmente in quella posizione (se esistente)
      e tutti gli elementi successivi (incrementa di uno i loro indici)
      O(n) nel caso peggiore e medio
      @param obj nuovo elemento da aggiungere
      @throws ArrayIndexOutOfBoundsException se l'indice non e' nell'intervallo
      ammesso (index < 0 || index > size())
   */
   public void add(int index, Object obj)
   {
      if (index < 0 || index > size())
         throw new ArrayIndexOutOfBoundsException();
         
      if (index >= v.length)
         v = resize(v, 2 * v.length);
         
      for (int i = vSize; i > index; i--)
         v[i] = v[i - 1];
         
      v[index] = obj;
      vSize++;
   }

   /**
      verifica se l'elemento specificato e' un componente di questo Vettore
      O(n) nel caso medio
      @param obj elemento da verificare
      @return true se e solo se l'elemento specificato e' uguale a un
      componente di questo Vettore, come determinato dal metodo equals;
      false altrimenti
   */
   public boolean contains(Object obj)
   {
      for (int i = 0; i < vSize; i++)
         if (obj.equals(v[i]))
            return true;
            
      return false;
   }
   
   /**
      restituisce l'elemento all'indice specificato
      O(1)
      @param index indice
      @return elemento all'indice specificato
      @throws ArrayIndexOutOfBoundsException se l'indice < 0 || >= size()
   */
   public Object get(int index)
   {
      if (index < 0 || index >= size())
         throw new ArrayIndexOutOfBoundsException();
         
      return v[index];
   }

   /**
       ricerca la prima occorrenza dell'elemento passato come parametro,
       verificando l'eguaglianza tramite il metodo equals
       iniziando la ricerca
       O(n) nel caso medio
       @param index obj l'elemento oggetto della verifica
       @return indice della prima occorrenza
   */
   public int indexOf(Object obj)
   {
      for (int i = 0; i < vSize; i++)
         if (obj.equals(v[i]))
            return i;
            
      return -1;
   }
   
   /**
      rimuove l'elemento alla posizione specificata in questo Vettore.
      Sposta ogni elemento successivo a sinistra (decrementa di uno i loro indici)
      Ritorna l'elemento che ha rimosso dal Vettore.
      O(n) nel caso medio
      @param index l'indice a cui rimuovere l'elemento
      @param l'elemento rimosso
      @throws ArrayIndexOutOfBoundsException se l'indice <0 || indice >= size()
   */
   public Object remove(int index)
   {
      if (index < 0 || index >= size())
         throw new ArrayIndexOutOfBoundsException();
         
      Object obj = v[index];

      for (int i = index; i < vSize - 1; i++)
         v[i] = v[i + 1];
         
      vSize--;
      
      return obj;
   }

   /**
      rimuove la prima occorrenza dell'elemento specificato in questo Vettore.
      Se il Vettore non contiene l'elemento, il Vettore rimane immutato.
      O(n) nel caso medio
      @param obj elemento da rimuovere
      @return true se l'elemento e' rimosso, false altrimenti.
   */
   public boolean remove(Object obj)
   {
      int index = indexOf(obj);
      if (index >= 0)
         remove(index);
         
      return index >= 0;
   }
   
   public ListIterator getIterator()
   {
      return new ArrayIterator(0);
   }
   
   // ridimensiona l'array
   private static Object[] resize(Object[] a, int length)
   {
      int minLength = length;

      if (a.length < minLength)
         minLength = a.length;

      Object[] newArray = new Object[length];
      System.arraycopy(a, 0, newArray, 0, minLength);
      
      return newArray;
   }

   /*
      classe interna
      l'iteratore e' posizionato prima dell'elemento di rango = current
   */
   class ArrayIterator implements ListIterator
   {
      int current;
      int previous;
      
      public ArrayIterator(int n)
      {
         current = n;
         previous = -1;
      }
      

      /*
         verifica se e' possibile invocare il metodo next() senza generare l'eccezione
         @return false se l'iteratore e' posizionato alla fine della lista, true altrimenti
      */
      public boolean hasNext()
      {
         return current < vSize;
      }
      
      /*
         restituisce l'elemento che segue la posizione dell'iteratore e lo fa avanzare
         @return l'elemento che segue l'iteratore
         @throws NoSuchElementException se l'iteratore e' posizionato alla fine della lista
      */
      public Object next()
      {
         if (!hasNext())
            throw new NoSuchElementException();

         Object tmp = get(current);
         previous = current;
         current++;
         return tmp;
      }
      

      /*
         inserisce l'elemento x nella lista
         che si aggiunge DOPO la posizione attuale dell'iteratore
         posiziona poi l'iteratore dopo il nuovo elemento inserito
      */
      public void add(Object x)
      {

         if (current >= v.length)
            v = resize(v, 2 * v.length);
         
         for (int i = vSize; i > current; i--)
            v[i] = v[i - 1];
         
         v[current] = x;
         vSize++;
         current++;
         previous = -1;
      }

      /*
         elimina l'ultimo dato esaminato dal metodo next()
         senza modificare la posizione dell'iteratore;
         puo' essere invocato solo dopo un'invocazione
         del metodo next()
         @throws IllegalStateException
      */
      public void remove()
      {
         if (previous == -1)
            throw new IllegalStateException();

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

         vSize--;
         previous = -1;
      }
   }
}