package dataStructures;

import java.util.*;

/**
 * <p>Titulo: A classe local Nó</p>
 * <p>Descrição: Usado para guardar informação das listas ligadas</p>
 * @version 1.0
 */
class Node implements Cloneable {

  public Object item;
  public Node   next;

  /**
   * @param o O objecto a armazenar
   * @param n O proximo nó
   */

  //@ requires  o != null;
  //@ ensures item.equals(o);
  //@ ensures n!=null ==> next.equals(n);
  public Node(Object o, Node n) {
    item = o;
    next = n;
  }

  /**
   * @param n O nó a ser comparado
   * @return TRUE se ambos os nós referenciarem o mesmo objecto
             e o mesmo nó seguinte, senão FALSE
   */

  /*@ pure @*/ public boolean equals(Node n) {
    if (n==null)
      return false;
    if (next==null)
      return n.next==null;
    return item.equals(n.item) && next.equals(n.next);
  }

  /* A cópia é executada recursivamente */
  //@ also
  //@ ensures (\result != this) && equals((Node)\result);
  /*@ pure @*/ public Object clone() {
    Node copia = new Node(item,next);
    if (next!=null)
      copia.next = (Node)next.clone();      // recursive cloning...
    return copia;
  }
} //endClass Node
//////////////////////////////////////////////////////

/**
 * <p>Titulo: A classe Lista</p>
 * <p>Descrição: Usado para guardar informação numa estrutura
 *               de nós cuja dimensão é dinâmica</p>
 *
 * @author João Neto
 * @version 1.0
 */

public class DList implements List,Cloneable {

  private Node theHead;

  public DList() {
    theHead = null;
  }

  public List empty() {
    return new DList();
  }

  public void cons(Object o) {
    addBegin(o);
  }

  public Object head() {
    return theHead.item;
  }

  public boolean isEmpty() {
    return theHead == null;
  }

  public int length() {
    int i = 0;
    for(Node aux=theHead; aux!=null; aux=aux.next)
      i++;
    return i;
  }

  public Object get(int n) {
    Node aux=theHead;
    for(int i=1;i<n;i++)
      aux=aux.next;
    return aux.item;
  }

  public void addBegin(Object o) {
    theHead = new Node(o,theHead);
  }

  public void addEnd(Object o) {
    Node n = new Node(o,null);

    if (isEmpty())
      theHead = n;
    else {
      Node aux=theHead;
      while(aux.next!=null)
        aux=aux.next;
      aux.next = n;
    }
  }

  public void add(Object o, int n) {
    if (n==1)
      addBegin(o);
    else {
      Node aux = theHead;

      for (int i=1;i<n-1;i++)
        aux = aux.next;

      aux.next = new Node(o,aux.next);
    }
  }

  public void removeBegin() {
    theHead = theHead.next;
  }

  public void removeEnd() {
    if (theHead.next==null)
      theHead=null;
    else {
      Node aux = theHead;
      while (aux.next.next != null)
        aux = aux.next;
      aux.next = null;
    }
  }

  public List tail() {
    DList l = new DList();
    l.theHead = theHead.next;
    return l;
  }

  public boolean contains(Object o) {
    for(Node aux=theHead; aux!=null; aux=aux.next)
      if (aux.item.equals(o))
        return true;
    return false;
  }

  public int indexOf(Object o) {
    Node aux=theHead;
    int p=0;

    while (aux!=null) {
      p++;
      if (aux.item.equals(o))
        return p;
      aux=aux.next;
    }
    return 0;
  }

  public void remFirst(Object o) {
    if (theHead.item.equals(o))
      theHead = theHead.next;
    else {
      Node aux = theHead;

      while(aux.next!=null && !aux.next.item.equals(o))
        aux=aux.next;

      if (aux.next!=null)
        aux.next = aux.next.next;
    }
  }

  public void remAll(Object o) {
    while (theHead!=null && theHead.item.equals(o))
      theHead = theHead.next;   // remover todas as ocorrencias da frente

    if (theHead!=null) {          // se ainda há elementos...
      Node aux=theHead;
      while (aux.next!=null)
        if (aux.next.item.equals(o)) // encontrou-se outro, entao...
          aux.next = aux.next.next;  //  ... remove-se
        else
          aux=aux.next;          // senão, passa para o próximo
    }
  }

  public boolean equals(List l) {
    if (isEmpty() && l.isEmpty())
      return true;

    if (l instanceof DList) {  // versão rápida, mesma implementaçao
      Node aux1 = theHead,
           aux2 = ((DList)l).theHead;

      while (aux1!=null && aux2!=null && aux1.item.equals(aux2.item)) {
        aux1=aux1.next;
        aux2=aux2.next;
      }
      return (aux1==null && aux2==null);
    }

    // versão lenta para implementaçoes diferentes de listas
    int s = length();

    if (s != l.length())
      return false;

    for(int i=1;i<=s;i++)
      if (!get(i).equals(l.get(i)))
        return false;
    return true;
  }

