jdsl.core.ref
Class NodeSequence

java.lang.Object
  jdsl.core.ref.AbstractPositionalContainer
      jdsl.core.ref.NodeSequence

All Implemented Interfaces:

Container, InspectableContainer, InspectablePositionalContainer, InspectableSequence, PositionalContainer, Sequence

public class NodeSequence

extends AbstractPositionalContainer

implements Sequence

A Sequence based on a doubly-linked-list implementation.

It incorporates the iterator caching optimization:
calls to iterator() are amortized O(n/k) time if called k times between modifications of the sequence. This is accomplished by making a list of the positions of the sequence whenever iterating through the list is necessary, and using it until there is a modification to the Sequence.

This implementation does not use fictitious positions at the beginning or end of the Sequence, and the head and tail node have null pointers past the beginning or end of the Sequence.

The non-interface methods for inserting positions are implemented separately in order to allow greater constant-factor efficiency and comprehensibility in the Sequence insertion methods and to allow later separation of their functionality.

Version:

JDSL 2.1.1

Author:

Benoit Hudson, Mark Handy, Andrew Schwerin, Ryan Shaun Baker

Nested Class Summary

static class

NodeSequence.FNSNode This nested class is the node for NodeSequence.

Constructor Summary

NodeSequence()
The default constructor for NodeSequence, as well as the only one.

Method Summary

Position	after(Position p) O(1) time
Position	atRank(int rank) O(1) time if the positions_ cache is valid (no modifications since cache was generated) O(N) if cache is invalid (must traverse up to half of Sequence)
Position	before(Position p) O(1) time
boolean	contains(Accessor a) O(1) time
ObjectIterator	elements() O(1) time if the cache already exists Otherwise O(N) to construct it
Position	first() O(1) time
Position	insertAfter(Position p, Object elt) This method also clears the position cache.
Position	insertAtRank(int rank, Object elt) This method also clears the position cache.
Position	insertBefore(Position p, Object elt) This method also clears the position cache.
Position	insertFirst(Object elt) This method also clears the position cache.
Position	insertLast(Object elt) This method also clears the position cache.
boolean	isFirst(Position p) O(1) time
boolean	isLast(Position p) O(1) time
Position	last() O(1) time
Container	newContainer() Creates a new, empty container of the same class as this one (and therefore of the same interface as this one).
void	posInsertAfter(Position willBePredecessor, Position toInsert) Make toInsert the successor of willBePredecessor
void	posInsertAtRank(int rank, Position toInsert) Make toInsert the rank'th position in this sequence
void	posInsertBefore(Position willBeSuccessor, Position toInsert) Make toInsert the predecessor of willBeSuccessor
void	posInsertFirst(Position toInsert) Make toInsert the first position of this sequence
void	posInsertLast(Position toInsert) Make toInsert the last position of this sequence
PositionIterator	positions() O(1) time if the cache already exists Otherwise O(N) to construct it
int	rankOf(Position p) O(1) time if the positions_ cache is valid (no modifications since cache was generated) O(N) if cache is invalid (must traverse rank elements of Sequence)
Object	remove(Position p) This method also clears the position cache.
Object	removeAfter(Position p) This method also clears the position cache.
Object	removeAtRank(int i) This method also clears the position cache.
Object	removeBefore(Position p) This method also clears the position cache.
Object	removeFirst() This method also clears the position cache.
Object	removeLast() This method also clears the position cache.
Object	replaceElement(Accessor a, Object newElement) O(1) time
int	size() O(1) time
String	toString()

Methods inherited from class jdsl.core.ref.AbstractPositionalContainer

isEmpty, swapElements

Methods inherited from class java.lang.Object

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

Methods inherited from interface jdsl.core.api.InspectableContainer

isEmpty

Methods inherited from interface jdsl.core.api.PositionalContainer

swapElements

Constructor Detail

NodeSequence

public NodeSequence()

The default constructor for NodeSequence, as well as the only one.

Method Detail

newContainer

public Container newContainer()

Description copied from interface: Container

Creates a new, empty container of the same class as this one (and therefore of the same interface as this one). That is, if newContainer() is called on a NodeSequence, the Container that is returned is actually a NodeSequence. This is a use of the Factory Method design pattern.

Specified by:

newContainer in interface Container

Returns:

A new, empty Container of the same class as this one.

first

public Position first()
               throws EmptyContainerException

O(1) time

