ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/AbstractList.java

Comparing jsr166/src/main/java/util/AbstractList.java (file contents):
Revision 1.5 by jsr166, Mon Dec 5 02:56:59 2005 UTC vs.
Revision 1.17 by jsr166, Sun May 20 07:54:01 2007 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2006 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
27
28		/**
29	<	* This class provides a skeletal implementation of the <tt>List</tt>
29	>	* This class provides a skeletal implementation of the {@link List}
30		* interface to minimize the effort required to implement this interface
31		* backed by a "random access" data store (such as an array).  For sequential
32	<	* access data (such as a linked list), <tt>AbstractSequentialList</tt> should
33	<	* be used in preference to this class.<p>
32	>	* access data (such as a linked list), {@link AbstractSequentialList} should
33	>	* be used in preference to this class.
34	>	*
35	>	* <p>To implement an unmodifiable list, the programmer needs only to extend
36	>	* this class and provide implementations for the {@link #get(int)} and
37	>	* {@link List#size() size()} methods.
38		*
39	<	* To implement an unmodifiable list, the programmer needs only to extend this
40	<	* class and provide implementations for the <tt>get(int index)</tt> and
41	<	* <tt>size()</tt> methods.<p>
42	<	*
43	<	* To implement a modifiable list, the programmer must additionally override
22	<	* the <tt>set(int index, Object element)</tt> method (which otherwise throws
23	<	* an <tt>UnsupportedOperationException</tt>.  If the list is variable-size
24	<	* the programmer must additionally override the <tt>add(int index, Object
25	<	* element)</tt> and <tt>remove(int index)</tt> methods.<p>
26	<	*
27	<	* The programmer should generally provide a void (no argument) and collection
28	<	* constructor, as per the recommendation in the <tt>Collection</tt> interface
29	<	* specification.<p>
39	>	* <p>To implement a modifiable list, the programmer must additionally
40	>	* override the {@link #set(int, Object) set(int, E)} method (which otherwise
41	>	* throws an {@code UnsupportedOperationException}).  If the list is
42	>	* variable-size the programmer must additionally override the
43	>	* {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods.
44		*
45	<	* Unlike the other abstract collection implementations, the programmer does
45	>	* <p>The programmer should generally provide a void (no argument) and collection
46	>	* constructor, as per the recommendation in the {@link Collection} interface
47	>	* specification.
48	>	*
49	>	* <p>Unlike the other abstract collection implementations, the programmer does
50		* <i>not</i> have to provide an iterator implementation; the iterator and
51		* list iterator are implemented by this class, on top of the "random access"
52	<	* methods: <tt>get(int index)</tt>, <tt>set(int index, E element)</tt>,
53	<	* <tt>add(int index, E element)</tt> and <tt>remove(int index)</tt>.<p>
52	>	* methods:
53	>	* {@link #get(int)},
54	>	* {@link #set(int, Object) set(int, E)},
55	>	* {@link #add(int, Object) add(int, E)} and
56	>	* {@link #remove(int)}.
57		*
58	<	* The documentation for each non-abstract methods in this class describes its
58	>	* <p>The documentation for each non-abstract method in this class describes its
59		* implementation in detail.  Each of these methods may be overridden if the
60	<	* collection being implemented admits a more efficient implementation.<p>
60	>	* collection being implemented admits a more efficient implementation.
61		*
62	<	* This class is a member of the
63	<	* <a href="{@docRoot}/../guide/collections/index.html">
62	>	* <p>This class is a member of the
63	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
64		* Java Collections Framework</a>.
65		*
66		* @author  Josh Bloch
67		* @author  Neal Gafter
68	<	* @version 1.37, 01/18/03
48	<	* @see Collection
49	<	* @see List
50	<	* @see AbstractSequentialList
51	<	* @see AbstractCollection
68	>	* @version %I%, %G%
69		* @since 1.2
70		*/
71
#	Line 71 | Line 88 | public abstract class AbstractList<E> ex
88		* classes should clearly specify in their documentation any restrictions
89		* on what elements may be added.
90		*
91	<	* <p>This implementation calls <tt>add(size(), e)</tt>.
91	>	* <p>This implementation calls {@code add(size(), e)}.
92		*
93		* <p>Note that this implementation throws an
94	<	* <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
95	<	* is overridden.
94	>	* {@code UnsupportedOperationException} unless
95	>	* {@link #add(int, Object) add(int, E)} is overridden.
96		*
97		* @param e element to be appended to this list
98	<	* @return <tt>true</tt> (as specified by {@link Collection#add})
99	<	* @throws UnsupportedOperationException if the <tt>add</tt> operation
98	>	* @return {@code true} (as specified by {@link Collection#add})
99	>	* @throws UnsupportedOperationException if the {@code add} operation
100		*         is not supported by this list
101		* @throws ClassCastException if the class of the specified element
102		*         prevents it from being added to this list
#	Line 104 | Line 121 | public abstract class AbstractList<E> ex
121		* {@inheritDoc}
122		*
123		* <p>This implementation always throws an
124	<	* <tt>UnsupportedOperationException</tt>.
124	>	* {@code UnsupportedOperationException}.
125		*
126		* @throws UnsupportedOperationException {@inheritDoc}
127		* @throws ClassCastException            {@inheritDoc}
#	Line 120 | Line 137 | public abstract class AbstractList<E> ex
137		* {@inheritDoc}
138		*
139		* <p>This implementation always throws an
140	<	* <tt>UnsupportedOperationException</tt>.
140	>	* {@code UnsupportedOperationException}.
141		*
142		* @throws UnsupportedOperationException {@inheritDoc}
143		* @throws ClassCastException            {@inheritDoc}
#	Line 136 | Line 153 | public abstract class AbstractList<E> ex
153		* {@inheritDoc}
154		*
155		* <p>This implementation always throws an
156	<	* <tt>UnsupportedOperationException</tt>.
156	>	* {@code UnsupportedOperationException}.
157		*
158		* @throws UnsupportedOperationException {@inheritDoc}
159		* @throws IndexOutOfBoundsException     {@inheritDoc}
#	Line 152 | Line 169 | public abstract class AbstractList<E> ex
169		* {@inheritDoc}
170		*
171		* <p>This implementation first gets a list iterator (with
172	<	* <tt>listIterator()</tt>).  Then, it iterates over the list until the
172	>	* {@code listIterator()}).  Then, it iterates over the list until the
173		* specified element is found or the end of the list is reached.
174		*
175		* @throws ClassCastException   {@inheritDoc}
#	Line 176 | Line 193 | public abstract class AbstractList<E> ex
193		* {@inheritDoc}
194		*
195		* <p>This implementation first gets a list iterator that points to the end
196	<	* of the list (with <tt>listIterator(size())</tt>).  Then, it iterates
196	>	* of the list (with {@code listIterator(size())}).  Then, it iterates
197		* backwards over the list until the specified element is found, or the
198		* beginning of the list is reached.
199		*
#	Line 204 | Line 221 | public abstract class AbstractList<E> ex
221		* Removes all of the elements from this list (optional operation).
222		* The list will be empty after this call returns.
223		*
224	<	* <p>This implementation calls <tt>removeRange(0, size())</tt>.
224	>	* <p>This implementation calls {@code removeRange(0, size())}.
225		*
226		* <p>Note that this implementation throws an
227	<	* <tt>UnsupportedOperationException</tt> unless <tt>remove(int
228	<	* index)</tt> or <tt>removeRange(int fromIndex, int toIndex)</tt> is
227	>	* {@code UnsupportedOperationException} unless {@code remove(int
228	>	* index)} or {@code removeRange(int fromIndex, int toIndex)} is
229		* overridden.
230		*
231	<	* @throws UnsupportedOperationException if the <tt>clear</tt> operation
231	>	* @throws UnsupportedOperationException if the {@code clear} operation
232		*         is not supported by this list
233		*/
234		public void clear() {
#	Line 221 | Line 238 | public abstract class AbstractList<E> ex
238		/**
239		* {@inheritDoc}
240		*
241	<	* <p>This implementation gets an iterator over the specified collection and
242	<	* iterates over it, inserting the elements obtained from the iterator
243	<	* into this list at the appropriate position, one at a time, using
244	<	* <tt>add(int, Object)</tt>.  Many implementations will override this
245	<	* method for efficiency.
241	>	* <p>This implementation gets an iterator over the specified collection
242	>	* and iterates over it, inserting the elements obtained from the
243	>	* iterator into this list at the appropriate position, one at a time,
244	>	* using {@code add(int, E)}.
245	>	* Many implementations will override this method for efficiency.
246		*
247		* <p>Note that this implementation throws an
248	<	* <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
249	<	* is overridden.
248	>	* {@code UnsupportedOperationException} unless
249	>	* {@link #add(int, Object) add(int, E)} is overridden.
250		*
251		* @throws UnsupportedOperationException {@inheritDoc}
252		* @throws ClassCastException            {@inheritDoc}
#	Line 251 | Line 268 | public abstract class AbstractList<E> ex
268		// Iterators
269
270		/**
271	<	* Returns an iterator over the elements in this list in proper
272	<	* sequence. <p>
271	>	* Returns an iterator over the elements in this list in proper sequence.
272	>	*
273	>	* <p>This implementation returns a straightforward implementation of the
274	>	* iterator interface, relying on the backing list's {@code size()},
275	>	* {@code get(int)}, and {@code remove(int)} methods.
276		*
277	<	* This implementation returns a straightforward implementation of the
278	<	* iterator interface, relying on the backing list's <tt>size()</tt>,
279	<	* <tt>get(int)</tt>, and <tt>remove(int)</tt> methods.<p>
280	<	*
281	<	* Note that the iterator returned by this method will throw an
282	<	* <tt>UnsupportedOperationException</tt> in response to its
283	<	* <tt>remove</tt> method unless the list's <tt>remove(int)</tt> method is
284	<	* overridden.<p>
265	<	*
266	<	* This implementation can be made to throw runtime exceptions in the face
267	<	* of concurrent modification, as described in the specification for the
268	<	* (protected) <tt>modCount</tt> field.
277	>	* <p>Note that the iterator returned by this method will throw an
278	>	* {@code UnsupportedOperationException} in response to its
279	>	* {@code remove} method unless the list's {@code remove(int)} method is
280	>	* overridden.
281	>	*
282	>	* <p>This implementation can be made to throw runtime exceptions in the
283	>	* face of concurrent modification, as described in the specification
284	>	* for the (protected) {@code modCount} field.
285		*
286		* @return an iterator over the elements in this list in proper sequence
287		*
#	Line 278 | Line 294 | public abstract class AbstractList<E> ex
294		/**
295		* {@inheritDoc}
296		*
297	<	* <p>This implementation returns <tt>listIterator(0)</tt>.
297	>	* <p>This implementation returns {@code listIterator(0)}.
298		*
299		* @see #listIterator(int)
300		*/
#	Line 290 | Line 306 | public abstract class AbstractList<E> ex
306		* {@inheritDoc}
307		*
308		* <p>This implementation returns a straightforward implementation of the
309	<	* <tt>ListIterator</tt> interface that extends the implementation of the
310	<	* <tt>Iterator</tt> interface returned by the <tt>iterator()</tt> method.
311	<	* The <tt>ListIterator</tt> implementation relies on the backing list's
312	<	* <tt>get(int)</tt>, <tt>set(int, Object)</tt>, <tt>add(int, Object)</tt>
313	<	* and <tt>remove(int)</tt> methods.
309	>	* {@code ListIterator} interface that extends the implementation of the
310	>	* {@code Iterator} interface returned by the {@code iterator()} method.
311	>	* The {@code ListIterator} implementation relies on the backing list's
312	>	* {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
313	>	* and {@code remove(int)} methods.
314		*
315		* <p>Note that the list iterator returned by this implementation will
316	<	* throw an <tt>UnsupportedOperationException</tt> in response to its
317	<	* <tt>remove</tt>, <tt>set</tt> and <tt>add</tt> methods unless the
318	<	* list's <tt>remove(int)</tt>, <tt>set(int, Object)</tt>, and
319	<	* <tt>add(int, Object)</tt> methods are overridden.
316	>	* throw an {@code UnsupportedOperationException} in response to its
317	>	* {@code remove}, {@code set} and {@code add} methods unless the
318	>	* list's {@code remove(int)}, {@code set(int, E)}, and
319	>	* {@code add(int, E)} methods are overridden.
320		*
321		* <p>This implementation can be made to throw runtime exceptions in the
322		* face of concurrent modification, as described in the specification for
323	<	* the (protected) <tt>modCount</tt> field.
323	>	* the (protected) {@code modCount} field.
324		*
325		* @throws IndexOutOfBoundsException {@inheritDoc}
326		*
#	Line 342 | Line 358 | public abstract class AbstractList<E> ex
358		}
359
360		public E next() {
361	<	try {
362	<	int i = cursor;
363	<	E next = get(i);
364	<	lastRet = i;
365	<	cursor = i + 1;
366	<	return next;
367	<	} catch (IndexOutOfBoundsException ex) {
368	<	throw new NoSuchElementException();
369	<	} finally {
354	<	if (expectedModCount != modCount)
355	<	throw new ConcurrentModificationException();
356	<	}
361	>	checkForComodification();
362	>	try {
363	>	E next = get(cursor);
364	>	lastRet = cursor++;
365	>	return next;
366	>	} catch (IndexOutOfBoundsException e) {
367	>	checkForComodification();
368	>	throw new NoSuchElementException();
369	>	}
370		}
371
372		public void remove() {
373		if (lastRet == -1)
374		throw new IllegalStateException();
375	<	if (expectedModCount != modCount)
376	<	throw new ConcurrentModificationException();
375	>	checkForComodification();
376	>
377		try {
378		AbstractList.this.remove(lastRet);
379		if (lastRet < cursor)
#	Line 371 | Line 384 | public abstract class AbstractList<E> ex
384		throw new ConcurrentModificationException();
385		}
386		}
387	+
388	+	final void checkForComodification() {
389	+	if (modCount != expectedModCount)
390	+	throw new ConcurrentModificationException();
391	+	}
392		}
393	<
393	>
394		private class ListItr extends Itr implements ListIterator<E> {
395		ListItr(int index) {
396		cursor = index;
#	Line 382 | Line 400 | public abstract class AbstractList<E> ex
400		return cursor != 0;
401		}
402
385	–	public int nextIndex() {
386	–	return cursor;
387	–	}
388	–
389	–	public int previousIndex() {
390	–	return cursor - 1;
391	–	}
392	–
403		public E previous() {
404	+	checkForComodification();
405		try {
406		int i = cursor - 1;
407	<	E prev = get(i);
408	<	lastRet = i;
409	<	cursor = i;
410	<	return prev;
411	<	} catch (IndexOutOfBoundsException ex) {
407	>	E previous = get(i);
408	>	lastRet = cursor = i;
409	>	return previous;
410	>	} catch (IndexOutOfBoundsException e) {
411	>	checkForComodification();
412		throw new NoSuchElementException();
402	–	} finally {
403	–	if (expectedModCount != modCount)
404	–	throw new ConcurrentModificationException();
413		}
414		}
415
416	+	public int nextIndex() {
417	+	return cursor;
418	+	}
419	+
420	+	public int previousIndex() {
421	+	return cursor-1;
422	+	}
423	+
424		public void set(E e) {
425		if (lastRet == -1)
426		throw new IllegalStateException();
427	<	if (expectedModCount != modCount)
428	<	throw new ConcurrentModificationException();
427	>	checkForComodification();
428	>
429		try {
430		AbstractList.this.set(lastRet, e);
431		expectedModCount = modCount;
#	Line 419 | Line 435 | public abstract class AbstractList<E> ex
435		}
436
437		public void add(E e) {
438	<	if (expectedModCount != modCount)
439	<	throw new ConcurrentModificationException();
438	>	checkForComodification();
439	>
440		try {
441		int i = cursor;
442		AbstractList.this.add(i, e);
#	Line 437 | Line 453 | public abstract class AbstractList<E> ex
453		* {@inheritDoc}
454		*
455		* <p>This implementation returns a list that subclasses
456	<	* <tt>AbstractList</tt>.  The subclass stores, in private fields, the
456	>	* {@code AbstractList}.  The subclass stores, in private fields, the
457		* offset of the subList within the backing list, the size of the subList
458		* (which can change over its lifetime), and the expected
459	<	* <tt>modCount</tt> value of the backing list.  There are two variants
460	<	* of the subclass, one of which implements <tt>RandomAccess</tt>.
461	<	* If this list implements <tt>RandomAccess</tt> the returned list will
462	<	* be an instance of the subclass that implements <tt>RandomAccess</tt>.
463	<	*
464	<	* <p>The subclass's <tt>set(int, Object)</tt>, <tt>get(int)</tt>,
465	<	* <tt>add(int, Object)</tt>, <tt>remove(int)</tt>, <tt>addAll(int,
466	<	* Collection)</tt> and <tt>removeRange(int, int)</tt> methods all
459	>	* {@code modCount} value of the backing list.  There are two variants
460	>	* of the subclass, one of which implements {@code RandomAccess}.
461	>	* If this list implements {@code RandomAccess} the returned list will
462	>	* be an instance of the subclass that implements {@code RandomAccess}.
463	>	*
464	>	* <p>The subclass's {@code set(int, E)}, {@code get(int)},
465	>	* {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
466	>	* Collection)} and {@code removeRange(int, int)} methods all
467		* delegate to the corresponding methods on the backing abstract list,
468		* after bounds-checking the index and adjusting for the offset.  The
469	<	* <tt>addAll(Collection c)</tt> method merely returns <tt>addAll(size,
470	<	* c)</tt>.
469	>	* {@code addAll(Collection c)} method merely returns {@code addAll(size,
470	>	* c)}.
471		*
472	<	* <p>The <tt>listIterator(int)</tt> method returns a "wrapper object"
472	>	* <p>The {@code listIterator(int)} method returns a "wrapper object"
473		* over a list iterator on the backing list, which is created with the
474	<	* corresponding method on the backing list.  The <tt>iterator</tt> method
475	<	* merely returns <tt>listIterator()</tt>, and the <tt>size</tt> method
476	<	* merely returns the subclass's <tt>size</tt> field.
474	>	* corresponding method on the backing list.  The {@code iterator} method
475	>	* merely returns {@code listIterator()}, and the {@code size} method
476	>	* merely returns the subclass's {@code size} field.
477		*
478	<	* <p>All methods first check to see if the actual <tt>modCount</tt> of
478	>	* <p>All methods first check to see if the actual {@code modCount} of
479		* the backing list is equal to its expected value, and throw a
480	<	* <tt>ConcurrentModificationException</tt> if it is not.
480	>	* {@code ConcurrentModificationException} if it is not.
481		*
482		* @throws IndexOutOfBoundsException endpoint index value out of range
483	<	*         <tt>(fromIndex &lt; 0 || toIndex &gt; size)</tt>
483	>	*         {@code (fromIndex < 0 || toIndex > size)}
484		* @throws IllegalArgumentException if the endpoint indices are out of order
485	<	*         <tt>(fromIndex &gt; toIndex)</tt>
485	>	*         {@code (fromIndex > toIndex)}
486		*/
487		public List<E> subList(int fromIndex, int toIndex) {
488		return (this instanceof RandomAccess ?
489	<	new RandomAccessSubList<E>(this, fromIndex, toIndex) :
490	<	new SubList<E>(this, fromIndex, toIndex));
489	>	new RandomAccessSubList(this, this, fromIndex, fromIndex, toIndex) :
490	>	new SubList(this, this, fromIndex, fromIndex, toIndex));
491		}
492
493		// Comparison and hashing
494
495		/**
496		* Compares the specified object with this list for equality.  Returns
497	<	* <tt>true</tt> if and only if the specified object is also a list, both
497	>	* {@code true} if and only if the specified object is also a list, both
498		* lists have the same size, and all corresponding pairs of elements in
499	<	* the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
500	<	* <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
501	<	* e1.equals(e2))</tt>.)  In other words, two lists are defined to be
502	<	* equal if they contain the same elements in the same order.<p>
503	<	*
504	<	* This implementation first checks if the specified object is this
505	<	* list. If so, it returns <tt>true</tt>; if not, it checks if the
506	<	* specified object is a list. If not, it returns <tt>false</tt>; if so,
499	>	* the two lists are <i>equal</i>.  (Two elements {@code e1} and
500	>	* {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
501	>	* e1.equals(e2))}.)  In other words, two lists are defined to be
502	>	* equal if they contain the same elements in the same order.
503	>	*
504	>	* <p>This implementation first checks if the specified object is this
505	>	* list. If so, it returns {@code true}; if not, it checks if the
506	>	* specified object is a list. If not, it returns {@code false}; if so,
507		* it iterates over both lists, comparing corresponding pairs of elements.
508	<	* If any comparison returns <tt>false</tt>, this method returns
509	<	* <tt>false</tt>.  If either iterator runs out of elements before the
510	<	* other it returns <tt>false</tt> (as the lists are of unequal length);
511	<	* otherwise it returns <tt>true</tt> when the iterations complete.
508	>	* If any comparison returns {@code false}, this method returns
509	>	* {@code false}.  If either iterator runs out of elements before the
510	>	* other it returns {@code false} (as the lists are of unequal length);
511	>	* otherwise it returns {@code true} when the iterations complete.
512		*
513		* @param o the object to be compared for equality with this list
514	<	* @return <tt>true</tt> if the specified object is equal to this list
514	>	* @return {@code true} if the specified object is equal to this list
515		*/
516		public boolean equals(Object o) {
517		if (o == this)
#	Line 515 | Line 531 | public abstract class AbstractList<E> ex
531		}
532
533		/**
534	<	* Returns the hash code value for this list. <p>
534	>	* Returns the hash code value for this list.
535		*
536	<	* This implementation uses exactly the code that is used to define the
536	>	* <p>This implementation uses exactly the code that is used to define the
537		* list hash function in the documentation for the {@link List#hashCode}
538		* method.
539		*
#	Line 535 | Line 551 | public abstract class AbstractList<E> ex
551
552		/**
553		* Removes from this list all of the elements whose index is between
554	<	* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
554	>	* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
555		* Shifts any succeeding elements to the left (reduces their index).
556	<	* This call shortens the ArrayList by <tt>(toIndex - fromIndex)</tt>
557	<	* elements.  (If <tt>toIndex==fromIndex</tt>, this operation has no
558	<	* effect.)<p>
556	>	* This call shortens the ArrayList by {@code (toIndex - fromIndex)}
557	>	* elements.  (If {@code toIndex==fromIndex}, this operation has no
558	>	* effect.)
559		*
560	<	* This method is called by the <tt>clear</tt> operation on this list
560	>	* <p>This method is called by the {@code clear} operation on this list
561		* and its subLists.  Overriding this method to take advantage of
562		* the internals of the list implementation can <i>substantially</i>
563	<	* improve the performance of the <tt>clear</tt> operation on this list
564	<	* and its subLists.<p>
563	>	* improve the performance of the {@code clear} operation on this list
564	>	* and its subLists.
565		*
566	<	* This implementation gets a list iterator positioned before
567	<	* <tt>fromIndex</tt>, and repeatedly calls <tt>ListIterator.next</tt>
568	<	* followed by <tt>ListIterator.remove</tt> until the entire range has
569	<	* been removed.  <b>Note: if <tt>ListIterator.remove</tt> requires linear
566	>	* <p>This implementation gets a list iterator positioned before
567	>	* {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
568	>	* followed by {@code ListIterator.remove} until the entire range has
569	>	* been removed.  <b>Note: if {@code ListIterator.remove} requires linear
570		* time, this implementation requires quadratic time.</b>
571		*
572		* @param fromIndex index of first element to be removed
#	Line 568 | Line 584 | public abstract class AbstractList<E> ex
584		* The number of times this list has been <i>structurally modified</i>.
585		* Structural modifications are those that change the size of the
586		* list, or otherwise perturb it in such a fashion that iterations in
587	<	* progress may yield incorrect results.<p>
587	>	* progress may yield incorrect results.
588		*
589	<	* This field is used by the iterator and list iterator implementation
590	<	* returned by the <tt>iterator</tt> and <tt>listIterator</tt> methods.
589	>	* <p>This field is used by the iterator and list iterator implementation
590	>	* returned by the {@code iterator} and {@code listIterator} methods.
591		* If the value of this field changes unexpectedly, the iterator (or list
592	<	* iterator) will throw a <tt>ConcurrentModificationException</tt> in
593	<	* response to the <tt>next</tt>, <tt>remove</tt>, <tt>previous</tt>,
594	<	* <tt>set</tt> or <tt>add</tt> operations.  This provides
592	>	* iterator) will throw a {@code ConcurrentModificationException} in
593	>	* response to the {@code next}, {@code remove}, {@code previous},
594	>	* {@code set} or {@code add} operations.  This provides
595		* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
596	<	* the face of concurrent modification during iteration.<p>
596	>	* the face of concurrent modification during iteration.
597		*
598	<	* <b>Use of this field by subclasses is optional.</b> If a subclass
598	>	* <p><b>Use of this field by subclasses is optional.</b> If a subclass
599		* wishes to provide fail-fast iterators (and list iterators), then it
600	<	* merely has to increment this field in its <tt>add(int, Object)</tt> and
601	<	* <tt>remove(int)</tt> methods (and any other methods that it overrides
600	>	* merely has to increment this field in its {@code add(int, E)} and
601	>	* {@code remove(int)} methods (and any other methods that it overrides
602		* that result in structural modifications to the list).  A single call to
603	<	* <tt>add(int, Object)</tt> or <tt>remove(int)</tt> must add no more than
603	>	* {@code add(int, E)} or {@code remove(int)} must add no more than
604		* one to this field, or the iterators (and list iterators) will throw
605	<	* bogus <tt>ConcurrentModificationExceptions</tt>.  If an implementation
605	>	* bogus {@code ConcurrentModificationExceptions}.  If an implementation
606		* does not wish to provide fail-fast iterators, this field may be
607		* ignored.
608		*/
609		protected transient int modCount = 0;
610		}
611
612	+	/**
613	+	* Generic sublists. Non-nested to enable construction by other
614	+	* classes in this package.
615	+	*/
616		class SubList<E> extends AbstractList<E> {
617	<	private AbstractList<E> l;
618	<	private int offset;
619	<	private int size;
620	<	private int expectedModCount;
621	<
622	<	SubList(AbstractList<E> list, int fromIndex, int toIndex) {
617	>	/*
618	>	* A SubList has both a "base", the ultimate backing list, as well
619	>	* as a "parent", which is the list or sublist creating this
620	>	* sublist. All methods that may cause structural modifications
621	>	* must propagate through the parent link, with O(k) performance
622	>	* where k is sublist depth. For example in the case of a
623	>	* sub-sub-list, invoking remove(x) will result in a chain of
624	>	* three remove calls. However, all other non-structurally
625	>	* modifying methods can bypass this chain, and relay directly to
626	>	* the base list. In particular, doing so signficantly speeds up
627	>	* the performance of iterators for deeply-nested sublists.
628	>	*/
629	>	final AbstractList<E> base;   // Backing list
630	>	final AbstractList<E> parent; // Parent list
631	>	final int baseOffset;         // index wrt base
632	>	final int parentOffset;       // index wrt parent
633	>	int length;                   // Number of elements in this sublist
634	>
635	>	SubList(AbstractList<E> base,
636	>	AbstractList<E> parent,
637	>	int baseIndex,
638	>	int fromIndex,
639	>	int toIndex) {
640		if (fromIndex < 0)
641		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
642	<	if (toIndex > list.size())
642	>	if (toIndex > parent.size())
643		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
644		if (fromIndex > toIndex)
645		throw new IllegalArgumentException("fromIndex(" + fromIndex +
646		") > toIndex(" + toIndex + ")");
647	<	l = list;
648	<	offset = fromIndex;
649	<	size = toIndex - fromIndex;
650	<	expectedModCount = l.modCount;
647	>	this.base = base;
648	>	this.parent = parent;
649	>	this.baseOffset = baseIndex;
650	>	this.parentOffset = fromIndex;
651	>	this.length = toIndex - fromIndex;
652	>	this.modCount = base.modCount;
653	>	}
654	>
655	>	/**
656	>	* Returns an IndexOutOfBoundsException with nicer message
657	>	*/
658	>	private IndexOutOfBoundsException indexError(int index) {
659	>	return new IndexOutOfBoundsException("Index: " + index +
660	>	", Size: " + length);
661		}
662
663		public E set(int index, E element) {
664	<	rangeCheck(index);
665	<	checkForComodification();
666	<	return l.set(index+offset, element);
664	>	if (index < 0 || index >= length)
665	>	throw indexError(index);
666	>	if (base.modCount != modCount)
667	>	throw new ConcurrentModificationException();
668	>	return base.set(index + baseOffset, element);
669		}
670
671		public E get(int index) {
672	<	rangeCheck(index);
673	<	checkForComodification();
674	<	return l.get(index+offset);
672	>	if (index < 0 || index >= length)
673	>	throw indexError(index);
674	>	if (base.modCount != modCount)
675	>	throw new ConcurrentModificationException();
676	>	return base.get(index + baseOffset);
677		}
678
679		public int size() {
680	<	checkForComodification();
681	<	return size;
680	>	if (base.modCount != modCount)
681	>	throw new ConcurrentModificationException();
682	>	return length;
683		}
684
685		public void add(int index, E element) {
686	<	if (index<0 || index>size)
687	<	throw new IndexOutOfBoundsException();
688	<	checkForComodification();
689	<	l.add(index+offset, element);
690	<	expectedModCount = l.modCount;
691	<	size++;
692	<	modCount++;
686	>	if (index < 0 || index>length)
687	>	throw indexError(index);
688	>	if (base.modCount != modCount)
689	>	throw new ConcurrentModificationException();
690	>	parent.add(index + parentOffset, element);
691	>	length++;
692	>	modCount = base.modCount;
693		}
694
695		public E remove(int index) {
696	<	rangeCheck(index);
697	<	checkForComodification();
698	<	E result = l.remove(index+offset);
699	<	expectedModCount = l.modCount;
700	<	size--;
701	<	modCount++;
696	>	if (index < 0 || index >= length)
697	>	throw indexError(index);
698	>	if (base.modCount != modCount)
699	>	throw new ConcurrentModificationException();
700	>	E result = parent.remove(index + parentOffset);
701	>	length--;
702	>	modCount = base.modCount;
703		return result;
704		}
705
706		protected void removeRange(int fromIndex, int toIndex) {
707	<	checkForComodification();
708	<	l.removeRange(fromIndex+offset, toIndex+offset);
709	<	expectedModCount = l.modCount;
710	<	size -= (toIndex-fromIndex);
711	<	modCount++;
707	>	if (base.modCount != modCount)
708	>	throw new ConcurrentModificationException();
709	>	parent.removeRange(fromIndex + parentOffset, toIndex + parentOffset);
710	>	length -= (toIndex-fromIndex);
711	>	modCount = base.modCount;
712		}
713
714		public boolean addAll(Collection<? extends E> c) {
715	<	return addAll(size, c);
715	>	return addAll(length, c);
716		}
717
718		public boolean addAll(int index, Collection<? extends E> c) {
719	<	if (index<0 || index>size)
720	<	throw new IndexOutOfBoundsException(
668	<	"Index: "+index+", Size: "+size);
719	>	if (index < 0 || index > length)
720	>	throw indexError(index);
721		int cSize = c.size();
722		if (cSize==0)
723		return false;
724
725	<	checkForComodification();
726	<	l.addAll(offset+index, c);
727	<	expectedModCount = l.modCount;
728	<	size += cSize;
729	<	modCount++;
725	>	if (base.modCount != modCount)
726	>	throw new ConcurrentModificationException();
727	>	parent.addAll(parentOffset + index, c);
728	>	length += cSize;
729	>	modCount = base.modCount;
730		return true;
731		}
732
733	+	public List<E> subList(int fromIndex, int toIndex) {
734	+	return new SubList(base, this, fromIndex + baseOffset,
735	+	fromIndex, toIndex);
736	+	}
737	+
738		public Iterator<E> iterator() {
739	<	return listIterator();
739	>	return new SubListIterator(this, 0);
740		}
741
742	<	public ListIterator<E> listIterator(final int index) {
743	<	checkForComodification();
744	<	if (index<0 || index>size)
688	<	throw new IndexOutOfBoundsException(
689	<	"Index: "+index+", Size: "+size);
742	>	public ListIterator<E> listIterator() {
743	>	return new SubListIterator(this, 0);
744	>	}
745
746	<	return new ListIterator<E>() {
747	<	private ListIterator<E> i = l.listIterator(index+offset);
746	>	public ListIterator<E> listIterator(int index) {
747	>	if (index < 0 || index>length)
748	>	throw indexError(index);
749	>	return new SubListIterator(this, index);
750	>	}
751
752	<	public boolean hasNext() {
753	<	return nextIndex() < size;
754	<	}
752	>	/**
753	>	* Generic sublist iterator obeying fastfail semantics via
754	>	* modCount.  The hasNext and next methods locally check for
755	>	* in-range indices before relaying to backing list to get
756	>	* element. If this either encounters an unexpected modCount or
757	>	* fails, the backing list must have been concurrently modified,
758	>	* and is so reported.  The add and remove methods performing
759	>	* structural modifications instead relay them through the
760	>	* sublist.
761	>	*/
762	>	private static final class SubListIterator<E> implements ListIterator<E> {
763	>	final SubList<E> outer;       // Sublist creating this iteraor
764	>	final AbstractList<E> base;   // base list
765	>	final int offset;             // Cursor offset wrt base
766	>	int cursor;                   // Current index
767	>	int fence;                    // Upper bound on cursor
768	>	int lastRet;                  // Index of returned element, or -1
769	>	int expectedModCount;         // Expected modCount of base
770	>
771	>	SubListIterator(SubList<E> list, int index) {
772	>	this.lastRet = -1;
773	>	this.cursor = index;
774	>	this.outer = list;
775	>	this.offset = list.baseOffset;
776	>	this.fence = list.length;
777	>	this.base = list.base;
778	>	this.expectedModCount = base.modCount;
779	>	}
780
781	<	public E next() {
782	<	if (hasNext())
783	<	return i.next();
701	<	else
702	<	throw new NoSuchElementException();
703	<	}
781	>	public boolean hasNext() {
782	>	return cursor < fence;
783	>	}
784
785	<	public boolean hasPrevious() {
786	<	return previousIndex() >= 0;
787	<	}
785	>	public boolean hasPrevious() {
786	>	return cursor > 0;
787	>	}
788
789	<	public E previous() {
790	<	if (hasPrevious())
791	<	return i.previous();
712	<	else
713	<	throw new NoSuchElementException();
714	<	}
789	>	public int nextIndex() {
790	>	return cursor;
791	>	}
792
793	<	public int nextIndex() {
794	<	return i.nextIndex() - offset;
795	<	}
793	>	public int previousIndex() {
794	>	return cursor - 1;
795	>	}
796
797	<	public int previousIndex() {
798	<	return i.previousIndex() - offset;
797	>	public E next() {
798	>	int i = cursor;
799	>	if (cursor >= fence)
800	>	throw new NoSuchElementException();
801	>	if (expectedModCount == base.modCount) {
802	>	try {
803	>	Object next = base.get(i + offset);
804	>	lastRet = i;
805	>	cursor = i + 1;
806	>	return (E)next;
807	>	} catch (IndexOutOfBoundsException fallThrough) {
808	>	}
809		}
810	+	throw new ConcurrentModificationException();
811	+	}
812
813	<	public void remove() {
814	<	i.remove();
815	<	expectedModCount = l.modCount;
816	<	size--;
817	<	modCount++;
813	>	public E previous() {
814	>	int i = cursor - 1;
815	>	if (i < 0)
816	>	throw new NoSuchElementException();
817	>	if (expectedModCount == base.modCount) {
818	>	try {
819	>	Object prev = base.get(i + offset);
820	>	lastRet = i;
821	>	cursor = i;
822	>	return (E)prev;
823	>	} catch (IndexOutOfBoundsException fallThrough) {
824	>	}
825		}
826	+	throw new ConcurrentModificationException();
827	+	}
828
829	<	public void set(E e) {
830	<	i.set(e);
829	>	public void set(E e) {
830	>	if (lastRet < 0)
831	>	throw new IllegalStateException();
832	>	if (expectedModCount != base.modCount)
833	>	throw new ConcurrentModificationException();
834	>	try {
835	>	outer.set(lastRet, e);
836	>	expectedModCount = base.modCount;
837	>	} catch (IndexOutOfBoundsException ex) {
838	>	throw new ConcurrentModificationException();
839		}
840	+	}
841
842	<	public void add(E e) {
843	<	i.add(e);
844	<	expectedModCount = l.modCount;
845	<	size++;
846	<	modCount++;
842	>	public void remove() {
843	>	int i = lastRet;
844	>	if (i < 0)
845	>	throw new IllegalStateException();
846	>	if (expectedModCount != base.modCount)
847	>	throw new ConcurrentModificationException();
848	>	try {
849	>	outer.remove(i);
850	>	if (i < cursor)
851	>	cursor--;
852	>	lastRet = -1;
853	>	fence = outer.length;
854	>	expectedModCount = base.modCount;
855	>	} catch (IndexOutOfBoundsException ex) {
856	>	throw new ConcurrentModificationException();
857		}
858	<	};
742	<	}
743	<
744	<	public List<E> subList(int fromIndex, int toIndex) {
745	<	return new SubList<E>(this, fromIndex, toIndex);
746	<	}
858	>	}
859
860	<	private void rangeCheck(int index) {
861	<	if (index<0 || index>=size)
862	<	throw new IndexOutOfBoundsException("Index: "+index+
863	<	",Size: "+size);
860	>	public void add(E e) {
861	>	if (expectedModCount != base.modCount)
862	>	throw new ConcurrentModificationException();
863	>	try {
864	>	int i = cursor;
865	>	outer.add(i, e);
866	>	cursor = i + 1;
867	>	lastRet = -1;
868	>	fence = outer.length;
869	>	expectedModCount = base.modCount;
870	>	} catch (IndexOutOfBoundsException ex) {
871	>	throw new ConcurrentModificationException();
872	>	}
873	>	}
874		}
875
754	–	private void checkForComodification() {
755	–	if (l.modCount != expectedModCount)
756	–	throw new ConcurrentModificationException();
757	–	}
876		}
877
878		class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
879	<	RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
880	<	super(list, fromIndex, toIndex);
879	>	RandomAccessSubList(AbstractList<E> base,
880	>	AbstractList<E> parent, int baseIndex,
881	>	int fromIndex, int toIndex) {
882	>	super(base, parent, baseIndex, fromIndex, toIndex);
883		}
884
885		public List<E> subList(int fromIndex, int toIndex) {
886	<	return new RandomAccessSubList<E>(this, fromIndex, toIndex);
886	>	return new RandomAccessSubList(base, this, fromIndex + baseOffset,
887	>	fromIndex, toIndex);
888		}
889		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines