|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object nz.ac.waikato.jdsl.core.ref.AbstractPositionalContainer nz.ac.waikato.jdsl.core.ref.NodeSequence
public class NodeSequence
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.
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,
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 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) |
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 nz.ac.waikato.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 nz.ac.waikato.jdsl.core.api.PositionalContainer |
---|
swapElements |
Methods inherited from interface nz.ac.waikato.jdsl.core.api.InspectableContainer |
---|
isEmpty |
Constructor Detail |
---|
public NodeSequence()
Method Detail |
---|
public Container newContainer()
Container
newContainer
in interface Container
public Position first() throws EmptyContainerException
first
in interface InspectableSequence
EmptyContainerException
- if this sequence is emptypublic Position last() throws EmptyContainerException
last
in interface InspectableSequence
EmptyContainerException
- if this sequence is emptypublic boolean isFirst(Position p) throws InvalidAccessorException
isFirst
in interface InspectableSequence
p
- A Position in this sequence
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic boolean isLast(Position p) throws InvalidAccessorException
isLast
in interface InspectableSequence
p
- A Position in this sequenceInvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic Position atRank(int rank) throws BoundaryViolationException
atRank
in interface InspectableSequence
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)
.
BoundaryViolationException
- if rank<0 or rank>=size()public int rankOf(Position p) throws InvalidAccessorException
rankOf
in interface InspectableSequence
p
- A Position in this sequence
size() - 1
.
InvalidAccessorException
- if p
is
not a valid position in this sequencepublic Position before(Position p) throws InvalidAccessorException
before
in interface InspectableSequence
p
- A Position in this sequence
p
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic Position after(Position p) throws InvalidAccessorException
after
in interface InspectableSequence
p
- A Position in this sequence.
p
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic Position insertBefore(Position p, java.lang.Object elt) throws InvalidAccessorException
insertBefore
in interface Sequence
p
- Position in this sequence before which to insert an
element.elt
- Any java.lang.Objectelement
and before
Position p
.
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic Position insertFirst(java.lang.Object elt) throws InvalidAccessorException
insertFirst
in interface Sequence
elt
- Any java.lang.Object
Position
containing that element
,
which is now the first position in the sequence.
InvalidAccessorException
public Position insertAfter(Position p, java.lang.Object elt) throws InvalidAccessorException
insertAfter
in interface Sequence
p
- Position in this sequence after which to insert an
element.elt
- Any java.lang.Objectelement
and after
Position p
.
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic Position insertLast(java.lang.Object elt) throws InvalidAccessorException
insertLast
in interface Sequence
elt
- Any java.lang.Object
Position
containing that element
,
which is now the last in the sequence.
InvalidAccessorException
public Position insertAtRank(int rank, java.lang.Object elt) throws InvalidAccessorException, BoundaryViolationException
insertAtRank
in interface Sequence
rank
- Rank that element
should have after insertion.elt
- Any java.lang.Objectelement
in the sequence.
BoundaryViolationException
- if rank
exceeds
size()
or if 0 exceeds rank
InvalidAccessorException
public void posInsertFirst(Position toInsert) throws InvalidAccessorException
toInsert
- Position of a compatible type for this sequence
InvalidAccessorException
- If toInsert is already
contained or is of an incompatible type
This method also clears the position cache.
O(1) timepublic void posInsertLast(Position toInsert) throws InvalidAccessorException
toInsert
- Position of a compatible type for this sequence
InvalidAccessorException
- If toInsert is already
contained or is of an incompatible type
This method also clears the position cache.
O(1) timepublic void posInsertBefore(Position willBeSuccessor, Position toInsert) throws InvalidAccessorException
willBeSuccessor
- a position in this sequencetoInsert
- Position of a compatible type for this sequence
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) timepublic void posInsertAfter(Position willBePredecessor, Position toInsert) throws InvalidAccessorException
willBePredecessor
- a position in this sequencetoInsert
- Position of a compatible type for this sequence
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) timepublic void posInsertAtRank(int rank, Position toInsert) throws InvalidAccessorException
rank
- for n the size of this sequence, rank must be in [0,n]toInsert
- Position of a compatible type for this sequence
InvalidAccessorException
- If toInsert is already
contained or is of an incompatible type
This method also clears the position cache.
O(1) timepublic java.lang.Object remove(Position p) throws InvalidAccessorException
remove
in interface Sequence
p
- the position to be removed
InvalidAccessorException
- if the specified position is
invalid or not belong to this container.public java.lang.Object removeAfter(Position p) throws InvalidAccessorException
removeAfter
in interface Sequence
p
- a position
InvalidAccessorException
- if the specified position is
invalid or not belong to this container.public java.lang.Object removeBefore(Position p) throws InvalidAccessorException
removeBefore
in interface Sequence
p
- a position
InvalidAccessorException
- if the specified position is
invalid or not belong to this container.public java.lang.Object removeFirst() throws InvalidAccessorException
removeFirst
in interface Sequence
InvalidAccessorException
public java.lang.Object removeLast() throws InvalidAccessorException
removeLast
in interface Sequence
InvalidAccessorException
public java.lang.Object removeAtRank(int i) throws InvalidAccessorException
removeAtRank
in interface Sequence
i
- the rank of the position to be removed
InvalidAccessorException
public int size()
size
in interface InspectableContainer
public java.lang.Object replaceElement(Accessor a, java.lang.Object newElement) throws InvalidAccessorException
replaceElement
in interface Container
a
- Accessor in this containernewElement
- to be stored at a
InvalidAccessorException
- if a is null or does not
belong to this containerpublic PositionIterator positions()
positions
in interface InspectablePositionalContainer
public ObjectIterator elements()
elements
in interface InspectableContainer
public boolean contains(Accessor a) throws InvalidAccessorException
contains
in interface InspectableContainer
InvalidAccessorException
- if a is nullpublic java.lang.String toString()
toString
in class java.lang.Object
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |