jdsl.core.ref
Class ArraySequence

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.core.ref.ArraySequence
All Implemented Interfaces:
Container, InspectableContainer, InspectablePositionalContainer, InspectableSequence, PositionalContainer, Sequence

public class ArraySequence
extends AbstractPositionalContainer
implements Sequence

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.

Version:
$Id: ArraySequence.java,v 1.19 2000/11/07 23:21:08 lv Exp $
Author:
Lucy Perry (lep), Mark Handy (mdh), Jitchaya Buranahirun (jbr), Benoit Hudson (bh), Ryan Shaun Baker (rsb)

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

ArraySequence

public ArraySequence()
The default constructor for ArraySequence Initial array capacity defaults to 16. The array is shrinkable by default.

ArraySequence

public ArraySequence(int initialCapacity)
Creates an empty Sequence. Uses the given initial capacity for the array.

ArraySequence

public ArraySequence(boolean permitShrinkage)
Creates an empty Sequence. Lets the client specify non-shrinkable. Uses default inital array capacity of 16.

ArraySequence

public ArraySequence(int initialCapacity,
                     boolean permitShrinkage)
Creates an empty Sequence. Lets the client specify the array's initial capacity, and whether the array is shrinkable.
Method Detail

newContainer

public Container newContainer()
Returns an empty ArraySequence. O(1) time.
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.
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.
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,
                       BoundaryViolationException
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,
                      BoundaryViolationException
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 and element caches. O(n) time, where n is the number of elements in the Sequence. In fact, at most n/2 Positions are shifted in one execution of insertBefore(p,elt).
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

insertAfter

public Position insertAfter(Position p,
                            java.lang.Object elt)
                     throws InvalidAccessorException
This method also clears the Position and element caches. O(n) time. In fact, at most n/2 Positions will be shiften in one execution of insertAfter(p,elt).
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

insertFirst

public Position insertFirst(java.lang.Object elt)
                     throws InvalidAccessorException
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.
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.

insertLast

public Position insertLast(java.lang.Object elt)
                    throws InvalidAccessorException
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.
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 and element caches. O(1) time if rank==0 or rank==size_, except in overflow cases. O(n) time in the general case.
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
Makes 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, 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.

posInsertLast

public void posInsertLast(Position toInsert)
                   throws InvalidAccessorException
Makes 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, 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.

posInsertBefore

public void posInsertBefore(Position willBeSuccessor,
                            Position toInsert)
                     throws InvalidAccessorException
Makes 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 is null; or if willBeSuccessor is null, incompatible, or not contained This method also clears the Position and element caches. O(n) time.

posInsertAfter

public void posInsertAfter(Position willBePredecessor,
                           Position toInsert)
                    throws InvalidAccessorException
Makes toInsert the predecessor of willBeSuccessor.
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 is null; or if willBePredecessor is null, incompatible, or not contained This method also clears the Position and element caches. O(n) time.

posInsertAtRank

public void posInsertAtRank(int rank,
                            Position toInsert)
                     throws InvalidAccessorException
Makes toInsert to 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, 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.

remove

public java.lang.Object remove(Position p)
                        throws InvalidAccessorException
This method also clears the Position and element caches. O(1) time if p is first or last, and no shrinkage of the array is needed. O(n) otherwise.
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,
                                    BoundaryViolationException
This method also clears the Position and element caches. O(n) 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,
                                     BoundaryViolationException
This method also clears the Position and element caches. O(n) 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 EmptyContainerException
This method also clears the Position and element caches. O(1) time, except in cases where the array size must be halved, to maintain a load factor of at least 0.25.
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 EmptyContainerException
This method also clears the Position and element caches. O(1) time, except in cases where the array size must be halved, to maintain a load factor of at least 0.25.
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 BoundaryViolationException
This method also clears the Position and element caches. O(n) 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
This method also invalidates the elements cache. 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 exitsts. Otherwise O(n) time 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) time 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()
O(n) time.
Overrides:
toString in class java.lang.Object

setArrayShrinkability

public void setArrayShrinkability(boolean permitShrinkage)
A public convenience method that allows the user to toggle the shrinkability of the array. O(1) time.