java.util.concurrent
Class CopyOnWriteArrayList<E>

java.lang.Object
  extended by java.util.concurrent.CopyOnWriteArrayList<E>
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess

public class CopyOnWriteArrayList<E>
extends Object
implements List<E>, RandomAccess, Cloneable, Serializable

A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is as special ArrayList which performs copies of the underlying storage each time a write (remove, add etc..) operation is performed.

The update operation in this class run usually in O(n) or worse, but traversal operations are fast and efficient, especially when running in a multi-thread environment without the need to design complex synchronize mechanisms.

Iterators in this class work on a snapshot of the backing store at the moment the iterator itself was created, hence the iterator will not reflect changes in the underlying storage. Thus, update operation on the Iterators are not supported, but as interferences from other threads are impossible, no ConcurrentModificationException will be ever thrown from within the Iterator.

This class is especially useful when used with event handling, like the following code demonstrates:


 CopyOnWriteArrayList listeners =
   new CopyOnWriteArrayList();

 [...]

 for (final EventListener listener : listeners)
   {
     Runnable dispatcher = new Runnable() {
       public void run()
       {
         listener.preferenceChange(event);
       }
     };

     Executor executor = Executors.newSingleThreadExecutor();
     executor.execute(dispatcher);
   }
 

Since:
1.5
See Also:
Serialized Form

Constructor Summary
CopyOnWriteArrayList()
          Construct a new ArrayList with the default capacity (16).
CopyOnWriteArrayList(Collection<? extends E> c)
          Construct a new ArrayList, and initialize it with the elements in the supplied Collection.
CopyOnWriteArrayList(E[] array)
          Construct a new ArrayList, and initialize it with the elements in the supplied array.
 
Method Summary
 boolean add(E e)
          Appends the supplied element to the end of this list.
 void add(int index, E e)
          Adds the supplied element at the specified index, shifting all elements currently at that index or higher one to the right.
 boolean addAll(Collection<? extends E> c)
          Add each element in the supplied Collection to this List.
 boolean addAll(int index, Collection<? extends E> c)
          Add all elements in the supplied collection, inserting them beginning at the specified index. c can contain objects of any type, as well as null values.
 int addAllAbsent(Collection<? extends E> c)
          Adds all the element from the given collection that are not already in this list.
 boolean addIfAbsent(E val)
          Adds an element if the list does not contains it already.
 void clear()
          Removes all elements from this List
 Object clone()
          Creates a shallow copy of this ArrayList (elements are not cloned).
 boolean contains(Object e)
          Returns true if element is in this ArrayList.
 boolean containsAll(Collection<?> c)
          Tests whether this collection contains all the elements in a given collection.
 boolean equals(Object o)
          Determine whether this Object is semantically equal to another Object.
 E get(int index)
          Retrieves the element at the user-supplied index.
 int hashCode()
          Get a value that represents this Object, as uniquely as possible within the confines of an int.
 int indexOf(E e, int index)
          Return the lowest index greater equal index at which e appears in this List, or -1 if it does not appear.
 int indexOf(Object e)
          Returns the lowest index at which element appears in this List, or -1 if it does not appear.
 boolean isEmpty()
          Checks if the list is empty.
 Iterator<E> iterator()
          Return an Iterator containing the elements of this list.
 int lastIndexOf(E e, int index)
          Returns the highest index lesser equal index at which e appears in this List, or -1 if it does not appear.
 int lastIndexOf(Object e)
          Returns the highest index at which element appears in this List, or -1 if it does not appear.
 ListIterator<E> listIterator()
          Return a ListIterator containing the elements of this list.
 ListIterator<E> listIterator(int index)
          Return a ListIterator over the elements of this list starting at the specified index.
 E remove(int index)
          Removes the element at the user-supplied index.
 boolean remove(Object element)
          Remove the first occurrence, if any, of the given object from this list, returning true if the object was removed, false otherwise.
 boolean removeAll(Collection<?> c)
          Removes all the elements contained in the given collection.
 boolean retainAll(Collection<?> c)
          Removes all the elements that are not in the passed collection.
 E set(int index, E e)
          Sets the element at the specified index.
 int size()
          Returns the number of elements in this list.
 List<E> subList(int fromIndex, int toIndex)
          Obtain a List view of a subsection of this list, from fromIndex (inclusive) to toIndex (exclusive).
 Object[] toArray()
          Returns an Object array containing all of the elements in this ArrayList.
