package net.datastructures;
/** 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;
}
/** Returns the rank of the element stored at the given position;
* O(n) time. */
public int rankOf(Position p)
throws InvalidPositionException {
DNode query = checkPosition(p);
DNode node = (DNode) first();
for (int i = 0; node != trailer; i++, node = node.getNext())
if (query == node) return i;
throw new InvalidPositionException("Position not found.");
}
/** Returns the element stored at the given rank; O(n) time */
public Object elemAtRank (int rank)
throws BoundaryViolationException {
checkRank(rank, size());
return atRank(rank).element();
}
/** 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));
}
/** Replaces the element stored at the given rank; O(n) time. */
public Object replaceAtRank (int rank, Object element)
throws BoundaryViolationException {
checkRank(rank, size());
return replace(atRank(rank),element);
}
}
|