--- jsr166/src/main/java/util/AbstractList.java 2007/01/07 07:38:27 1.16 +++ jsr166/src/main/java/util/AbstractList.java 2009/09/01 22:28:19 1.21 @@ -1,8 +1,26 @@ /* - * %W% %E% + * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * - * Copyright 2007 Sun Microsystems, Inc. All rights reserved. - * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. */ package java.util; @@ -47,7 +65,6 @@ package java.util; * * @author Josh Bloch * @author Neal Gafter - * @version %I%, %G% * @since 1.2 */ @@ -88,8 +105,8 @@ public abstract class AbstractList ex * prevents it from being added to this list */ public boolean add(E e) { - add(size(), e); - return true; + add(size(), e); + return true; } /** @@ -112,7 +129,7 @@ public abstract class AbstractList ex * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { - throw new UnsupportedOperationException(); + throw new UnsupportedOperationException(); } /** @@ -128,7 +145,7 @@ public abstract class AbstractList ex * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { - throw new UnsupportedOperationException(); + throw new UnsupportedOperationException(); } /** @@ -141,7 +158,7 @@ public abstract class AbstractList ex * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { - throw new UnsupportedOperationException(); + throw new UnsupportedOperationException(); } @@ -158,17 +175,17 @@ public abstract class AbstractList ex * @throws NullPointerException {@inheritDoc} */ public int indexOf(Object o) { - ListIterator e = listIterator(); - if (o==null) { - while (e.hasNext()) - if (e.next()==null) - return e.previousIndex(); - } else { - while (e.hasNext()) - if (o.equals(e.next())) - return e.previousIndex(); - } - return -1; + ListIterator e = listIterator(); + if (o==null) { + while (e.hasNext()) + if (e.next()==null) + return e.previousIndex(); + } else { + while (e.hasNext()) + if (o.equals(e.next())) + return e.previousIndex(); + } + return -1; } /** @@ -183,17 +200,17 @@ public abstract class AbstractList ex * @throws NullPointerException {@inheritDoc} */ public int lastIndexOf(Object o) { - ListIterator e = listIterator(size()); - if (o==null) { - while (e.hasPrevious()) - if (e.previous()==null) - return e.nextIndex(); - } else { - while (e.hasPrevious()) - if (o.equals(e.previous())) - return e.nextIndex(); - } - return -1; + ListIterator e = listIterator(size()); + if (o==null) { + while (e.hasPrevious()) + if (e.previous()==null) + return e.nextIndex(); + } else { + while (e.hasPrevious()) + if (o.equals(e.previous())) + return e.nextIndex(); + } + return -1; } @@ -237,13 +254,13 @@ public abstract class AbstractList ex * @throws IndexOutOfBoundsException {@inheritDoc} */ public boolean addAll(int index, Collection c) { - boolean modified = false; - Iterator e = c.iterator(); - while (e.hasNext()) { - add(index++, e.next()); - modified = true; - } - return modified; + rangeCheckForAdd(index); + boolean modified = false; + for (E e : c) { + add(index++, e); + modified = true; + } + return modified; } @@ -257,20 +274,18 @@ public abstract class AbstractList ex * {@code get(int)}, and {@code remove(int)} methods. * *

Note that the iterator returned by this method will throw an - * {@code UnsupportedOperationException} in response to its + * {@link UnsupportedOperationException} in response to its * {@code remove} method unless the list's {@code 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) {@code modCount} field. + * for the (protected) {@link #modCount} field. * * @return an iterator over the elements in this list in proper sequence - * - * @see #modCount */ public Iterator iterator() { - return new Itr(); + return new Itr(); } /** @@ -281,7 +296,7 @@ public abstract class AbstractList ex * @see #listIterator(int) */ public ListIterator listIterator() { - return listIterator(0); + return listIterator(0); } /** @@ -295,92 +310,91 @@ public abstract class AbstractList ex * and {@code remove(int)} methods. * *

