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.