  public void concat(List l) {
    if (l.isEmpty())
      return;

    boolean wasEmpty = isEmpty();
    int length = l.length();
    Node aux = theHead;

    if (!wasEmpty)  //referenciar aux para o ultimo nó da lista
      while (aux.next!=null)
        aux=aux.next;
    else           //adicionar a cabeça de 'l' à cabeça
      aux = theHead = new Node(l.head(),null);

    for(int i=wasEmpty?2:1;i<=length;i++) {
      aux.next = new Node(l.get(i),null);  //cria um novo nó no fim
      aux=aux.next;
    }
  }

  public void reverse() {
    if (theHead==null)
      return;

    DList lstInv = new DList();
    Node aux;

    while (theHead!=null) {
      aux = lstInv.theHead;
      lstInv.theHead = theHead;
      theHead = theHead.next;
      lstInv.theHead.next = aux;
    }
    theHead = lstInv.theHead;
  }

  public Object clone() {
    DList copy = new DList();
    if (theHead!=null)
      copy.theHead = (Node)theHead.clone();
    return copy;
  }

  /**
   * Traduz a lista numa string
   * @return a string que descreve a lista, eg. [3,4,6]
   */
  public String toString() {
    if (isEmpty())
      return "[]";

    String result = "[" + theHead.item;
    Node aux = theHead.next;

    while(aux!=null) {
      result += "," + aux.item;
      aux=aux.next;
    }
    return result + "]";
  }

  /**
   * <u>MÉTODO DE CLASSE</u> - As duas listas são iguais?
   *
   * @param lst1 A primeira lista a ser comparada
   * @param lst2 A segunda lista a ser comparada
   * @return TRUE se lst1=lst2, FALSE c.c.
   */

  //@ensures lst1.isEmpty() && lst2.isEmpty() ==> \result;
  //@ensures lst1.length() != lst2.length()       ==> !\result;
  //@ensures lst1.length() == lst2.length()       ==> \result == (\forall int i; 1<=i && i<=lst1.length(); lst1.get(i).equals(lst2.get(i)));
  public static boolean equalLists(DList lst1, DList lst2) {
    if (lst1.isEmpty() && lst2.isEmpty())
      return true;

    Node aux1 = lst1.theHead,
         aux2 = lst2.theHead;

    while (aux1!=null && aux2!=null && aux1.item.equals(aux2.item)) {
      aux1=aux1.next;
      aux2=aux2.next;
    }
    return (aux1==null && aux2==null);
  }

  //*************** Métodos para a interface Iterator

  public Iterator iterator() {
    return new ListIterator();
  }

  private class ListIterator implements Iterator {
    private Node nextNode = null;

    private ListIterator() {
      if (isEmpty()) {
        nextNode = null;
        return;
      }
      nextNode = theHead;
    }

    public boolean hasNext() {
      return nextNode != null;
    };

    public Object next() {
      if (nextNode == null)
        return null;

      Object actualObject = nextNode.item;
      nextNode = nextNode.next;
      return actualObject;
    };

    public void remove() {
      throw new UnsupportedOperationException();
    }

  }

  //********************************************************************
  public static void main (String[] args) throws CloneNotSupportedException {

    DList n  = new DList(), m = new DList();

    m.reverse();
    m.cons(new Integer(0));
    m.addBegin(new Integer(1));
    m.addBegin(new Integer(2));
    m.addBegin(new Integer(3));
    m.addBegin(new Integer(4));
    m.addBegin(new Integer(4));
    m.addBegin(new Integer(5));
    m.addEnd(new Integer(0));
    m.add(new Integer(6),3);

    DList p = (DList)m.tail();
    p.removeBegin();

    m.removeBegin();
    m.removeEnd();
    m.remFirst(new Integer(6));

    n = (DList)m.clone();
    n.reverse();
    System.out.println("m = " + m + "/ posiçao do 4:" + m.indexOf(new Integer(4)));
    System.out.println("m = " + m + "/ posiçao do 0:" + m.indexOf(new Integer(0)));
    System.out.println("m = " + m + "/ posiçao do 7:" + m.indexOf(new Integer(7)));
    System.out.println("m = " + m + "/" + m.length());
    System.out.println("n = " + n + "/" + n.length() + "\n Apagar o 4...");

    m.remAll(new Integer(4));
    System.out.println("m = " + m + "/" + m.length());
    n.remAll(new Integer(4));
    System.out.println("n = " + n + "/" + n.length());

    System.out.println(m.indexOf(new Integer(3)));
    System.out.println(m.equals(n)?"==":"!=");
    System.out.println(m.equals(m)?"==":"!=");
    System.out.println("m contem 5? " + m.contains(new Integer(5)));
    System.out.println("m contem 3? " + m.contains(new Integer(3)));
    m.concat(n);
    System.out.println(m);
    DList o = new DList();
    o.concat(n);
    System.out.println(o);
 }//end main()

}//endClass DList