package net.datastructures;
import java.util.Iterator;
/**
* Realization of a List using a doubly-linked list of nodes.
*
* @author Michael Goodrich, Natasha Gelfand, Roberto Tamassia, Eric Zamore
*/
public class NodeList implements List {
protected int numElts; // Number of elements in the list
protected DNode header, trailer; // Special sentinels
/** Constructor that creates an empty list; 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
}
/** Checks if position is valid for this list and converts it to
* DNode if it is valid; 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 list");
}
}
/** Returns the number of elements in the list; O(1) time */
public int size() { return numElts; }
/** Returns whether the list is empty; O(1) time */
public boolean isEmpty() { return (numElts == 0); }
/** Returns the first position in the list; O(1) time */
public Position first()
throws EmptyListException {
if (isEmpty())
throw new EmptyListException("List is empty");
return header.getNext();
}
/** Returns the last position in the list; O(1) time */
public Position last()
throws EmptyListException {
if (isEmpty())
throw new EmptyListException("List is empty");
return trailer.getPrev();
}
/** Returns the position before the given one; O(1) time */
public Position prev(Position p)
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;
}
/** Returns the position after the given one; O(1) time */
public Position next(Position p)
throws InvalidPositionException, BoundaryViolationException {
DNode v = checkPosition(p);
DNode next = v.getNext();
if (next == trailer)
throw new BoundaryViolationException
("Cannot advance past the end of the list");
return next;
}
/** Insert the given element before the given position, returning
* the new position; O(1) time */
public Position insertBefore(Position p, Object element)
throws InvalidPositionException { //
DNode v = checkPosition(p);
numElts++;
DNode newNode = new DNode(v.getPrev(), v, element);
v.getPrev().setNext(newNode);
v.setPrev(newNode);
return newNode;
}
/** Insert the given element after the given position, returning the
* new position; O(1) time */
public Position insertAfter(Position p, Object element)
throws InvalidPositionException {
DNode v = checkPosition(p);
numElts++;
DNode newNode = new DNode(v, v.getNext(), element);
v.getNext().setPrev(newNode);
v.setNext(newNode);
return newNode;
}
/** Insert the given element at the beginning of the list, returning
* the new position; O(1) time */
public Position insertFirst(Object element) {
numElts++;
DNode newNode = new DNode(header, header.getNext(), element);
header.getNext().setPrev(newNode);
header.setNext(newNode);
return newNode;
}
/** Insert the given element at the end of the list, returning
* the new position; O(1) time */
public Position insertLast(Object element) {
numElts++;
DNode oldLast = trailer.getPrev();
DNode newNode = new DNode(oldLast, trailer, element);
oldLast.setNext(newNode);
trailer.setPrev(newNode);
return newNode;
}
/**Remove the given position from the list; O(1) time */
public Object remove(Position p)
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;
}
/** Replace the element at the given position with the new element
* and return the old element; O(1) time */
public Object replace(Position p, Object element)
throws InvalidPositionException {
DNode v = checkPosition(p);
Object oldElt = v.element();
v.setElement(element);
return oldElt;
}
/** Returns an iterator of all the nodes in the list. */
public Iterator positions() { return new PositionIterator(this); }
/** Returns an iterator of all the elements in the list. */
public Iterator elements() { return new ElementIterator(this); }
// Convenience methods
/** Returns whether a position is the first one; O(1) time */
public boolean isFirst(Position p)
throws InvalidPositionException {
DNode v = checkPosition(p);
return v.getPrev() == header;
}
/** Returns whether a position is the last one; O(1) time */
public boolean isLast(Position p)
throws InvalidPositionException {
DNode v = checkPosition(p);
return v.getNext() == trailer;
}
/** Swap the elements of two give positions; O(1) time */
public void swapElements(Position a, Position b)
throws InvalidPositionException {
DNode pA = checkPosition(a);
DNode pB = checkPosition(b);
Object temp = pA.element();
pA.setElement(pB.element());
pB.setElement(temp);
}
/** Returns a textual representation of the list */
public String toString() {
String s = "[";
if (!isEmpty()) {
Position p = first();
while (true) {
s += p.element();
if (p==last())
break;
s += ", ";
p = next(p);
}
}
s += "]";
return s;
}
}
|