/**
  * ArrayVector Classe: laboratorio VIII
  * realizza un vettore ridimensionabile usando un array
  * @author A. Luchetta
  * @version 24-Nov-2006
  * @see MyList
  */
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;
   }
   
   // 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;
   }
}