Note that the list iterator returned by this implementation will - * throw an {@code UnsupportedOperationException} in response to its + * throw an {@link UnsupportedOperationException} in response to its * {@code remove}, {@code set} and {@code add} methods unless the * list's {@code remove(int)}, {@code set(int, E)}, and * {@code add(int, E)} 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) {@code modCount} field. + * the (protected) {@link #modCount} field. * * @throws IndexOutOfBoundsException {@inheritDoc} - * - * @see #modCount */ public ListIterator listIterator(final int index) { - if (index<0 || index>size()) - throw new IndexOutOfBoundsException("Index: "+index); + rangeCheckForAdd(index); - return new ListItr(index); + return new ListItr(index); } private class Itr implements Iterator { - /** - * Index of element to be returned by subsequent call to next. - */ - int cursor = 0; - - /** - * Index of element returned by most recent call to next or - * previous. Reset to -1 if this element is deleted by a call - * to remove. - */ - int lastRet = -1; - - /** - * The modCount value that the iterator believes that the backing - * List should have. If this expectation is violated, the iterator - * has detected concurrent modification. - */ - int expectedModCount = modCount; + /** + * Index of element to be returned by subsequent call to next. + */ + int cursor = 0; + + /** + * Index of element returned by most recent call to next or + * previous. Reset to -1 if this element is deleted by a call + * to remove. + */ + int lastRet = -1; + + /** + * The modCount value that the iterator believes that the backing + * List should have. If this expectation is violated, the iterator + * has detected concurrent modification. + */ + int expectedModCount = modCount; - public boolean hasNext() { + public boolean hasNext() { return cursor != size(); - } + } - public E next() { + public E next() { checkForComodification(); - try { - E next = get(cursor); - lastRet = cursor++; - return next; - } catch (IndexOutOfBoundsException e) { - checkForComodification(); - throw new NoSuchElementException(); - } - } - - public void remove() { - if (lastRet == -1) - throw new IllegalStateException(); + try { + int i = cursor; + E next = get(i); + lastRet = i; + cursor = i + 1; + return next; + } catch (IndexOutOfBoundsException e) { + checkForComodification(); + throw new NoSuchElementException(); + } + } + + public void remove() { + if (lastRet < 0) + throw new IllegalStateException(); checkForComodification(); - try { - AbstractList.this.remove(lastRet); - if (lastRet < cursor) - cursor--; - lastRet = -1; - expectedModCount = modCount; - } catch (IndexOutOfBoundsException e) { - throw new ConcurrentModificationException(); - } - } - - final void checkForComodification() { - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - } + try { + AbstractList.this.remove(lastRet); + if (lastRet < cursor) + cursor--; + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException e) { + throw new ConcurrentModificationException(); + } + } + + final void checkForComodification() { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + } } private class ListItr extends Itr implements ListIterator { - ListItr(int index) { - cursor = index; - } - - public boolean hasPrevious() { - return cursor != 0; - } + ListItr(int index) { + cursor = index; + } + + public boolean hasPrevious() { + return cursor != 0; + } public E previous() { checkForComodification(); @@ -395,40 +409,40 @@ public abstract class AbstractList ex } } - public int nextIndex() { - return cursor; - } - - public int previousIndex() { - return cursor-1; - } - - public void set(E e) { - if (lastRet == -1) - throw new IllegalStateException(); + public int nextIndex() { + return cursor; + } + + public int previousIndex() { + return cursor-1; + } + + public void set(E e) { + if (lastRet < 0) + throw new IllegalStateException(); checkForComodification(); - try { - AbstractList.this.set(lastRet, e); - expectedModCount = modCount; - } catch (IndexOutOfBoundsException ex) { - throw new ConcurrentModificationException(); - } - } + try { + AbstractList.this.set(lastRet, e); + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } - public void add(E e) { + public void add(E e) { checkForComodification(); - try { + try { int i = cursor; - AbstractList.this.add(i, e); + AbstractList.this.add(i, e); + lastRet = -1; cursor = i + 1; - lastRet = -1; - expectedModCount = modCount; - } catch (IndexOutOfBoundsException ex) { - throw new ConcurrentModificationException(); - } - } + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } } /** @@ -461,15 +475,15 @@ public abstract class AbstractList ex * the backing list is equal to its expected value, and throw a * {@code ConcurrentModificationException} if it is not. * - * @throws IndexOutOfBoundsException endpoint index value out of range + * @throws IndexOutOfBoundsException if an endpoint index value is out of range * {@code (fromIndex < 0 || toIndex > size)} * @throws IllegalArgumentException if the endpoint indices are out of order * {@code (fromIndex > toIndex)} */ public List subList(int fromIndex, int toIndex) { return (this instanceof RandomAccess ? - new RandomAccessSubList(this, this, fromIndex, fromIndex, toIndex) : - new SubList(this, this, fromIndex, fromIndex, toIndex)); + new RandomAccessSubList(this, fromIndex, toIndex) : + new SubList(this, fromIndex, toIndex)); } // Comparison and hashing @@ -481,9 +495,9 @@ public abstract class AbstractList ex * the two lists are equal. (Two elements {@code e1} and * {@code e2} are equal if {@code (e1==null ? e2==null : * e1.equals(e2))}.) In other words, two lists are defined to be - * equal if they contain the same elements in the same order. + * equal if they contain the same elements in the same order.

* - *

This implementation first checks if the specified object is this + * This implementation first checks if the specified object is this * list. If so, it returns {@code true}; if not, it checks if the * specified object is a list. If not, it returns {@code false}; if so, * it iterates over both lists, comparing corresponding pairs of elements. @@ -496,20 +510,20 @@ public abstract class AbstractList ex * @return {@code 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 e1 = listIterator(); - ListIterator e2 = ((List) o).listIterator(); - while(e1.hasNext() && e2.hasNext()) { - E o1 = e1.next(); - Object o2 = e2.next(); - if (!(o1==null ? o2==null : o1.equals(o2))) - return false; - } - return !(e1.hasNext() || e2.hasNext()); + if (o == this) + return true; + if (!(o instanceof List)) + return false; + + ListIterator e1 = listIterator(); + ListIterator e2 = ((List) o).listIterator(); + while(e1.hasNext() && e2.hasNext()) { + E o1 = e1.next(); + Object o2 = e2.next(); + if (!(o1==null ? o2==null : o1.equals(o2))) + return false; + } + return !(e1.hasNext() || e2.hasNext()); } /** @@ -522,22 +536,18 @@ public abstract class AbstractList ex * @return the hash code value for this list */ public int hashCode() { - int hashCode = 1; - Iterator i = iterator(); - while (i.hasNext()) { - E obj = i.next(); - hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); - } - return hashCode; + int hashCode = 1; + for (E e : this) + hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); + return hashCode; } /** * Removes from this list all of the elements whose index is between * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. * Shifts any succeeding elements to the left (reduces their index). - * This call shortens the ArrayList by {@code (toIndex - fromIndex)} - * elements. (If {@code toIndex==fromIndex}, this operation has no - * effect.) + * This call shortens the list by {@code (toIndex - fromIndex)} elements. + * (If {@code toIndex==fromIndex}, this operation has no effect.) * *

This method is called by the {@code clear} operation on this list * and its subLists. Overriding this method to take advantage of @@ -589,283 +599,183 @@ public abstract class AbstractList ex * ignored. */ protected transient int modCount = 0; + + private void rangeCheckForAdd(int index) { + if (index < 0 || index > size()) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); + } + + private String outOfBoundsMsg(int index) { + return "Index: "+index+", Size: "+size(); + } } -/** - * Generic sublists. Non-nested to enable construction by other - * classes in this package. - */ class SubList extends AbstractList { - /* - * A SubList has both a "base", the ultimate backing list, as well - * as a "parent", which is the list or sublist creating this - * sublist. All methods that may cause structural modifications - * must propagate through the parent link, with O(k) performance - * where k is sublist depth. For example in the case of a - * sub-sub-list, invoking remove(x) will result in a chain of - * three remove calls. However, all other non-structurally - * modifying methods can bypass this chain, and relay directly to - * the base list. In particular, doing so signficantly speeds up - * the performance of iterators for deeply-nested sublists. - */ - final AbstractList base; // Backing list - final AbstractList parent; // Parent list - final int baseOffset; // index wrt base - final int parentOffset; // index wrt parent - int length; // Number of elements in this sublist - - SubList(AbstractList base, - AbstractList parent, - int baseIndex, - int fromIndex, - int toIndex) { + private final AbstractList l; + private final int offset; + private int size; + + SubList(AbstractList list, int fromIndex, int toIndex) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); - if (toIndex > parent.size()) + if (toIndex > list.size()) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); - this.base = base; - this.parent = parent; - this.baseOffset = baseIndex; - this.parentOffset = fromIndex; - this.length = toIndex - fromIndex; - this.modCount = base.modCount; - } - - /** - * Returns an IndexOutOfBoundsException with nicer message - */ - private IndexOutOfBoundsException indexError(int index) { - return new IndexOutOfBoundsException("Index: " + index + - ", Size: " + length); + l = list; + offset = fromIndex; + size = toIndex - fromIndex; + this.modCount = l.modCount; } public E set(int index, E element) { - if (index < 0 || index >= length) - throw indexError(index); - if (base.modCount != modCount) - throw new ConcurrentModificationException(); - return base.set(index + baseOffset, element); + rangeCheck(index); + checkForComodification(); + return l.set(index+offset, element); } public E get(int index) { - if (index < 0 || index >= length) - throw indexError(index); - if (base.modCount != modCount) - throw new ConcurrentModificationException(); - return base.get(index + baseOffset); + rangeCheck(index); + checkForComodification(); + return l.get(index+offset); } public int size() { - if (base.modCount != modCount) - throw new ConcurrentModificationException(); - return length; + checkForComodification(); + return size; } public void add(int index, E element) { - if (index < 0 || index>length) - throw indexError(index); - if (base.modCount != modCount) - throw new ConcurrentModificationException(); - parent.add(index + parentOffset, element); - length++; - modCount = base.modCount; + rangeCheckForAdd(index); + checkForComodification(); + l.add(index+offset, element); + this.modCount = l.modCount; + size++; } public E remove(int index) { - if (index < 0 || index >= length) - throw indexError(index); - if (base.modCount != modCount) - throw new ConcurrentModificationException(); - E result = parent.remove(index + parentOffset); - length--; - modCount = base.modCount; + rangeCheck(index); + checkForComodification(); + E result = l.remove(index+offset); + this.modCount = l.modCount; + size--; return result; } protected void removeRange(int fromIndex, int toIndex) { - if (base.modCount != modCount) - throw new ConcurrentModificationException(); - parent.removeRange(fromIndex + parentOffset, toIndex + parentOffset); - length -= (toIndex-fromIndex); - modCount = base.modCount; + checkForComodification(); + l.removeRange(fromIndex+offset, toIndex+offset); + this.modCount = l.modCount; + size -= (toIndex-fromIndex); } public boolean addAll(Collection c) { - return addAll(length, c); + return addAll(size, c); } public boolean addAll(int index, Collection c) { - if (index < 0 || index > length) - throw indexError(index); + rangeCheckForAdd(index); int cSize = c.size(); if (cSize==0) return false; - if (base.modCount != modCount) - throw new ConcurrentModificationException(); - parent.addAll(parentOffset + index, c); - length += cSize; - modCount = base.modCount; + checkForComodification(); + l.addAll(offset+index, c); + this.modCount = l.modCount; + size += cSize; return true; } - public List subList(int fromIndex, int toIndex) { - return new SubList(base, this, fromIndex + baseOffset, - fromIndex, toIndex); - } - public Iterator iterator() { - return new SubListIterator(this, 0); + return listIterator(); } - public ListIterator listIterator() { - return new SubListIterator(this, 0); - } + public ListIterator listIterator(final int index) { + checkForComodification(); + rangeCheckForAdd(index); - public ListIterator listIterator(int index) { - if (index < 0 || index>length) - throw indexError(index); - return new SubListIterator(this, index); - } + return new ListIterator() { + private final ListIterator i = l.listIterator(index+offset); - /** - * Generic sublist iterator obeying fastfail semantics via - * modCount. The hasNext and next methods locally check for - * in-range indices before relaying to backing list to get - * element. If this either encounters an unexpected modCount or - * fails, the backing list must have been concurrently modified, - * and is so reported. The add and remove methods performing - * structural modifications instead relay them through the - * sublist. - */ - private static final class SubListIterator implements ListIterator { - final SubList outer; // Sublist creating this iteraor - final AbstractList base; // base list - final int offset; // Cursor offset wrt base - int cursor; // Current index - int fence; // Upper bound on cursor - int lastRet; // Index of returned element, or -1 - int expectedModCount; // Expected modCount of base - - SubListIterator(SubList list, int index) { - this.lastRet = -1; - this.cursor = index; - this.outer = list; - this.offset = list.baseOffset; - this.fence = list.length; - this.base = list.base; - this.expectedModCount = base.modCount; - } - - public boolean hasNext() { - return cursor < fence; - } + public boolean hasNext() { + return nextIndex() < size; + } - public boolean hasPrevious() { - return cursor > 0; - } + public E next() { + if (hasNext()) + return i.next(); + else + throw new NoSuchElementException(); + } - public int nextIndex() { - return cursor; - } + public boolean hasPrevious() { + return previousIndex() >= 0; + } - public int previousIndex() { - return cursor - 1; - } + public E previous() { + if (hasPrevious()) + return i.previous(); + else + throw new NoSuchElementException(); + } - public E next() { - int i = cursor; - if (cursor >= fence) - throw new NoSuchElementException(); - if (expectedModCount == base.modCount) { - try { - Object next = base.get(i + offset); - lastRet = i; - cursor = i + 1; - return (E)next; - } catch (IndexOutOfBoundsException fallThrough) { - } + public int nextIndex() { + return i.nextIndex() - offset; } - throw new ConcurrentModificationException(); - } - public E previous() { - int i = cursor - 1; - if (i < 0) - throw new NoSuchElementException(); - if (expectedModCount == base.modCount) { - try { - Object prev = base.get(i + offset); - lastRet = i; - cursor = i; - return (E)prev; - } catch (IndexOutOfBoundsException fallThrough) { - } + public int previousIndex() { + return i.previousIndex() - offset; } - throw new ConcurrentModificationException(); - } - public void set(E e) { - if (lastRet < 0) - throw new IllegalStateException(); - if (expectedModCount != base.modCount) - throw new ConcurrentModificationException(); - try { - outer.set(lastRet, e); - expectedModCount = base.modCount; - } catch (IndexOutOfBoundsException ex) { - throw new ConcurrentModificationException(); + public void remove() { + i.remove(); + SubList.this.modCount = l.modCount; + size--; } - } - public void remove() { - int i = lastRet; - if (i < 0) - throw new IllegalStateException(); - if (expectedModCount != base.modCount) - throw new ConcurrentModificationException(); - try { - outer.remove(i); - if (i < cursor) - cursor--; - lastRet = -1; - fence = outer.length; - expectedModCount = base.modCount; - } catch (IndexOutOfBoundsException ex) { - throw new ConcurrentModificationException(); + public void set(E e) { + i.set(e); } - } - public void add(E e) { - if (expectedModCount != base.modCount) - throw new ConcurrentModificationException(); - try { - int i = cursor; - outer.add(i, e); - cursor = i + 1; - lastRet = -1; - fence = outer.length; - expectedModCount = base.modCount; - } catch (IndexOutOfBoundsException ex) { - throw new ConcurrentModificationException(); + public void add(E e) { + i.add(e); + SubList.this.modCount = l.modCount; + size++; } - } + }; + } + + public List subList(int fromIndex, int toIndex) { + return new SubList(this, fromIndex, toIndex); + } + + private void rangeCheck(int index) { + if (index < 0 || index >= size) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); + } + + private void rangeCheckForAdd(int index) { + if (index < 0 || index > size) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } + private String outOfBoundsMsg(int index) { + return "Index: "+index+", Size: "+size; + } + + private void checkForComodification() { + if (this.modCount != l.modCount) + throw new ConcurrentModificationException(); + } } class RandomAccessSubList extends SubList implements RandomAccess { - RandomAccessSubList(AbstractList base, - AbstractList parent, int baseIndex, - int fromIndex, int toIndex) { - super(base, parent, baseIndex, fromIndex, toIndex); + RandomAccessSubList(AbstractList list, int fromIndex, int toIndex) { + super(list, fromIndex, toIndex); } public List subList(int fromIndex, int toIndex) { - return new RandomAccessSubList(base, this, fromIndex + baseOffset, - fromIndex, toIndex); + return new RandomAccessSubList(this, fromIndex, toIndex); } }