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.16 by jsr166, Sun Jan 7 07:38:27 2007 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2007 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
8		package java.util;
9
10		/**
11	<	* This class provides a skeletal implementation of the <tt>List</tt>
11	>	* This class provides a skeletal implementation of the {@link List}
12		* interface to minimize the effort required to implement this interface
13		* backed by a "random access" data store (such as an array).  For sequential
14	<	* access data (such as a linked list), <tt>AbstractSequentialList</tt> should
15	<	* be used in preference to this class.<p>
14	>	* access data (such as a linked list), {@link AbstractSequentialList} should
15	>	* be used in preference to this class.
16		*
17	<	* To implement an unmodifiable list, the programmer needs only to extend this
18	<	* class and provide implementations for the <tt>get(int index)</tt> and
19	<	* <tt>size()</tt> methods.<p>
17	>	* <p>To implement an unmodifiable list, the programmer needs only to extend
18	>	* this class and provide implementations for the {@link #get(int)} and
19	>	* {@link List#size() size()} methods.
20		*
21	<	* 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>
21	>	* <p>To implement a modifiable list, the programmer must additionally
22	>	* override the {@link #set(int, Object) set(int, E)} method (which otherwise
23	>	* throws an {@code UnsupportedOperationException}).  If the list is
24	>	* variable-size the programmer must additionally override the
25	>	* {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods.
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>
27	>	* <p>The programmer should generally provide a void (no argument) and collection
28	>	* constructor, as per the recommendation in the {@link Collection} interface
29	>	* specification.
30		*
31	<	* Unlike the other abstract collection implementations, the programmer does
31	>	* <p>Unlike the other abstract collection implementations, the programmer does
32		* <i>not</i> have to provide an iterator implementation; the iterator and
33		* list iterator are implemented by this class, on top of the "random access"
34	<	* methods: <tt>get(int index)</tt>, <tt>set(int index, E element)</tt>,
35	<	* <tt>add(int index, E element)</tt> and <tt>remove(int index)</tt>.<p>
34	>	* methods:
35	>	* {@link #get(int)},
36	>	* {@link #set(int, Object) set(int, E)},
37	>	* {@link #add(int, Object) add(int, E)} and
38	>	* {@link #remove(int)}.
39		*
40	<	* The documentation for each non-abstract methods in this class describes its
40	>	* <p>The documentation for each non-abstract method in this class describes its
41		* implementation in detail.  Each of these methods may be overridden if the
42	<	* collection being implemented admits a more efficient implementation.<p>
42	>	* collection being implemented admits a more efficient implementation.
43		*
44	<	* This class is a member of the
45	<	* <a href="{@docRoot}/../guide/collections/index.html">
44	>	* <p>This class is a member of the
45	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
46		* Java Collections Framework</a>.
47		*
48		* @author  Josh Bloch
49		* @author  Neal Gafter
50	<	* @version 1.37, 01/18/03
48	<	* @see Collection
49	<	* @see List
50	<	* @see AbstractSequentialList
51	<	* @see AbstractCollection
50	>	* @version %I%, %G%
51		* @since 1.2
52		*/
53
#	Line 71 | Line 70 | public abstract class AbstractList<E> ex
70		* classes should clearly specify in their documentation any restrictions
71		* on what elements may be added.
72		*
73	<	* <p>This implementation calls <tt>add(size(), e)</tt>.
73	>	* <p>This implementation calls {@code add(size(), e)}.
74		*
75		* <p>Note that this implementation throws an
76	<	* <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
77	<	* is overridden.
76	>	* {@code UnsupportedOperationException} unless
77	>	* {@link #add(int, Object) add(int, E)} is overridden.
78		*
79		* @param e element to be appended to this list
80	<	* @return <tt>true</tt> (as specified by {@link Collection#add})
81	<	* @throws UnsupportedOperationException if the <tt>add</tt> operation
80	>	* @return {@code true} (as specified by {@link Collection#add})
81	>	* @throws UnsupportedOperationException if the {@code add} operation
82		*         is not supported by this list
83		* @throws ClassCastException if the class of the specified element
84		*         prevents it from being added to this list
#	Line 104 | Line 103 | public abstract class AbstractList<E> ex
103		* {@inheritDoc}
104		*
105		* <p>This implementation always throws an
106	<	* <tt>UnsupportedOperationException</tt>.
106	>	* {@code UnsupportedOperationException}.
107		*
108		* @throws UnsupportedOperationException {@inheritDoc}
109		* @throws ClassCastException            {@inheritDoc}
#	Line 120 | Line 119 | public abstract class AbstractList<E> ex
119		* {@inheritDoc}
120		*
121		* <p>This implementation always throws an
122	<	* <tt>UnsupportedOperationException</tt>.
122	>	* {@code UnsupportedOperationException}.
123		*
124		* @throws UnsupportedOperationException {@inheritDoc}
125		* @throws ClassCastException            {@inheritDoc}
#	Line 136 | Line 135 | public abstract class AbstractList<E> ex
135		* {@inheritDoc}
136		*
137		* <p>This implementation always throws an
138	<	* <tt>UnsupportedOperationException</tt>.
138	>	* {@code UnsupportedOperationException}.
139		*
140		* @throws UnsupportedOperationException {@inheritDoc}
141		* @throws IndexOutOfBoundsException     {@inheritDoc}
#	Line 152 | Line 151 | public abstract class AbstractList<E> ex
151		* {@inheritDoc}
152		*
153		* <p>This implementation first gets a list iterator (with
154	<	* <tt>listIterator()</tt>).  Then, it iterates over the list until the
154	>	* {@code listIterator()}).  Then, it iterates over the list until the
155		* specified element is found or the end of the list is reached.
156		*
157		* @throws ClassCastException   {@inheritDoc}
#	Line 176 | Line 175 | public abstract class AbstractList<E> ex
175		* {@inheritDoc}
176		*
177		* <p>This implementation first gets a list iterator that points to the end
178	<	* of the list (with <tt>listIterator(size())</tt>).  Then, it iterates
178	>	* of the list (with {@code listIterator(size())}).  Then, it iterates
179		* backwards over the list until the specified element is found, or the
180		* beginning of the list is reached.
181		*
#	Line 204 | Line 203 | public abstract class AbstractList<E> ex
203		* Removes all of the elements from this list (optional operation).
204		* The list will be empty after this call returns.
205		*
206	<	* <p>This implementation calls <tt>removeRange(0, size())</tt>.
206	>	* <p>This implementation calls {@code removeRange(0, size())}.
207		*
208		* <p>Note that this implementation throws an
209	<	* <tt>UnsupportedOperationException</tt> unless <tt>remove(int
210	<	* index)</tt> or <tt>removeRange(int fromIndex, int toIndex)</tt> is
209	>	* {@code UnsupportedOperationException} unless {@code remove(int
210	>	* index)} or {@code removeRange(int fromIndex, int toIndex)} is
211		* overridden.
212		*
213	<	* @throws UnsupportedOperationException if the <tt>clear</tt> operation
213	>	* @throws UnsupportedOperationException if the {@code clear} operation
214		*         is not supported by this list
215		*/
216		public void clear() {
#	Line 221 | Line 220 | public abstract class AbstractList<E> ex
220		/**
221		* {@inheritDoc}
222		*
223	<	* <p>This implementation gets an iterator over the specified collection and
224	<	* iterates over it, inserting the elements obtained from the iterator
225	<	* into this list at the appropriate position, one at a time, using
226	<	* <tt>add(int, Object)</tt>.  Many implementations will override this
227	<	* method for efficiency.
223	>	* <p>This implementation gets an iterator over the specified collection
224	>	* and iterates over it, inserting the elements obtained from the
225	>	* iterator into this list at the appropriate position, one at a time,
226	>	* using {@code add(int, E)}.
227	>	* Many implementations will override this method for efficiency.
228		*
229		* <p>Note that this implementation throws an
230	<	* <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
231	<	* is overridden.
230	>	* {@code UnsupportedOperationException} unless
231	>	* {@link #add(int, Object) add(int, E)} is overridden.
232		*
233		* @throws UnsupportedOperationException {@inheritDoc}
234		* @throws ClassCastException            {@inheritDoc}
#	Line 251 | Line 250 | public abstract class AbstractList<E> ex
250		// Iterators
251
252		/**
253	<	* Returns an iterator over the elements in this list in proper
255	<	* sequence. <p>
253	>	* Returns an iterator over the elements in this list in proper sequence.
254		*
255	<	* This implementation returns a straightforward implementation of the
256	<	* iterator interface, relying on the backing list's <tt>size()</tt>,
257	<	* <tt>get(int)</tt>, and <tt>remove(int)</tt> methods.<p>
258	<	*
259	<	* Note that the iterator returned by this method will throw an
260	<	* <tt>UnsupportedOperationException</tt> in response to its
261	<	* <tt>remove</tt> method unless the list's <tt>remove(int)</tt> method is
262	<	* overridden.<p>
263	<	*
264	<	* This implementation can be made to throw runtime exceptions in the face
265	<	* of concurrent modification, as described in the specification for the
266	<	* (protected) <tt>modCount</tt> field.
255	>	* <p>This implementation returns a straightforward implementation of the
256	>	* iterator interface, relying on the backing list's {@code size()},
257	>	* {@code get(int)}, and {@code remove(int)} methods.
258	>	*
259	>	* <p>Note that the iterator returned by this method will throw an
260	>	* {@code UnsupportedOperationException} in response to its
261	>	* {@code remove} method unless the list's {@code remove(int)} method is
262	>	* overridden.
263	>	*
264	>	* <p>This implementation can be made to throw runtime exceptions in the
265	>	* face of concurrent modification, as described in the specification
266	>	* for the (protected) {@code modCount} field.
267		*
268		* @return an iterator over the elements in this list in proper sequence
269		*
#	Line 278 | Line 276 | public abstract class AbstractList<E> ex
276		/**
277		* {@inheritDoc}
278		*
279	<	* <p>This implementation returns <tt>listIterator(0)</tt>.
279	>	* <p>This implementation returns {@code listIterator(0)}.
280		*
281		* @see #listIterator(int)
282		*/
#	Line 290 | Line 288 | public abstract class AbstractList<E> ex
288		* {@inheritDoc}
289		*
290		* <p>This implementation returns a straightforward implementation of the
291	<	* <tt>ListIterator</tt> interface that extends the implementation of the
292	<	* <tt>Iterator</tt> interface returned by the <tt>iterator()</tt> method.
293	<	* The <tt>ListIterator</tt> implementation relies on the backing list's
294	<	* <tt>get(int)</tt>, <tt>set(int, Object)</tt>, <tt>add(int, Object)</tt>
295	<	* and <tt>remove(int)</tt> methods.
291	>	* {@code ListIterator} interface that extends the implementation of the
292	>	* {@code Iterator} interface returned by the {@code iterator()} method.
293	>	* The {@code ListIterator} implementation relies on the backing list's
294	>	* {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
295	>	* and {@code remove(int)} methods.
296		*
297		* <p>Note that the list iterator returned by this implementation will
298	<	* throw an <tt>UnsupportedOperationException</tt> in response to its
299	<	* <tt>remove</tt>, <tt>set</tt> and <tt>add</tt> methods unless the
300	<	* list's <tt>remove(int)</tt>, <tt>set(int, Object)</tt>, and
301	<	* <tt>add(int, Object)</tt> methods are overridden.
298	>	* throw an {@code UnsupportedOperationException} in response to its
299	>	* {@code remove}, {@code set} and {@code add} methods unless the
300	>	* list's {@code remove(int)}, {@code set(int, E)}, and
301	>	* {@code add(int, E)} methods are overridden.
302		*
303		* <p>This implementation can be made to throw runtime exceptions in the
304		* face of concurrent modification, as described in the specification for
305	<	* the (protected) <tt>modCount</tt> field.
305	>	* the (protected) {@code modCount} field.
306		*
307		* @throws IndexOutOfBoundsException {@inheritDoc}
308		*
#	Line 342 | Line 340 | public abstract class AbstractList<E> ex
340		}
341
342		public E next() {
343	<	try {
344	<	int i = cursor;
345	<	E next = get(i);
346	<	lastRet = i;
347	<	cursor = i + 1;
348	<	return next;
349	<	} catch (IndexOutOfBoundsException ex) {
350	<	throw new NoSuchElementException();
351	<	} finally {
354	<	if (expectedModCount != modCount)
355	<	throw new ConcurrentModificationException();
356	<	}
343	>	checkForComodification();
344	>	try {
345	>	E next = get(cursor);
346	>	lastRet = cursor++;
347	>	return next;
348	>	} catch (IndexOutOfBoundsException e) {
349	>	checkForComodification();
350	>	throw new NoSuchElementException();
351	>	}
352		}
353
354		public void remove() {
355		if (lastRet == -1)
356		throw new IllegalStateException();
357	<	if (expectedModCount != modCount)
358	<	throw new ConcurrentModificationException();
357	>	checkForComodification();
358	>
359		try {
360		AbstractList.this.remove(lastRet);
361		if (lastRet < cursor)
#	Line 371 | Line 366 | public abstract class AbstractList<E> ex
366		throw new ConcurrentModificationException();
367		}
368		}
369	+
370	+	final void checkForComodification() {
371	+	if (modCount != expectedModCount)
372	+	throw new ConcurrentModificationException();
373	+	}
374		}
375	<
375	>
376		private class ListItr extends Itr implements ListIterator<E> {
377		ListItr(int index) {
378		cursor = index;
#	Line 382 | Line 382 | public abstract class AbstractList<E> ex
382		return cursor != 0;
383		}
384
385	–	public int nextIndex() {
386	–	return cursor;
387	–	}
388	–
389	–	public int previousIndex() {
390	–	return cursor - 1;
391	–	}
392	–
385		public E previous() {
386	+	checkForComodification();
387		try {
388		int i = cursor - 1;
389	<	E prev = get(i);
390	<	lastRet = i;
391	<	cursor = i;
392	<	return prev;
393	<	} catch (IndexOutOfBoundsException ex) {
389	>	E previous = get(i);
390	>	lastRet = cursor = i;
391	>	return previous;
392	>	} catch (IndexOutOfBoundsException e) {
393	>	checkForComodification();
394		throw new NoSuchElementException();
402	–	} finally {
403	–	if (expectedModCount != modCount)
404	–	throw new ConcurrentModificationException();
395		}
396		}
397
398	+	public int nextIndex() {
399	+	return cursor;
400	+	}
401	+
402	+	public int previousIndex() {
403	+	return cursor-1;
404	+	}
405	+
406		public void set(E e) {
407		if (lastRet == -1)
408		throw new IllegalStateException();
409	<	if (expectedModCount != modCount)
410	<	throw new ConcurrentModificationException();
409	>	checkForComodification();
410	>
411		try {
412		AbstractList.this.set(lastRet, e);
413		expectedModCount = modCount;
#	Line 419 | Line 417 | public abstract class AbstractList<E> ex
417		}
418
419		public void add(E e) {
420	<	if (expectedModCount != modCount)
421	<	throw new ConcurrentModificationException();
420	>	checkForComodification();
421	>
422		try {
423		int i = cursor;
424		AbstractList.this.add(i, e);
#	Line 437 | Line 435 | public abstract class AbstractList<E> ex
435		* {@inheritDoc}
436		*
437		* <p>This implementation returns a list that subclasses
438	<	* <tt>AbstractList</tt>.  The subclass stores, in private fields, the
438	>	* {@code AbstractList}.  The subclass stores, in private fields, the
439		* offset of the subList within the backing list, the size of the subList
440		* (which can change over its lifetime), and the expected
441	<	* <tt>modCount</tt> value of the backing list.  There are two variants
442	<	* of the subclass, one of which implements <tt>RandomAccess</tt>.
443	<	* If this list implements <tt>RandomAccess</tt> the returned list will
444	<	* be an instance of the subclass that implements <tt>RandomAccess</tt>.
445	<	*
446	<	* <p>The subclass's <tt>set(int, Object)</tt>, <tt>get(int)</tt>,
447	<	* <tt>add(int, Object)</tt>, <tt>remove(int)</tt>, <tt>addAll(int,
448	<	* Collection)</tt> and <tt>removeRange(int, int)</tt> methods all
441	>	* {@code modCount} value of the backing list.  There are two variants
442	>	* of the subclass, one of which implements {@code RandomAccess}.
443	>	* If this list implements {@code RandomAccess} the returned list will
444	>	* be an instance of the subclass that implements {@code RandomAccess}.
445	>	*
446	>	* <p>The subclass's {@code set(int, E)}, {@code get(int)},
447	>	* {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
448	>	* Collection)} and {@code removeRange(int, int)} methods all
449		* delegate to the corresponding methods on the backing abstract list,
450		* after bounds-checking the index and adjusting for the offset.  The
451	<	* <tt>addAll(Collection c)</tt> method merely returns <tt>addAll(size,
452	<	* c)</tt>.
451	>	* {@code addAll(Collection c)} method merely returns {@code addAll(size,
452	>	* c)}.
453		*
454	<	* <p>The <tt>listIterator(int)</tt> method returns a "wrapper object"
454	>	* <p>The {@code listIterator(int)} method returns a "wrapper object"
455		* over a list iterator on the backing list, which is created with the
456	<	* corresponding method on the backing list.  The <tt>iterator</tt> method
457	<	* merely returns <tt>listIterator()</tt>, and the <tt>size</tt> method
458	<	* merely returns the subclass's <tt>size</tt> field.
456	>	* corresponding method on the backing list.  The {@code iterator} method
457	>	* merely returns {@code listIterator()}, and the {@code size} method
458	>	* merely returns the subclass's {@code size} field.
459		*
460	<	* <p>All methods first check to see if the actual <tt>modCount</tt> of
460	>	* <p>All methods first check to see if the actual {@code modCount} of
461		* the backing list is equal to its expected value, and throw a
462	<	* <tt>ConcurrentModificationException</tt> if it is not.
462	>	* {@code ConcurrentModificationException} if it is not.
463		*
464		* @throws IndexOutOfBoundsException endpoint index value out of range
465	<	*         <tt>(fromIndex &lt; 0 || toIndex &gt; size)</tt>
465	>	*         {@code (fromIndex < 0 || toIndex > size)}
466		* @throws IllegalArgumentException if the endpoint indices are out of order
467	<	*         <tt>(fromIndex &gt; toIndex)</tt>
467	>	*         {@code (fromIndex > toIndex)}
468		*/
469		public List<E> subList(int fromIndex, int toIndex) {
470		return (this instanceof RandomAccess ?
471	<	new RandomAccessSubList<E>(this, fromIndex, toIndex) :
472	<	new SubList<E>(this, fromIndex, toIndex));
471	>	new RandomAccessSubList(this, this, fromIndex, fromIndex, toIndex) :
472	>	new SubList(this, this, fromIndex, fromIndex, toIndex));
473		}
474
475		// Comparison and hashing
476
477		/**
478		* Compares the specified object with this list for equality.  Returns
479	<	* <tt>true</tt> if and only if the specified object is also a list, both
479	>	* {@code true} if and only if the specified object is also a list, both
480		* lists have the same size, and all corresponding pairs of elements in
481	<	* the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
482	<	* <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
483	<	* e1.equals(e2))</tt>.)  In other words, two lists are defined to be
484	<	* equal if they contain the same elements in the same order.<p>
485	<	*
486	<	* This implementation first checks if the specified object is this
487	<	* list. If so, it returns <tt>true</tt>; if not, it checks if the
488	<	* specified object is a list. If not, it returns <tt>false</tt>; if so,
481	>	* the two lists are <i>equal</i>.  (Two elements {@code e1} and
482	>	* {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
483	>	* e1.equals(e2))}.)  In other words, two lists are defined to be
484	>	* equal if they contain the same elements in the same order.
485	>	*
486	>	* <p>This implementation first checks if the specified object is this
487	>	* list. If so, it returns {@code true}; if not, it checks if the
488	>	* specified object is a list. If not, it returns {@code false}; if so,
489		* it iterates over both lists, comparing corresponding pairs of elements.
490	<	* If any comparison returns <tt>false</tt>, this method returns
491	<	* <tt>false</tt>.  If either iterator runs out of elements before the
492	<	* other it returns <tt>false</tt> (as the lists are of unequal length);
493	<	* otherwise it returns <tt>true</tt> when the iterations complete.
490	>	* If any comparison returns {@code false}, this method returns
491	>	* {@code false}.  If either iterator runs out of elements before the
492	>	* other it returns {@code false} (as the lists are of unequal length);
493	>	* otherwise it returns {@code true} when the iterations complete.
494		*
495		* @param o the object to be compared for equality with this list
496	<	* @return <tt>true</tt> if the specified object is equal to this list
496	>	* @return {@code true} if the specified object is equal to this list
497		*/
498		public boolean equals(Object o) {
499		if (o == this)
#	Line 515 | Line 513 | public abstract class AbstractList<E> ex
513		}
514
515		/**
516	<	* Returns the hash code value for this list. <p>
516	>	* Returns the hash code value for this list.
517		*
518	<	* This implementation uses exactly the code that is used to define the
518	>	* <p>This implementation uses exactly the code that is used to define the
519		* list hash function in the documentation for the {@link List#hashCode}
520		* method.
521		*
#	Line 535 | Line 533 | public abstract class AbstractList<E> ex
533
534		/**
535		* Removes from this list all of the elements whose index is between
536	<	* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
536	>	* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
537		* Shifts any succeeding elements to the left (reduces their index).
538	<	* This call shortens the ArrayList by <tt>(toIndex - fromIndex)</tt>
539	<	* elements.  (If <tt>toIndex==fromIndex</tt>, this operation has no
540	<	* effect.)<p>
538	>	* This call shortens the ArrayList by {@code (toIndex - fromIndex)}
539	>	* elements.  (If {@code toIndex==fromIndex}, this operation has no
540	>	* effect.)
541		*
542	<	* This method is called by the <tt>clear</tt> operation on this list
542	>	* <p>This method is called by the {@code clear} operation on this list
543		* and its subLists.  Overriding this method to take advantage of
544		* the internals of the list implementation can <i>substantially</i>
545	<	* improve the performance of the <tt>clear</tt> operation on this list
546	<	* and its subLists.<p>
545	>	* improve the performance of the {@code clear} operation on this list
546	>	* and its subLists.
547		*
548	<	* This implementation gets a list iterator positioned before
549	<	* <tt>fromIndex</tt>, and repeatedly calls <tt>ListIterator.next</tt>
550	<	* followed by <tt>ListIterator.remove</tt> until the entire range has
551	<	* been removed.  <b>Note: if <tt>ListIterator.remove</tt> requires linear
548	>	* <p>This implementation gets a list iterator positioned before
549	>	* {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
550	>	* followed by {@code ListIterator.remove} until the entire range has
551	>	* been removed.  <b>Note: if {@code ListIterator.remove} requires linear
552		* time, this implementation requires quadratic time.</b>
553		*
554		* @param fromIndex index of first element to be removed
#	Line 568 | Line 566 | public abstract class AbstractList<E> ex
566		* The number of times this list has been <i>structurally modified</i>.
567		* Structural modifications are those that change the size of the
568		* list, or otherwise perturb it in such a fashion that iterations in
569	<	* progress may yield incorrect results.<p>
569	>	* progress may yield incorrect results.
570		*
571	<	* This field is used by the iterator and list iterator implementation
572	<	* returned by the <tt>iterator</tt> and <tt>listIterator</tt> methods.
571	>	* <p>This field is used by the iterator and list iterator implementation
572	>	* returned by the {@code iterator} and {@code listIterator} methods.
573		* If the value of this field changes unexpectedly, the iterator (or list
574	<	* iterator) will throw a <tt>ConcurrentModificationException</tt> in
575	<	* response to the <tt>next</tt>, <tt>remove</tt>, <tt>previous</tt>,
576	<	* <tt>set</tt> or <tt>add</tt> operations.  This provides
574	>	* iterator) will throw a {@code ConcurrentModificationException} in
575	>	* response to the {@code next}, {@code remove}, {@code previous},
576	>	* {@code set} or {@code add} operations.  This provides
577		* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
578	<	* the face of concurrent modification during iteration.<p>
578	>	* the face of concurrent modification during iteration.
579		*
580	<	* <b>Use of this field by subclasses is optional.</b> If a subclass
580	>	* <p><b>Use of this field by subclasses is optional.</b> If a subclass
581		* wishes to provide fail-fast iterators (and list iterators), then it
582	<	* merely has to increment this field in its <tt>add(int, Object)</tt> and
583	<	* <tt>remove(int)</tt> methods (and any other methods that it overrides
582	>	* merely has to increment this field in its {@code add(int, E)} and
583	>	* {@code remove(int)} methods (and any other methods that it overrides
584		* that result in structural modifications to the list).  A single call to
585	<	* <tt>add(int, Object)</tt> or <tt>remove(int)</tt> must add no more than
585	>	* {@code add(int, E)} or {@code remove(int)} must add no more than
586		* one to this field, or the iterators (and list iterators) will throw
587	<	* bogus <tt>ConcurrentModificationExceptions</tt>.  If an implementation
587	>	* bogus {@code ConcurrentModificationExceptions}.  If an implementation
588		* does not wish to provide fail-fast iterators, this field may be
589		* ignored.
590		*/
591		protected transient int modCount = 0;
592		}
593
594	+	/**
595	+	* Generic sublists. Non-nested to enable construction by other
596	+	* classes in this package.
597	+	*/
598		class SubList<E> extends AbstractList<E> {
599	<	private AbstractList<E> l;
600	<	private int offset;
601	<	private int size;
602	<	private int expectedModCount;
603	<
604	<	SubList(AbstractList<E> list, int fromIndex, int toIndex) {
599	>	/*
600	>	* A SubList has both a "base", the ultimate backing list, as well
601	>	* as a "parent", which is the list or sublist creating this
602	>	* sublist. All methods that may cause structural modifications
603	>	* must propagate through the parent link, with O(k) performance
604	>	* where k is sublist depth. For example in the case of a
605	>	* sub-sub-list, invoking remove(x) will result in a chain of
606	>	* three remove calls. However, all other non-structurally
607	>	* modifying methods can bypass this chain, and relay directly to
608	>	* the base list. In particular, doing so signficantly speeds up
609	>	* the performance of iterators for deeply-nested sublists.
610	>	*/
611	>	final AbstractList<E> base;   // Backing list
612	>	final AbstractList<E> parent; // Parent list
613	>	final int baseOffset;         // index wrt base
614	>	final int parentOffset;       // index wrt parent
615	>	int length;                   // Number of elements in this sublist
616	>
617	>	SubList(AbstractList<E> base,
618	>	AbstractList<E> parent,
619	>	int baseIndex,
620	>	int fromIndex,
621	>	int toIndex) {
622		if (fromIndex < 0)
623		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
624	<	if (toIndex > list.size())
624	>	if (toIndex > parent.size())
625		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
626		if (fromIndex > toIndex)
627		throw new IllegalArgumentException("fromIndex(" + fromIndex +
628		") > toIndex(" + toIndex + ")");
629	<	l = list;
630	<	offset = fromIndex;
631	<	size = toIndex - fromIndex;
632	<	expectedModCount = l.modCount;
629	>	this.base = base;
630	>	this.parent = parent;
631	>	this.baseOffset = baseIndex;
632	>	this.parentOffset = fromIndex;
633	>	this.length = toIndex - fromIndex;
634	>	this.modCount = base.modCount;
635	>	}
636	>
637	>	/**
638	>	* Returns an IndexOutOfBoundsException with nicer message
639	>	*/
640	>	private IndexOutOfBoundsException indexError(int index) {
641	>	return new IndexOutOfBoundsException("Index: " + index +
642	>	", Size: " + length);
643		}
644
645		public E set(int index, E element) {
646	<	rangeCheck(index);
647	<	checkForComodification();
648	<	return l.set(index+offset, element);
646	>	if (index < 0 || index >= length)
647	>	throw indexError(index);
648	>	if (base.modCount != modCount)
649	>	throw new ConcurrentModificationException();
650	>	return base.set(index + baseOffset, element);
651		}
652
653		public E get(int index) {
654	<	rangeCheck(index);
655	<	checkForComodification();
656	<	return l.get(index+offset);
654	>	if (index < 0 || index >= length)
655	>	throw indexError(index);
656	>	if (base.modCount != modCount)
657	>	throw new ConcurrentModificationException();
658	>	return base.get(index + baseOffset);
659		}
660
661		public int size() {
662	<	checkForComodification();
663	<	return size;
662	>	if (base.modCount != modCount)
663	>	throw new ConcurrentModificationException();
664	>	return length;
665		}
666
667		public void add(int index, E element) {
668	<	if (index<0 || index>size)
669	<	throw new IndexOutOfBoundsException();
670	<	checkForComodification();
671	<	l.add(index+offset, element);
672	<	expectedModCount = l.modCount;
673	<	size++;
674	<	modCount++;
668	>	if (index < 0 || index>length)
669	>	throw indexError(index);
670	>	if (base.modCount != modCount)
671	>	throw new ConcurrentModificationException();
672	>	parent.add(index + parentOffset, element);
673	>	length++;
674	>	modCount = base.modCount;
675		}
676
677		public E remove(int index) {
678	<	rangeCheck(index);
679	<	checkForComodification();
680	<	E result = l.remove(index+offset);
681	<	expectedModCount = l.modCount;
682	<	size--;
683	<	modCount++;
678	>	if (index < 0 || index >= length)
679	>	throw indexError(index);
680	>	if (base.modCount != modCount)
681	>	throw new ConcurrentModificationException();
682	>	E result = parent.remove(index + parentOffset);
683	>	length--;
684	>	modCount = base.modCount;
685		return result;
686		}
687
688		protected void removeRange(int fromIndex, int toIndex) {
689	<	checkForComodification();
690	<	l.removeRange(fromIndex+offset, toIndex+offset);
691	<	expectedModCount = l.modCount;
692	<	size -= (toIndex-fromIndex);
693	<	modCount++;
689	>	if (base.modCount != modCount)
690	>	throw new ConcurrentModificationException();
691	>	parent.removeRange(fromIndex + parentOffset, toIndex + parentOffset);
692	>	length -= (toIndex-fromIndex);
693	>	modCount = base.modCount;
694		}
695
696		public boolean addAll(Collection<? extends E> c) {
697	<	return addAll(size, c);
697	>	return addAll(length, c);
698		}
699
700		public boolean addAll(int index, Collection<? extends E> c) {
701	<	if (index<0 || index>size)
702	<	throw new IndexOutOfBoundsException(
668	<	"Index: "+index+", Size: "+size);
701	>	if (index < 0 || index > length)
702	>	throw indexError(index);
703		int cSize = c.size();
704		if (cSize==0)
705		return false;
706
707	<	checkForComodification();
708	<	l.addAll(offset+index, c);
709	<	expectedModCount = l.modCount;
710	<	size += cSize;
711	<	modCount++;
707	>	if (base.modCount != modCount)
708	>	throw new ConcurrentModificationException();
709	>	parent.addAll(parentOffset + index, c);
710	>	length += cSize;
711	>	modCount = base.modCount;
712		return true;
713		}
714
715	+	public List<E> subList(int fromIndex, int toIndex) {
716	+	return new SubList(base, this, fromIndex + baseOffset,
717	+	fromIndex, toIndex);
718	+	}
719	+
720		public Iterator<E> iterator() {
721	<	return listIterator();
721	>	return new SubListIterator(this, 0);
722		}
723
724	<	public ListIterator<E> listIterator(final int index) {
725	<	checkForComodification();
726	<	if (index<0 || index>size)
688	<	throw new IndexOutOfBoundsException(
689	<	"Index: "+index+", Size: "+size);
724	>	public ListIterator<E> listIterator() {
725	>	return new SubListIterator(this, 0);
726	>	}
727
728	<	return new ListIterator<E>() {
729	<	private ListIterator<E> i = l.listIterator(index+offset);
728	>	public ListIterator<E> listIterator(int index) {
729	>	if (index < 0 || index>length)
730	>	throw indexError(index);
731	>	return new SubListIterator(this, index);
732	>	}
733
734	<	public boolean hasNext() {
735	<	return nextIndex() < size;
736	<	}
734	>	/**
735	>	* Generic sublist iterator obeying fastfail semantics via
736	>	* modCount.  The hasNext and next methods locally check for
737	>	* in-range indices before relaying to backing list to get
738	>	* element. If this either encounters an unexpected modCount or
739	>	* fails, the backing list must have been concurrently modified,
740	>	* and is so reported.  The add and remove methods performing
741	>	* structural modifications instead relay them through the
742	>	* sublist.
743	>	*/
744	>	private static final class SubListIterator<E> implements ListIterator<E> {
745	>	final SubList<E> outer;       // Sublist creating this iteraor
746	>	final AbstractList<E> base;   // base list
747	>	final int offset;             // Cursor offset wrt base
748	>	int cursor;                   // Current index
749	>	int fence;                    // Upper bound on cursor
750	>	int lastRet;                  // Index of returned element, or -1
751	>	int expectedModCount;         // Expected modCount of base
752	>
753	>	SubListIterator(SubList<E> list, int index) {
754	>	this.lastRet = -1;
755	>	this.cursor = index;
756	>	this.outer = list;
757	>	this.offset = list.baseOffset;
758	>	this.fence = list.length;
759	>	this.base = list.base;
760	>	this.expectedModCount = base.modCount;
761	>	}
762
763	<	public E next() {
764	<	if (hasNext())
765	<	return i.next();
701	<	else
702	<	throw new NoSuchElementException();
703	<	}
763	>	public boolean hasNext() {
764	>	return cursor < fence;
765	>	}
766
767	<	public boolean hasPrevious() {
768	<	return previousIndex() >= 0;
769	<	}
767	>	public boolean hasPrevious() {
768	>	return cursor > 0;
769	>	}
770
771	<	public E previous() {
772	<	if (hasPrevious())
773	<	return i.previous();
712	<	else
713	<	throw new NoSuchElementException();
714	<	}
771	>	public int nextIndex() {
772	>	return cursor;
773	>	}
774
775	<	public int nextIndex() {
776	<	return i.nextIndex() - offset;
777	<	}
775	>	public int previousIndex() {
776	>	return cursor - 1;
777	>	}
778
779	<	public int previousIndex() {
780	<	return i.previousIndex() - offset;
779	>	public E next() {
780	>	int i = cursor;
781	>	if (cursor >= fence)
782	>	throw new NoSuchElementException();
783	>	if (expectedModCount == base.modCount) {
784	>	try {
785	>	Object next = base.get(i + offset);
786	>	lastRet = i;
787	>	cursor = i + 1;
788	>	return (E)next;
789	>	} catch (IndexOutOfBoundsException fallThrough) {
790	>	}
791		}
792	+	throw new ConcurrentModificationException();
793	+	}
794
795	<	public void remove() {
796	<	i.remove();
797	<	expectedModCount = l.modCount;
798	<	size--;
799	<	modCount++;
795	>	public E previous() {
796	>	int i = cursor - 1;
797	>	if (i < 0)
798	>	throw new NoSuchElementException();
799	>	if (expectedModCount == base.modCount) {
800	>	try {
801	>	Object prev = base.get(i + offset);
802	>	lastRet = i;
803	>	cursor = i;
804	>	return (E)prev;
805	>	} catch (IndexOutOfBoundsException fallThrough) {
806	>	}
807		}
808	+	throw new ConcurrentModificationException();
809	+	}
810
811	<	public void set(E e) {
812	<	i.set(e);
811	>	public void set(E e) {
812	>	if (lastRet < 0)
813	>	throw new IllegalStateException();
814	>	if (expectedModCount != base.modCount)
815	>	throw new ConcurrentModificationException();
816	>	try {
817	>	outer.set(lastRet, e);
818	>	expectedModCount = base.modCount;
819	>	} catch (IndexOutOfBoundsException ex) {
820	>	throw new ConcurrentModificationException();
821		}
822	+	}
823
824	<	public void add(E e) {
825	<	i.add(e);
826	<	expectedModCount = l.modCount;
827	<	size++;
828	<	modCount++;
824	>	public void remove() {
825	>	int i = lastRet;
826	>	if (i < 0)
827	>	throw new IllegalStateException();
828	>	if (expectedModCount != base.modCount)
829	>	throw new ConcurrentModificationException();
830	>	try {
831	>	outer.remove(i);
832	>	if (i < cursor)
833	>	cursor--;
834	>	lastRet = -1;
835	>	fence = outer.length;
836	>	expectedModCount = base.modCount;
837	>	} catch (IndexOutOfBoundsException ex) {
838	>	throw new ConcurrentModificationException();
839		}
840	<	};
742	<	}
743	<
744	<	public List<E> subList(int fromIndex, int toIndex) {
745	<	return new SubList<E>(this, fromIndex, toIndex);
746	<	}
840	>	}
841
842	<	private void rangeCheck(int index) {
843	<	if (index<0 || index>=size)
844	<	throw new IndexOutOfBoundsException("Index: "+index+
845	<	",Size: "+size);
842	>	public void add(E e) {
843	>	if (expectedModCount != base.modCount)
844	>	throw new ConcurrentModificationException();
845	>	try {
846	>	int i = cursor;
847	>	outer.add(i, e);
848	>	cursor = i + 1;
849	>	lastRet = -1;
850	>	fence = outer.length;
851	>	expectedModCount = base.modCount;
852	>	} catch (IndexOutOfBoundsException ex) {
853	>	throw new ConcurrentModificationException();
854	>	}
855	>	}
856		}
857
754	–	private void checkForComodification() {
755	–	if (l.modCount != expectedModCount)
756	–	throw new ConcurrentModificationException();
757	–	}
858		}
859
860		class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
861	<	RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
862	<	super(list, fromIndex, toIndex);
861	>	RandomAccessSubList(AbstractList<E> base,
862	>	AbstractList<E> parent, int baseIndex,
863	>	int fromIndex, int toIndex) {
864	>	super(base, parent, baseIndex, fromIndex, toIndex);
865		}
866
867		public List<E> subList(int fromIndex, int toIndex) {
868	<	return new RandomAccessSubList<E>(this, fromIndex, toIndex);
868	>	return new RandomAccessSubList(base, this, fromIndex + baseOffset,
869	>	fromIndex, toIndex);
870		}
871		}

Diff Legend

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