com.virtuosotechnologies.lib.ring
Class RotatingArrayList

java.lang.Object
  extended byjava.util.AbstractCollection
      extended byjava.util.AbstractList
          extended bycom.virtuosotechnologies.lib.ring.RotatingArrayList
All Implemented Interfaces:
Cloneable, Collection, List, Serializable

public class RotatingArrayList
extends AbstractList
implements List, Cloneable, Serializable

Rotating resizeable array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list.

This class is roughly equivalent to ArrayList (and is based on the ArrayList implementation) with one important distinction. The add(index, object) method operates in amortized constant time rather than linear time when inserting at the beginning or end of a list, and the remove(index) method also operates in amortized constant time when removing from the beginning or end. This enables efficient use of this class in double-ended queues.

This class is not thread-safe.

See Also:
Serialized Form

Field Summary
 
Fields inherited from class java.util.AbstractList
modCount
 
Constructor Summary
RotatingArrayList()
          Constructs an empty list.
RotatingArrayList(Collection c)
          Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
RotatingArrayList(int initialCapacity)
          Constructs an empty list with the specified initial capacity.
 
Method Summary
 void add(int index, Object element)
          Inserts the specified element at the specified position in this list.
 boolean add(Object o)
          Appends the specified element to the end of this list.
 boolean addAll(Collection c)
          Appends all of the elements in the specified Collection to the end of this list, in the order that they are returned by the specified Collection's Iterator.
 boolean addAll(int index, Collection c)
          Inserts all of the elements in the specified Collection into this list, starting at the specified position.
 boolean addAllFirst(Collection c)
          Appends all of the elements in the specified Collection to the beginning of this list, in the order that they are returned by the specified Collection's Iterator.
 boolean addAllLast(Collection c)
          Appends all of the elements in the specified Collection to the end of this list, in the order that they are returned by the specified Collection's Iterator.
 boolean addFirst(Object o)
          Appends the specified element to the front of this list.
 boolean addLast(Object o)
          Appends the specified element to the back of this list.
 void clear()
          Removes all of the elements from this list.
 Object clone()
          Returns a shallow copy of this RotatingArrayList instance.
 boolean contains(Object elem)
          Returns true if this list contains the specified element.
 void ensureCapacity(int minCapacity)
          Increases the capacity of this ArraRotatingArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
 Object get(int index)
          Returns the element at the specified position in this list.
 Object getFirst()
          Returns the element at the front of the list.
 Object getLast()
          Returns the element at the back of the list.
 int indexOf(Object elem)
          Searches for the first occurence of the given argument, testing for equality using the equals method.
 boolean isEmpty()
          Tests if this list has no elements.
 int lastIndexOf(Object elem)
          Returns the index of the last occurrence of the specified object in this list.
 Object remove(int index)
          Removes the element at the specified position in this list.
 Object removeFirst()
          Removes the element from the front of this list.
 void removeFirst(int num)
          Removes from this List the first num elements.
 Object removeLast()
          Removes the element from the back of this list.
 void removeLast(int num)
          Removes from this List the last num elements.
 void removeRange(int fromIndex, int toIndex)
          Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.
 Object set(int index, Object element)
          Replaces the element at the specified position in this list with the specified element.
 Object setFirst(Object element)
          Replaces the element at the front of this list with the specified element.
 Object setLast(Object element)
          Replaces the element at the back of this list with the specified element.
 int size()
          Returns the number of elements in this list.
 Object[] toArray()
          Returns an array containing all of the elements in this list in the correct order.
 Object[] toArray(Object[] a)
          Returns an array containing all of the elements in this list in the correct order.
 void trimToSize()
          Trims the capacity of this RotatingArrayList instance to be the list's current size.
 
Methods inherited from class java.util.AbstractList
equals, hashCode, iterator, listIterator, listIterator, subList
 
Methods inherited from class java.util.AbstractCollection
containsAll, remove, removeAll, retainAll, toString
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.List
containsAll, equals, hashCode, iterator, listIterator, listIterator, remove, removeAll, retainAll, subList
 

Constructor Detail

RotatingArrayList

public RotatingArrayList(int initialCapacity)
Constructs an empty list with the specified initial capacity.

