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)
    throws BoundaryViolationException  // O(n) 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;
  }

  public int rankOf(Position p)
    throws BoundaryViolationException  
  {
    DNode n = checkPosition(p); 
      int rank = 0; 
      DNode current = header.getNext(); 
      while (current != p) { 
        rank++; 
        current = current.getNext(); 
      } 
      return rank; 
  }

  public void insertAtRank(int rank, Object element)
    throws BoundaryViolationException  // O(n) time
  {
    if (rank == size())
      insertLast(element);
    else
      insertBefore(atRank(rank), element);
  }

  public Object removeAtRank(int rank)
    throws BoundaryViolationException  // O(n) time
  {
    return remove(atRank(rank));
  }

  public Object replaceAtRank(int rank, Object element)
    throws BoundaryViolationException  // O(n) time
  {
    return replaceElement(atRank(rank),element);
  }

  public String toString()
  {
    String str = "";
    DNode node = header.getNext();
    while (node != trailer)
    {
      str = str + node.element() + " ";
      node = node.getNext();
    }
    return str;
  }

  public Object clone()
  {
    NodeSequence clonedSeq = new NodeSequence();
    DNode node = header.getNext();
    while (node != trailer)
    {
      clonedSeq.insertLast(node.element());
      node = node.getNext();
    }
    return clonedSeq;
  }
}