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:
$Id: NodeSequence.java,v 1.31 2001/03/22 20:32:38 lv Exp $
Author:
Benoit Hudson, Mark Handy, Andrew Schwerin, Ryan Shaun Baker

Inner 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, java.lang.Object elt)
          This method also clears the position cache.
 Position insertAtRank(int rank, java.lang.Object elt)
          This method also clears the position cache.
 Position insertBefore(Position p, java.lang.Object elt)
          This method also clears the position cache.
 Position insertFirst(java.lang.Object elt)
          This method also clears the position cache.
 Position insertLast(java.lang.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 rankOfPos'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)
 java.lang.Object remove(Position p)
          This method also clears the position cache.
 java.lang.Object removeAfter(Position p)
          This method also clears the position cache.
 java.lang.Object removeAtRank(int i)
          This method also clears the position cache.
 java.lang.Object removeBefore(Position p)
          This method also clears the position cache.
 java.lang.Object removeFirst()
          This method also clears the position cache.
 java.lang.Object removeLast()
          This method also clears the position cache.
 java.lang.Object replaceElement(Accessor a, java.lang.Object newElement)
          O(1) time
 int size()
          O(1) time
 java.lang.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
BoundaryViolationException - if p is the first position of this sequence.

after

public Position after(Position p)
               throws InvalidAccessorException
O(1) time
Specified by:
after in interface InspectableSequence
Following copied from interface: jdsl.core.api.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
BoundaryViolationException - if p is the last position of this sequence.

insertBefore

public Position insertBefore(Position p,
                             java.lang.Object elt)
                      throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
insertBefore in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
p - Position in this sequence before which to insert an element.
element - 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(java.lang.Object elt)
                     throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
insertFirst in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
element - Any java.lang.Object
Returns:
The Position containing that element, which is now the first position in the sequence.

insertAfter

public Position insertAfter(Position p,
                            java.lang.Object elt)
                     throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
insertAfter in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
p - Position in this sequence after which to insert an element.
element - 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(java.lang.Object elt)
                    throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
insertLast in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
element - Any java.lang.Object
Returns:
The Position containing that element, which is now the last in the sequence.

insertAtRank

public Position insertAtRank(int rank,
                             java.lang.Object elt)
                      throws InvalidAccessorException,
                             BoundaryViolationException
This method also clears the position cache. O(1) time
Specified by:
insertAtRank in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
rank - Rank that element should have after insertion.
element - Any java.lang.Object
Returns:
Position of element in the sequence.
Throws:
BoundaryViolationException - if rank exceeds size() or if 0 exceeds rank

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 rankOfPos'th position in this sequence
Parameters:
rankOfPos - for n the size of this sequence, rankOfPos 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 java.lang.Object remove(Position p)
                        throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
remove in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
pos - 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 java.lang.Object removeAfter(Position p)
                             throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
removeAfter in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
pos - a position
Returns:
the element formerly stored at the position after pos
Throws:
BoundaryViolationException - if pos is the last position of this sequence
InvalidAccessorException - if the specified position is invalid or not belong to this container.

removeBefore

public java.lang.Object removeBefore(Position p)
                              throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
removeBefore in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
pos - a position
Returns:
the element formerly stored at the position before pos
Throws:
BoundaryViolationException - if pos is the first position of this sequence.
InvalidAccessorException - if the specified position is invalid or not belong to this container.

removeFirst

public java.lang.Object removeFirst()
                             throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
removeFirst in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Returns:
the element formerly stored at the first position of this
Throws:
EmptyContainerException - if this sequence is empty

removeLast

public java.lang.Object removeLast()
                            throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
removeLast in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Returns:
the element formerly stored at the last position of this
Throws:
EmptyContainerException - if this sequence is empty

removeAtRank

public java.lang.Object removeAtRank(int i)
                              throws InvalidAccessorException
This method also clears the position cache. O(1) time
Specified by:
removeAtRank in interface Sequence
Following copied from interface: jdsl.core.api.Sequence
Parameters:
rank - the rank of the position to be removed
Returns:
the element formerly stored at the position at rank
Throws:
BoundaryViolationException - if rank is less than 0 or greater than the size of this sequence

size

public int size()
O(1) time
Specified by:
size in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
Number of elements stored by the container.

replaceElement

public java.lang.Object replaceElement(Accessor a,
                                       java.lang.Object newElement)
                                throws InvalidAccessorException
O(1) time
Specified by:
replaceElement in interface Container
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.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
Following copied from interface: jdsl.core.api.InspectableContainer
Throws:
InvalidAccessorException - if a is null

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object