<T> T[]
toArray(T[] a)
          Returns an Array whose component type is the runtime component type of the passed-in Array.
 String toString()
          Convert this Object to a human-readable String.
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

CopyOnWriteArrayList

public CopyOnWriteArrayList()
Construct a new ArrayList with the default capacity (16).


CopyOnWriteArrayList

public CopyOnWriteArrayList(Collection<? extends E> c)
Construct a new ArrayList, and initialize it with the elements in the supplied Collection. The initial capacity is 110% of the Collection's size.

Parameters:
c - the collection whose elements will initialize this list
Throws:
NullPointerException - if c is null

CopyOnWriteArrayList

public CopyOnWriteArrayList(E[] array)
Construct a new ArrayList, and initialize it with the elements in the supplied array.

Parameters:
array - the array used to initialize this list
Throws:
NullPointerException - if array is null
Method Detail

size

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

Specified by:
size in interface Collection<E>
Specified by:
size in interface List<E>
Returns:
the list size

isEmpty

public boolean isEmpty()
Checks if the list is empty.

Specified by:
isEmpty in interface Collection<E>
Specified by:
isEmpty in interface List<E>
Returns:
true if there are no elements

contains

public boolean contains(Object e)
Returns true if element is in this ArrayList.

Specified by:
contains in interface Collection<E>
Specified by:
contains in interface List<E>
Parameters:
e - the element whose inclusion in the List is being tested
Returns:
true if the list contains e

containsAll

public boolean containsAll(Collection<?> c)
Tests whether this collection contains all the elements in a given collection. This implementation iterates over the given collection, testing whether each element is contained in this collection. If any one is not, false is returned. Otherwise true is returned.

Specified by:
containsAll in interface Collection<E>
Specified by:
containsAll in interface List<E>
Parameters:
c - the collection to test against
Returns:
true if this collection contains all the elements in the given collection
Throws:
NullPointerException - if the given collection is null
See Also:
contains(Object)

indexOf

public int indexOf(Object e)
Returns the lowest index at which element appears in this List, or -1 if it does not appear.

Specified by:
indexOf in interface List<E>
Parameters:
e - the element whose inclusion in the List is being tested
Returns:
the index where e was found

indexOf

public int indexOf(E e,
                   int index)
Return the lowest index greater equal index at which e appears in this List, or -1 if it does not appear.

Parameters:
e - the element whose inclusion in the list is being tested
index - the index at which the search begins
Returns:
the index where e was found

lastIndexOf

public int lastIndexOf(Object e)
Returns the highest index at which element appears in this List, or -1 if it does not appear.

Specified by:
lastIndexOf in interface List<E>
Parameters:
e - the element whose inclusion in the List is being tested
Returns:
the index where e was found

lastIndexOf

public int lastIndexOf(E e,
                       int index)
Returns the highest index lesser equal index at which e appears in this List, or -1 if it does not appear.

Parameters:
e - the element whose inclusion in the list is being tested
index - the index at which the search begins
Returns:
the index where e was found

clone

public Object clone()
Creates a shallow copy of this ArrayList (elements are not cloned).

Overrides:
clone in class Object
Returns:
the cloned object
See Also:
Cloneable

toArray

public Object[] toArray()
Returns an Object array containing all of the elements in this ArrayList. The array is independent of this list.

Specified by:
toArray in interface Collection<E>
Specified by:
toArray in interface List<E>
Returns:
an array representation of this list

toArray

public <T> T[] toArray(T[] a)
Returns an Array whose component type is the runtime component type of the passed-in Array. The returned Array is populated with all of the elements in this ArrayList. If the passed-in Array is not large enough to store all of the elements in this List, a new Array will be created and returned; if the passed-in Array is larger than the size of this List, then size() index will be set to null.

Specified by:
toArray in interface Collection<E>
Specified by:
toArray in interface List<E>
Parameters:
a - the passed-in Array
Returns:
an array representation of this list
Throws:
ArrayStoreException - if the runtime type of a does not allow an element in this list
NullPointerException - if a is null

get

public E get(int index)
Retrieves the element at the user-supplied index.

Specified by:
get in interface List<E>
Parameters:
index - the index of the element we are fetching
Returns:
the element at index index in this list
Throws:
IndexOutOfBoundsException - if index < 0 || index >= size()

set

public E set(int index,
             E e)
Sets the element at the specified index. The new element, e, can be an object of any type or null.

Specified by:
set in interface List<E>
Parameters:
index - the index at which the element is being set
e - the element to be set
Returns:
the element previously at the specified index
Throws:
IndexOutOfBoundsException - if index < 0 || index >= 0

