/* * @(#)AbstractList.java 1.46 04/02/10 * * Copyright 2004 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; /** * This class provides a skeletal implementation of the List * interface to minimize the effort required to implement this interface * backed by a "random access" data store (such as an array). For sequential * access data (such as a linked list), AbstractSequentialList should * be used in preference to this class.
* * To implement an unmodifiable list, the programmer needs only to extend this * class and provide implementations for the get(int index) and * size() methods.
* * To implement a modifiable list, the programmer must additionally override * the set(int index, Object element) method (which otherwise throws * an UnsupportedOperationException. If the list is variable-size * the programmer must additionally override the add(int index, Object * element) and remove(int index) methods.
* * The programmer should generally provide a void (no argument) and collection * constructor, as per the recommendation in the Collection interface * specification.
* * Unlike the other abstract collection implementations, the programmer does * not have to provide an iterator implementation; the iterator and * list iterator are implemented by this class, on top the "random access" * methods: get(int index), set(int index, Object element), * set(int index, Object element), add(int index, Object * element) and remove(int index).
* * The documentation for each non-abstract methods in this class describes its * implementation in detail. Each of these methods may be overridden if the * collection being implemented admits a more efficient implementation.
*
* This class is a member of the
*
* Java Collections Framework.
*
* @author Josh Bloch
* @author Neal Gafter
* @version 1.37, 01/18/03
* @see Collection
* @see List
* @see AbstractSequentialList
* @see AbstractCollection
* @since 1.2
*/
public abstract class AbstractList
*
* This implementation calls add(size(), o).
*
* Note that this implementation throws an
* UnsupportedOperationException unless add(int, Object)
* is overridden.
*
* @param o element to be appended to this list.
*
* @return true (as per the general contract of
* Collection.add).
*
* @throws UnsupportedOperationException if the add method is not
* supported by this Set.
*
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this set.
*
* @throws IllegalArgumentException some aspect of this element prevents
* it from being added to this collection.
*/
public boolean add(E o) {
add(size(), o);
return true;
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of element to return.
*
* @return the element at the specified position in this list.
* @throws IndexOutOfBoundsException if the given index is out of range
* (index < 0 || index >= size()).
*/
abstract public E get(int index);
/**
* Replaces the element at the specified position in this list with the
* specified element (optional operation).
*
* This implementation always throws an
* UnsupportedOperationException.
*
* @param index index of element to replace.
* @param element element to be stored at the specified position.
* @return the element previously at the specified position.
*
* @throws UnsupportedOperationException if the set method is not
* supported by this List.
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this list.
* @throws IllegalArgumentException if some aspect of the specified
* element prevents it from being added to this list.
*
* @throws IndexOutOfBoundsException if the specified index is out of
* range (index < 0 || index >= size()).
*/
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
/**
* Inserts the specified element at the specified position in this list
* (optional operation). Shifts the element currently at that position
* (if any) and any subsequent elements to the right (adds one to their
* indices).
*
* This implementation always throws an UnsupportedOperationException.
*
* @param index index at which the specified element is to be inserted.
* @param element element to be inserted.
*
* @throws UnsupportedOperationException if the add method is not
* supported by this list.
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this list.
* @throws IllegalArgumentException if some aspect of the specified
* element prevents it from being added to this list.
* @throws IndexOutOfBoundsException index is out of range (index <
* 0 || index > size()).
*/
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
/**
* Removes the element at the specified position in this list (optional
* operation). Shifts any subsequent elements to the left (subtracts one
* from their indices). Returns the element that was removed from the
* list.
*
* This implementation always throws an
* UnsupportedOperationException.
*
* @param index the index of the element to remove.
* @return the element previously at the specified position.
*
* @throws UnsupportedOperationException if the remove method is
* not supported by this list.
* @throws IndexOutOfBoundsException if the specified index is out of
* range (index < 0 || index >= size()).
*/
public E remove(int index) {
throw new UnsupportedOperationException();
}
// Search Operations
/**
* Returns the index in this list of the first occurence of the specified
* element, or -1 if the list does not contain this element. More
* formally, returns the lowest index i such that (o==null ?
* get(i)==null : o.equals(get(i))), or -1 if there is no such
* index.
*
* This implementation first gets a list iterator (with
* listIterator()). Then, it iterates over the list until the
* specified element is found or the end of the list is reached.
*
* @param o element to search for.
*
* @return the index in this List of the first occurence of the specified
* element, or -1 if the List does not contain this element.
*/
public int indexOf(Object o) {
ListIterator
*
* This implementation first gets a list iterator that points to the end
* of the list (with listIterator(size())). Then, it iterates backwards
* over the list until the specified element is found, or the beginning of
* the list is reached.
*
* @param o element to search for.
*
* @return the index in this list of the last occurence of the specified
* element, or -1 if the list does not contain this element.
*/
public int lastIndexOf(Object o) {
ListIterator
*
* This implementation calls removeRange(0, size()).
*
* Note that this implementation throws an
* UnsupportedOperationException unless remove(int
* index) or removeRange(int fromIndex, int toIndex) is
* overridden.
*
* @throws UnsupportedOperationException if the clear method is
* not supported by this Collection.
*/
public void clear() {
removeRange(0, size());
}
/**
* Inserts all of the elements in the specified collection into this list
* at the specified position (optional operation). 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. The behavior of this operation is unspecified if the
* specified collection is modified while the operation is in progress.
* (Note that this will occur if the specified collection is this list,
* and it's nonempty.)
*
* This implementation gets an iterator over the specified collection and
* iterates over it, inserting the elements obtained from the iterator
* into this list at the appropriate position, one at a time, using
* add(int, Object). Many implementations will override this
* method for efficiency.
*
* Note that this implementation throws an
* UnsupportedOperationException unless add(int, Object)
* is overridden.
*
* @return true if this list changed as a result of the call.
* @param index index at which to insert the first element from the
* specified collection.
* @param c elements to be inserted into this List.
*
* @throws UnsupportedOperationException if the addAll method is
* not supported by this list.
*
* @throws ClassCastException if the class of an element of the specified
* collection prevents it from being added to this List.
*
* @throws IllegalArgumentException some aspect an element of the
* specified collection prevents it from being added to this
* List.
*
* @throws IndexOutOfBoundsException index out of range (index < 0
* || index > size()).
*
* @throws NullPointerException if the specified collection is null.
*/
public boolean addAll(int index, Collection extends E> c) {
boolean modified = false;
Iterator extends E> e = c.iterator();
while (e.hasNext()) {
add(index++, e.next());
modified = true;
}
return modified;
}
// Iterators
/**
* Returns an iterator over the elements in this list in proper
* sequence.
*
* This implementation returns a straightforward implementation of the
* iterator interface, relying on the backing list's size(),
* get(int), and remove(int) methods.
*
* Note that the iterator returned by this method will throw an
* UnsupportedOperationException in response to its
* remove method unless the list's remove(int) method is
* overridden.
*
* This implementation can be made to throw runtime exceptions in the face
* of concurrent modification, as described in the specification for the
* (protected) modCount field.
*
* @return an iterator over the elements in this list in proper sequence.
*
* @see #modCount
*/
public Iterator
*
* This implementation returns a straightforward implementation of the
* ListIterator interface that extends the implementation of the
* Iterator interface returned by the iterator() method.
* The ListIterator implementation relies on the backing list's
* get(int), set(int, Object), add(int, Object)
* and remove(int) methods.
*
* Note that the list iterator returned by this implementation will throw
* an UnsupportedOperationException in response to its
* remove, set and add methods unless the
* list's remove(int), set(int, Object), and
* add(int, Object) methods are overridden.
*
* This implementation can be made to throw runtime exceptions in the
* face of concurrent modification, as described in the specification for
* the (protected) modCount field.
*
* @param index index of the first element to be returned from the list
* iterator (by a call to the next method).
*
* @return a list iterator of the elements in this list (in proper
* sequence), starting at the specified position in the list.
*
* @throws IndexOutOfBoundsException if the specified index is out of
* range (index < 0 || index > size()).
*
* @see #modCount
*/
public ListIterator
*
* This method eliminates the need for explicit range operations (of the
* sort that commonly exist for arrays). Any operation that expects a
* list can be used as a range operation by operating on a subList view
* instead of a whole list. For example, the following idiom removes a
* range of elements from a list:
*
*
* The semantics of the list returned by this method become undefined if
* the backing list (i.e., this list) is structurally modified in
* any way other than via the returned list. (Structural modifications are
* those that change the size of the list, or otherwise perturb it in such
* a fashion that iterations in progress may yield incorrect results.)
*
* This implementation returns a list that subclasses
* AbstractList. The subclass stores, in private fields, the
* offset of the subList within the backing list, the size of the subList
* (which can change over its lifetime), and the expected
* modCount value of the backing list. There are two variants
* of the subclass, one of which implements RandomAccess.
* If this list implements RandomAccess the returned list will
* be an instance of the subclass that implements RandomAccess.
*
* 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.
*
* @param fromIndex low endpoint (inclusive) of the subList.
* @param toIndex high endpoint (exclusive) of the subList.
* @return a view of the specified range within this list.
* @throws IndexOutOfBoundsException endpoint index value out of range
* (fromIndex < 0 || toIndex > size)
* @throws IllegalArgumentException endpoint indices out of order
* (fromIndex > toIndex) */
public List
*
* This implementation first checks if the specified object is this
* list. If so, it returns true; if not, it checks if the
* specified object is a list. If not, it returns false; if so,
* it iterates over both lists, comparing corresponding pairs of elements.
* If any comparison returns false, this method returns
* false. If either iterator runs out of elements before the
* other it returns false (as the lists are of unequal length);
* otherwise it returns true when the iterations complete.
*
* @param o the object to be compared for equality with this list.
*
* @return true if the specified object is equal to this list.
*/
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator
*
* This implementation uses exactly the code that is used to define the
* list hash function in the documentation for the List.hashCode
* method.
*
* @return the hash code value for this list.
*/
public int hashCode() {
int hashCode = 1;
Iterator
*
* This method is called by the clear operation on this list
* and its subLists. Overriding this method to take advantage of
* the internals of the list implementation can substantially
* improve the performance of the clear operation on this list
* and its subLists.
*
* This implementation gets a list iterator positioned before
* fromIndex, and repeatedly calls ListIterator.next
* followed by ListIterator.remove until the entire range has
* been removed. Note: if ListIterator.remove requires linear
* time, this implementation requires quadratic time.
*
* @param fromIndex index of first element to be removed.
* @param toIndex index after last element to be removed.
*/
protected void removeRange(int fromIndex, int toIndex) {
ListIterator
*
* This field is used by the iterator and list iterator implementation
* returned by the iterator and listIterator methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a ConcurrentModificationException in
* response to the next, remove, previous,
* set or add operations. This provides
* fail-fast behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* Use of this field by subclasses is optional. If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its add(int, Object) and
* remove(int) methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* add(int, Object) or remove(int) must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus ConcurrentModificationExceptions. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;
}
class SubList
* list.subList(from, to).clear();
*
* Similar idioms may be constructed for indexOf and
* lastIndexOf, and all of the algorithms in the
* Collections class can be applied to a subList.