com.internationalnetwork.util
Class CircularArray<Type>

Object
  extended by com.internationalnetwork.util.CircularArray<Type>

public class CircularArray<Type>
extends Object

A circular array has a backing array whose size never changes. A head and a tail are tracked internally instead of adding and removing items as is the case with ArrayList and LinkedList objects, hence yielding better overall performance for certain tasks.

There are two types of methods used to add elements; one which requires unused elements, and the other which replaces elements at the tail end.


Field Summary
static String VERSION
          Version number of this Package (read-only).
 
Constructor Summary
CircularArray(Class<Type> type, int capacity, Type... elements)
          Constructs a circular array with the specified size.
CircularArray(Class<Type> type, Type... elements)
          Constructs a circular array with one or more pre-defined elements.
 
Method Summary
 boolean add(Type... elements)
          Adds any number of elements to the head of the array as long as enough empty slots are available.
 int chomp()
          Reduces the capacity to the current number of elements (if the array is empty, the capacity will be reduced to 1).
 Type delete()
          Returns an element from the tail after deleting it from the array.
 Type get()
          Returns the last element from the tail without deleting it from the array.
 Type get(int index)
          Returns the element at the specified logical position within the array, relative to the tail (a negative value causes processing relative to the head, but where the index begins at -1 instead of 0), without deleting it.
 int head()
          Returns the actual position of the head in the backing array.
 boolean isEmpty()
          Indicates if the circular array currently has no elements.
 boolean isFragmented()
          Indicates if the elements are wrapped over the end and beginning of the backing array.
 boolean isFull()
          Indicates if the circular array is at full capacity.
 boolean isOptimal()
          Indicates if the tail element in the backing array is located at slot 0 (which also implicitly means that the backing array is not fragmented).
 int length()
          Returns the maximum capacity of the backing array.
 boolean optimize()
          Defragments the backing array, and re-locates the tail to position 0.
 Type[] put(Type... elements)
          Destructively adds any number of elements to the head of the array, deleting the last elements from the tail when there are no empty slots.
 Type[] resize(int capacity)
          Changes the maximum capacity of the backing array, returning any excess elements that were truncated in the process.
 int size()
          Returns the number of elements between the head and the tail.
 int tail()
          Returns the actual position of the tail in the backing array.
 Type[] toArray()
          Returns all elements between the head and the tail in the form of an array.
 
Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

VERSION

public static final String VERSION
Version number of this Package (read-only).

See Also:
Constant Field Values
Constructor Detail

CircularArray

public CircularArray(Class<Type> type,
                     int capacity,
                     Type... elements)
Constructs a circular array with the specified size.

Parameters:
type - The class type of the Object (e.g., use String.class to create a circular array of String objects). This must match the type specified with Java's Generics, and is used to avoid type erasure which simplifies calls to methods such as toArray().
capacity - The number of elements in the backing array (must be a positive integer)
elements - Any number of elements to place in the backing array
Throws:
NegativeArraySizeException - If a negative size is specified
java.lang.IllegalArgumentExecption - If a size of 0 is specified

CircularArray

public CircularArray(Class<Type> type,
                     Type... elements)
Constructs a circular array with one or more pre-defined elements.

Parameters:
type - The class type of the Object (e.g., use String.class to create a circular array of String objects). This must match the type specified with Java's Generics, and is used to avoid type erasure which simplifies calls to methods such as toArray().
elements - One or more elements to place in the backing array (if no elements or an empty array is provided, an exception will be thrown)
Throws:
java.lang.IllegalArgumentExecption - If no elements were supplied
Method Detail

add

public boolean add(Type... elements)
Adds any number of elements to the head of the array as long as enough empty slots are available.

Parameters:
elements - The elements to add
Returns:
TRUE if successful, FALSE if no empty slots are available
See Also:
put(Type...)

chomp

public int chomp()
Reduces the capacity to the current number of elements (if the array is empty, the capacity will be reduced to 1). Consequently, the array is also defragmented.

Returns:
The number of empty slots removed from the backing array

delete

public Type delete()
Returns an element from the tail after deleting it from the array.

Returns:
The element that was deleted from the tail
Throws:
IndexOutOfBoundsException - if the array is empty
See Also:
resize(int), get()

get

public Type get()
Returns the last element from the tail without deleting it from the array.

Returns:
The element
Throws:
IndexOutOfBoundsException - if the array is empty
See Also:
delete()

get

public Type get(int index)
Returns the element at the specified logical position within the array, relative to the tail (a negative value causes processing relative to the head, but where the index begins at -1 instead of 0), without deleting it.

Parameters:
index - The logical position, within the circular array, of the element to return
Returns:
The element
Throws:
IndexOutOfBoundsException - if the array is empty or the position is out of bounds
See Also:
delete()

head

public int head()
Returns the actual position of the head in the backing array. Although this information is only for internal use, it may be useful for interactive output in a user interface.

Returns:
Actual position of head

isEmpty

public boolean isEmpty()
Indicates if the circular array currently has no elements.

Returns:
TRUE if the circular array is empty

isFragmented

public boolean isFragmented()
Indicates if the elements are wrapped over the end and beginning of the backing array.

Returns:
TRUE if the backing array is fragmented
See Also:
optimize()

isFull

public boolean isFull()
Indicates if the circular array is at full capacity.

Returns:
TRUE if the circular array is full

isOptimal

public boolean isOptimal()
Indicates if the tail element in the backing array is located at slot 0 (which also implicitly means that the backing array is not fragmented).

Returns:
TRUE if the backing array is optimal
See Also:
optimize()

length

public int length()
Returns the maximum capacity of the backing array.

Returns:
Maximum length
See Also:
size

optimize

public boolean optimize()
Defragments the backing array, and re-locates the tail to position 0.

This might be useful for ensuring fairness in benchmarks, even though it only temporarily eliminates wrapping the head and tail to position 0 in operations such as toArray(), get(int), put(), etc., hence the benefit is minimal.

Returns:
TRUE if optimization was performed
See Also:
head, tail

put

public Type[] put(Type... elements)
Destructively adds any number of elements to the head of the array, deleting the last elements from the tail when there are no empty slots.

Parameters:
elements - The elements to add
Returns:
An array containing the elements that were deleted from the tail.
See Also:
add(Type...)

resize

public Type[] resize(int capacity)
Changes the maximum capacity of the backing array, returning any excess elements that were truncated in the process.

Parameters:
capacity - The new size of the backing array
Returns:
an array containing only the elements that were truncated (will be an empty array if no elements were truncated)
See Also:
chomp(), length(), size

size

public int size()
Returns the number of elements between the head and the tail.

Returns:
Number of elements
See Also:
length()

tail

public int tail()
Returns the actual position of the tail in the backing array. Although this information is only for internal use, it may be useful for interactive output in a user interface.

Returns:
Actual position of tail

toArray

public Type[] toArray()
Returns all elements between the head and the tail in the form of an array. This operation uses a loop to copy all elements from the circular array, thus causing some processing overhead, so consider using the get(int) method for random access to a small number of elements.

Returns:
The array, which excludes unused elements (will be less than or equal to the maximum size)
See Also:
get()