ptolemy.backtrack.util.java.util

Class ArrayList

java.lang.Object

ptolemy.backtrack.util.java.util.AbstractCollection

ptolemy.backtrack.util.java.util.AbstractList

ptolemy.backtrack.util.java.util.ArrayList

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.util.RandomAccess, Rollbackable, Collection, List

public class ArrayList
extends AbstractList
implements List, java.util.RandomAccess, java.lang.Cloneable, java.io.Serializable, Rollbackable

An array-backed implementation of the List interface. This implements all optional list operations, and permits null elements, so that it is better than Vector, which it replaces. Random access is roughly constant time, and iteration is roughly linear time, so it is nice and fast, with less overhead than a LinkedList.

Each list has a capacity, and as the array reaches that capacity it is automatically transferred to a larger array. You also have access to ensureCapacity and trimToSize to control the backing array's size, avoiding reallocation or wasted memory.

ArrayList is not synchronized, so if you need multi-threaded access, consider using:
List l = Collections.synchronizedList(new ArrayList(...));

The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a{

Author:

Jon A. Zeppieri, Bryce McKinlay, Eric Blake (ebb9@email.byu.edu)

See Also:

Collection, List, LinkedList, Vector, Collections.synchronizedList(List), AbstractList, Serialized Form

Status

updated to 1.4

Field Summary

Fields inherited from class ptolemy.backtrack.util.java.util.AbstractCollection

$CHECKPOINT, $RECORD$$CHECKPOINT

Constructor Summary

Constructors

Constructor and Description
ArrayList() Construct a new ArrayList with the default capacity (16).
ArrayList(Collection c) Construct a new ArrayList, and initialize it with the elements in the supplied Collection.
ArrayList(int capacity) Construct a new ArrayList with the supplied initial capacity.

Method Summary

Modifier and Type	Method and Description
void	$COMMIT(long timestamp) Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.
void	$RESTORE(long timestamp, boolean trim) Restore a previous state to all the private fields of this rollbackable object.
void	add(int index, java.lang.Object e) Adds the supplied element at the specified index, shifting all elements currently at that index or higher one to the right.
boolean	add(java.lang.Object e) Appends the supplied element to the end of this list.
boolean	addAll(Collection c) Add each element in the supplied Collection to this List.
boolean	addAll(int index, Collection c) Add all elements in the supplied collection, inserting them beginning at the specified index.
void	clear() Removes all elements from this List
java.lang.Object	clone() Creates a shallow copy of this ArrayList (elements are not cloned).
boolean	contains(java.lang.Object e) Returns true iff element is in this ArrayList.
void	ensureCapacity(int minCapacity) Guarantees that this list will have at least enough capacity to hold minCapacity elements.
java.lang.Object	get(int index) Retrieves the element at the user-supplied index.
int	indexOf(java.lang.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.
int	lastIndexOf(java.lang.Object e) Returns the highest index at which element appears in this List, or -1 if it does not appear.
java.lang.Object	remove(int index) Removes the element at the user-supplied index.
protected void	removeRange(int fromIndex, int toIndex) Removes all elements in the half-open interval [fromIndex, toIndex).
java.lang.Object	set(int index, java.lang.Object e) Sets the element at the specified index.
int	size() Returns the number of elements in this list.
java.lang.Object[]	toArray() Returns an Object array containing all of the elements in this ArrayList.
java.lang.Object[]	toArray(java.lang.Object[] a) Returns an Array whose component type is the runtime component type of the passed-in Array.
void	trimToSize() Trims the capacity of this List to be equal to its size; a memory saver.

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractList

equals, getModCount, hashCode, iterator, listIterator, listIterator, setModCount, subList

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractCollection

$GET$CHECKPOINT, $SET$CHECKPOINT, containsAll, remove, removeAll, retainAll, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface ptolemy.backtrack.util.java.util.List

$GET$CHECKPOINT, $SET$CHECKPOINT, containsAll, equals, hashCode, iterator, listIterator, listIterator, remove, removeAll, retainAll, subList

Constructor Detail

ArrayList

public ArrayList(int capacity)

Construct a new ArrayList with the supplied initial capacity.

Parameters:

capacity - initial capacity of this ArrayList

Throws:

java.lang.IllegalArgumentException - if capacity is negative

ArrayList

public ArrayList()

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

ArrayList

public ArrayList(Collection 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:

java.lang.NullPointerException - if c is null

Method Detail

trimToSize

public void trimToSize()

Trims the capacity of this List to be equal to its size; a memory saver.

ensureCapacity

public void ensureCapacity(int minCapacity)

Guarantees that this list will have at least enough capacity to hold minCapacity elements. This implementation will grow the list to max(current * 2, minCapacity) if (minCapacity > current). The JCL says explictly that "this method increases its capacity to minCap", while the JDK 1.3 online docs specify that the list will grow to at least the size specified.

Parameters:

minCapacity - the minimum guaranteed capacity

size

public int size()

Returns the number of elements in this list.

Specified by:

size in interface Collection

Specified by:

size in interface List

Specified by:

size in class AbstractCollection

Returns:

the list size

isEmpty

public boolean isEmpty()

Checks if the list is empty.

Specified by:

isEmpty in interface Collection

Specified by:

isEmpty in interface List

Overrides:

isEmpty in class AbstractCollection

Returns:

true if there are no elements

See Also:

AbstractCollection.size()

contains

public boolean contains(java.lang.Object e)

Returns true iff element is in this ArrayList.

Specified by:

contains in interface Collection

Specified by:

contains in interface List

Overrides:

contains in class AbstractCollection

Parameters:

e - the element whose inclusion in the List is being tested

Returns:

true if the list contains e

indexOf

public int indexOf(java.lang.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

Overrides:

indexOf in class AbstractList

Parameters:

e - the element whose inclusion in the List is being tested

Returns:

the index where e was found

lastIndexOf

public int lastIndexOf(java.lang.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

Overrides:

lastIndexOf in class AbstractList

Parameters:

e - the element whose inclusion in the List is being tested

Returns:

the index where e was found

clone

public java.lang.Object clone()

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

Overrides:

clone in class java.lang.Object

Returns:

the cloned object

toArray

public java.lang.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

Specified by:

toArray in interface List

Overrides:

toArray in class AbstractCollection

Returns:

an array representation of this list

toArray

public java.lang.Object[] toArray(java.lang.Object[] 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

Specified by:

toArray in interface List

Overrides:

toArray in class AbstractCollection

Parameters:

a - the passed-in Array

Returns:

an array representation of this list

Throws:

java.lang.ArrayStoreException - if the runtime type of a does not allow an element in this list

java.lang.NullPointerException - if a is null

get

public java.lang.Object get(int index)

Retrieves the element at the user-supplied index.

Specified by:

get in interface List

Specified by:

get in class AbstractList

Parameters:

index - the index of the element we are fetching

Returns:

the element at that position

Throws:

java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()

set

public java.lang.Object set(int index,
                            java.lang.Object 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

Overrides:

set in class AbstractList

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:

java.lang.IndexOutOfBoundsException - if index < 0 || index >= 0

add

public boolean add(java.lang.Object 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

Specified by:

add in interface List

Overrides:

add in class AbstractList

Parameters:

e - the element to be appended to this list

Returns:

true, the add will always succeed

See Also:

AbstractList.add(int, Object)

add

public void add(int index,
                java.lang.Object 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

Overrides:

add in class AbstractList

Parameters:

index - the index at which the element is being added

e - the item being added

Throws:

java.lang.IndexOutOfBoundsException - if index < 0 || index > size()

See Also:

AbstractList.modCount

remove

public java.lang.Object remove(int index)

Removes the element at the user-supplied index.

Specified by:

remove in interface List

Overrides:

remove in class AbstractList

Parameters:

index - the index of the element to be removed

Returns:

the removed Object

Throws:

java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()

See Also:

AbstractList.modCount

clear

public void clear()

Removes all elements from this List

Specified by:

clear in interface Collection

Specified by:

clear in interface List

Overrides:

clear in class AbstractList

See Also:

AbstractList.remove(int), AbstractList.removeRange(int, int)

addAll

public boolean addAll(Collection 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

Specified by:

addAll in interface List

Overrides:

addAll in class AbstractCollection

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:

java.lang.NullPointerException - if c is null

See Also:

AbstractCollection.add(Object)

addAll

public boolean addAll(int index,
                      Collection 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

Overrides:

addAll in class AbstractList

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:

java.lang.IndexOutOfBoundsException - if index < 0 || index > 0

java.lang.NullPointerException - if c is null

See Also:

AbstractList.add(int, Object)

removeRange

protected void removeRange(int fromIndex,
                           int toIndex)

Removes all elements in the half-open interval [fromIndex, toIndex). Does nothing when toIndex is equal to fromIndex.

Overrides:

removeRange in class AbstractList

Parameters:

fromIndex - the first index which will be removed

toIndex - one greater than the last index which will be removed

Throws:

java.lang.IndexOutOfBoundsException - if fromIndex > toIndex

$COMMIT

public void $COMMIT(long timestamp)

Description copied from interface: Rollbackable

Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.

Specified by:

$COMMIT in interface Rollbackable

Specified by:

$COMMIT in interface Collection

Specified by:

$COMMIT in interface List

Overrides:

$COMMIT in class AbstractList

Parameters:

timestamp - The timestamp.

$RESTORE

public void $RESTORE(long timestamp,
                     boolean trim)

Description copied from interface: Rollbackable

Restore a previous state to all the private fields of this rollbackable object.

Specified by:

$RESTORE in interface Rollbackable

Specified by:

$RESTORE in interface Collection

Specified by:

$RESTORE in interface List

Overrides:

$RESTORE in class AbstractList

Parameters:

timestamp - The timestamp taken at the time when the previous state was recorded.

trim - Whether to delete the records used for the rollback.

See Also:

Checkpoint.rollback(long, boolean)