add

public boolean add(E e)
Appends the supplied element to the end of this list. The element, e, can be an object of any type or null.

Specified by:
add in interface Collection<E>
Specified by:
add in interface List<E>
Parameters:
e - the element to be appended to this list
Returns:
true, the add will always succeed

add

public void add(int index,
                E e)
Adds the supplied element at the specified index, shifting all elements currently at that index or higher one to the right. The element, e, can be an object of any type or null.

Specified by:
add in interface List<E>
Parameters:
index - the index at which the element is being added
e - the item being added
Throws:
IndexOutOfBoundsException - if index < 0 || index > size()

remove

public E remove(int index)
Removes the element at the user-supplied index.

Specified by:
remove in interface List<E>
Parameters:
index - the index of the element to be removed
Returns:
the removed Object
Throws:
IndexOutOfBoundsException - if index < 0 || index >= size()

remove

public boolean remove(Object element)
Remove the first occurrence, if any, of the given object from this list, returning true if the object was removed, false otherwise.

Specified by:
remove in interface Collection<E>
Specified by:
remove in interface List<E>
Parameters:
element - the object to be removed.
Returns:
true if element was removed, false otherwise. false means also that the underlying storage was unchanged after this operation concluded.

removeAll

public boolean removeAll(Collection<?> c)
Removes all the elements contained in the given collection. This method removes the elements that are contained in both this list and in the given collection.

Specified by:
removeAll in interface Collection<E>
Specified by:
removeAll in interface List<E>
Parameters:
c - the collection containing the elements to be removed from this list.
Returns:
true if at least one element was removed, indicating that the list internal storage changed as a result, false otherwise.
See Also:
List.remove(Object), List.contains(Object)

retainAll

public boolean retainAll(Collection<?> c)
Removes all the elements that are not in the passed collection. If the collection is void, this method has the same effect of clear(). Please, note that this method is extremely slow (unless the argument has size == 0) and has bad performance is both space and time usage.

Specified by:
retainAll in interface Collection<E>
Specified by:
retainAll in interface List<E>
Parameters:
c - the collection containing the elements to be retained by this list.
Returns:
true the list internal storage changed as a result of this operation, false otherwise.
See Also:
List.remove(Object), List.contains(Object)

clear

public void clear()
Removes all elements from this List

Specified by:
clear in interface Collection<E>
Specified by:
clear in interface List<E>

addAll

public boolean addAll(Collection<? extends E> c)
Add each element in the supplied Collection to this List. It is undefined what happens if you modify the list while this is taking place; for example, if the collection contains this list. c can contain objects of any type, as well as null values.

Specified by:
addAll in interface Collection<E>
Specified by:
addAll in interface List<E>
Parameters:
c - a Collection containing elements to be added to this List
Returns:
true if the list was modified, in other words c is not empty
Throws:
NullPointerException - if c is null
See Also:
List.add(Object)

addAll

public boolean addAll(int index,
                      Collection<? extends E> c)
Add all elements in the supplied collection, inserting them beginning at the specified index. c can contain objects of any type, as well as null values.

Specified by:
addAll in interface List<E>
Parameters:
index - the index at which the elements will be inserted
c - the Collection containing the elements to be inserted
Returns:
true if the list was modified by this action, that is, if c is non-empty
Throws:
IndexOutOfBoundsException - if index < 0 || index > 0
NullPointerException - if c is null
See Also:
List.add(int, Object)

addIfAbsent

public boolean addIfAbsent(E val)
Adds an element if the list does not contains it already.

Parameters:
val - the element to add to the list.
Returns:
true if the element was added, false otherwise.

addAllAbsent

public int addAllAbsent(Collection<? extends E> c)
Adds all the element from the given collection that are not already in this list.

Parameters:
c - the Collection containing the elements to be inserted
Returns:
true the list internal storage changed as a result of this operation, false otherwise.

toString

public String toString()
Description copied from class: Object
Convert this Object to a human-readable String. There are no limits placed on how long this String should be or what it should contain. We suggest you make it as intuitive as possible to be able to place it into System.out.println() and such.

It is typical, but not required, to ensure that this method never completes abruptly with a RuntimeException.

This method will be called when performing string concatenation with this object. If the result is null, string concatenation will instead use "null".

The default implementation returns getClass().getName() + "@" + Integer.toHexString(hashCode()).

