/**
  * Lista concatenata: classe didattica
  * realizza l'ADT lista
  * @author A. Luchetta
  * @version 20-Nov-2006
  * @see EmptyLinkedListException
  * @see java.util.NoSuchElementException
  * @see java.lang.IllegalStateException
*/
import java.util.NoSuchElementException;

public class LinkedListWithIterator implements List
{
   // parte privata
   private ListNode head, tail;
   private int size;

   /**
      Inizializza una lista concatenata vuota
   */
   public LinkedListWithIterator()
   {  makeEmpty();
   }

   /**
      rende vuoto il contenitore
   */
   public void makeEmpty()
   {  head = tail = new ListNode();
      size = 0;
   }

   /**
      verifica se il contenitore e' vuota
      @return true se la lista e' vuota, false altrimenti
   */
   public boolean isEmpty()
   {  return (head == tail);
   }
   
   /**
      restituisce il numero di elementi nel contenitore
      @return numero di elementi nel contenitore
   */
   public int size()
   {  return size;
   }

   /**
      ispeziona il primo elemento della lista
      complessita' temporale O(1)
      @return il primo elemento della lista
   */
   public Object getFirst() throws EmptyLinkedListException
   {
      if (isEmpty())
         throw new EmptyLinkedListException();

      return head.getNext().getElement();
   }

    /**
      ispeziona l'ultimo elemento della lista
      complessita' temporale O(1)
      @return l'ultimo elemento della lista
   */
   public Object getLast() throws EmptyLinkedListException
   {
      if (isEmpty())
         throw new EmptyLinkedListException();

      return tail.getElement();
   }

    /**
      inserisce un elemento in testa alla lista
      complessita' temporale O(1)
      @param e l'elemento da inserire
   */
   public void addFirst(Object e)
   {
      // inserisce il dato nell’header attuale
      head.setElement(e);

      // crea un nodo con due riferimenti null
      ListNode newNode = new ListNode();

      // collega il nuovo nodo all’header attuale
      newNode.setNext(head);

      // il nuovo nodo diventa il nodo header
      head = newNode;
      
      // incrementa il numero di elementi
      size++;

      // tail non viene modificato
   }

    /**
      rimuove un elemento in testa alla lista
      complessita' temporale O(1)
      @return l'elemento rimosso
   */
   public Object removeFirst() throws EmptyLinkedListException
   {
      // delega a getFirst il controllo di lista vuota
      Object e = getFirst();

      // aggiorno l’header
      head = head.getNext();
      head.setElement(null);
      
      // decrementa il numero di elementi nel contenitore
      size--;

      return e;
   }

    /**
      inserisce un elemento in coda alla lista
      complessita' temporale O(1)
      @param e l'elemento da inserire
   */
   public void addLast(Object e)
   {
      tail.setNext(new ListNode(e, null));
      tail = tail.getNext();
      
      // incrementa il numero di elementi nel contenitore
      size++;
   }

    /**
      rimuove un elemento in coda alla lista
      complessita' temporale O(n)
      @return l'elemento rimosso
   */
   public Object removeLast() throws EmptyLinkedListException
   {
      // delega a getLast il controllo di lista vuota
      Object e = getLast();
 
      /*
        bisogna cercare il penultimo nodo partendo dall’inizio e finché non si
        arriva alla fine della catena
      */
      ListNode temp = head;
      while (temp.getNext() != tail)
         temp = temp.getNext();
 
      // a questo punto temp si riferisce al penultimo nodo
      tail = temp;
      tail.setNext(null);
      
      // decrementa il numero di elementi nel contenitore
      size--;
      return e;
   }
   
   /**
      restituisce un iteratore della lista. L'iteratore restituito
      si trova nella prima posizione della lista
      @return iteratore
   */
   public ListIterator getIterator()
   {
      return new LinkedListIterator(head);
   }

   // classe interna che realizza l'interfaccia ListIterator
   class LinkedListIterator implements ListIterator
   {
      private ListNode current;    // nodo che precede la posizione attuale (non è mai null)
      private ListNode previous;   // nodo precedente

      // inizializza un iteratore che si trova in posizione dopo il nodo
      // selezionato
      // @param il nodo precedente alla posizione dell'iteratore
      public LinkedListIterator(ListNode h)
      {
         current = h; previous = null;
      }
      
      /**
         verifica se e' presente almeno un elemento dopo la posizione corrente
         dell'iteratore
         @return true se e' presente almeno un elemento, false altrimenti
      */
      public boolean hasNext()
      {
         return current.getNext() != null;
      }

      /**
         ispeziona l'elemento DOPO la posizione corrente dell'iteratore, avanzando
         successivamente l'iteratore di una posizione nella lista
         param elemento ispezionato, se presente
         throws java.util.NoSuchElementException se non ci sono elementi dopo la
         posizione corrente
      */
      public Object next()
      {
         if (!hasNext())
            throw new NoSuchElementException();

         previous = current;
         current = current.getNext();
         
         return current.getElement();
      }
      
      /**
         inserisce un nuovo elemento dopo la posizione corrente dell'iteratore,
         avanzando successivamente l'iteratore di un posto nella lista
         @param elemento da inserire
      */
      public void add(Object obj)
      {
        ListNode n = new ListNode(obj, current.getNext());
        current.setNext(n);
        current = n;     // l'iteratore avanza
        previous = null; // non si puo’ invocare remove
      }
      
      /**
         elimina l'ultimo nodo esaminato dal metodo next()
         puo' essere invocato solo dopo l'invocazione del metodo next()
         @throws java.lang.IllegalStateException se precedentemente non e' stato
         invocato il metodo next()
      */
      public void remove()
      {
         // si puo' invocare il metodo solo dopo un'invocazione al metodo next
         if (previous == null)
            throw new IllegalStateException();

         previous.setNext(current.getNext());

         current = previous;
         previous = null; // non si puo’ chiamare emove() due volte
      }
   }


   class ListNode
   {
      private Object element;
      private ListNode next;
 
      public ListNode(Object e, ListNode n)
      {
        element = e;
        next = n;
      }
 
      public ListNode()
      {
         this(null, null);
      }
 
      public Object getElement() { return element; }
 
      public ListNode getNext()  { return next; }
 
      public void setElement(Object e) { element = e; }
 
      public void setNext(ListNode n) {  next = n; }
   }
}