Package org.apache.commons.collections

Class FastArrayList

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.ArrayList
org.apache.commons.collections.FastArrayList
All Implemented Interfaces:
Serializable, Cloneable, Iterable, Collection, List, RandomAccess
public class FastArrayList extends ArrayList

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: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $
Author:
Craig R. McClanahan, Stephen Colebourne
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected boolean
    fast
    Are we operating in "fast" mode?
    protected ArrayList
    list
    The underlying list we are managing.

    Fields inherited from class java.util.AbstractList

    modCount

  • Constructor Summary

    Constructors
    Constructor
    Description
    FastArrayList()
    Construct a an empty list.
    FastArrayList(int capacity)
    Construct an empty list with the specified capacity.
    FastArrayList(Collection collection)
    Construct a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(int index, Object element)
    Insert the specified element at the specified position in this list, and shift all remaining elements up one position.
    boolean
    add(Object element)
    Appends the specified element to the end of this list.
    boolean
    addAll(int index, Collection 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.
    boolean
    addAll(Collection 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.
    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.
    Object
    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
    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
    listIterator()
    Return an iterator of the elements of this list, in proper sequence.
    ListIterator
    listIterator(int index)
    Return an iterator of the elements of this list, in proper sequence, starting at the specified position.
    Object
    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.
    Object
    set(int index, Object 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
    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.
    Object[]
    toArray(Object[] 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

    forEach, removeIf, removeRange, replaceAll, sort, spliterator

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface java.util.Collection

    parallelStream, stream, toArray

  • Field Details

    • list

      protected ArrayList list
      The underlying list we are managing.

    • fast

      protected boolean fast
      Are we operating in "fast" mode?

  • Constructor Details

    • 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 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 Details

    • 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(Object element)
      Appends the specified element to the end of this list.
      Specified by:
      add in interface Collection
      Specified by:
      add in interface List
      Overrides:
      add in class ArrayList
      Parameters:
      element - The element to be appended

    • add

      public void add(int index, Object 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
      Overrides:
      add in class ArrayList
      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 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
      Specified by:
      addAll in interface List
      Overrides:
      addAll in class ArrayList
      Parameters:
      collection - The collection to be appended

    • addAll

      public boolean addAll(int index, Collection 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
      Overrides:
      addAll in class ArrayList
      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
      Specified by:
      clear in interface List
      Overrides:
      clear in class ArrayList
      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

    • contains

      public boolean contains(Object element)
      Return true if this list contains the specified element.
      Specified by:
      contains in interface Collection
      Specified by:
      contains in interface List
      Overrides:
      contains in class ArrayList
      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
      Specified by:
      containsAll in interface List
      Overrides:
      containsAll in class AbstractCollection
      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
      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
      Specified by:
      equals in interface List
      Overrides:
      equals in class ArrayList
      Parameters:
      o - Object to be compared to this list

    • get

      public Object get(int index)
      Return the element at the specified position in the list.
      Specified by:
      get in interface List
      Overrides:
      get in class ArrayList
      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
      Specified by:
      hashCode in interface List
      Overrides:
      hashCode in class ArrayList

    • 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
      Overrides:
      indexOf in class ArrayList
      Parameters:
      element - The element to search for

    • isEmpty

      public boolean isEmpty()
      Test if this list has no elements.
      Specified by:
      isEmpty in interface Collection
      Specified by:
      isEmpty in interface List
      Overrides:
      isEmpty in class ArrayList

    • iterator

      public Iterator iterator()
      Return an iterator over the elements in this list in proper sequence.

      Thread safety
      The iterator returned is thread-safe ONLY in FAST mode. In slow mode there is no way to synchronize, or make the iterator thread-safe.

      In fast mode iteration and modification may occur in parallel on different threads, however there is a restriction. Modification must be EITHER via the Iterator interface methods OR the List interface. If a mixture of modification methods is used a ConcurrentModificationException is thrown from the iterator modification method. If the List modification methods are used the changes are NOT visible in the iterator (it shows the list contents at the time the iterator was created).

      Specified by:
      iterator in interface Collection
      Specified by:
      iterator in interface Iterable
      Specified by:
      iterator in interface List
      Overrides:
      iterator in class ArrayList
      Returns:
      the iterator

    • 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
      Overrides:
      lastIndexOf in class ArrayList
      Parameters:
      element - The element to search for

    • listIterator

      public ListIterator listIterator()
      Return an iterator of the elements of this list, in proper sequence.

      Thread safety
      The iterator returned is thread-safe ONLY in FAST mode. In slow mode there is no way to synchronize, or make the iterator thread-safe.

      In fast mode iteration and modification may occur in parallel on different threads, however there is a restriction. Modification must be EITHER via the Iterator interface methods OR the List interface. If a mixture of modification methods is used a ConcurrentModificationException is thrown from the iterator modification method. If the List modification methods are used the changes are NOT visible in the iterator (it shows the list contents at the time the iterator was created).

      Specified by:
      listIterator in interface List
      Overrides:
      listIterator in class ArrayList
      Returns:
      the list iterator

    • listIterator

      public ListIterator listIterator(int index)
      Return an iterator of the elements of this list, in proper sequence, starting at the specified position.

      Thread safety
      The iterator returned is thread-safe ONLY in FAST mode. In slow mode there is no way to synchronize, or make the iterator thread-safe.

      In fast mode iteration and modification may occur in parallel on different threads, however there is a restriction. Modification must be EITHER via the Iterator interface methods OR the List interface. If a mixture of modification methods is used a ConcurrentModificationException is thrown from the iterator modification method. If the List modification methods are used the changes are NOT visible in the iterator (it shows the list contents at the time the iterator was created).

      Specified by:
      listIterator in interface List
      Overrides:
      listIterator in class ArrayList
      Parameters:
      index - The starting position of the iterator to return
      Returns:
      the list iterator
      Throws:
      IndexOutOfBoundsException - if the index is out of range

    • remove

      public Object 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
      Overrides:
      remove in class ArrayList
      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
      Specified by:
      remove in interface List
      Overrides:
      remove in class ArrayList
      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
      Specified by:
      removeAll in interface List
      Overrides:
      removeAll in class ArrayList
      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
      Specified by:
      retainAll in interface List
      Overrides:
      retainAll in class ArrayList
      Parameters:
      collection - Collection containing elements to be retained
      Throws:
      UnsupportedOperationException - if this optional operation is not supported by this list

    • set

      public Object set(int index, Object 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
      Overrides:
      set in class ArrayList
      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
      Specified by:
      size in interface List
      Overrides:
      size in class ArrayList

    • subList

      public List 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
      Overrides:
      subList in class ArrayList
      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
      Specified by:
      toArray in interface List
      Overrides:
      toArray in class ArrayList

    • toArray

      public Object[] toArray(Object[] 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
      Specified by:
      toArray in interface List
      Overrides:
      toArray in class ArrayList
      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

    • 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