Specified by:

first in interface InspectableSequence

Returns:

Position of the first element in the sequence

Throws:

EmptyContainerException - if this sequence is empty

last

public Position last()
              throws EmptyContainerException

O(1) time

Specified by:

last in interface InspectableSequence

Returns:

Position of the last element in the sequence

Throws:

EmptyContainerException - if this sequence is empty

isFirst

public boolean isFirst(Position p)
                throws InvalidAccessorException

O(1) time

Specified by:

isFirst in interface InspectableSequence

Parameters:

p - A Position in this sequence

Returns:

True if and only if the given position is the first in the sequence

Throws:

InvalidAccessorException - Thrown if p is not a valid position in this sequence

isLast

public boolean isLast(Position p)
               throws InvalidAccessorException

O(1) time

Specified by:

isLast in interface InspectableSequence

Parameters:

p - A Position in this sequence

Returns:

True if and only if the given position is the last in the sequence

Throws:

InvalidAccessorException - Thrown if p is not a valid position in this sequence

atRank

public Position atRank(int rank)
                throws BoundaryViolationException

O(1) time if the positions_ cache is valid (no modifications since cache was generated) O(N) if cache is invalid (must traverse up to half of Sequence)

Specified by:

atRank in interface InspectableSequence

Parameters:

rank - An integer index of positions in the sequence; the Position returned by first() is the same as that returned by atRank(0)last() is the same as that returned by atRank(size() - 1).

Returns:

position at the specified rank

Throws:

BoundaryViolationException - if rank<0 or rank>=size()

rankOf

public int rankOf(Position p)
           throws InvalidAccessorException

O(1) time if the positions_ cache is valid (no modifications since cache was generated) O(N) if cache is invalid (must traverse rank elements of Sequence)

Specified by:

rankOf in interface InspectableSequence

Parameters:

p - A Position in this sequence

Returns:

Rank of that element, where first element has rank 0 and the last has rank size() - 1.

Throws:

InvalidAccessorException - if p is not a valid position in this sequence

before

public Position before(Position p)
                throws InvalidAccessorException

O(1) time

Specified by:

before in interface InspectableSequence

Parameters:

p - A Position in this sequence

Returns:

Position previous to parameter position p

Throws:

InvalidAccessorException - Thrown if p is not a valid position in this sequence

after

public Position after(Position p)
               throws InvalidAccessorException

O(1) time

Specified by:

after in interface InspectableSequence

Parameters:

p - A Position in this sequence.

Returns:

Position after parameter position p

Throws:

InvalidAccessorException - Thrown if p is not a valid position in this sequence

insertBefore

public Position insertBefore(Position p,
                             Object elt)
                      throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

insertBefore in interface Sequence

Parameters:

p - Position in this sequence before which to insert an element.

elt - Any java.lang.Object

Returns:

Position containing element and before Position p.

Throws:

InvalidAccessorException - Thrown if p is not a valid position in this sequence

insertFirst

public Position insertFirst(Object elt)
                     throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

insertFirst in interface Sequence

Parameters:

elt - Any java.lang.Object

Returns:

The Position containing that element, which is now the first position in the sequence.

Throws:

InvalidAccessorException

insertAfter

public Position insertAfter(Position p,
                            Object elt)
                     throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

insertAfter in interface Sequence

Parameters:

p - Position in this sequence after which to insert an element.

elt - Any java.lang.Object

Returns:

Position containing element and after Position p.

Throws:

InvalidAccessorException - Thrown if p is not a valid position in this sequence

insertLast

public Position insertLast(Object elt)
                    throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

insertLast in interface Sequence

Parameters:

elt - Any java.lang.Object

Returns:

The Position containing that element, which is now the last in the sequence.

Throws:

InvalidAccessorException

insertAtRank

public Position insertAtRank(int rank,
                             Object elt)
                      throws InvalidAccessorException,
                             BoundaryViolationException

This method also clears the position cache. O(1) time

Specified by:

insertAtRank in interface Sequence

Parameters:

rank - Rank that element should have after insertion.

elt - Any java.lang.Object

Returns:

Position of element in the sequence.

Throws:

BoundaryViolationException - if rank exceeds size() or if 0 exceeds rank

InvalidAccessorException

posInsertFirst

public void posInsertFirst(Position toInsert)
                    throws InvalidAccessorException

Make toInsert the first position of this sequence

