package net.datastructures;
import java.util.Iterator;
/**  
 * Realization of a List using a doubly-linked list of nodes.
 *   
 * @author Michael Goodrich, Natasha Gelfand, Roberto Tamassia, Eric Zamore
 */
/** 
 * @costaContext net/datastructures/DNode
 */  
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 it is valid; O(1) time */
	protected DNode checkPosition(Position p) throws InvalidPositionException {
		if (p == null)
			throw new InvalidPositionException	
			("Null position passed to NodeList");
		if (p == header)
			throw new InvalidPositionException
			("The header node is not a valid position");
		if (p == trailer)
			throw new InvalidPositionException
			("The trailer node is not a valid position");
		try {
			DNode temp = (DNode)p;
			if ((temp.getPrev() == null) || (temp.getNext() == null))
				throw new InvalidPositionException
				("Position does not belong to a valid NodeList");
			return temp;
		} catch (ClassCastException e) {
			throw new InvalidPositionException
			("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 EmptyListException {
		if (isEmpty())
			throw new EmptyListException("List is empty");
		return header.getNext();
	}

	/** Returns the last position in the list; O(1) time */
	public Position last()
		throws EmptyListException {
		if (isEmpty())
			throw new EmptyListException("List is empty");
		return trailer.getPrev();
	}

	/** Returns the position before the given one; O(1) time */
	public Position prev(Position p)
		throws InvalidPositionException, BoundaryViolationException {
		DNode v = checkPosition(p);
		DNode prev = v.getPrev();
		if (prev == header)
			throw new BoundaryViolationException
			("Cannot advance past the beginning of the list");
		return prev;
	}

	/** Returns the position after the given one; O(1) time */
	public Position next(Position p)
		throws InvalidPositionException, BoundaryViolationException {
		DNode v = checkPosition(p);
		DNode next = v.getNext();
		if (next == trailer)
			throw new BoundaryViolationException
			("Cannot advance past the end of the list");
		return next;
	}

	/** Insert the given element before the given position, returning
	 * the new position; O(1) time  */
	public Position insertBefore(Position p, Object element) 
		throws InvalidPositionException {			// 
		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 after the given position, returning the
	 * new position; O(1) time  */
	public Position insertAfter(Position p, Object element) 
		throws InvalidPositionException {
		DNode v = checkPosition(p);
		numElts++;
		DNode newNode = new DNode(v, v.getNext(), element);
		v.getNext().setPrev(newNode);
		v.setNext(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;
	}

	/** Insert the given element at the end of the list, returning
	 * the new position; O(1) time  */
	public Position insertLast(Object element) {
		numElts++;
		DNode oldLast = trailer.getPrev();
		DNode newNode = new DNode(oldLast, trailer, element);
		oldLast.setNext(newNode);
		trailer.setPrev(newNode);
		return newNode;
	}

	/**Remove the given position from the list; O(1) time */
	public Object remove(Position p)
		throws InvalidPositionException {
		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 InvalidPositionException {
		DNode v = checkPosition(p);
		Object oldElt = v.element();
		v.setElement(element);
		return oldElt;
}

	/** Returns an iterator of all the nodes in the list. */
	public Iterator positions() { return new PositionIterator(this); }
	/** Returns an iterator of all the elements in the list. */
	public Iterator elements() { return new ElementIterator(this); }

	// Convenience methods
	/** Returns whether a position is the first one;  O(1) time */
	public boolean isFirst(Position p)
		throws InvalidPositionException {  
		DNode v = checkPosition(p);
		return v.getPrev() == header;
	}

	/** Returns whether a position is the last one;  O(1) time */
	public boolean isLast(Position p)
		throws InvalidPositionException {  
		DNode v = checkPosition(p);
		return v.getNext() == trailer;
	}

	/** Swap the elements of two give positions;  O(1) time */ 
	public void swapElements(Position a, Position b) 
		throws InvalidPositionException {
		DNode pA = checkPosition(a);
		DNode pB = checkPosition(b);
		Object temp = pA.element();
		pA.setElement(pB.element());
		pB.setElement(temp);
	}

	/** Returns a textual representation of the list */
	public String toString() {
		String s = "[";
		if (!isEmpty()) {
			Position p = first();
			while (true) {
				s += p.element();
				if (p==last())
					break; 
				s += ", ";
				p = next(p);
			}
		}
		s += "]";
		return s;
	}

	public static void main(String[] args) {

		// Prepare the test
		NodeList test = new NodeList();
		Position p = null;
		/*for (int i = 0; i < 25; i++) {
			Integer testNumber = i;
			p = test.insertLast(testNumber);
			}*/
		// Test
		//for (int i = 0; i < 10; i++) {
			p = test.prev(p);
			//}
		
	}
}