/**
  * LinkedListVector Classe: laboratorio VIII
  * realizza un array ridimensionabile usando una lista concatenata
  * @author A. Luchetta
  * @version 24-Nov-2006
  */
public class LinkedListVector implements MyList
{
   private ListNode head;
   private ListNode tail;

   private int size;
   
   /**
      costruttore
   */
   public LinkedListVector()
   {
      head = tail = new ListNode();
   }

   /**
      @return true se il contenitore e' vuoto, false altrimenti
   */
   public boolean isEmpty()
   {
      return size == 0;
   }
   
   /**
      rende vuoto il contenitore
      mantiene immutata la capacita' del contenitore
   */
   public void makeEmpty()
   {
      head = tail = new ListNode();
      size = 0;
   }
   
   /**
      @return numero di elementi nel contenitore
   */
   public int size()
   {
      return size;
   }
   
   /**
      aggiunge l'elemento specificato alla fine di questo Vettore
      O(1)
      @param obj nuovo elemento da aggiungere
   */
   public void add(Object obj)
   {
      tail.next = new ListNode(obj, null);
      tail = tail.next;
      size++;
   }

   /**
      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 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();
         
      ListNode nodePtr = head;
      
      int i = 0;
      while (i < index)
      {
         nodePtr = nodePtr.next;
         i++;
      }
      
      nodePtr.next = new ListNode(obj, nodePtr.next);

      size++;
   }

   /**
      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)
   {
      ListNode nodePtr = head.next;

      while (nodePtr != null)
      {
         if (obj.equals(nodePtr.element))
            return true;

         nodePtr = nodePtr.next;
      }

      return false;
   }
   
   /**
      restituisce l'elemento all'indice specificato
      O(n) nel caso medio
      @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();
         
      ListNode nodePtr = head.next;

      int i = 0;
      while (i < index)
      {
         nodePtr = nodePtr.next;
         i++;
      }
      
      return nodePtr.element;
   }
   
   /**
       ricerca la prima occorrenza dell'elemento passato come parametro,
       verificando l'eguaglianza tramite il metodo equals
       iniziando la ricerca dall'indice zero
       O(n) nel caso medio
       @param index obj l'elemento oggetto della verifica
       @return indice della prima occorrenza
   */
   public int indexOf(Object obj)
   {
      ListNode nodePtr = head.next;

      int i = 0;
      while (nodePtr != null)
      {
         if (obj.equals(nodePtr.element))
            return i;

         nodePtr = nodePtr.next;
         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();

      ListNode nodePtr = head;

      int i = 0;
      while (i < index)
      {
         nodePtr = nodePtr.next;
         i++;
      }
         
      Object obj = nodePtr.next.element;
      nodePtr.next = nodePtr.next.next;
      
      size--;

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

   // classe interna
   class ListNode
   {
      Object element;
      ListNode next;

      public ListNode(Object obj, ListNode n)
      {
         element = obj;
         next = n;
      }
      
      public ListNode()
      {
         this(null, null);
      }
   }
}