Parameters:

toInsert - Position of a compatible type for this sequence

Throws:

InvalidAccessorException - If toInsert is already contained or is of an incompatible type This method also clears the position cache. O(1) time

posInsertLast

public void posInsertLast(Position toInsert)
                   throws InvalidAccessorException

Make toInsert the last position of this sequence

Parameters:

toInsert - Position of a compatible type for this sequence

Throws:

InvalidAccessorException - If toInsert is already contained or is of an incompatible type This method also clears the position cache. O(1) time

posInsertBefore

public void posInsertBefore(Position willBeSuccessor,
                            Position toInsert)
                     throws InvalidAccessorException

Make toInsert the predecessor of willBeSuccessor

Parameters:

willBeSuccessor - a position in this sequence

toInsert - Position of a compatible type for this sequence

Throws:

InvalidAccessorException - If toInsert is already contained or is of an incompatible type, or if willBeSuccessor is invalid for one of the usual invalid-position reasons This method also clears the position cache. O(1) time

posInsertAfter

public void posInsertAfter(Position willBePredecessor,
                           Position toInsert)
                    throws InvalidAccessorException

Make toInsert the successor of willBePredecessor

Parameters:

willBePredecessor - a position in this sequence

toInsert - Position of a compatible type for this sequence

Throws:

InvalidAccessorException - If toInsert is already contained or is of an incompatible type, or if willBePredecessor is invalid for one of the usual invalid-position reasons This method also clears the position cache. O(1) time

posInsertAtRank

public void posInsertAtRank(int rank,
                            Position toInsert)
                     throws InvalidAccessorException

Make toInsert the rank'th position in this sequence

Parameters:

rank - for n the size of this sequence, rank must be in [0,n]

toInsert - Position of a compatible type for this sequence

Throws:

InvalidAccessorException - If toInsert is already contained or is of an incompatible type This method also clears the position cache. O(1) time

remove

public Object remove(Position p)
              throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

remove in interface Sequence

Parameters:

p - the position to be removed

Returns:

the element formerly stored at pos

Throws:

InvalidAccessorException - if the specified position is invalid or not belong to this container.

removeAfter

public Object removeAfter(Position p)
                   throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

removeAfter in interface Sequence

Parameters:

p - a position

Returns:

the element formerly stored at the position after pos

Throws:

InvalidAccessorException - if the specified position is invalid or not belong to this container.

removeBefore

public Object removeBefore(Position p)
                    throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

removeBefore in interface Sequence

Parameters:

p - a position

Returns:

the element formerly stored at the position before pos

Throws:

InvalidAccessorException - if the specified position is invalid or not belong to this container.

removeFirst

public Object removeFirst()
                   throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

removeFirst in interface Sequence

Returns:

the element formerly stored at the first position of this

Throws:

InvalidAccessorException

removeLast

public Object removeLast()
                  throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

removeLast in interface Sequence

Returns:

the element formerly stored at the last position of this

Throws:

InvalidAccessorException

removeAtRank

public Object removeAtRank(int i)
                    throws InvalidAccessorException

This method also clears the position cache. O(1) time

Specified by:

removeAtRank in interface Sequence

Parameters:

i - the rank of the position to be removed

Returns:

the element formerly stored at the position at rank

Throws:

InvalidAccessorException

size

public int size()

O(1) time

Specified by:

size in interface InspectableContainer

Returns:

Number of elements stored by the container.

replaceElement

public Object replaceElement(Accessor a,
                             Object newElement)
                      throws InvalidAccessorException

O(1) time

Specified by:

replaceElement in interface Container

Parameters:

a - Accessor in this container

newElement - to be stored at a

Returns:

old element, previously stored at a

Throws:

InvalidAccessorException - if a is null or does not belong to this container

positions

public PositionIterator positions()

O(1) time if the cache already exists Otherwise O(N) to construct it

Specified by:

positions in interface InspectablePositionalContainer

Returns:

A PositionIterator over all positions in the container

elements

public ObjectIterator elements()

O(1) time if the cache already exists Otherwise O(N) to construct it

Specified by:

elements in interface InspectableContainer

Returns:

an iterator over all the elements stored in this container

contains

public boolean contains(Accessor a)
                 throws InvalidAccessorException

O(1) time

Specified by:

contains in interface InspectableContainer

Throws:

InvalidAccessorException - if a is null

toString

public String toString()