Overrides:
toString in class Object
Returns:
the String representing this Object, which may be null
See Also:
Object.getClass(), Object.hashCode(), Class.getName(), Integer.toHexString(int)

equals

public boolean equals(Object o)
Description copied from class: Object
Determine whether this Object is semantically equal to another Object.

There are some fairly strict requirements on this method which subclasses must follow:

This is typically overridden to throw a ClassCastException if the argument is not comparable to the class performing the comparison, but that is not a requirement. It is legal for a.equals(b) to be true even though a.getClass() != b.getClass(). Also, it is typical to never cause a NullPointerException.

In general, the Collections API (java.util) use the equals method rather than the == operator to compare objects. However, IdentityHashMap is an exception to this rule, for its own good reasons.

The default implementation returns this == o.

Specified by:
equals in interface Collection<E>
Specified by:
equals in interface List<E>
Overrides:
equals in class Object
Parameters:
o - the Object to compare to
Returns:
whether this Object is semantically equal to another
See Also:
Object.hashCode()

hashCode

public int hashCode()
Description copied from class: Object
Get a value that represents this Object, as uniquely as possible within the confines of an int.

There are some requirements on this method which subclasses must follow:

Notice that since hashCode is used in Hashtable and other hashing classes, a poor implementation will degrade the performance of hashing (so don't blindly implement it as returning a constant!). Also, if calculating the hash is time-consuming, a class may consider caching the results.

The default implementation returns System.identityHashCode(this)

Specified by:
hashCode in interface Collection<E>
Specified by:
hashCode in interface List<E>
Overrides:
hashCode in class Object
Returns:
the hash code for this Object
See Also:
Object.equals(Object), System.identityHashCode(Object)

iterator

public Iterator<E> iterator()
Return an Iterator containing the elements of this list. The Iterator uses a snapshot of the state of the internal storage at the moment this method is called and does not support update operations, so no synchronization is needed to traverse the iterator.

Specified by:
iterator in interface Iterable<E>
Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface List<E>
Returns:
an Iterator containing the elements of this list in sequence.

listIterator

public ListIterator<E> listIterator()
Return a ListIterator containing the elements of this list. The Iterator uses a snapshot of the state of the internal storage at the moment this method is called and does not support update operations, so no synchronization is needed to traverse the iterator.

Specified by:
listIterator in interface List<E>
Returns:
a ListIterator containing the elements of this list in sequence.

listIterator

public ListIterator<E> listIterator(int index)
Return a ListIterator over the elements of this list starting at the specified index. An initial call to next() will thus return the element at index, while an initial call to previous() will return the element at index-1. The Iterator uses a snapshot of the state of the internal storage at the moment this method is called and does not support update operations, so no synchronization is needed to traverse the iterator.

Specified by:
listIterator in interface List<E>
Parameters:
index - the index at which to start iterating.
Returns:
a ListIterator containing the elements of this list in sequence.

subList

public List<E> subList(int fromIndex,
                       int toIndex)
Obtain a List view of a subsection of this list, from fromIndex (inclusive) to toIndex (exclusive). If the two indices are equal, the sublist is empty. The returned list should be modifiable if and only if this list is modifiable. Changes to the returned list should be reflected in this list. If this list is structurally modified in any way other than through the returned list, the result of any subsequent operations on the returned list is undefined.

This implementation returns a subclass of AbstractList. It stores, in private fields, the offset and size of the sublist, and the expected modCount of the backing list. If the backing list implements RandomAccess, the sublist will also.

The subclass's set(int, Object), get(int), add(int, Object), remove(int), addAll(int, Collection) and removeRange(int, int) methods all delegate to the corresponding methods on the backing abstract list, after bounds-checking the index and adjusting for the offset. The addAll(Collection c) method merely returns addAll(size, c). The listIterator(int) method returns a "wrapper object" over a list iterator on the backing list, which is created with the corresponding method on the backing list. The iterator() method merely returns listIterator(), and the size() method merely returns the subclass's size field.

All methods first check to see if the actual modCount of the backing list is equal to its expected value, and throw a ConcurrentModificationException if it is not.

Specified by:
subList in interface List<E>
Parameters:
fromIndex - the index that the returned list should start from (inclusive)
toIndex - the index that the returned list should go to (exclusive)
Returns:
a List backed by a subsection of this list
Throws:
IndexOutOfBoundsException - if fromIndex < 0 || toIndex > size()
IndexOutOfBoundsException - if fromIndex > toIndex
See Also:
ConcurrentModificationException, RandomAccess