public class NodeSequence extends NodeList implements Sequence {
  // Check that rank is in the range [0,numElts-1]; O(1) time
  protected void checkRank(int rank)
      throws BoundaryViolationException {
    if (rank < 0 || rank >= numElts)
      throw new BoundaryViolationException("Rank " + rank + 
	" is invalid for this sequence of " + numElts + " elements.");
  }
  public Position atRank (int rank) {		// O(1) time
    DNode node;
    checkRank(rank);
    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;
  }
  // . . . (skipping methods elemAtRank(r) and rankOf(p))
  public void insertAtRank (int rank, Object element)
      throws BoundaryViolationException {	// O(n) time
    if (rank == size()) // we shouldn't checkRank in this case
      insertLast(element);
    else {
      checkRank(rank);
      insertBefore(atRank(rank), element);
      }
  }
  public Object removeAtRank (int rank)		// O(n) time
    throws BoundaryViolationException {
    checkRank(rank);
    return remove(atRank(rank));
  }
  public Object replaceAtRank (int rank, Object element) 
      throws BoundaryViolationException {	// O(n) time
    checkRank(rank);
    return replaceElement(atRank(rank),element);
  }
}