Parameters:
initialCapacity - the initial capacity of the list.
Throws:
IllegalArgumentException - if the specified initial capacity is negative

RotatingArrayList

public RotatingArrayList()
Constructs an empty list.


RotatingArrayList

public RotatingArrayList(Collection c)
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator. The RotatingArrayList instance has an initial capacity of 110% the size of the specified collection.

Parameters:
c - the collection whose elements are to be placed into this list.
Method Detail

trimToSize

public void trimToSize()
Trims the capacity of this RotatingArrayList instance to be the list's current size. An application can use this operation to minimize the storage of a RotatingArrayList instance.


ensureCapacity

public void ensureCapacity(int minCapacity)
Increases the capacity of this ArraRotatingArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

Parameters:
minCapacity - the desired minimum capacity.

size

public int size()
Returns the number of elements in this list.

Specified by:
size in interface List
Returns:
the number of elements in this list.

isEmpty

public boolean isEmpty()
Tests if this list has no elements.

Specified by:
isEmpty in interface List
Returns:
true if this list has no elements; false otherwise.

contains

public boolean contains(Object elem)
Returns true if this list contains the specified element.

Specified by:
contains in interface List
Parameters:
elem - element whose presence in this List is to be tested.

indexOf

public int indexOf(Object elem)
Searches for the first occurence of the given argument, testing for equality using the equals method.

Specified by:
indexOf in interface List
Parameters:
elem - an object.
Returns:
the index of the first occurrence of the argument in this list; returns -1 if the object is not found.

lastIndexOf

public int lastIndexOf(Object elem)
Returns the index of the last occurrence of the specified object in this list.

Specified by:
lastIndexOf in interface List
Parameters:
elem - the desired element.
Returns:
the index of the last occurrence of the specified object in this list; returns -1 if the object is not found.

clone

public Object clone()
Returns a shallow copy of this RotatingArrayList instance. (The elements themselves are not copied.)

Returns:
a clone of this RotatingArrayList instance.

toArray

public Object[] toArray()
Returns an array containing all of the elements in this list in the correct order.

Specified by:
toArray in interface List
Returns:
an array containing all of the elements in this list in the correct order.

toArray

public Object[] toArray(Object[] a)
Returns an array containing all of the elements in this list in the correct order. The runtime type of the returned array is that of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.

If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), the element in the array immediately following the end of the collection is set to null. This is useful in determining the length of the list only if the caller knows that the list does not contain any null elements.

Specified by:
toArray in interface List
Parameters:
a - the array into which the elements of the list are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
Returns:
an array containing the elements of the list.
Throws:
ArrayStoreException - if the runtime type of a is not a supertype of the runtime type of every element in this list.

get

public Object get(int index)
Returns the element at the specified position in this list.

Specified by:
get in interface List
Parameters:
index - index of element to return.
Returns:
the element at the specified position in this list.
Throws:
IndexOutOfBoundsException - if index is out of range (index < 0 || index >= size()).

getFirst

public Object getFirst()
Returns the element at the front of the list.

Returns:
the element at the front of this list.
Throws:
IndexOutOfBoundsException - if the list is empty

getLast

public Object getLast()
Returns the element at the back of the list.

Returns:
the element at the back of this list.
Throws:
IndexOutOfBoundsException - if the list is empty

set

public Object set(int index,
                  Object element)
Replaces the element at the specified position in this list with the specified element.

Specified by:
set in interface List
Parameters:
index - index of element to replace.
element - element to be stored at the specified position.
Returns:
the element previously at the specified position.
Throws:
IndexOutOfBoundsException - if index out of range (index < 0 || index >= size()).

setFirst

public Object setFirst(Object element)
Replaces the element at the front of this list with the specified element.

Parameters:
element - element to be stored at the front.
Returns:
the element previously at the the front.
Throws:
IndexOutOfBoundsException - if the list is empty.

setLast

public Object setLast(Object element)
Replaces the element at the back of this list with the specified element.

Parameters:
element - element to be stored at the back.
Returns:
the element previously at the back.
Throws:
IndexOutOfBoundsException - if the list is empty.

add

public boolean add(Object o)
Appends the specified element to the end of this list.

Specified by:
add in interface List
Parameters:
o - element to be appended to this list.
Returns:
true (as per the general contract of Collection.add).

addLast

public boolean addLast(Object o)
Appends the specified element to the back of this list.

Parameters:
o - element to be appended to this list.
Returns:
true (as per the general contract of Collection.add).

addFirst

public boolean addFirst(Object o)
Appends the specified element to the front of this list.

Parameters:
o - element to be appended to this list.
Returns:
true (as per the general contract of Collection.add).

add

public void add(int index,
                Object element)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Specified by:
add in interface List
Parameters:
index - index at which the specified element is to be inserted.
element - element to be inserted.
Throws:
IndexOutOfBoundsException - if index is out of range (index < 0 || index > size()).

removeFirst

public Object removeFirst()
Removes the element from the front of this list. Shifts any subsequent elements to the left (subtracts one from their indices).

Returns:
the element that was removed from the list.
Throws:
IndexOutOfBoundsException - if the list is empty.

removeLast

public Object removeLast()
Removes the element from the back of this list.

Returns:
the element that was removed from the list.
Throws:
IndexOutOfBoundsException - if the list is empty.

remove

public Object remove(int index)
Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

Specified by:
remove in interface List
Parameters:
index - the index of the element to removed.
Returns:
the element that was removed from the list.
Throws:
IndexOutOfBoundsException - if index out of range (index < 0 || index >= size()).

clear

public void clear()
Removes all of the elements from this list. The list will be empty after this call returns.

Specified by:
clear in interface List

addAll

public boolean addAll(Collection c)
Appends all of the elements in the specified Collection to the end of this list, in the order that they are returned by the specified Collection's Iterator. The behavior of this operation is undefined if the specified Collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified Collection is this list, and this list is nonempty.)

Specified by:
addAll in interface List
Parameters:
c - the elements to be inserted into this list.
Throws:
IndexOutOfBoundsException - if index out of range (index < 0 || index > size()).

addAllLast

public boolean addAllLast(Collection c)
Appends all of the elements in the specified Collection to the end of this list, in the order that they are returned by the specified Collection's Iterator. The behavior of this operation is undefined if the specified Collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified Collection is this list, and this list is nonempty.)

Parameters:
c - the elements to be inserted into this list.
Throws:
IndexOutOfBoundsException - if index out of range (index < 0 || index > size()).

addAllFirst

public boolean addAllFirst(Collection c)
Appends all of the elements in the specified Collection to the beginning of this list, in the order that they are returned by the specified Collection's Iterator. The behavior of this operation is undefined if the specified Collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified Collection is this list, and this list is nonempty.)

Parameters:
c - the elements to be inserted into this list.
Throws:
IndexOutOfBoundsException - if index out of range (index < 0 || index > size()).

addAll

public boolean addAll(int index,
                      Collection c)
Inserts all of the elements in the specified Collection into this list, starting at the specified position. Shifts the element currently at that position (if any) and any subsequent elements to the right (increases their indices). The new elements will appear in the list in the order that they are returned by the specified Collection's iterator.

Specified by:
addAll in interface List
Parameters:
index - index at which to insert first element from the specified collection.
c - elements to be inserted into this list.
Throws:
IndexOutOfBoundsException - if index out of range (index < 0 || index > size()).

removeLast

public void removeLast(int num)
Removes from this List the last num elements. This call shortens the list by num elements. (If num==0, this operation has no effect.)

Parameters:
num - number of elements to remove

removeFirst

public void removeFirst(int num)
Removes from this List the first num elements. Shifts all remaining elements to the left (reduces their index). This call shortens the list by num elements. (If num==0, this operation has no effect.)

Parameters:
num - number of elements to remove

removeRange

public void removeRange(int fromIndex,
                        int toIndex)
Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index). This call shortens the list by (toIndex - fromIndex) elements. (If toIndex<=fromIndex, this operation has no effect.)

AbstractList.removeRange() is protected, but RotatingArrayList makes this method public since it may be useful to clients.

Parameters:
fromIndex - index of first element to be removed.
toIndex - index after last element to be removed.