import java.util.Iterator;

public class NodeList implements List  {
	protected int numElts;            	// Number of elements in the list
	protected DNode header, trailer;	// Special sentinels



	/** Constructor that creates an empty list; O(1) time */

	public NodeList() {
		numElts = 0;
		header = new DNode(null, null, null);		// create header
		trailer = new DNode(header, null, null);	// create trailer
		header.setNext(trailer);		// make header and trailer point to each other
	}




	/** Checks if position is valid for this list and converts it to DNode if so; O(1) time */

	protected DNode checkPosition(Position p) throws ExceptionInvalidPosition {
		if(p == null)
			throw new ExceptionInvalidPosition("Null position passed to NodeList");
		if(p == header)
			throw new ExceptionInvalidPosition("The header node is not a valid position");
		if(p == trailer)
			throw new ExceptionInvalidPosition("The trailer node is not a valid position");


		try {
			DNode temp = (DNode) p;
			if((temp.getPrev() == null) || (temp.getNext() == null))
				throw new ExceptionInvalidPosition("Position does not belong to a valid NodeList");
			return temp;
		}

		catch (ClassCastException e) {
			throw new ExceptionInvalidPosition("Position is of wrong type for this list");
		}
	}



	/** Returns the number of elements in the list;  O(1) time */
	public int size() { return numElts; }

	/** Returns whether the list is empty;  O(1) time  */
	public boolean isEmpty() { return (numElts == 0); }




	/** Returns the first position in the list; O(1) time */

	public Position first() throws ExceptionEmptyList {
		if (isEmpty())
			throw new ExceptionEmptyList("List is empty");
		return header.getNext();
	}


	/** Returns the last position in the list; O(1) time */

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




	/** Insert the given element before the given position, returning the new position; O(1) time  */

	public Position insertBefore(Position p, Object element) throws ExceptionInvalidPosition {
		DNode v = checkPosition(p);
		numElts++;
		DNode newNode = new DNode(v.getPrev(), v, element);
		v.getPrev().setNext(newNode);
		v.setPrev(newNode);
		return newNode;
	}

	/** Insert the given element at the beginning of the list, returning the new position; O(1) time  */

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



	/**Remove the given position from the list; O(1) time */

	public Object remove(Position p) throws ExceptionInvalidPosition {
		DNode v = checkPosition(p);
		numElts--;
		DNode vPrev = v.getPrev();
		DNode vNext = v.getNext();
		vPrev.setNext(vNext);
		vNext.setPrev(vPrev);
		Object vElem = v.element();

		// unlink the position from the list and make it invalid

		v.setNext(null);
		v.setPrev(null);
		return vElem;
	}

	/** Replace the element at the given position with the new element and return the old element; O(1) time  */

	public Object replace(Position p, Object element) throws ExceptionInvalidPosition {
		DNode v = checkPosition(p);
		Object oldElt = v.element();
		v.setElement(element);
		return oldElt;
	}





	/** Returns the given position; O(1) time */

	public Position pos(Position p) throws ExceptionInvalidPosition, ExceptionBoundaryViolation {
		DNode v = checkPosition(p);
		return v;
	}


	/** Returns the position before the given one; O(1) time */

	public Position prev(Position p) throws ExceptionInvalidPosition, ExceptionBoundaryViolation {
		DNode v = checkPosition(p);
		DNode prev = v.getPrev();
		if (prev == header)
			throw new ExceptionBoundaryViolation("Cannot advance past the beginning of the list");
		return prev;
	}


	/** Returns the node after a given node in the list. */

	public Position next(Position p) throws ExceptionInvalidPosition, ExceptionBoundaryViolation {
		DNode v = checkPosition(p);
		return v.getNext();
	}




	/** Inserts an element at the back of the list. (between trailer and trailer.getPrev() */

	public Position insertLast(Object e) {
		DNode v = checkPosition(last());
		numElts++;
		DNode newNode = new DNode(v, v.getNext(), e);
		v.setNext(newNode);
		newNode.setPrev(v);
		newNode.setNext(trailer);
		return v;
	}


	/** Inserts an element after the given node in the list. */

	public Position insertAfter(Position p, Object e) throws ExceptionInvalidPosition {
		DNode v = checkPosition(p);
		DNode temp = v.getNext();
		numElts++;

		DNode newNode = new DNode(v, v.getNext(), e);	// node at (p + 1)
		v.setNext(newNode);
		newNode.setPrev(v);
		newNode.setNext(temp);
		return newNode;
	}
	public Iterator elements() {
		return new ElementIterator(this);
		}

}