|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jdsl.core.ref.AbstractPositionalContainer | +--jdsl.core.ref.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.
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 |
public NodeSequence()
Method Detail |
public Container newContainer()
Container
newContainer
in interface Container
jdsl.core.api.Container
public Position first() throws EmptyContainerException
first
in interface InspectableSequence
jdsl.core.api.InspectableSequence
EmptyContainerException
- if this sequence is emptypublic Position last() throws EmptyContainerException
last
in interface InspectableSequence
jdsl.core.api.InspectableSequence
EmptyContainerException
- if this sequence is emptypublic boolean isFirst(Position p) throws InvalidAccessorException
isFirst
in interface InspectableSequence
jdsl.core.api.InspectableSequence
p
- A Position in this sequenceInvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic boolean isLast(Position p) throws InvalidAccessorException
isLast
in interface InspectableSequence
jdsl.core.api.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
jdsl.core.api.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
jdsl.core.api.InspectableSequence
p
- A Position in this sequencesize() - 1
.InvalidAccessorException
- if p
is
not a valid position in this sequencepublic Position before(Position p) throws InvalidAccessorException
before
in interface InspectableSequence
jdsl.core.api.InspectableSequence
p
- A Position in this sequencep
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequenceBoundaryViolationException
- if p is the first position of
this sequence.public Position after(Position p) throws InvalidAccessorException
after
in interface InspectableSequence
jdsl.core.api.InspectableSequence
p
- A Position in this sequence.p
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequenceBoundaryViolationException
- if p is the last position of
this sequence.public Position insertBefore(Position p, java.lang.Object elt) throws InvalidAccessorException
insertBefore
in interface Sequence
jdsl.core.api.Sequence
p
- Position in this sequence before which to insert an
element.element
- 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
jdsl.core.api.Sequence
element
- Any java.lang.ObjectPosition
containing that element
,
which is now the first position in the sequence.public Position insertAfter(Position p, java.lang.Object elt) throws InvalidAccessorException
insertAfter
in interface Sequence
jdsl.core.api.Sequence
p
- Position in this sequence after which to insert an
element.element
- 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
jdsl.core.api.Sequence
element
- Any java.lang.ObjectPosition
containing that element
,
which is now the last in the sequence.public Position insertAtRank(int rank, java.lang.Object elt) throws InvalidAccessorException, BoundaryViolationException
insertAtRank
in interface Sequence
jdsl.core.api.Sequence
rank
- Rank that element
should have after insertion.element
- Any java.lang.Objectelement
in the sequence.BoundaryViolationException
- if rank
exceeds
size()
or if 0 exceeds rank
public void posInsertFirst(Position toInsert) throws InvalidAccessorException
toInsert
- Position of a compatible type for this sequenceInvalidAccessorException
- 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 sequenceInvalidAccessorException
- 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 sequenceInvalidAccessorException
- 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 sequenceInvalidAccessorException
- 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
rankOfPos
- for n the size of this sequence, rankOfPos must be
in [0,n]toInsert
- Position of a compatible type for this sequenceInvalidAccessorException
- 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
jdsl.core.api.Sequence
pos
- the position to be removedInvalidAccessorException
- 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
jdsl.core.api.Sequence
pos
- a positionBoundaryViolationException
- if pos is the last position of this
sequenceInvalidAccessorException
- 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
jdsl.core.api.Sequence
pos
- a positionBoundaryViolationException
- if pos is the first position of
this sequence.InvalidAccessorException
- if the specified position is
invalid or not belong to this container.public java.lang.Object removeFirst() throws InvalidAccessorException
removeFirst
in interface Sequence
jdsl.core.api.Sequence
EmptyContainerException
- if this sequence is emptypublic java.lang.Object removeLast() throws InvalidAccessorException
removeLast
in interface Sequence
jdsl.core.api.Sequence
EmptyContainerException
- if this sequence is emptypublic java.lang.Object removeAtRank(int i) throws InvalidAccessorException
removeAtRank
in interface Sequence
jdsl.core.api.Sequence
rank
- the rank of the position to be removedBoundaryViolationException
- if rank is less than 0 or greater
than the size of this sequencepublic int size()
size
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public java.lang.Object replaceElement(Accessor a, java.lang.Object newElement) throws InvalidAccessorException
replaceElement
in interface Container
jdsl.core.api.Container
a
- Accessor in this containernewElement
- to be stored at aInvalidAccessorException
- if a is null or does not
belong to this containerpublic PositionIterator positions()
positions
in interface InspectablePositionalContainer
jdsl.core.api.InspectablePositionalContainer
public ObjectIterator elements()
elements
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public boolean contains(Accessor a) throws InvalidAccessorException
contains
in interface InspectableContainer
jdsl.core.api.InspectableContainer
InvalidAccessorException
- if a is nullpublic java.lang.String toString()
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |