org.apache.commons.collections
Class FastArrayList<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.ArrayList<E>
              org.apache.commons.collections.FastArrayList<E>

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess

public class FastArrayList<E>
extends ArrayList<E>

A customized implementation of java.util.ArrayList designed to operate in a multithreaded environment where the large majority of method calls are read-only, instead of structural changes. When operating in "fast" mode, read calls are non-synchronized and write calls perform the following steps:

• Clone the existing collection
• Perform the modification on the clone
• Replace the existing collection with the (modified) clone

When first created, objects of this class default to "slow" mode, where all accesses of any type are synchronized but no cloning takes place. This is appropriate for initially populating the collection, followed by a switch to "fast" mode (by calling setFast(true)) after initialization is complete.

NOTE: If you are creating and accessing an ArrayList only within a single thread, you should use java.util.ArrayList directly (with no synchronization), for maximum performance.

NOTE: This class is not cross-platform. Using it may cause unexpected failures on some architectures. It suffers from the same problems as the double-checked locking idiom. In particular, the instruction that clones the internal collection and the instruction that sets the internal reference to the clone can be executed or perceived out-of-order. This means that any read operation might fail unexpectedly, as it may be reading the state of the internal collection before the internal collection is fully formed. For more information on the double-checked locking idiom, see the Double-Checked Locking Idiom Is Broken Declaration.

Since:

Commons Collections 1.0

Version:

$Revision: 1.1.1.1 $ $Date: 2005/05/23 04:32:59 $

Author:

Matt Hall, John Watkinson, Craig R. McClanahan

See Also:

Serialized Form

Field Summary

protected boolean	fast Are we operating in "fast" mode?
protected ArrayList<E>	list The underlying list we are managing.

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

FastArrayList()
Construct a an empty list.

FastArrayList(Collection<E> collection)
Construct a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

FastArrayList(int capacity)
Construct an empty list with the specified capacity.

Method Summary

boolean	add(E element) Appends the specified element to the end of this list.
void	add(int index, E element) Insert the specified element at the specified position in this list, and shift all remaining elements up one position.
boolean	addAll(Collection<? extends E> collection) Append 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<? extends E> collection) Insert all of the elements in the specified Collection at the specified position in this list, and shift any previous elements upwards as needed.
void	clear() Remove all of the elements from this list.
Object	clone() Return a shallow copy of this FastArrayList instance.
boolean	contains(Object element) Return true if this list contains the specified element.
boolean	containsAll(Collection<?> collection) Return true if this list contains all of the elements in the specified Collection.
void	ensureCapacity(int capacity) Increase the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
boolean	equals(Object o) Compare the specified object with this list for equality.
E	get(int index) Return the element at the specified position in the list.
boolean	getFast() Returns true if this list is operating in fast mode.
int	hashCode() Return the hash code value for this list.
int	indexOf(Object element) Search for the first occurrence of the given argument, testing for equality using the equals() method, and return the corresponding index, or -1 if the object is not found.
boolean	isEmpty() Test if this list has no elements.
Iterator<E>	iterator() Return an iterator over the elements in this list in proper sequence.
int	lastIndexOf(Object element) Search for the last occurrence of the given argument, testing for equality using the equals() method, and return the corresponding index, or -1 if the object is not found.
ListIterator<E>	listIterator() Return an iterator of the elements of this list, in proper sequence.
ListIterator<E>	listIterator(int index) Return an iterator of the elements of this list, in proper sequence, starting at the specified position.
E	remove(int index) Remove the element at the specified position in the list, and shift any subsequent elements down one position.
boolean	remove(Object element) Remove the first occurrence of the specified element from the list, and shift any subsequent elements down one position.
boolean	removeAll(Collection<?> collection) Remove from this collection all of its elements that are contained in the specified collection.
boolean	retainAll(Collection<?> collection) Remove from this collection all of its elements except those that are contained in the specified collection.
E	set(int index, E element) Replace the element at the specified position in this list with the specified element.
void	setFast(boolean fast) Sets whether this list will operate in fast mode.
int	size() Return the number of elements in this list.
List<E>	subList(int fromIndex, int toIndex) Return a view of the portion of this list between fromIndex (inclusive) and toIndex (exclusive).
Object[]	toArray() Return an array containing all of the elements in this list in the correct order.
<T> T[]	toArray(T[] array) Return an array containing all of the elements in this list in the correct order.
String	toString() Return a String representation of this object.
void	trimToSize() Trim the capacity of this ArrayList instance to be the list's current size.

Methods inherited from class java.util.ArrayList

removeRange

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

list

protected ArrayList<E> list

The underlying list we are managing.

fast

protected boolean fast

Are we operating in "fast" mode?

Constructor Detail

FastArrayList

public FastArrayList()

Construct a an empty list.

FastArrayList

public FastArrayList(int capacity)

Construct an empty list with the specified capacity.

Parameters:

capacity - The initial capacity of the empty list

FastArrayList

public FastArrayList(Collection<E> collection)

Construct a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Parameters:

collection - The collection whose elements initialize the contents of this list

Method Detail

getFast

public boolean getFast()

Returns true if this list is operating in fast mode.

Returns:

true if this list is operating in fast mode

setFast

public void setFast(boolean fast)

Sets whether this list will operate in fast mode.

Parameters:

fast - true if the list should operate in fast mode

add

public boolean add(E element)

Appends the specified element to the end of this list.

Specified by:

add in interface Collection<E>

Specified by:

add in interface List<E>

Overrides:

add in class ArrayList<E>

Parameters:

element - The element to be appended

add

public void add(int index,
                E element)

Insert the specified element at the specified position in this list, and shift all remaining elements up one position.

Specified by:

add in interface List<E>

Overrides:

add in class ArrayList<E>

Parameters:

index - Index at which to insert this element

element - The element to be inserted

Throws:

IndexOutOfBoundsException - if the index is out of range

addAll

public boolean addAll(Collection<? extends E> collection)

Append 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.

Specified by:

addAll in interface Collection<E>

Specified by:

addAll in interface List<E>

Overrides:

addAll in class ArrayList<E>

Parameters:

collection - The collection to be appended

addAll

public boolean addAll(int index,
                      Collection<? extends E> collection)

Insert all of the elements in the specified Collection at the specified position in this list, and shift any previous elements upwards as needed.

Specified by:

addAll in interface List<E>

Overrides:

addAll in class ArrayList<E>

Parameters:

index - Index at which insertion takes place

collection - The collection to be added

Throws:

IndexOutOfBoundsException - if the index is out of range

clear

public void clear()

Remove all of the elements from this list. The list will be empty after this call returns.

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface List<E>

Overrides:

clear in class ArrayList<E>

Throws:

UnsupportedOperationException - if clear() is not supported by this list

clone

public Object clone()

Return a shallow copy of this FastArrayList instance. The elements themselves are not copied.

Overrides:

clone in class ArrayList<E>

contains

public boolean contains(Object element)

Return true if this list contains the specified element.

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface List<E>

Overrides:

contains in class ArrayList<E>

Parameters:

element - The element to test for

containsAll

public boolean containsAll(Collection<?> collection)

Return true if this list contains all of the elements in the specified Collection.

Specified by:

containsAll in interface Collection<E>

Specified by:

containsAll in interface List<E>

Overrides:

containsAll in class AbstractCollection<E>

Parameters:

collection - Collection whose elements are to be checked

ensureCapacity

public void ensureCapacity(int capacity)

Increase the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

Overrides:

ensureCapacity in class ArrayList<E>

Parameters:

capacity - The new minimum capacity

equals

public boolean equals(Object o)

Compare the specified object with this list for equality. This implementation uses exactly the code that is used to define the list equals function in the documentation for the List.equals method.

Specified by:

equals in interface Collection<E>

Specified by:

equals in interface List<E>

Overrides:

equals in class AbstractList<E>

Parameters:

o - Object to be compared to this list

get

public E get(int index)

Return the element at the specified position in the list.

Specified by:

get in interface List<E>

Overrides:

get in class ArrayList<E>

Parameters:

index - The index of the element to return

Throws:

IndexOutOfBoundsException - if the index is out of range

hashCode

public int hashCode()

Return the hash code value for this list. This implementation uses exactly the code that is used to define the list hash function in the documentation for the List.hashCode method.

Specified by:

hashCode in interface Collection<E>

Specified by:

hashCode in interface List<E>

Overrides:

hashCode in class AbstractList<E>

indexOf

public int indexOf(Object element)

Search for the first occurrence of the given argument, testing for equality using the equals() method, and return the corresponding index, or -1 if the object is not found.

Specified by:

indexOf in interface List<E>

Overrides:

indexOf in class ArrayList<E>

Parameters:

element - The element to search for

isEmpty

public boolean isEmpty()

Test if this list has no elements.

Specified by:

isEmpty in interface Collection<E>

Specified by:

isEmpty in interface List<E>

Overrides:

isEmpty in class ArrayList<E>

iterator

public Iterator<E> iterator()

Return an iterator over the elements in this list in proper sequence.

IMPLEMENTATION NOTE - If the list is operating in fast mode, an Iterator is returned, and a structural modification to the list is made, then the Iterator will continue over the previous contents of the list (at the time that the Iterator was created), rather than failing due to concurrent modifications.

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface List<E>

Overrides:

iterator in class AbstractList<E>

lastIndexOf

public int lastIndexOf(Object element)

Search for the last occurrence of the given argument, testing for equality using the equals() method, and return the corresponding index, or -1 if the object is not found.

Specified by:

lastIndexOf in interface List<E>

Overrides:

lastIndexOf in class ArrayList<E>

Parameters:

element - The element to search for

listIterator

public ListIterator<E> listIterator()

Return an iterator of the elements of this list, in proper sequence. See the implementation note on iterator().

Specified by:

listIterator in interface List<E>

Overrides:

listIterator in class AbstractList<E>

listIterator

public ListIterator<E> listIterator(int index)

Return an iterator of the elements of this list, in proper sequence, starting at the specified position. See the implementation note on iterator().

Specified by:

listIterator in interface List<E>

Overrides:

listIterator in class AbstractList<E>

Parameters:

index - The starting position of the iterator to return

Throws:

IndexOutOfBoundsException - if the index is out of range

remove

public E remove(int index)

Remove the element at the specified position in the list, and shift any subsequent elements down one position.

Specified by:

remove in interface List<E>

Overrides:

remove in class ArrayList<E>

Parameters:

index - Index of the element to be removed

Throws:

IndexOutOfBoundsException - if the index is out of range

remove

public boolean remove(Object element)

Remove the first occurrence of the specified element from the list, and shift any subsequent elements down one position.

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface List<E>

Overrides:

remove in class ArrayList<E>

Parameters:

element - Element to be removed

removeAll

public boolean removeAll(Collection<?> collection)

Remove from this collection all of its elements that are contained in the specified collection.

Specified by:

removeAll in interface Collection<E>

Specified by:

removeAll in interface List<E>

Overrides:

removeAll in class AbstractCollection<E>

Parameters:

collection - Collection containing elements to be removed

Throws:

UnsupportedOperationException - if this optional operation is not supported by this list

retainAll

public boolean retainAll(Collection<?> collection)

Remove from this collection all of its elements except those that are contained in the specified collection.

Specified by:

retainAll in interface Collection<E>

Specified by:

retainAll in interface List<E>

Overrides:

retainAll in class AbstractCollection<E>

Parameters:

collection - Collection containing elements to be retained

Throws:

UnsupportedOperationException - if this optional operation is not supported by this list

set

public E set(int index,
             E element)

Replace the element at the specified position in this list with the specified element. Returns the previous object at that position.

IMPLEMENTATION NOTE - This operation is specifically documented to not be a structural change, so it is safe to be performed without cloning.

Specified by:

set in interface List<E>

Overrides:

set in class ArrayList<E>

Parameters:

index - Index of the element to replace

element - The new element to be stored

Throws:

IndexOutOfBoundsException - if the index is out of range

size

public int size()

Return the number of elements in this list.

Specified by:

size in interface Collection<E>

Specified by:

size in interface List<E>

Overrides:

size in class ArrayList<E>

subList

public List<E> subList(int fromIndex,
                       int toIndex)

Return a view of the portion of this list between fromIndex (inclusive) and toIndex (exclusive). The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list. The returned list supports all of the optional list operations supported by this list.

Specified by:

subList in interface List<E>

Overrides:

subList in class AbstractList<E>

Parameters:

fromIndex - The starting index of the sublist view

toIndex - The index after the end of the sublist view

Throws:

IndexOutOfBoundsException - if an index is out of range

toArray

public Object[] toArray()

Return an array containing all of the elements in this list in the correct order.

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface List<E>

Overrides:

toArray in class ArrayList<E>

toArray

public <T> T[] toArray(T[] array)

Return 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.

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface List<E>

Overrides:

toArray in class ArrayList<E>

Parameters:

array - Array defining the element type of the returned list

Throws:

ArrayStoreException - if the runtime type of array is not a supertype of the runtime type of every element in this list

toString

public String toString()

Return a String representation of this object.

Overrides:

toString in class AbstractCollection<E>

trimToSize

public void trimToSize()

Trim the capacity of this ArrayList instance to be the list's current size. An application can use this operation to minimize the storage of an ArrayList instance.

Overrides:

trimToSize in class ArrayList<E>