/**
  * LinkedListVector Classe: laboratorio IX
  * realizza un array ridimensionabile usando una lista concatenata
  * @author A. Luchetta
  * @version 24-Nov-2006
  */

import java.util.NoSuchElementException;
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;
   }
   

   /**
      costruisce un iteratore posizionato all'inizio di questa lista
      O(1)
      @return un iteratore per questa lista
   */
   public ListIterator getIterator()
   {
      return new LinkedListIterator(head);
   }

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

      public ListNode(Object obj, ListNode n)
      {
         element = obj;
         next = n;
      }
      
      public ListNode()
      {
         this(null, null);
      }
   }
   
   /*
      classe interna
      l'iteratore e' posizionato dopo il nodo current
   */
   class LinkedListIterator implements ListIterator
   {
      ListNode current;
      ListNode previous;
      
      public LinkedListIterator(ListNode n)
      {
         current = n;
         previous = null;
      }
      
      /**
         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.next != null;
      }
      
      /*
         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();

         previous = current;
         current = current.next;
         
         return current.element;
      }
      
      /**
         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)
      {
         current.next = new ListNode(x, current.next);
         current = current.next;
         previous = null;
      }
      
      /**
         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 == null)
            throw new IllegalStateException();

         previous.next = current.next;
         current = previous;
         previous = null;
      }
   }
}