|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | 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,
Object elt)
This method also clears the Position and element caches. |
Position |
insertAtRank(int rank,
Object elt)
This method also clears the Position and element caches. |
Position |
insertBefore(Position p,
Object elt)
This method also clears the Position and element caches. |
Position |
insertFirst(Object elt)
This method also clears the Position and element caches. |
Position |
insertLast(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 rank'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. |
Object |
remove(Position p)
This method also clears the Position and element caches. |
Object |
removeAfter(Position p)
This method also clears the Position and element caches. |
Object |
removeAtRank(int i)
This method also clears the Position and element caches. |
Object |
removeBefore(Position p)
This method also clears the Position and element caches. |
Object |
removeFirst()
This method also clears the Position and element caches. |
Object |
removeLast()
This method also clears the Position and element caches. |
Object |
replaceElement(Accessor a,
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. |
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
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, BoundaryViolationException
before
in interface InspectableSequence
p
- A Position in this sequence
p
BoundaryViolationException
- if p is the first position of
this sequence.
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequencepublic Position after(Position p) throws InvalidAccessorException, BoundaryViolationException
after
in interface InspectableSequence
p
- A Position in this sequence.
p
InvalidAccessorException
- Thrown if p
is
not a valid position in this sequence
BoundaryViolationException
- if p is the last position of
this sequence.public Position insertBefore(Position p, 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 insertAfter(Position p, 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 insertFirst(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 insertLast(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, 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, 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 Sequence
InvalidAccessorException
- 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 Sequence
InvalidAccessorException
- 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 Sequence
InvalidAccessorException
- 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
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, 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 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 Object removeAfter(Position p) throws InvalidAccessorException, BoundaryViolationException
removeAfter
in interface Sequence
p
- a position
BoundaryViolationException
- if pos is the last position of this
sequence
InvalidAccessorException
- if the specified position is
invalid or not belong to this container.public Object removeBefore(Position p) throws InvalidAccessorException, BoundaryViolationException
removeBefore
in interface Sequence
p
- a position
InvalidAccessorException
- if the specified position is
invalid or not belong to this container.
BoundaryViolationException
- if pos is the first position of
this sequence.public Object removeFirst() throws EmptyContainerException
removeFirst
in interface Sequence
EmptyContainerException
- if this sequence is emptypublic Object removeLast() throws EmptyContainerException
removeLast
in interface Sequence
EmptyContainerException
- if this sequence is emptypublic Object removeAtRank(int i) throws BoundaryViolationException
removeAtRank
in interface Sequence
i
- the rank of the position to be removed
BoundaryViolationException
- if rank is less than 0 or greater
than the size of this sequencepublic int size()
size
in interface InspectableContainer
public Object replaceElement(Accessor a, 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 String toString()
public void setArrayShrinkability(boolean permitShrinkage)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |