net.datastructures
Class NodePositionList<E>

java.lang.Object
  net.datastructures.NodePositionList<E>

All Implemented Interfaces:

Iterable<E>, PositionList<E>

public class NodePositionList<E>
extends Object
implements PositionList<E>

Realization of a PositionList using a doubly-linked list of nodes.

Author:

Michael Goodrich, Natasha Gelfand, Roberto Tamassia, Eric Zamore

Field Summary

protected DNode<E>	header
protected int	numElts
protected DNode<E>	trailer

Constructor Summary

NodePositionList()
Constructor that creates an empty list; O(1) time

Method Summary

void	addAfter(Position<E> p, E element) Insert the given element after the given position; O(1) time
void	addBefore(Position<E> p, E element) Insert the given element before the given position; O(1) time
void	addFirst(E element) Insert the given element at the beginning of the list, returning the new position; O(1) time
void	addLast(E element) Insert the given element at the end of the list, returning the new position; O(1) time
protected DNode<E>	checkPosition(Position<E> p) Checks if position is valid for this list and converts it to DNode if it is valid; O(1) time
Position<E>	first() Returns the first position in the list; O(1) time
static <E> String	forEachToString(PositionList<E> L) Returns a textual representation of a given node list using for-each
boolean	isEmpty() Returns whether the list is empty; O(1) time
boolean	isFirst(Position<E> p) Returns whether a position is the first one; O(1) time
boolean	isLast(Position<E> p) Returns whether a position is the last one; O(1) time
Iterator<E>	iterator() Returns an iterator of all the elements in the list.
Position<E>	last() Returns the last position in the list; O(1) time
Position<E>	next(Position<E> p) Returns the position after the given one; O(1) time
Iterable<Position<E>>	positions() Returns an iterable collection of all the nodes in the list.
Position<E>	prev(Position<E> p) Returns the position before the given one; O(1) time
E	remove(Position<E> p) Remove the given position from the list; O(1) time
E	set(Position<E> p, E element) Replace the element at the given position with the new element and return the old element; O(1) time
int	size() Returns the number of elements in the list; O(1) time
void	swapElements(Position<E> a, Position<E> b) Swap the elements of two give positions; O(1) time
String	toString() Returns a textual representation of the list
static <E> String	toString(PositionList<E> l) Returns a textual representation of a given node list

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

numElts

protected int numElts

header

protected DNode<E> header

trailer

protected DNode<E> trailer

Constructor Detail

NodePositionList

public NodePositionList()

Constructor that creates an empty list; O(1) time

Method Detail

checkPosition

protected DNode<E> checkPosition(Position<E> p)
                          throws InvalidPositionException

Checks if position is valid for this list and converts it to DNode if it is valid; O(1) time

Throws:

InvalidPositionException

size

public int size()

Returns the number of elements in the list; O(1) time

Specified by:

size in interface PositionList<E>

isEmpty

public boolean isEmpty()

Returns whether the list is empty; O(1) time

Specified by:

isEmpty in interface PositionList<E>

first

public Position<E> first()
                  throws EmptyListException

Returns the first position in the list; O(1) time

Specified by:

first in interface PositionList<E>

Throws:

EmptyListException

last

public Position<E> last()
                 throws EmptyListException

Returns the last position in the list; O(1) time

Specified by:

last in interface PositionList<E>

Throws:

EmptyListException

prev

public Position<E> prev(Position<E> p)
                 throws InvalidPositionException,
                        BoundaryViolationException

Returns the position before the given one; O(1) time

Specified by:

prev in interface PositionList<E>

Throws:

InvalidPositionException

BoundaryViolationException

next

public Position<E> next(Position<E> p)
                 throws InvalidPositionException,
                        BoundaryViolationException

Returns the position after the given one; O(1) time

Specified by:

next in interface PositionList<E>

Throws:

InvalidPositionException

BoundaryViolationException

addBefore

public void addBefore(Position<E> p,
                      E element)
               throws InvalidPositionException

Insert the given element before the given position; O(1) time

Specified by:

addBefore in interface PositionList<E>

Throws:

InvalidPositionException

addAfter

public void addAfter(Position<E> p,
                     E element)
              throws InvalidPositionException

Insert the given element after the given position; O(1) time

Specified by:

addAfter in interface PositionList<E>

Throws:

InvalidPositionException

addFirst

public void addFirst(E element)

Insert the given element at the beginning of the list, returning the new position; O(1) time

Specified by:

addFirst in interface PositionList<E>

addLast

public void addLast(E element)

Insert the given element at the end of the list, returning the new position; O(1) time

Specified by:

addLast in interface PositionList<E>

remove

public E remove(Position<E> p)
         throws InvalidPositionException

Remove the given position from the list; O(1) time

Specified by:

remove in interface PositionList<E>

Throws:

InvalidPositionException

set

public E set(Position<E> p,
             E element)
      throws InvalidPositionException

Replace the element at the given position with the new element and return the old element; O(1) time

Specified by:

set in interface PositionList<E>

Throws:

InvalidPositionException

iterator

public Iterator<E> iterator()

Returns an iterator of all the elements in the list.

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface PositionList<E>

positions

public Iterable<Position<E>> positions()

Returns an iterable collection of all the nodes in the list.

Specified by:

positions in interface PositionList<E>

isFirst

public boolean isFirst(Position<E> p)
                throws InvalidPositionException

Returns whether a position is the first one; O(1) time

Throws:

InvalidPositionException

isLast

public boolean isLast(Position<E> p)
               throws InvalidPositionException

Returns whether a position is the last one; O(1) time

Throws:

InvalidPositionException

swapElements

public void swapElements(Position<E> a,
                         Position<E> b)
                  throws InvalidPositionException

Swap the elements of two give positions; O(1) time

Throws:

InvalidPositionException

forEachToString

public static <E> String forEachToString(PositionList<E> L)

Returns a textual representation of a given node list using for-each

toString

public static <E> String toString(PositionList<E> l)

Returns a textual representation of a given node list

toString

public String toString()

Returns a textual representation of the list

Overrides:

toString in class Object