|
|||||||||
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.ArraySequence
A Sequence implemented on top of an array.
In this design, the Sequence's Positions keep track of their ranks in the Sequence, making all atRank(int) operations O(1) time. The Positions also keep track of their Container (the Sequence), so the Sequence's contains(Accessor) method takes O(1) time.
The array is used in a circular fashion -- the first Position in the Sequence can occupy any index in the array, and the Sequence's subsequent Positions may wrap around the end of the array to occupy indices at the front of the array. Insertion and removal operations generally take O(n) time. When items are inserted into or removed from the Sequence, Positions must be shifted up or down the array to make room for the new Position. In these cases, the design of the shifting operation ensures that the minimum number of Positions are moved around. In any insertion or removal operation, no more than n/2 Positions will be shifted in the array (where n is the total number of items in the Sequence). The methods insertFirst(Obj), insertLast(Obj), posInsertFirst(Pos), posInsertLast(Pos), removeFirst(), and removeLast() generally take O(1) time, since no internal shifting is required. But when the array has to be reallocated and copied, these methods take O(n) time.
The capacity of the Sequence is equal to the capacity of the underlying array. Whenever the size of the Sequence becomes equal to the size of the underlying array, the next insertion operation will cause the array to double in size. The load factor of the array is the ratio of the number of elements stored in the array to the capacity of the array. The capacity of the array is possibly halved when the load factor of the array falls below 0.25. The initial capacity of the array is 16 (or the capacity in the constructor). The maximum capacity of the array is 2^26. If a client attempts to exceed this maximum, a ContainerFullException is thrown.
This ArraySequence incorporates the iterator caching optimization: calls to iterator-returning methods 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.
Constructor Summary | |
ArraySequence()
The default constructor for ArraySequence Initial array capacity defaults to 16. |
|
ArraySequence(boolean permitShrinkage)
Creates an empty Sequence. |
|
ArraySequence(int initialCapacity)
Creates an empty Sequence. |
|
ArraySequence(int initialCapacity,
boolean permitShrinkage)
Creates an empty Sequence. |
Method Summary | |
Position |
after(Position p)
O(1) time. |
Position |
atRank(int rank)
O(1) time. |
Position |
before(Position p)
O(1) time. |
boolean |
contains(Accessor a)
O(1) time. |
ObjectIterator |
elements()
O(1) time if the cache already exists. |
Position |
first()
O(1) time. |
Position |
insertAfter(Position p,
java.lang.Object elt)
This method also clears the Position and element caches. |
Position |
insertAtRank(int rank,
java.lang.Object elt)
This method also clears the Position and element caches. |
Position |
insertBefore(Position p,
java.lang.Object elt)
This method also clears the Position and element caches. |
Position |
insertFirst(java.lang.Object elt)
This method also clears the Position and element caches. |
Position |
insertLast(java.lang.Object elt)
This method also clears the Position and element caches. |
boolean |
isFirst(Position p)
O(1) time. |
boolean |
isLast(Position p)
O(1) time. |
Position |
last()
O(1) time. |
Container |
newContainer()
Returns an empty ArraySequence. |
void |
posInsertAfter(Position willBePredecessor,
Position toInsert)
Makes toInsert the predecessor of willBeSuccessor. |
void |
posInsertAtRank(int rank,
Position toInsert)
Makes toInsert to rankOfPos'th Position in this Sequence. |
void |
posInsertBefore(Position willBeSuccessor,
Position toInsert)
Makes toInsert the predecessor of willBeSuccessor. |
void |
posInsertFirst(Position toInsert)
Makes toInsert the first Position of this Sequence. |
void |
posInsertLast(Position toInsert)
Makes toInsert the last Position of this Sequence. |
PositionIterator |
positions()
O(1) time if the cache already exitsts. |
int |
rankOf(Position p)
O(1) time. |
java.lang.Object |
remove(Position p)
This method also clears the Position and element caches. |
java.lang.Object |
removeAfter(Position p)
This method also clears the Position and element caches. |
java.lang.Object |
removeAtRank(int i)
This method also clears the Position and element caches. |
java.lang.Object |
removeBefore(Position p)
This method also clears the Position and element caches. |
java.lang.Object |
removeFirst()
This method also clears the Position and element caches. |
java.lang.Object |
removeLast()
This method also clears the Position and element caches. |
java.lang.Object |
replaceElement(Accessor a,
java.lang.Object newElement)
This method also invalidates the elements cache. |
void |
setArrayShrinkability(boolean permitShrinkage)
A public convenience method that allows the user to toggle the shrinkability of the array. |
int |
size()
O(1) time. |
java.lang.String |
toString()
O(n) time. |
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 ArraySequence()
public ArraySequence(int initialCapacity)
public ArraySequence(boolean permitShrinkage)
public ArraySequence(int initialCapacity, boolean permitShrinkage)
Method Detail |
public Container newContainer()
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, BoundaryViolationException
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, BoundaryViolationException
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 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 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 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, or is null
This method also clears the Position and element caches.
O(1) time in the general case.
O(n) time if the array size must be doubled because of overflow.public 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, or is null
This method also clears the Position and element caches.
O(1) time in the general case.
O(n) time if the array size must be doubled because of overflow.public 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 is null; or if willBeSuccessor is
null, incompatible, or not contained
This method also clears the Position and element caches.
O(n) time.public 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 is null; or if willBePredecessor is
null, incompatible, or not contained
This method also clears the Position and element caches.
O(n) time.public 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, or is null
This method also clears the Position and element caches.
O(1) time if rank==0 or rank==size_ and no array overflow occurs.
O(n) time otherwise.public 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, BoundaryViolationException
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, BoundaryViolationException
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 EmptyContainerException
removeFirst
in interface Sequence
jdsl.core.api.Sequence
EmptyContainerException
- if this sequence is emptypublic java.lang.Object removeLast() throws EmptyContainerException
removeLast
in interface Sequence
jdsl.core.api.Sequence
EmptyContainerException
- if this sequence is emptypublic java.lang.Object removeAtRank(int i) throws BoundaryViolationException
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
public void setArrayShrinkability(boolean permitShrinkage)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |