import java.util.Vector;
import java.util.Iterator;

/**
   The NodeList class implements the List interface by means of a
   doubly linked list with dummy nodes.
  
   @author      Franck van Breugel
   @version     1.5    June 26, 2001
*/
public class NodeList implements List 
{
    private int size;      // size of the list
    private DNode header;  // dummy node at the begining of the list
    private DNode trailer; // dummy node at the end of the list
 
    /** Constructs an empty list. */
    public NodeList() 
    {
        size = 0;
        header = new DNode();
        trailer = new DNode();
        header.setNext(trailer);
        trailer.setPrev(header);
    }
 
    /**
       Returns the specified position as a DNode.
       Throws an InvalidPositionException if the specified position
       is invalid: the specified position is not a DNode or the
       specified position is not part of this list or the specified 
       position is a dummy node.
      
       @param position The position to be returned a DNode.
       @return The specified position as a DNode.
       @exception PositionalSequenceException if the specified position
       is invalid.
    */
    private DNode checkPosition(Position position) throws InvalidPositionException 
    {
        if (position == null)
        {    
            throw new InvalidPositionException("Null position passed to list.");
        }
        if (position == header || position == trailer)
        {
	    throw new InvalidPositionException("Dummy node is not a valid position.");
        }
        try 
        {
            DNode node = (DNode) position;
            if (node.getPrev() == null || node.getNext() == null)
	    {
                throw new InvalidPositionException("Position does not belong to this list");
	    }
            return node;
        } 
        catch (ClassCastException e) 
        {
            throw new InvalidPositionException("Position is of the wrong type for this container.");
        }
    }

    public int size() 
    {
        return size;
    }

    public boolean isEmpty() 
    {
        return (size == 0);
    }

    public Iterator elements()
    {
        Vector collection = new Vector();
        DNode node = header.getNext();
        while (node != trailer)
        {
            collection.addElement(node.element());
            node = node.getNext();
        }
        return collection.iterator();
    }

    public Iterator positions()
    {
        Vector collection = new Vector();
        DNode node = header.getNext();
        while (node != trailer)
	{
	    collection.addElement(node);
	    node = node.getNext();
        }
        return collection.iterator();
    }
 
    public Position first() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("List is empty.");
        }
        return header.getNext();
    }

    public Position last() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("List is empty.");
        }
        return trailer.getPrev();
    }

    public Position before(Position position) throws InvalidPositionException, BoundaryViolationException 
    {
        DNode node = checkPosition(position);
        if (isFirst(node)) 
        {
            throw new BoundaryViolationException("Cannot go past the beginning of the list.");
        }
        return node.getPrev();
    }

    public Position after(Position position) throws InvalidPositionException, BoundaryViolationException 
    {
        DNode node = checkPosition(position);
        if (isLast(node))
        {
            throw new BoundaryViolationException("Cannot go past the end of the list.");
        }
        return node.getNext();
    }

    public boolean isFirst(Position position) throws InvalidPositionException 
    {
        DNode node = checkPosition(position);
        return (node == first());
    }

    public boolean isLast(Position position) throws InvalidPositionException 
    {
        DNode node = checkPosition(position);
        return (node == last());
    }

    public Object replaceElement(Position position, Object element) throws InvalidPositionException 
    {
        DNode node = checkPosition(position);
        Object temp = node.element();
        node.setElement(element);
        return temp;
    }

    public void swapElements(Position firstPosition, Position secondPosition) throws InvalidPositionException 
    {
        DNode firstNode = checkPosition(firstPosition);
        DNode secondNode = checkPosition(secondPosition);
        Object firstElement = firstNode.element();
        Object secondElement = secondNode.element();
        firstNode.setElement(secondElement);
        secondNode.setElement(firstElement);
    }

    public Position insertFirst(Object element)
    {
        DNode first = header.getNext();
        DNode node = new DNode(header, first, element);
        header.setNext(node);
        first.setPrev(node);
        size++;
        return node;
    }

    public Position insertLast(Object element)
    {
        DNode last = trailer.getPrev();
        DNode node = new DNode(last, trailer, element);
        last.setNext(node);
        trailer.setPrev(node);
        size++;
        return node;
    }

    public Position insertBefore(Position position, Object element) throws InvalidPositionException
    {
        DNode node = checkPosition(position);
        DNode prev = node.getPrev();
        DNode newNode = new DNode(prev, node, element);
        prev.setNext(newNode);
        node.setPrev(newNode);
        size++;
        return newNode;
    }

    public Position insertAfter(Position position, Object element) throws InvalidPositionException
    {
        DNode node = checkPosition(position);
        DNode next = node.getNext();
        DNode newNode = new DNode(node, next, element);
        node.setNext(newNode);
        next.setPrev(newNode);
        size++;
        return newNode;
    }

    public Object remove(Position position) throws InvalidPositionException 
    {
        DNode node = checkPosition(position);
        Object element = node.element();
        DNode prev = node.getPrev();
        DNode next = node.getNext();
        prev.setNext(next);
        next.setPrev(prev);
        node.setNext(null); // unlink position from this list
        node.setPrev(null); // unlink position from this list
        size--;
        return element;
    }    

    /**
       Returns a string representation of this list.
      
       @return A string representation of this list.
    */
    public String toString() 
    {
        String rep = "";
        DNode node = header.getNext();
        while (node != trailer)
        {
            rep += node.element().toString();
            rep += "\n";
            node = node.getNext();
        }
        return rep;
    }
}