/** Implementation of a sequence by means of a doubly linked list. */
public class NodeSequence extends NodeList implements Sequence {
  /** Checks whether the given rank is in the range [0, n - 1] */
  protected void checkRank(int r, int n) 
    throws BoundaryViolationException {
    if (r < 0 || r >= n)
      throw new BoundaryViolationException("Illegal rank: " + r);
  }
  /** Returns the position containing the element at the given rank;
   * O(n) time. */
  public Position atRank (int rank) {
    DNode node;
    checkRank(rank, size());
    if (rank <= size()/2) { // scan forward from the head
      node = header.getNext();
      for (int i=0; i < rank; i++)
	node = node.getNext();
    }
    else { // scan backward from the tail
      node = trailer.getPrev(); 
      for (int i=1; i < size()-rank; i++)
	node = node.getPrev();
    }
    return node;
  }
  /** Inserts an element at the given rank; O(n) time. */
  public void insertAtRank (int rank, Object element)
    throws BoundaryViolationException {
    checkRank(rank, size() + 1);
    if (rank == size())
      insertLast(element);
    else {
      insertBefore(atRank(rank), element);
      }
  }
  /** Removes the element stored at the given rank; O(n) time. */
  public Object removeAtRank (int rank)
    throws BoundaryViolationException {
    checkRank(rank, size());
    return remove(atRank(rank));
  }