statalign.base
Class CircularArray<E>

java.lang.Object
  statalign.base.CircularArray<E>

Type Parameters:

E - element type

public class CircularArray<E>
extends java.lang.Object

Dynamically growing circular array with extremely efficient deque and hash operations. Can be used as a dynamically growing hash (with semi-contiguous key range for space-efficiency), deque (queue or stack), array, perhaps in turns. Offers amortised O(1) time for each implemented operation. Does not shrink.

Author:

novadam

Constructor Summary

CircularArray()
Constructs an empty CircularArray with an initial capacity of MIN_CAPACITY.

CircularArray(int initialCapacity)
Constructs an empty CircularArray with a given minimal initial capacity but at least MIN_CAPACITY.

Method Summary

E	get(int key) Retrieves the element at the given key in the array or null if there is no element with that key.
int	length() Difference between the highest and lowest key of elements in the array plus 1.
E	pop() Retrieves the last element in the array (element with key endKey-1) and decreases endKey.
void	push(E elem) Adds new element at the end of the array (key endKey is assigned), growing the array if full, then endKey is increased.
void	put(int key, E element) Puts a new (key,element) pair into the CircularArray, growing the array if the new key range doesn't fit into the array.
E	shift() Retrieves the first element in the array (element with key startKey) and increases startKey.
E[]	toArray(E[] newData) Copies contents of this CircularArray to a regular array.
void	unshift(E elem) Adds new element at the beginning of the array (key startKey-1 is assigned), growing the array if full, then startKey is decreased.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CircularArray

public CircularArray()

Constructs an empty CircularArray with an initial capacity of MIN_CAPACITY.

CircularArray

public CircularArray(int initialCapacity)

Constructs an empty CircularArray with a given minimal initial capacity but at least MIN_CAPACITY.

Parameters:

initialCapacity - minimum capacity of the new array

Method Detail

length

public int length()

Difference between the highest and lowest key of elements in the array plus 1. This is the length of the data area which is considered nonempty. If array is used solely as a deque (or at least keys are contiguous), this equals the number of elements in the array.

Returns:

length as defined above

put

public void put(int key,
                E element)

Puts a new (key,element) pair into the CircularArray, growing the array if the new key range doesn't fit into the array. This operation might destroy the property of contiguous keys.

Parameters:

key - key of the element

element - the element to store at the given key

get

public E get(int key)

Retrieves the element at the given key in the array or null if there is no element with that key.

Parameters:

key - the given key

Returns:

element at the key or null

push

public void push(E elem)

Adds new element at the end of the array (key endKey is assigned), growing the array if full, then endKey is increased. If key range is contiguous before the call, this operation will maintain the property.

Parameters:

elem - the element to be added

pop

public E pop()

Retrieves the last element in the array (element with key endKey-1) and decreases endKey. If key range is contiguous, a null value can only be returned if array is empty or if null values have been added to the array explicitly. Otherwise, null may be returned for keys with an unspecified value.

Returns:

the last element in the array or null if empty

unshift

public void unshift(E elem)

Adds new element at the beginning of the array (key startKey-1 is assigned), growing the array if full, then startKey is decreased. If key range is contiguous before the call, this operation will maintain the property.

Parameters:

elem - the element to be added

shift

public E shift()

Retrieves the first element in the array (element with key startKey) and increases startKey. If key range is contiguous, a null value can only be returned if array is empty or if null values have been added to the array explicitly. Otherwise, null may be returned for keys with an unspecified value.

Returns:

the first element in the array or null if empty

toArray

public E[] toArray(E[] newData)

Copies contents of this CircularArray to a regular array. It must be at least of length() size.

Returns:

array