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.
 *
 * @version     1.5    June 26, 2001
 * @author      Franck van Breugel
 * @see List
 * @see Position
 * @see DNode
 */
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.");
        }
    }

    /** 
     * Returns the size of this list.
     *
     * @return The size of this list.
     */
    public int size() 
    {
        return size;
    }

    /** 
     * Tests if this list is empty. 
     *
     * @return true if this list is empty, false otherwise.
     */
    public boolean isEmpty() 
    {
        return (size == 0);
    }

    /**
     * Returns the collection of elements of this list.
     *
     * @return The collection of elements of this list.
     */
    public Iterator elements()
    {
        Vector collection = new Vector();
        DNode node = header.getNext();
        while (node != trailer)
        {
            collection.addElement(node.element());
            node = node.getNext();
        }
        return collection.iterator();
    }

    /**
     * Returns the collection of positions of this list.
     *
     * @return The collection of positions of this list.
     */
    public Iterator positions()
    {
        Vector collection = new Vector();
        DNode node = header.getNext();
        while (node != trailer)
	{
	    collection.addElement(node);
	    node = node.getNext();
        }
        return collection.iterator();
    }
 
    /**
     * Returns the first position of this list.
     * Throws an EmptyContainerException if this list is empty.
     *
     * @return The first position of this list.
     * @exception EmptyContainerException if this list is empty.
     */
    public Position first() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("List is empty.");
        }
        return header.getNext();
    }

    /**
     * Returns the last position of this list.
     * Throws an EmptyContainerException if this list is empty.
     *
     * @return The last position of this list.
     * @exception EmptyContainerException if this list is empty.
     */
    public Position last() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("List is empty.");
        }
        return trailer.getPrev();
    }

    /**
     * Returns the position before the specified position in this list.
     * Throws an InvalidPositionException if the specified position is
     * invalid.
     * Throws a BoundaryViolationException if the specified position is
     * the first position of this list.
     *
     * @param position The position the predecessor of which is to be returned.
     * @return The position before the specified position in this list.
     * @exception InvalidPositionException if the specified position is 
     * invalid.
     * @exception BoundaryViolationException if the specified position is
     * the first position of this list.
     */
    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();
    }

    /**
     * Returns the position after the specified position in this list.
     * Throws an InvalidPositionException if the specified position is
     * invalid.
     * Throws a BoundaryViolationException if the specified position is
     * the last position of this list.
     *
     * @param position The position the successor of which is to be returned.
     * @return The position after the specified position in this list.
     * @exception InvalidPositionException if the specified position is 
     * invalid.
     * @exception BoundaryViolationException if the specified position is
     * the last position of this list.
     */
    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();
    }

    /**
     * Tests if the specified position is the first position of this list.
     * Throws an InvalidPositionException if the specified position is invalid.
     *
     * @param position The position to be tested to be the first position
     * of this list.
     * @result true if the specified position is the first position
     * of this list, false otherwise.
     * @exception InvalidPositionException if the specified position is
     * invalid.
     */
    public boolean isFirst(Position position) throws InvalidPositionException 
    {
        DNode node = checkPosition(position);
        return (node == first());
    }

    /**
     * Tests if the specified position is the last position of this list.
     * Throws an InvalidPositionException if the specified position is
     * invalid.
     *
     * @param position The position to be tested to be the last position
     * of this list.
     * @result true if the specified position is the last position
     * of this list, false otherwise.
     * @exception InvalidPositionException if the specified position is
     * invalid.
     */
    public boolean isLast(Position position) throws InvalidPositionException 
    {
        DNode node = checkPosition(position);
        return (node == last());
    }

    /**
     * Replaces the element at the specified position in this list
     * with the specified element and returns the replaced element.
     * Throws an InvalidPositionException if the specified position is
     * invalid.
     *
     * @param position The position the element of which is to be replaced.
     * @param element The replacement element.
     * @result The replaced element.
     * @exception InvalidPositionException if the specified position is
     * invalid.
     */
    public Object replaceElement(Position position, Object element) throws InvalidPositionException 
    {
        DNode node = checkPosition(position);
        Object temp = node.element();
        node.setElement(element);
        return temp;
    }

    /**
     * Swaps the elements of the specified positions in this list.
     * Throws an InvalidPositionException if one of the specified positions 
     * is invalid.
     *
     * @param firstPosition The position the element of which is to be swapped.
     * @param secondPosition The position the element of which is to be swapped.
     * @exception InvalidPositionException if one of the specified positions
     * is invalid.
     */
    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);
    }

    /**
     * Inserts the specified element at the beginning of this list
     * and returns its position.
     *
     * @param element The element to be inserted.
     * @result The position of the inserted element.
     */
    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;
    }

    /**
     * Inserts the specified element at the end of this list
     * and returns its position.
     *
     * @param element The element to be inserted.
     * @result The position of the inserted element.
     */
    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;
    }

    /**
     * Inserts the specified element before the specified position of this 
     * list and returns its position.
     * Throws an InvalidPositionException if the specified position is
     * invalid.
     *
     * @param element The element to be inserted.
     * @param position The position before which the element is to be inserted.
     * @result The position of the inserted element.
     * @exception InvalidPositionException if the specified position is
     * invalid.
     */
    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;
    }

    /**
     * Inserts the specified element after the specified position of this 
     * list and returns its position.
     * Throws an InvalidPositionException if the specified position is
     * invalid.
     *
     * @param element The element to be inserted.
     * @param position The position after which the element is to be inserted.
     * @result The position of the inserted element.
     * @exception InvalidPositionException if the specified position is
     * invalid.
     */
    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;
    }

    /**
     * Removes the specified position from this list and
     * returns its element.
     * Throws an InvalidPositionException if the specified position is
     * invalid.
     *
     * @param position The position to be removed.
     * @return The element of the removed position.
     * @exception InvalidPositionException if the specified position is
     * invalid.
     */
    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;
    }
}