diff options
Diffstat (limited to 'libjava/java/util/AbstractList.java')
| -rw-r--r-- | libjava/java/util/AbstractList.java | 809 |
1 files changed, 595 insertions, 214 deletions
diff --git a/libjava/java/util/AbstractList.java b/libjava/java/util/AbstractList.java index ba589e3..714f92a 100644 --- a/libjava/java/util/AbstractList.java +++ b/libjava/java/util/AbstractList.java @@ -1,5 +1,5 @@ /* AbstractList.java -- Abstract implementation of most of List - Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,67 +25,192 @@ This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ -// TO DO: -// ~ Doc comments for almost everything. -// ~ Better general commenting - package java.util; /** * A basic implementation of most of the methods in the List interface to make - * it easier to create a List based on a random-access data structure. To - * create an unmodifiable list, it is only necessary to override the size() and - * get(int) methods (this contrasts with all other abstract collection classes - * which require an iterator to be provided). To make the list modifiable, the - * set(int, Object) method should also be overridden, and to make the list - * resizable, the add(int, Object) and remove(int) methods should be overridden - * too. Other methods should be overridden if the backing data structure allows - * for a more efficient implementation. The precise implementation used by - * AbstractList is documented, so that subclasses can tell which methods could - * be implemented more efficiently. + * it easier to create a List based on a random-access data structure. If + * the list is sequential (such as a linked list), use AbstractSequentialList. + * To create an unmodifiable list, it is only necessary to override the + * size() and get(int) methods (this contrasts with all other abstract + * collection classes which require an iterator to be provided). To make the + * list modifiable, the set(int, Object) method should also be overridden, and + * to make the list resizable, the add(int, Object) and remove(int) methods + * should be overridden too. Other methods should be overridden if the + * backing data structure allows for a more efficient implementation. + * The precise implementation used by AbstractList is documented, so that + * subclasses can tell which methods could be implemented more efficiently. + * <p> + * + * As recommended by Collection and List, the subclass should provide at + * least a no-argument and a Collection constructor. This class is not + * synchronized. + * + * @author Original author unknown + * @author Bryce McKinlay + * @author Eric Blake <ebb9@email.byu.edu> + * @see Collection + * @see List + * @see AbstractSequentialList + * @see AbstractCollection + * @see ListIterator + * @since 1.2 + * @status updated to 1.4 */ public abstract class AbstractList extends AbstractCollection implements List { /** * A count of the number of structural modifications that have been made to - * the list (that is, insertions and removals). + * the list (that is, insertions and removals). Structural modifications + * are ones which change the list size or affect how iterations would + * behave. This field is available for use by Iterator and ListIterator, + * in order to throw a {@link ConcurrentModificationException} in response + * to the next operation on the iterator. This <i>fail-fast</i> behavior + * saves the user from many subtle bugs otherwise possible from concurrent + * modification during iteration. + * <p> + * + * To make lists fail-fast, increment this field by just 1 in the + * <code>add(int, Object)</code> and <code>remove(int)</code> methods. + * Otherwise, this field may be ignored. + */ + protected int modCount; + + /** + * The main constructor, for use by subclasses. */ - protected transient int modCount = 0; + protected AbstractList() + { + } + /** + * Returns the elements at the specified position in the list. + * + * @param index the element to return + * @return the element at that position + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + */ public abstract Object get(int index); + /** + * Insert an element into the list at a given position (optional operation). + * This shifts all existing elements from that position to the end one + * index to the right. This version of add has no return, since it is + * assumed to always succeed if there is no exception. This implementation + * always throws UnsupportedOperationException, and must be overridden to + * make a modifiable List. If you want fail-fast iterators, be sure to + * increment modCount when overriding this. + * + * @param index the location to insert the item + * @param o the object to insert + * @throws UnsupportedOperationException if this list does not support the + * add operation + * @throws IndexOutOfBoundsException if index < 0 || index > size() + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason + * @see #modCount + */ public void add(int index, Object o) { throw new UnsupportedOperationException(); } + /** + * Add an element to the end of the list (optional operation). If the list + * imposes restraints on what can be inserted, such as no null elements, + * this should be documented. This implementation calls + * <code>add(size(), o);</code>, and will fail if that version does. + * + * @param o the object to add + * @return true, as defined by Collection for a modified list + * @throws UnsupportedOperationException if this list does not support the + * add operation + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason + * @see #add(int, Object) + */ public boolean add(Object o) { add(size(), o); return true; } + /** + * Insert the contents of a collection into the list at a given position + * (optional operation). Shift all elements at that position to the right + * by the number of elements inserted. This operation is undefined if + * this list is modified during the operation (for example, if you try + * to insert a list into itself). This implementation uses the iterator of + * the collection, repeatedly calling add(int, Object); this will fail + * if add does. This can often be made more efficient. + * + * @param index the location to insert the collection + * @param c the collection to insert + * @return true if the list was modified by this action, that is, if c is + * non-empty + * @throws UnsupportedOperationException if this list does not support the + * addAll operation + * @throws IndexOutOfBoundsException if index < 0 || index > size() + * @throws ClassCastException if some element of c cannot be added to this + * list due to its type + * @throws IllegalArgumentException if some element of c cannot be added + * to this list for some other reason + * @throws NullPointerException if the specified collection is null + * @see #add(int, Object) + */ public boolean addAll(int index, Collection c) { Iterator itr = c.iterator(); int size = c.size(); - for (int pos = 0; pos < size; pos++) - { - add(index++, itr.next()); - } - return (size > 0); + for (int pos = size; pos > 0; pos--) + add(index++, itr.next()); + return size > 0; } + /** + * Clear the list, such that a subsequent call to isEmpty() would return + * true (optional operation). This implementation calls + * <code>removeRange(0, size())</code>, so it will fail unless remove + * or removeRange is overridden. + * + * @throws UnsupportedOperationException if this list does not support the + * clear operation + * @see #remove(int) + * @see #removeRange(int, int) + */ public void clear() { removeRange(0, size()); } + /** + * Test whether this list is equal to another object. A List is defined to be + * equal to an object if and only if that object is also a List, and the two + * lists have the same sequence. Two lists l1 and l2 are equal if and only + * if <code>l1.size() == l2.size()</code>, and for every integer n between 0 + * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ? + * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>. + * <p> + * + * This implementation returns true if the object is this, or false if the + * object is not a List. Otherwise, it iterates over both lists (with + * iterator()), returning false if two elements compare false or one list + * is shorter, and true if the iteration completes successfully. + * + * @param o the object to test for equality with this list + * @return true if o is equal to this list + * @see Object#equals(Object) + * @see #hashCode() + */ public boolean equals(Object o) { if (o == this) return true; - if (!(o instanceof List)) + if (! (o instanceof List)) return false; int size = size(); if (size != ((List) o).size()) @@ -94,77 +219,272 @@ public abstract class AbstractList extends AbstractCollection implements List Iterator itr1 = iterator(); Iterator itr2 = ((List) o).iterator(); - for (int pos = 0; pos < size; pos++) - { - Object e = itr1.next(); - if (e == null ? itr2.next() != null : !e.equals(itr2.next())) - return false; - } + while (--size >= 0) + if (! equals(itr1.next(), itr2.next())) + return false; return true; } + /** + * Obtain a hash code for this list. In order to obey the general contract of + * the hashCode method of class Object, this value is calculated as follows: + * <pre> + * hashCode = 1; + * Iterator i = list.iterator(); + * while (i.hasNext()) + * { + * Object obj = i.next(); + * hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode()); + * } + * </pre> + * This ensures that the general contract of Object.hashCode() is adhered to. + * + * @return the hash code of this list + * @see Object#hashCode() + * @see #equals(Object) + */ public int hashCode() { int hashCode = 1; Iterator itr = iterator(); - int size = size(); - for (int pos = 0; pos < size; pos++) - { - Object obj = itr.next(); - hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode()); - } + int pos = size(); + while (--pos >= 0) + hashCode = 31 * hashCode + hashCode(itr.next()); return hashCode; } + /** + * Obtain the first index at which a given object is to be found in this + * list. This implementation follows a listIterator() until a match is found, + * or returns -1 if the list end is reached. + * + * @param o the object to search for + * @return the least integer n such that <code>o == null ? get(n) == null : + * o.equals(get(n))</code>, or -1 if there is no such index + */ public int indexOf(Object o) { - ListIterator itr = listIterator(0); + ListIterator itr = listIterator(); int size = size(); for (int pos = 0; pos < size; pos++) - { - if (o == null ? itr.next() == null : o.equals(itr.next())) - return pos; - } + if (equals(o, itr.next())) + return pos; return -1; } + /** + * Obtain an Iterator over this list, whose sequence is the list order. + * This implementation uses size(), get(int), and remove(int) of the + * backing list, and does not support remove unless the list does. This + * implementation is fail-fast if you correctly maintain modCount. + * Also, this implementation is specified by Sun to be distinct from + * listIterator, although you could easily implement it as + * <code>return listIterator(0)</code>. + * + * @return an Iterator over the elements of this list, in order + * @see #modCount + */ public Iterator iterator() { - return new AbstractListItr(0); + // Bah, Sun's implementation forbids using listIterator(0). + return new Iterator() + { + private int pos = 0; + private int size = size(); + private int last = -1; + private int knownMod = modCount; + + // This will get inlined, since it is private. + private void checkMod() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + } + + public boolean hasNext() + { + checkMod(); + return pos < size; + } + + public Object next() + { + checkMod(); + if (pos == size) + throw new NoSuchElementException(); + last = pos; + return get(pos++); + } + + public void remove() + { + checkMod(); + if (last < 0) + throw new IllegalStateException(); + AbstractList.this.remove(last); + pos--; + size--; + last = -1; + knownMod = modCount; + } + }; } + /** + * Obtain the last index at which a given object is to be found in this + * list. This implementation grabs listIterator(size()), then searches + * backwards for a match or returns -1. + * + * @return the greatest integer n such that <code>o == null ? get(n) == null + * : o.equals(get(n))</code>, or -1 if there is no such index + */ public int lastIndexOf(Object o) { - int size = size(); - ListIterator itr = listIterator(size); - for (int pos = size; pos > 0; pos--) - { - if (o == null ? itr.previous() == null : o.equals(itr.previous())) - return pos - 1; - } + int pos = size(); + ListIterator itr = listIterator(pos); + while (--pos >= 0) + if (equals(o, itr.previous())) + return pos; return -1; } /** - * Return an Iterator over this List. This implementation calls - * listIterator(0). + * Obtain a ListIterator over this list, starting at the beginning. This + * implementation returns listIterator(0). * - * @return an Iterator over this List + * @return a ListIterator over the elements of this list, in order, starting + * at the beginning */ public ListIterator listIterator() { return listIterator(0); } - public ListIterator listIterator(int index) + /** + * Obtain a ListIterator over this list, starting at a given position. + * A first call to next() would return the same as get(index), and a + * first call to previous() would return the same as get(index - 1). + * <p> + * + * This implementation uses size(), get(int), set(int, Object), + * add(int, Object), and remove(int) of the backing list, and does not + * support remove, set, or add unless the list does. This implementation + * is fail-fast if you correctly maintain modCount. + * + * @param index the position, between 0 and size() inclusive, to begin the + * iteration from + * @return a ListIterator over the elements of this list, in order, starting + * at index + * @throws IndexOutOfBoundsException if index < 0 || index > size() + * @see #modCount + */ + public ListIterator listIterator(final int index) { if (index < 0 || index > size()) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + - size()); + throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + + size()); - return new AbstractListItr(index); + return new ListIterator() + { + private int knownMod = modCount; + private int position = index; + private int lastReturned = -1; + private int size = size(); + + // This will get inlined, since it is private. + private void checkMod() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + } + + public boolean hasNext() + { + checkMod(); + return position < size; + } + + public boolean hasPrevious() + { + checkMod(); + return position > 0; + } + + public Object next() + { + checkMod(); + if (position == size) + throw new NoSuchElementException(); + lastReturned = position; + return get(position++); + } + + public Object previous() + { + checkMod(); + if (position == 0) + throw new NoSuchElementException(); + lastReturned = --position; + return get(lastReturned); + } + + public int nextIndex() + { + checkMod(); + return position; + } + + public int previousIndex() + { + checkMod(); + return position - 1; + } + + public void remove() + { + checkMod(); + if (lastReturned < 0) + throw new IllegalStateException(); + AbstractList.this.remove(lastReturned); + size--; + position = lastReturned; + lastReturned = -1; + knownMod = modCount; + } + + public void set(Object o) + { + checkMod(); + if (lastReturned < 0) + throw new IllegalStateException(); + AbstractList.this.set(lastReturned, o); + } + + public void add(Object o) + { + checkMod(); + AbstractList.this.add(position++, o); + size++; + lastReturned = -1; + knownMod = modCount; + } + }; } + /** + * Remove the element at a given position in this list (optional operation). + * Shifts all remaining elements to the left to fill the gap. This + * implementation always throws an UnsupportedOperationException. + * If you want fail-fast iterators, be sure to increment modCount when + * overriding this. + * + * @param index the position within the list of the object to remove + * @return the object that was removed + * @throws UnsupportedOperationException if this list does not support the + * remove operation + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + * @see #modCount + */ public Object remove(int index) { throw new UnsupportedOperationException(); @@ -175,8 +495,10 @@ public abstract class AbstractList extends AbstractCollection implements List * removeRange methods of the class which implements subList, which are * difficult for subclasses to override directly. Therefore, this method * should be overridden instead by the more efficient implementation, if one - * exists. + * exists. Overriding this can reduce quadratic efforts to constant time + * in some cases! * <p> + * * This implementation first checks for illegal or out of range arguments. It * then obtains a ListIterator over the list using listIterator(fromIndex). * It then calls next() and remove() on this iterator repeatedly, toIndex - @@ -190,152 +512,131 @@ public abstract class AbstractList extends AbstractCollection implements List ListIterator itr = listIterator(fromIndex); for (int index = fromIndex; index < toIndex; index++) { - itr.next(); - itr.remove(); + itr.next(); + itr.remove(); } } + /** + * Replace an element of this list with another object (optional operation). + * This implementation always throws an UnsupportedOperationException. + * + * @param index the position within this list of the element to be replaced + * @param o the object to replace it with + * @return the object that was replaced + * @throws UnsupportedOperationException if this list does not support the + * set operation + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason + */ public Object set(int index, Object o) { throw new UnsupportedOperationException(); } + /** + * 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. + * <p> + * + * 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. + * <p> + * + * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>, + * <code>add(int, Object)</code>, <code>remove(int)</code>, + * <code>addAll(int, Collection)</code> and + * <code>removeRange(int, int)</code> methods all delegate to the + * corresponding methods on the backing abstract list, after + * bounds-checking the index and adjusting for the offset. The + * <code>addAll(Collection c)</code> method merely returns addAll(size, c). + * The <code>listIterator(int)</code> 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 <code>iterator()</code> + * method merely returns listIterator(), and the <code>size()</code> method + * merely returns the subclass's size field. + * <p> + * + * 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 the index that the returned list should start from + * (inclusive) + * @param toIndex the index that the returned list should go to (exclusive) + * @return a List backed by a subsection of this list + * @throws IndexOutOfBoundsException if fromIndex < 0 + * || toIndex > size() + * @throws IllegalArgumentException if fromIndex > toIndex + * @see ConcurrentModificationException + * @see RandomAccess + */ public List subList(int fromIndex, int toIndex) { + // This follows the specification of AbstractList, but is inconsistent + // with the one in List. Don't you love Sun's inconsistencies? if (fromIndex > toIndex) throw new IllegalArgumentException(fromIndex + " > " + toIndex); if (fromIndex < 0 || toIndex > size()) throw new IndexOutOfBoundsException(); + if (this instanceof RandomAccess) + return new RandomAccessSubList(this, fromIndex, toIndex); return new SubList(this, fromIndex, toIndex); } - class AbstractListItr implements ListIterator - { - private int knownMod = modCount; - private int position; - private int lastReturned = -1; - private int size = size(); - - AbstractListItr(int start_pos) - { - this.position = start_pos; - } - - private void checkMod() - { - if (knownMod != modCount) - throw new ConcurrentModificationException(); - } - - public boolean hasNext() - { - checkMod(); - return position < size; - } - - public boolean hasPrevious() - { - checkMod(); - return position > 0; - } - - public Object next() - { - checkMod(); - if (position < size) - { - lastReturned = position++; - return get(lastReturned); - } - else - { - throw new NoSuchElementException(); - } - } - - public Object previous() - { - checkMod(); - if (position > 0) - { - lastReturned = --position; - return get(lastReturned); - } - else - { - throw new NoSuchElementException(); - } - } - - public int nextIndex() - { - checkMod(); - return position; - } - - public int previousIndex() - { - checkMod(); - return position - 1; - } - - public void remove() - { - checkMod(); - if (lastReturned < 0) - { - throw new IllegalStateException(); - } - AbstractList.this.remove(lastReturned); - knownMod++; - position = lastReturned; - lastReturned = -1; - } - - public void set(Object o) - { - checkMod(); - if (lastReturned < 0) - throw new IllegalStateException(); - AbstractList.this.set(lastReturned, o); - } - - public void add(Object o) - { - checkMod(); - AbstractList.this.add(position++, o); - lastReturned = -1; - knownMod++; - } - } // AbstractList.Iterator -} - +} // class AbstractList +/** + * This class follows the implementation requirements set forth in + * {@link AbstractList#subList(int, int)}. Some compilers have problems + * with AbstractList.this.modCount if this class is nested in AbstractList, + * even though the JLS defines that to be legal, so we make it a top-level + * class. + * + * @author Original author unknown + * @author Eric Blake <ebb9@email.byu.edu> + */ class SubList extends AbstractList { - private AbstractList backingList; - private int offset; + private final AbstractList backingList; + private final int offset; private int size; - public SubList(AbstractList backing, int fromIndex, int toIndex) + /** + * Construct the sublist. + * + * @param backing the list this comes from + * @param fromIndex the lower bound, inclusive + * @param toIndex the upper bound, exclusive + */ + SubList(AbstractList backing, int fromIndex, int toIndex) { backingList = backing; - modCount = backingList.modCount; + modCount = backing.modCount; offset = fromIndex; size = toIndex - fromIndex; } /** * This method checks the two modCount fields to ensure that there has - * not been a concurrent modification. It throws an exception if there - * has been, and otherwise returns normally. - * Note that since this method is private, it will be inlined. + * not been a concurrent modification, returning if all is okay. * - * @exception ConcurrentModificationException if there has been a - * concurrent modification. + * @throws ConcurrentModificationException if the backing list has been + * modified externally to this sublist */ + // This will get inlined, since it is private. private void checkMod() { if (modCount != backingList.modCount) @@ -345,45 +646,64 @@ class SubList extends AbstractList /** * This method checks that a value is between 0 and size (inclusive). If * it is not, an exception is thrown. - * Note that since this method is private, it will be inlined. * - * @exception IndexOutOfBoundsException if the value is out of range. + * @param index the value to check + * @throws IndexOutOfBoundsException if the value is out of range */ + // This will get inlined, since it is private. private void checkBoundsInclusive(int index) { if (index < 0 || index > size) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + - size); + throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + + size); } /** * This method checks that a value is between 0 (inclusive) and size * (exclusive). If it is not, an exception is thrown. - * Note that since this method is private, it will be inlined. * - * @exception IndexOutOfBoundsException if the value is out of range. + * @param index the value to check + * @throws IndexOutOfBoundsException if the value is out of range */ + // This will get inlined, since it is private. private void checkBoundsExclusive(int index) { if (index < 0 || index >= size) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + - size); + throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + + size); } + /** + * Specified by AbstractList.subList to return the private field size. + * + * @return the sublist size + */ public int size() { checkMod(); return size; } + /** + * Specified by AbstractList.subList to delegate to the backing list. + * + * @param index the location to modify + * @param o the new value + * @return the old value + */ public Object set(int index, Object o) { checkMod(); checkBoundsExclusive(index); - o = backingList.set(index + offset, o); - return o; + return backingList.set(index + offset, o); } + /** + * Specified by AbstractList.subList to delegate to the backing list. + * + * @param index the location to get from + * @return the object at that location + */ public Object get(int index) { checkMod(); @@ -391,62 +711,109 @@ class SubList extends AbstractList return backingList.get(index + offset); } + /** + * Specified by AbstractList.subList to delegate to the backing list. + * + * @param index the index to insert at + * @param o the object to add + */ public void add(int index, Object o) { checkMod(); checkBoundsInclusive(index); backingList.add(index + offset, o); - this.modCount++; size++; + modCount = backingList.modCount; } + /** + * Specified by AbstractList.subList to delegate to the backing list. + * + * @param index the index to remove + * @return the removed object + */ public Object remove(int index) { checkMod(); checkBoundsExclusive(index); Object o = backingList.remove(index + offset); - this.modCount++; size--; + modCount = backingList.modCount; return o; } - public void removeRange(int fromIndex, int toIndex) + /** + * Specified by AbstractList.subList to delegate to the backing list. + * This does no bounds checking, as it assumes it will only be called + * by trusted code like clear() which has already checked the bounds. + * + * @param fromIndex the lower bound, inclusive + * @param toIndex the upper bound, exclusive + */ + protected void removeRange(int fromIndex, int toIndex) { checkMod(); - checkBoundsExclusive(fromIndex); - checkBoundsInclusive(toIndex); - // this call will catch the toIndex < fromIndex condition backingList.removeRange(offset + fromIndex, offset + toIndex); - this.modCount = backingList.modCount; size -= toIndex - fromIndex; + modCount = backingList.modCount; } + /** + * Specified by AbstractList.subList to delegate to the backing list. + * + * @param index the location to insert at + * @param c the collection to insert + * @return true if this list was modified, in other words, c is non-empty + */ public boolean addAll(int index, Collection c) { checkMod(); checkBoundsInclusive(index); int csize = c.size(); boolean result = backingList.addAll(offset + index, c); - this.modCount = backingList.modCount; size += csize; + modCount = backingList.modCount; return result; } + /** + * Specified by AbstractList.subList to return addAll(size, c). + * + * @param c the collection to insert + * @return true if this list was modified, in other words, c is non-empty + */ + public boolean addAll(Collection c) + { + return addAll(size, c); + } + + /** + * Specified by AbstractList.subList to return listIterator(). + * + * @return an iterator over the sublist + */ public Iterator iterator() { - return listIterator(0); + return listIterator(); } + /** + * Specified by AbstractList.subList to return a wrapper around the + * backing list's iterator. + * + * @param index the start location of the iterator + * @return a list iterator over the sublist + */ public ListIterator listIterator(final int index) - { + { checkMod(); checkBoundsInclusive(index); - return new ListIterator() + return new ListIterator() { - ListIterator i = backingList.listIterator(index + offset); - int position = index; + private final ListIterator i = backingList.listIterator(index + offset); + private int position = index; public boolean hasNext() { @@ -462,44 +829,36 @@ class SubList extends AbstractList public Object next() { - if (position < size) - { - Object o = i.next(); - position++; - return o; - } - else + if (position == size) throw new NoSuchElementException(); + position++; + return i.next(); } public Object previous() { - if (position > 0) - { - Object o = i.previous(); - position--; - return o; - } - else + if (position == 0) throw new NoSuchElementException(); + position--; + return i.previous(); } public int nextIndex() { - return offset + i.nextIndex(); + return i.nextIndex() - offset; } public int previousIndex() { - return offset + i.previousIndex(); + return i.previousIndex() - offset; } public void remove() { i.remove(); - modCount++; size--; position = nextIndex(); + modCount = backingList.modCount; } public void set(Object o) @@ -510,14 +869,14 @@ class SubList extends AbstractList public void add(Object o) { i.add(o); - modCount++; size++; position++; + modCount = backingList.modCount; } // Here is the reason why the various modCount fields are mostly // ignored in this wrapper listIterator. - // IF the backing listIterator is failfast, then the following holds: + // If the backing listIterator is failfast, then the following holds: // Using any other method on this list will call a corresponding // method on the backing list *after* the backing listIterator // is created, which will in turn cause a ConcurrentModException @@ -530,9 +889,31 @@ class SubList extends AbstractList // only, but somewhat pointless when the list can be changed under // us. // Either way, no explicit handling of modCount is needed. - // However modCount++ must be executed in add and remove, and size - // must also be updated in these two methods, since they do not go - // through the corresponding methods of the subList. + // However modCount = backingList.modCount must be executed in add + // and remove, and size must also be updated in these two methods, + // since they do not go through the corresponding methods of the subList. }; } -} // SubList +} // class SubList + +/** + * This class is a RandomAccess version of SubList, as required by + * {@link AbstractList#subList(int, int)}. + * + * @author Eric Blake <ebb9@email.byu.edu> + */ +final class RandomAccessSubList extends SubList + implements RandomAccess +{ + /** + * Construct the sublist. + * + * @param backing the list this comes from + * @param fromIndex the lower bound, inclusive + * @param toIndex the upper bound, exclusive + */ + RandomAccessSubList(AbstractList backing, int fromIndex, int toIndex) + { + super(backing, fromIndex, toIndex); + } +} // class RandomAccessSubList |