jaroslav@557: /* jaroslav@557: * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. jaroslav@557: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. jaroslav@557: * jaroslav@557: * This code is free software; you can redistribute it and/or modify it jaroslav@557: * under the terms of the GNU General Public License version 2 only, as jaroslav@557: * published by the Free Software Foundation. Oracle designates this jaroslav@557: * particular file as subject to the "Classpath" exception as provided jaroslav@557: * by Oracle in the LICENSE file that accompanied this code. jaroslav@557: * jaroslav@557: * This code is distributed in the hope that it will be useful, but WITHOUT jaroslav@557: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or jaroslav@557: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License jaroslav@557: * version 2 for more details (a copy is included in the LICENSE file that jaroslav@557: * accompanied this code). jaroslav@557: * jaroslav@557: * You should have received a copy of the GNU General Public License version jaroslav@557: * 2 along with this work; if not, write to the Free Software Foundation, jaroslav@557: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. jaroslav@557: * jaroslav@557: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA jaroslav@557: * or visit www.oracle.com if you need additional information or have any jaroslav@557: * questions. jaroslav@557: */ jaroslav@557: jaroslav@557: package java.util; jaroslav@557: jaroslav@557: /** jaroslav@557: * This class provides a skeletal implementation of the {@link List} jaroslav@557: * interface to minimize the effort required to implement this interface jaroslav@557: * backed by a "random access" data store (such as an array). For sequential jaroslav@557: * access data (such as a linked list), {@link AbstractSequentialList} should jaroslav@557: * be used in preference to this class. jaroslav@557: * jaroslav@557: *
To implement an unmodifiable list, the programmer needs only to extend jaroslav@557: * this class and provide implementations for the {@link #get(int)} and jaroslav@557: * {@link List#size() size()} methods. jaroslav@557: * jaroslav@557: *
To implement a modifiable list, the programmer must additionally jaroslav@557: * override the {@link #set(int, Object) set(int, E)} method (which otherwise jaroslav@557: * throws an {@code UnsupportedOperationException}). If the list is jaroslav@557: * variable-size the programmer must additionally override the jaroslav@557: * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods. jaroslav@557: * jaroslav@557: *
The programmer should generally provide a void (no argument) and collection jaroslav@557: * constructor, as per the recommendation in the {@link Collection} interface jaroslav@557: * specification. jaroslav@557: * jaroslav@557: *
Unlike the other abstract collection implementations, the programmer does jaroslav@557: * not have to provide an iterator implementation; the iterator and jaroslav@557: * list iterator are implemented by this class, on top of the "random access" jaroslav@557: * methods: jaroslav@557: * {@link #get(int)}, jaroslav@557: * {@link #set(int, Object) set(int, E)}, jaroslav@557: * {@link #add(int, Object) add(int, E)} and jaroslav@557: * {@link #remove(int)}. jaroslav@557: * jaroslav@557: *
The documentation for each non-abstract method in this class describes its jaroslav@557: * implementation in detail. Each of these methods may be overridden if the jaroslav@557: * collection being implemented admits a more efficient implementation. jaroslav@557: * jaroslav@557: *
This class is a member of the
jaroslav@557: *
jaroslav@557: * Java Collections Framework.
jaroslav@557: *
jaroslav@557: * @author Josh Bloch
jaroslav@557: * @author Neal Gafter
jaroslav@557: * @since 1.2
jaroslav@557: */
jaroslav@557:
jaroslav@557: public abstract class AbstractList Lists that support this operation may place limitations on what
jaroslav@557: * elements may be added to this list. In particular, some
jaroslav@557: * lists will refuse to add null elements, and others will impose
jaroslav@557: * restrictions on the type of elements that may be added. List
jaroslav@557: * classes should clearly specify in their documentation any restrictions
jaroslav@557: * on what elements may be added.
jaroslav@557: *
jaroslav@557: * This implementation calls {@code add(size(), e)}.
jaroslav@557: *
jaroslav@557: * Note that this implementation throws an
jaroslav@557: * {@code UnsupportedOperationException} unless
jaroslav@557: * {@link #add(int, Object) add(int, E)} is overridden.
jaroslav@557: *
jaroslav@557: * @param e element to be appended to this list
jaroslav@557: * @return {@code true} (as specified by {@link Collection#add})
jaroslav@557: * @throws UnsupportedOperationException if the {@code add} operation
jaroslav@557: * is not supported by this list
jaroslav@557: * @throws ClassCastException if the class of the specified element
jaroslav@557: * prevents it from being added to this list
jaroslav@557: * @throws NullPointerException if the specified element is null and this
jaroslav@557: * list does not permit null elements
jaroslav@557: * @throws IllegalArgumentException if some property of this element
jaroslav@557: * prevents it from being added to this list
jaroslav@557: */
jaroslav@557: public boolean add(E e) {
jaroslav@557: add(size(), e);
jaroslav@557: return true;
jaroslav@557: }
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * {@inheritDoc}
jaroslav@557: *
jaroslav@557: * @throws IndexOutOfBoundsException {@inheritDoc}
jaroslav@557: */
jaroslav@557: abstract public E get(int index);
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * {@inheritDoc}
jaroslav@557: *
jaroslav@557: * This implementation always throws an
jaroslav@557: * {@code UnsupportedOperationException}.
jaroslav@557: *
jaroslav@557: * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557: * @throws ClassCastException {@inheritDoc}
jaroslav@557: * @throws NullPointerException {@inheritDoc}
jaroslav@557: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@557: * @throws IndexOutOfBoundsException {@inheritDoc}
jaroslav@557: */
jaroslav@557: public E set(int index, E element) {
jaroslav@557: throw new UnsupportedOperationException();
jaroslav@557: }
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * {@inheritDoc}
jaroslav@557: *
jaroslav@557: * This implementation always throws an
jaroslav@557: * {@code UnsupportedOperationException}.
jaroslav@557: *
jaroslav@557: * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557: * @throws ClassCastException {@inheritDoc}
jaroslav@557: * @throws NullPointerException {@inheritDoc}
jaroslav@557: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@557: * @throws IndexOutOfBoundsException {@inheritDoc}
jaroslav@557: */
jaroslav@557: public void add(int index, E element) {
jaroslav@557: throw new UnsupportedOperationException();
jaroslav@557: }
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * {@inheritDoc}
jaroslav@557: *
jaroslav@557: * This implementation always throws an
jaroslav@557: * {@code UnsupportedOperationException}.
jaroslav@557: *
jaroslav@557: * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557: * @throws IndexOutOfBoundsException {@inheritDoc}
jaroslav@557: */
jaroslav@557: public E remove(int index) {
jaroslav@557: throw new UnsupportedOperationException();
jaroslav@557: }
jaroslav@557:
jaroslav@557:
jaroslav@557: // Search Operations
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * {@inheritDoc}
jaroslav@557: *
jaroslav@557: * This implementation first gets a list iterator (with
jaroslav@557: * {@code listIterator()}). Then, it iterates over the list until the
jaroslav@557: * specified element is found or the end of the list is reached.
jaroslav@557: *
jaroslav@557: * @throws ClassCastException {@inheritDoc}
jaroslav@557: * @throws NullPointerException {@inheritDoc}
jaroslav@557: */
jaroslav@557: public int indexOf(Object o) {
jaroslav@557: ListIterator This implementation first gets a list iterator that points to the end
jaroslav@557: * of the list (with {@code listIterator(size())}). Then, it iterates
jaroslav@557: * backwards over the list until the specified element is found, or the
jaroslav@557: * beginning of the list is reached.
jaroslav@557: *
jaroslav@557: * @throws ClassCastException {@inheritDoc}
jaroslav@557: * @throws NullPointerException {@inheritDoc}
jaroslav@557: */
jaroslav@557: public int lastIndexOf(Object o) {
jaroslav@557: ListIterator This implementation calls {@code removeRange(0, size())}.
jaroslav@557: *
jaroslav@557: * Note that this implementation throws an
jaroslav@557: * {@code UnsupportedOperationException} unless {@code remove(int
jaroslav@557: * index)} or {@code removeRange(int fromIndex, int toIndex)} is
jaroslav@557: * overridden.
jaroslav@557: *
jaroslav@557: * @throws UnsupportedOperationException if the {@code clear} operation
jaroslav@557: * is not supported by this list
jaroslav@557: */
jaroslav@557: public void clear() {
jaroslav@557: removeRange(0, size());
jaroslav@557: }
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * {@inheritDoc}
jaroslav@557: *
jaroslav@557: * This implementation gets an iterator over the specified collection
jaroslav@557: * and iterates over it, inserting the elements obtained from the
jaroslav@557: * iterator into this list at the appropriate position, one at a time,
jaroslav@557: * using {@code add(int, E)}.
jaroslav@557: * Many implementations will override this method for efficiency.
jaroslav@557: *
jaroslav@557: * Note that this implementation throws an
jaroslav@557: * {@code UnsupportedOperationException} unless
jaroslav@557: * {@link #add(int, Object) add(int, E)} is overridden.
jaroslav@557: *
jaroslav@557: * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557: * @throws ClassCastException {@inheritDoc}
jaroslav@557: * @throws NullPointerException {@inheritDoc}
jaroslav@557: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@557: * @throws IndexOutOfBoundsException {@inheritDoc}
jaroslav@557: */
jaroslav@557: public boolean addAll(int index, Collection extends E> c) {
jaroslav@557: rangeCheckForAdd(index);
jaroslav@557: boolean modified = false;
jaroslav@557: for (E e : c) {
jaroslav@557: add(index++, e);
jaroslav@557: modified = true;
jaroslav@557: }
jaroslav@557: return modified;
jaroslav@557: }
jaroslav@557:
jaroslav@557:
jaroslav@557: // Iterators
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * Returns an iterator over the elements in this list in proper sequence.
jaroslav@557: *
jaroslav@557: * This implementation returns a straightforward implementation of the
jaroslav@557: * iterator interface, relying on the backing list's {@code size()},
jaroslav@557: * {@code get(int)}, and {@code remove(int)} methods.
jaroslav@557: *
jaroslav@557: * Note that the iterator returned by this method will throw an
jaroslav@557: * {@link UnsupportedOperationException} in response to its
jaroslav@557: * {@code remove} method unless the list's {@code remove(int)} method is
jaroslav@557: * overridden.
jaroslav@557: *
jaroslav@557: * This implementation can be made to throw runtime exceptions in the
jaroslav@557: * face of concurrent modification, as described in the specification
jaroslav@557: * for the (protected) {@link #modCount} field.
jaroslav@557: *
jaroslav@557: * @return an iterator over the elements in this list in proper sequence
jaroslav@557: */
jaroslav@557: public Iterator This implementation returns {@code listIterator(0)}.
jaroslav@557: *
jaroslav@557: * @see #listIterator(int)
jaroslav@557: */
jaroslav@557: public ListIterator This implementation returns a straightforward implementation of the
jaroslav@557: * {@code ListIterator} interface that extends the implementation of the
jaroslav@557: * {@code Iterator} interface returned by the {@code iterator()} method.
jaroslav@557: * The {@code ListIterator} implementation relies on the backing list's
jaroslav@557: * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
jaroslav@557: * and {@code remove(int)} methods.
jaroslav@557: *
jaroslav@557: * Note that the list iterator returned by this implementation will
jaroslav@557: * throw an {@link UnsupportedOperationException} in response to its
jaroslav@557: * {@code remove}, {@code set} and {@code add} methods unless the
jaroslav@557: * list's {@code remove(int)}, {@code set(int, E)}, and
jaroslav@557: * {@code add(int, E)} methods are overridden.
jaroslav@557: *
jaroslav@557: * This implementation can be made to throw runtime exceptions in the
jaroslav@557: * face of concurrent modification, as described in the specification for
jaroslav@557: * the (protected) {@link #modCount} field.
jaroslav@557: *
jaroslav@557: * @throws IndexOutOfBoundsException {@inheritDoc}
jaroslav@557: */
jaroslav@557: public ListIterator This implementation returns a list that subclasses
jaroslav@557: * {@code AbstractList}. The subclass stores, in private fields, the
jaroslav@557: * offset of the subList within the backing list, the size of the subList
jaroslav@557: * (which can change over its lifetime), and the expected
jaroslav@557: * {@code modCount} value of the backing list. There are two variants
jaroslav@557: * of the subclass, one of which implements {@code RandomAccess}.
jaroslav@557: * If this list implements {@code RandomAccess} the returned list will
jaroslav@557: * be an instance of the subclass that implements {@code RandomAccess}.
jaroslav@557: *
jaroslav@557: * The subclass's {@code set(int, E)}, {@code get(int)},
jaroslav@557: * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
jaroslav@557: * Collection)} and {@code removeRange(int, int)} methods all
jaroslav@557: * delegate to the corresponding methods on the backing abstract list,
jaroslav@557: * after bounds-checking the index and adjusting for the offset. The
jaroslav@557: * {@code addAll(Collection c)} method merely returns {@code addAll(size,
jaroslav@557: * c)}.
jaroslav@557: *
jaroslav@557: * The {@code listIterator(int)} method returns a "wrapper object"
jaroslav@557: * over a list iterator on the backing list, which is created with the
jaroslav@557: * corresponding method on the backing list. The {@code iterator} method
jaroslav@557: * merely returns {@code listIterator()}, and the {@code size} method
jaroslav@557: * merely returns the subclass's {@code size} field.
jaroslav@557: *
jaroslav@557: * All methods first check to see if the actual {@code modCount} of
jaroslav@557: * the backing list is equal to its expected value, and throw a
jaroslav@557: * {@code ConcurrentModificationException} if it is not.
jaroslav@557: *
jaroslav@557: * @throws IndexOutOfBoundsException if an endpoint index value is out of range
jaroslav@557: * {@code (fromIndex < 0 || toIndex > size)}
jaroslav@557: * @throws IllegalArgumentException if the endpoint indices are out of order
jaroslav@557: * {@code (fromIndex > toIndex)}
jaroslav@557: */
jaroslav@557: public List
jaroslav@557: *
jaroslav@557: * This implementation first checks if the specified object is this
jaroslav@557: * list. If so, it returns {@code true}; if not, it checks if the
jaroslav@557: * specified object is a list. If not, it returns {@code false}; if so,
jaroslav@557: * it iterates over both lists, comparing corresponding pairs of elements.
jaroslav@557: * If any comparison returns {@code false}, this method returns
jaroslav@557: * {@code false}. If either iterator runs out of elements before the
jaroslav@557: * other it returns {@code false} (as the lists are of unequal length);
jaroslav@557: * otherwise it returns {@code true} when the iterations complete.
jaroslav@557: *
jaroslav@557: * @param o the object to be compared for equality with this list
jaroslav@557: * @return {@code true} if the specified object is equal to this list
jaroslav@557: */
jaroslav@557: public boolean equals(Object o) {
jaroslav@557: if (o == this)
jaroslav@557: return true;
jaroslav@557: if (!(o instanceof List))
jaroslav@557: return false;
jaroslav@557:
jaroslav@557: ListIterator This implementation uses exactly the code that is used to define the
jaroslav@557: * list hash function in the documentation for the {@link List#hashCode}
jaroslav@557: * method.
jaroslav@557: *
jaroslav@557: * @return the hash code value for this list
jaroslav@557: */
jaroslav@557: public int hashCode() {
jaroslav@557: int hashCode = 1;
jaroslav@557: for (E e : this)
jaroslav@557: hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
jaroslav@557: return hashCode;
jaroslav@557: }
jaroslav@557:
jaroslav@557: /**
jaroslav@557: * Removes from this list all of the elements whose index is between
jaroslav@557: * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
jaroslav@557: * Shifts any succeeding elements to the left (reduces their index).
jaroslav@557: * This call shortens the list by {@code (toIndex - fromIndex)} elements.
jaroslav@557: * (If {@code toIndex==fromIndex}, this operation has no effect.)
jaroslav@557: *
jaroslav@557: * This method is called by the {@code clear} operation on this list
jaroslav@557: * and its subLists. Overriding this method to take advantage of
jaroslav@557: * the internals of the list implementation can substantially
jaroslav@557: * improve the performance of the {@code clear} operation on this list
jaroslav@557: * and its subLists.
jaroslav@557: *
jaroslav@557: * This implementation gets a list iterator positioned before
jaroslav@557: * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
jaroslav@557: * followed by {@code ListIterator.remove} until the entire range has
jaroslav@557: * been removed. Note: if {@code ListIterator.remove} requires linear
jaroslav@557: * time, this implementation requires quadratic time.
jaroslav@557: *
jaroslav@557: * @param fromIndex index of first element to be removed
jaroslav@557: * @param toIndex index after last element to be removed
jaroslav@557: */
jaroslav@557: protected void removeRange(int fromIndex, int toIndex) {
jaroslav@557: ListIterator This field is used by the iterator and list iterator implementation
jaroslav@557: * returned by the {@code iterator} and {@code listIterator} methods.
jaroslav@557: * If the value of this field changes unexpectedly, the iterator (or list
jaroslav@557: * iterator) will throw a {@code ConcurrentModificationException} in
jaroslav@557: * response to the {@code next}, {@code remove}, {@code previous},
jaroslav@557: * {@code set} or {@code add} operations. This provides
jaroslav@557: * fail-fast behavior, rather than non-deterministic behavior in
jaroslav@557: * the face of concurrent modification during iteration.
jaroslav@557: *
jaroslav@557: * Use of this field by subclasses is optional. If a subclass
jaroslav@557: * wishes to provide fail-fast iterators (and list iterators), then it
jaroslav@557: * merely has to increment this field in its {@code add(int, E)} and
jaroslav@557: * {@code remove(int)} methods (and any other methods that it overrides
jaroslav@557: * that result in structural modifications to the list). A single call to
jaroslav@557: * {@code add(int, E)} or {@code remove(int)} must add no more than
jaroslav@557: * one to this field, or the iterators (and list iterators) will throw
jaroslav@557: * bogus {@code ConcurrentModificationExceptions}. If an implementation
jaroslav@557: * does not wish to provide fail-fast iterators, this field may be
jaroslav@557: * ignored.
jaroslav@557: */
jaroslav@557: protected transient int modCount = 0;
jaroslav@557:
jaroslav@557: private void rangeCheckForAdd(int index) {
jaroslav@557: if (index < 0 || index > size())
jaroslav@557: throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
jaroslav@557: }
jaroslav@557:
jaroslav@557: private String outOfBoundsMsg(int index) {
jaroslav@557: return "Index: "+index+", Size: "+size();
jaroslav@557: }
jaroslav@557: }
jaroslav@557:
jaroslav@557: class SubList