// This is code fragments 5.8 and 5.9 from the textbook.
// Instead of documentation, Goodrich & Tamassia wrote chapter 5.
//
// You need to fill in some methods at the bottom.
// Then you will replace the two sentinels ("header" and "trailer")
// with a single sentinel ("sentinel").

public class NodeList implements List {

  protected int numElts;            	// Number of items in the list
  protected DNode header, trailer;	// Special sentinels

  // Constructor; 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
  }

  // Convenience function; 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 container.");
    }
  }


  // Simple accessor methods:
  public int size() {  return numElts; }		// O(1) time

  public boolean isEmpty() { return (numElts < 1); }	// O(1) time

  public boolean isFirst(Position p)			// O(1) time
      throws InvalidPositionException {
    DNode v = checkPosition(p);
    return v.getPrev() == header;
  }


  public Position first()				// O(1) time
      throws EmptyContainerException {
    if (isEmpty())
      throw new EmptyContainerException("List is empty");
    return header.getNext();
  }

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

  public Position before(Position p)			// O(1) time
      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;
  }

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

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

  public Object remove(Position p)			// O(1) time
      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;
  }

  public Object replaceElement(Position p, Object element)
      throws InvalidPositionException {			// O(1) time
    DNode v = checkPosition(p);
    Object oldElt = v.element();
    v.setElement(element);
    return oldElt;
  }

  public void swapElements(Position a, Position b)
      throws InvalidPositionException {			// O(1) time
    DNode pA = checkPosition(a);
    DNode pB = checkPosition(b);
    Object temp = pA.element();
    pA.setElement(pB.element());
    pB.setElement(temp);
  }

  //-----REMAINING METHODS FOR YOU TO FILL IN-----

  public Position insertLast(Object element) {
    // fill this in
  }

  public Position insertAfter (Position p, Object element)
    throws InvalidPositionException {
    // fill this in
  }

  public Position after (Position p) throws InvalidPositionException, BoundaryViolationException {
    // fill this in
  }

  public boolean isLast(Position p) throws InvalidPositionException {
    // fill this in
  }
}