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.13 by jsr166, Mon Jun 26 01:02:38 2006 UTC

#	Line 8 | Line 8
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 252 | Line 251 | public abstract class AbstractList<E> ex
251
252		/**
253		* Returns an iterator over the elements in this list in proper
254	<	* sequence. <p>
254	>	* sequence.
255		*
256	<	* This implementation returns a straightforward implementation of the
257	<	* iterator interface, relying on the backing list's <tt>size()</tt>,
258	<	* <tt>get(int)</tt>, and <tt>remove(int)</tt> methods.<p>
259	<	*
260	<	* Note that the iterator returned by this method will throw an
261	<	* <tt>UnsupportedOperationException</tt> in response to its
262	<	* <tt>remove</tt> method unless the list's <tt>remove(int)</tt> method is
263	<	* overridden.<p>
264	<	*
265	<	* This implementation can be made to throw runtime exceptions in the face
266	<	* of concurrent modification, as described in the specification for the
267	<	* (protected) <tt>modCount</tt> field.
256	>	* <p>This implementation returns a straightforward implementation of the
257	>	* iterator interface, relying on the backing list's {@code size()},
258	>	* {@code get(int)}, and {@code remove(int)} methods.
259	>	*
260	>	* <p>Note that the iterator returned by this method will throw an
261	>	* {@code UnsupportedOperationException} in response to its
262	>	* {@code remove} method unless the list's {@code remove(int)} method is
263	>	* overridden.
264	>	*
265	>	* <p>This implementation can be made to throw runtime exceptions in the
266	>	* face of concurrent modification, as described in the specification
267	>	* for the (protected) {@code modCount} field.
268		*
269		* @return an iterator over the elements in this list in proper sequence
270		*
#	Line 278 | Line 277 | public abstract class AbstractList<E> ex
277		/**
278		* {@inheritDoc}
279		*
280	<	* <p>This implementation returns <tt>listIterator(0)</tt>.
280	>	* <p>This implementation returns {@code listIterator(0)}.
281		*
282		* @see #listIterator(int)
283		*/
#	Line 290 | Line 289 | public abstract class AbstractList<E> ex
289		* {@inheritDoc}
290		*
291		* <p>This implementation returns a straightforward implementation of the
292	<	* <tt>ListIterator</tt> interface that extends the implementation of the
293	<	* <tt>Iterator</tt> interface returned by the <tt>iterator()</tt> method.
294	<	* The <tt>ListIterator</tt> implementation relies on the backing list's
295	<	* <tt>get(int)</tt>, <tt>set(int, Object)</tt>, <tt>add(int, Object)</tt>
296	<	* and <tt>remove(int)</tt> methods.
292	>	* {@code ListIterator} interface that extends the implementation of the
293	>	* {@code Iterator} interface returned by the {@code iterator()} method.
294	>	* The {@code ListIterator} implementation relies on the backing list's
295	>	* {@code get(int)}, {@code set(int, E)}, {@code add(int, Object)}
296	>	* and {@code remove(int)} methods.
297		*
298		* <p>Note that the list iterator returned by this implementation will
299	<	* throw an <tt>UnsupportedOperationException</tt> in response to its
300	<	* <tt>remove</tt>, <tt>set</tt> and <tt>add</tt> methods unless the
301	<	* list's <tt>remove(int)</tt>, <tt>set(int, Object)</tt>, and
302	<	* <tt>add(int, Object)</tt> methods are overridden.
299	>	* throw an {@code UnsupportedOperationException} in response to its
300	>	* {@code remove}, {@code set} and {@code add} methods unless the
301	>	* list's {@code remove(int)}, {@code set(int, E)}, and
302	>	* {@code add(int, E)} methods are overridden.
303		*
304		* <p>This implementation can be made to throw runtime exceptions in the
305		* face of concurrent modification, as described in the specification for
306	<	* the (protected) <tt>modCount</tt> field.
306	>	* the (protected) {@code modCount} field.
307		*
308		* @throws IndexOutOfBoundsException {@inheritDoc}
309		*
#	Line 342 | Line 341 | public abstract class AbstractList<E> ex
341		}
342
343		public E next() {
344	<	try {
345	<	int i = cursor;
346	<	E next = get(i);
347	<	lastRet = i;
348	<	cursor = i + 1;
349	<	return next;
350	<	} catch (IndexOutOfBoundsException ex) {
351	<	throw new NoSuchElementException();
352	<	} finally {
354	<	if (expectedModCount != modCount)
355	<	throw new ConcurrentModificationException();
356	<	}
344	>	checkForComodification();
345	>	try {
346	>	E next = get(cursor);
347	>	lastRet = cursor++;
348	>	return next;
349	>	} catch (IndexOutOfBoundsException e) {
350	>	checkForComodification();
351	>	throw new NoSuchElementException();
352	>	}
353		}
354
355		public void remove() {
356		if (lastRet == -1)
357		throw new IllegalStateException();
358	<	if (expectedModCount != modCount)
359	<	throw new ConcurrentModificationException();
358	>	checkForComodification();
359	>
360		try {
361		AbstractList.this.remove(lastRet);
362		if (lastRet < cursor)
#	Line 371 | Line 367 | public abstract class AbstractList<E> ex
367		throw new ConcurrentModificationException();
368		}
369		}
370	+
371	+	final void checkForComodification() {
372	+	if (modCount != expectedModCount)
373	+	throw new ConcurrentModificationException();
374	+	}
375		}
376	<
376	>
377		private class ListItr extends Itr implements ListIterator<E> {
378		ListItr(int index) {
379		cursor = index;
#	Line 382 | Line 383 | public abstract class AbstractList<E> ex
383		return cursor != 0;
384		}
385
385	–	public int nextIndex() {
386	–	return cursor;
387	–	}
388	–
389	–	public int previousIndex() {
390	–	return cursor - 1;
391	–	}
392	–
386		public E previous() {
387	+	checkForComodification();
388		try {
389		int i = cursor - 1;
390	<	E prev = get(i);
391	<	lastRet = i;
392	<	cursor = i;
393	<	return prev;
394	<	} catch (IndexOutOfBoundsException ex) {
390	>	E previous = get(i);
391	>	lastRet = cursor = i;
392	>	return previous;
393	>	} catch (IndexOutOfBoundsException e) {
394	>	checkForComodification();
395		throw new NoSuchElementException();
402	–	} finally {
403	–	if (expectedModCount != modCount)
404	–	throw new ConcurrentModificationException();
396		}
397		}
398
399	+	public int nextIndex() {
400	+	return cursor;
401	+	}
402	+
403	+	public int previousIndex() {
404	+	return cursor-1;
405	+	}
406	+
407		public void set(E e) {
408		if (lastRet == -1)
409		throw new IllegalStateException();
410	<	if (expectedModCount != modCount)
411	<	throw new ConcurrentModificationException();
410	>	checkForComodification();
411	>
412		try {
413		AbstractList.this.set(lastRet, e);
414		expectedModCount = modCount;
#	Line 419 | Line 418 | public abstract class AbstractList<E> ex
418		}
419
420		public void add(E e) {
421	<	if (expectedModCount != modCount)
422	<	throw new ConcurrentModificationException();
421	>	checkForComodification();
422	>
423		try {
424		int i = cursor;
425		AbstractList.this.add(i, e);
#	Line 437 | Line 436 | public abstract class AbstractList<E> ex
436		* {@inheritDoc}
437		*
438		* <p>This implementation returns a list that subclasses
439	<	* <tt>AbstractList</tt>.  The subclass stores, in private fields, the
439	>	* {@code AbstractList}.  The subclass stores, in private fields, the
440		* offset of the subList within the backing list, the size of the subList
441		* (which can change over its lifetime), and the expected
442	<	* <tt>modCount</tt> value of the backing list.  There are two variants
443	<	* of the subclass, one of which implements <tt>RandomAccess</tt>.
444	<	* If this list implements <tt>RandomAccess</tt> the returned list will
445	<	* be an instance of the subclass that implements <tt>RandomAccess</tt>.
446	<	*
447	<	* <p>The subclass's <tt>set(int, Object)</tt>, <tt>get(int)</tt>,
448	<	* <tt>add(int, Object)</tt>, <tt>remove(int)</tt>, <tt>addAll(int,
449	<	* Collection)</tt> and <tt>removeRange(int, int)</tt> methods all
442	>	* {@code modCount} value of the backing list.  There are two variants
443	>	* of the subclass, one of which implements {@code RandomAccess}.
444	>	* If this list implements {@code RandomAccess} the returned list will
445	>	* be an instance of the subclass that implements {@code RandomAccess}.
446	>	*
447	>	* <p>The subclass's {@code set(int, Object)}, {@code get(int)},
448	>	* {@code add(int, Object)}, {@code remove(int)}, {@code addAll(int,
449	>	* Collection)} and {@code removeRange(int, int)} methods all
450		* delegate to the corresponding methods on the backing abstract list,
451		* after bounds-checking the index and adjusting for the offset.  The
452	<	* <tt>addAll(Collection c)</tt> method merely returns <tt>addAll(size,
453	<	* c)</tt>.
452	>	* {@code addAll(Collection c)} method merely returns {@code addAll(size,
453	>	* c)}.
454		*
455	<	* <p>The <tt>listIterator(int)</tt> method returns a "wrapper object"
455	>	* <p>The {@code listIterator(int)} method returns a "wrapper object"
456		* over a list iterator on the backing list, which is created with the
457	<	* corresponding method on the backing list.  The <tt>iterator</tt> method
458	<	* merely returns <tt>listIterator()</tt>, and the <tt>size</tt> method
459	<	* merely returns the subclass's <tt>size</tt> field.
457	>	* corresponding method on the backing list.  The {@code iterator} method
458	>	* merely returns {@code listIterator()}, and the {@code size} method
459	>	* merely returns the subclass's {@code size} field.
460		*
461	<	* <p>All methods first check to see if the actual <tt>modCount</tt> of
461	>	* <p>All methods first check to see if the actual {@code modCount} of
462		* the backing list is equal to its expected value, and throw a
463	<	* <tt>ConcurrentModificationException</tt> if it is not.
463	>	* {@code ConcurrentModificationException} if it is not.
464		*
465		* @throws IndexOutOfBoundsException endpoint index value out of range
466	<	*         <tt>(fromIndex &lt; 0 || toIndex &gt; size)</tt>
466	>	*         {@code (fromIndex &lt; 0 || toIndex &gt; size)}
467		* @throws IllegalArgumentException if the endpoint indices are out of order
468	<	*         <tt>(fromIndex &gt; toIndex)</tt>
468	>	*         {@code (fromIndex &gt; toIndex)}
469		*/
470		public List<E> subList(int fromIndex, int toIndex) {
471		return (this instanceof RandomAccess ?
472	<	new RandomAccessSubList<E>(this, fromIndex, toIndex) :
473	<	new SubList<E>(this, fromIndex, toIndex));
472	>	new RandomAccessSubList(this, this, fromIndex, fromIndex, toIndex) :
473	>	new SubList(this, this, fromIndex, fromIndex, toIndex));
474		}
475
476		// Comparison and hashing
477
478		/**
479		* Compares the specified object with this list for equality.  Returns
480	<	* <tt>true</tt> if and only if the specified object is also a list, both
480	>	* {@code true} if and only if the specified object is also a list, both
481		* lists have the same size, and all corresponding pairs of elements in
482	<	* the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
483	<	* <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
484	<	* e1.equals(e2))</tt>.)  In other words, two lists are defined to be
485	<	* equal if they contain the same elements in the same order.<p>
486	<	*
487	<	* This implementation first checks if the specified object is this
488	<	* list. If so, it returns <tt>true</tt>; if not, it checks if the
489	<	* specified object is a list. If not, it returns <tt>false</tt>; if so,
482	>	* the two lists are <i>equal</i>.  (Two elements {@code e1} and
483	>	* {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
484	>	* e1.equals(e2))}.)  In other words, two lists are defined to be
485	>	* equal if they contain the same elements in the same order.
486	>	*
487	>	* <p>This implementation first checks if the specified object is this
488	>	* list. If so, it returns {@code true}; if not, it checks if the
489	>	* specified object is a list. If not, it returns {@code false}; if so,
490		* it iterates over both lists, comparing corresponding pairs of elements.
491	<	* If any comparison returns <tt>false</tt>, this method returns
492	<	* <tt>false</tt>.  If either iterator runs out of elements before the
493	<	* other it returns <tt>false</tt> (as the lists are of unequal length);
494	<	* otherwise it returns <tt>true</tt> when the iterations complete.
491	>	* If any comparison returns {@code false}, this method returns
492	>	* {@code false}.  If either iterator runs out of elements before the
493	>	* other it returns {@code false} (as the lists are of unequal length);
494	>	* otherwise it returns {@code true} when the iterations complete.
495		*
496		* @param o the object to be compared for equality with this list
497	<	* @return <tt>true</tt> if the specified object is equal to this list
497	>	* @return {@code true} if the specified object is equal to this list
498		*/
499		public boolean equals(Object o) {
500		if (o == this)
#	Line 515 | Line 514 | public abstract class AbstractList<E> ex
514		}
515
516		/**
517	<	* Returns the hash code value for this list. <p>
517	>	* Returns the hash code value for this list.
518		*
519	<	* This implementation uses exactly the code that is used to define the
519	>	* <p>This implementation uses exactly the code that is used to define the
520		* list hash function in the documentation for the {@link List#hashCode}
521		* method.
522		*
#	Line 535 | Line 534 | public abstract class AbstractList<E> ex
534
535		/**
536		* Removes from this list all of the elements whose index is between
537	<	* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
537	>	* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
538		* Shifts any succeeding elements to the left (reduces their index).
539	<	* This call shortens the ArrayList by <tt>(toIndex - fromIndex)</tt>
540	<	* elements.  (If <tt>toIndex==fromIndex</tt>, this operation has no
541	<	* effect.)<p>
539	>	* This call shortens the ArrayList by {@code (toIndex - fromIndex)}
540	>	* elements.  (If {@code toIndex==fromIndex}, this operation has no
541	>	* effect.)
542		*
543	<	* This method is called by the <tt>clear</tt> operation on this list
543	>	* <p>This method is called by the {@code clear} operation on this list
544		* and its subLists.  Overriding this method to take advantage of
545		* the internals of the list implementation can <i>substantially</i>
546	<	* improve the performance of the <tt>clear</tt> operation on this list
547	<	* and its subLists.<p>
546	>	* improve the performance of the {@code clear} operation on this list
547	>	* and its subLists.
548		*
549	<	* This implementation gets a list iterator positioned before
550	<	* <tt>fromIndex</tt>, and repeatedly calls <tt>ListIterator.next</tt>
551	<	* followed by <tt>ListIterator.remove</tt> until the entire range has
552	<	* been removed.  <b>Note: if <tt>ListIterator.remove</tt> requires linear
549	>	* <p>This implementation gets a list iterator positioned before
550	>	* {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
551	>	* followed by {@code ListIterator.remove} until the entire range has
552	>	* been removed.  <b>Note: if {@code ListIterator.remove} requires linear
553		* time, this implementation requires quadratic time.</b>
554		*
555		* @param fromIndex index of first element to be removed
#	Line 568 | Line 567 | public abstract class AbstractList<E> ex
567		* The number of times this list has been <i>structurally modified</i>.
568		* Structural modifications are those that change the size of the
569		* list, or otherwise perturb it in such a fashion that iterations in
570	<	* progress may yield incorrect results.<p>
570	>	* progress may yield incorrect results.
571		*
572	<	* This field is used by the iterator and list iterator implementation
573	<	* returned by the <tt>iterator</tt> and <tt>listIterator</tt> methods.
572	>	* <p>This field is used by the iterator and list iterator implementation
573	>	* returned by the {@code iterator} and {@code listIterator} methods.
574		* If the value of this field changes unexpectedly, the iterator (or list
575	<	* iterator) will throw a <tt>ConcurrentModificationException</tt> in
576	<	* response to the <tt>next</tt>, <tt>remove</tt>, <tt>previous</tt>,
577	<	* <tt>set</tt> or <tt>add</tt> operations.  This provides
575	>	* iterator) will throw a {@code ConcurrentModificationException} in
576	>	* response to the {@code next}, {@code remove}, {@code previous},
577	>	* {@code set} or {@code add} operations.  This provides
578		* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
579	<	* the face of concurrent modification during iteration.<p>
579	>	* the face of concurrent modification during iteration.
580		*
581	<	* <b>Use of this field by subclasses is optional.</b> If a subclass
581	>	* <p><b>Use of this field by subclasses is optional.</b> If a subclass
582		* wishes to provide fail-fast iterators (and list iterators), then it
583	<	* merely has to increment this field in its <tt>add(int, Object)</tt> and
584	<	* <tt>remove(int)</tt> methods (and any other methods that it overrides
583	>	* merely has to increment this field in its {@code add(int, Object)} and
584	>	* {@code remove(int)} methods (and any other methods that it overrides
585		* that result in structural modifications to the list).  A single call to
586	<	* <tt>add(int, Object)</tt> or <tt>remove(int)</tt> must add no more than
586	>	* {@code add(int, Object)} or {@code remove(int)} must add no more than
587		* one to this field, or the iterators (and list iterators) will throw
588	<	* bogus <tt>ConcurrentModificationExceptions</tt>.  If an implementation
588	>	* bogus {@code ConcurrentModificationExceptions}.  If an implementation
589		* does not wish to provide fail-fast iterators, this field may be
590		* ignored.
591		*/
592		protected transient int modCount = 0;
593		}
594
595	+	/**
596	+	* Generic sublists. Non-nested to enable construction by other
597	+	* classes in this package.
598	+	*/
599		class SubList<E> extends AbstractList<E> {
600	<	private AbstractList<E> l;
601	<	private int offset;
602	<	private int size;
603	<	private int expectedModCount;
604	<
605	<	SubList(AbstractList<E> list, int fromIndex, int toIndex) {
600	>	/*
601	>	* A SubList has both a "base", the ultimate backing list, as well
602	>	* as a "parent", which is the list or sublist creating this
603	>	* sublist. All methods that may cause structural modifications
604	>	* must propagate through the parent link, with O(k) performance
605	>	* where k is sublist depth. For example in the case of a
606	>	* sub-sub-list, invoking remove(x) will result in a chain of
607	>	* three remove calls. However, all other non-structurally
608	>	* modifying methods can bypass this chain, and relay directly to
609	>	* the base list. In particular, doing so signficantly speeds up
610	>	* the performance of iterators for deeply-nested sublists.
611	>	*/
612	>	final AbstractList<E> base;   // Backing list
613	>	final AbstractList<E> parent; // Parent list
614	>	final int baseOffset;         // index wrt base
615	>	final int parentOffset;       // index wrt parent
616	>	int length;                   // Number of elements in this sublist
617	>
618	>	SubList(AbstractList<E> base,
619	>	AbstractList<E> parent,
620	>	int baseIndex,
621	>	int fromIndex,
622	>	int toIndex) {
623		if (fromIndex < 0)
624		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
625	<	if (toIndex > list.size())
625	>	if (toIndex > parent.size())
626		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
627		if (fromIndex > toIndex)
628		throw new IllegalArgumentException("fromIndex(" + fromIndex +
629		") > toIndex(" + toIndex + ")");
630	<	l = list;
631	<	offset = fromIndex;
632	<	size = toIndex - fromIndex;
633	<	expectedModCount = l.modCount;
630	>	this.base = base;
631	>	this.parent = parent;
632	>	this.baseOffset = baseIndex;
633	>	this.parentOffset = fromIndex;
634	>	this.length = toIndex - fromIndex;
635	>	this.modCount = base.modCount;
636	>	}
637	>
638	>	/**
639	>	* Returns an IndexOutOfBoundsException with nicer message
640	>	*/
641	>	private IndexOutOfBoundsException indexError(int index) {
642	>	return new IndexOutOfBoundsException("Index: " + index +
643	>	", Size: " + length);
644		}
645
646		public E set(int index, E element) {
647	<	rangeCheck(index);
648	<	checkForComodification();
649	<	return l.set(index+offset, element);
647	>	if (index < 0 || index >= length)
648	>	throw indexError(index);
649	>	if (base.modCount != modCount)
650	>	throw new ConcurrentModificationException();
651	>	return base.set(index + baseOffset, element);
652		}
653
654		public E get(int index) {
655	<	rangeCheck(index);
656	<	checkForComodification();
657	<	return l.get(index+offset);
655	>	if (index < 0 || index >= length)
656	>	throw indexError(index);
657	>	if (base.modCount != modCount)
658	>	throw new ConcurrentModificationException();
659	>	return base.get(index + baseOffset);
660		}
661
662		public int size() {
663	<	checkForComodification();
664	<	return size;
663	>	if (base.modCount != modCount)
664	>	throw new ConcurrentModificationException();
665	>	return length;
666		}
667
668		public void add(int index, E element) {
669	<	if (index<0 || index>size)
670	<	throw new IndexOutOfBoundsException();
671	<	checkForComodification();
672	<	l.add(index+offset, element);
673	<	expectedModCount = l.modCount;
674	<	size++;
675	<	modCount++;
669	>	if (index < 0 || index>length)
670	>	throw indexError(index);
671	>	if (base.modCount != modCount)
672	>	throw new ConcurrentModificationException();
673	>	parent.add(index + parentOffset, element);
674	>	length++;
675	>	modCount = base.modCount;
676		}
677
678		public E remove(int index) {
679	<	rangeCheck(index);
680	<	checkForComodification();
681	<	E result = l.remove(index+offset);
682	<	expectedModCount = l.modCount;
683	<	size--;
684	<	modCount++;
679	>	if (index < 0 || index >= length)
680	>	throw indexError(index);
681	>	if (base.modCount != modCount)
682	>	throw new ConcurrentModificationException();
683	>	E result = parent.remove(index + parentOffset);
684	>	length--;
685	>	modCount = base.modCount;
686		return result;
687		}
688
689		protected void removeRange(int fromIndex, int toIndex) {
690	<	checkForComodification();
691	<	l.removeRange(fromIndex+offset, toIndex+offset);
692	<	expectedModCount = l.modCount;
693	<	size -= (toIndex-fromIndex);
694	<	modCount++;
690	>	if (base.modCount != modCount)
691	>	throw new ConcurrentModificationException();
692	>	parent.removeRange(fromIndex + parentOffset, toIndex + parentOffset);
693	>	length -= (toIndex-fromIndex);
694	>	modCount = base.modCount;
695		}
696
697		public boolean addAll(Collection<? extends E> c) {
698	<	return addAll(size, c);
698	>	return addAll(length, c);
699		}
700
701		public boolean addAll(int index, Collection<? extends E> c) {
702	<	if (index<0 || index>size)
703	<	throw new IndexOutOfBoundsException(
668	<	"Index: "+index+", Size: "+size);
702	>	if (index < 0 || index > length)
703	>	throw indexError(index);
704		int cSize = c.size();
705		if (cSize==0)
706		return false;
707
708	<	checkForComodification();
709	<	l.addAll(offset+index, c);
710	<	expectedModCount = l.modCount;
711	<	size += cSize;
712	<	modCount++;
708	>	if (base.modCount != modCount)
709	>	throw new ConcurrentModificationException();
710	>	parent.addAll(parentOffset + index, c);
711	>	length += cSize;
712	>	modCount = base.modCount;
713		return true;
714		}
715
716	+	public List<E> subList(int fromIndex, int toIndex) {
717	+	return new SubList(base, this, fromIndex + baseOffset,
718	+	fromIndex, toIndex);
719	+	}
720	+
721		public Iterator<E> iterator() {
722	<	return listIterator();
722	>	return new SubListIterator(this, 0);
723		}
724
725	<	public ListIterator<E> listIterator(final int index) {
726	<	checkForComodification();
727	<	if (index<0 || index>size)
688	<	throw new IndexOutOfBoundsException(
689	<	"Index: "+index+", Size: "+size);
725	>	public ListIterator<E> listIterator() {
726	>	return new SubListIterator(this, 0);
727	>	}
728
729	<	return new ListIterator<E>() {
730	<	private ListIterator<E> i = l.listIterator(index+offset);
729	>	public ListIterator<E> listIterator(int index) {
730	>	if (index < 0 || index>length)
731	>	throw indexError(index);
732	>	return new SubListIterator(this, index);
733	>	}
734
735	<	public boolean hasNext() {
736	<	return nextIndex() < size;
737	<	}
735	>	/**
736	>	* Generic sublist iterator obeying fastfail semantics via
737	>	* modCount.  The hasNext and next methods locally check for
738	>	* in-range indices before relaying to backing list to get
739	>	* element. If this either encounters an unexpected modCount or
740	>	* fails, the backing list must have been concurrently modified,
741	>	* and is so reported.  The add and remove methods performing
742	>	* structural modifications instead relay them through the
743	>	* sublist.
744	>	*/
745	>	private static final class SubListIterator<E> implements ListIterator<E> {
746	>	final SubList<E> outer;       // Sublist creating this iteraor
747	>	final AbstractList<E> base;   // base list
748	>	final int offset;             // Cursor offset wrt base
749	>	int cursor;                   // Current index
750	>	int fence;                    // Upper bound on cursor
751	>	int lastRet;                  // Index of returned element, or -1
752	>	int expectedModCount;         // Expected modCount of base
753	>
754	>	SubListIterator(SubList<E> list, int index) {
755	>	this.lastRet = -1;
756	>	this.cursor = index;
757	>	this.outer = list;
758	>	this.offset = list.baseOffset;
759	>	this.fence = list.length;
760	>	this.base = list.base;
761	>	this.expectedModCount = base.modCount;
762	>	}
763
764	<	public E next() {
765	<	if (hasNext())
766	<	return i.next();
701	<	else
702	<	throw new NoSuchElementException();
703	<	}
764	>	public boolean hasNext() {
765	>	return cursor < fence;
766	>	}
767
768	<	public boolean hasPrevious() {
769	<	return previousIndex() >= 0;
770	<	}
768	>	public boolean hasPrevious() {
769	>	return cursor > 0;
770	>	}
771
772	<	public E previous() {
773	<	if (hasPrevious())
774	<	return i.previous();
712	<	else
713	<	throw new NoSuchElementException();
714	<	}
772	>	public int nextIndex() {
773	>	return cursor;
774	>	}
775
776	<	public int nextIndex() {
777	<	return i.nextIndex() - offset;
778	<	}
776	>	public int previousIndex() {
777	>	return cursor - 1;
778	>	}
779
780	<	public int previousIndex() {
781	<	return i.previousIndex() - offset;
780	>	public E next() {
781	>	int i = cursor;
782	>	if (cursor >= fence)
783	>	throw new NoSuchElementException();
784	>	if (expectedModCount == base.modCount) {
785	>	try {
786	>	Object next = base.get(i + offset);
787	>	lastRet = i;
788	>	cursor = i + 1;
789	>	return (E)next;
790	>	} catch (IndexOutOfBoundsException fallThrough) {
791	>	}
792		}
793	+	throw new ConcurrentModificationException();
794	+	}
795
796	<	public void remove() {
797	<	i.remove();
798	<	expectedModCount = l.modCount;
799	<	size--;
800	<	modCount++;
796	>	public E previous() {
797	>	int i = cursor - 1;
798	>	if (i < 0)
799	>	throw new NoSuchElementException();
800	>	if (expectedModCount == base.modCount) {
801	>	try {
802	>	Object prev = base.get(i + offset);
803	>	lastRet = i;
804	>	cursor = i;
805	>	return (E)prev;
806	>	} catch (IndexOutOfBoundsException fallThrough) {
807	>	}
808		}
809	+	throw new ConcurrentModificationException();
810	+	}
811
812	<	public void set(E e) {
813	<	i.set(e);
812	>	public void set(E e) {
813	>	if (lastRet < 0)
814	>	throw new IllegalStateException();
815	>	if (expectedModCount != base.modCount)
816	>	throw new ConcurrentModificationException();
817	>	try {
818	>	outer.set(lastRet, e);
819	>	expectedModCount = base.modCount;
820	>	} catch (IndexOutOfBoundsException ex) {
821	>	throw new ConcurrentModificationException();
822		}
823	+	}
824
825	<	public void add(E e) {
826	<	i.add(e);
827	<	expectedModCount = l.modCount;
828	<	size++;
829	<	modCount++;
825	>	public void remove() {
826	>	int i = lastRet;
827	>	if (i < 0)
828	>	throw new IllegalStateException();
829	>	if (expectedModCount != base.modCount)
830	>	throw new ConcurrentModificationException();
831	>	try {
832	>	outer.remove(i);
833	>	if (i < cursor)
834	>	cursor--;
835	>	lastRet = -1;
836	>	fence = outer.length;
837	>	expectedModCount = base.modCount;
838	>	} catch (IndexOutOfBoundsException ex) {
839	>	throw new ConcurrentModificationException();
840		}
841	<	};
742	<	}
743	<
744	<	public List<E> subList(int fromIndex, int toIndex) {
745	<	return new SubList<E>(this, fromIndex, toIndex);
746	<	}
841	>	}
842
843	<	private void rangeCheck(int index) {
844	<	if (index<0 || index>=size)
845	<	throw new IndexOutOfBoundsException("Index: "+index+
846	<	",Size: "+size);
843	>	public void add(E e) {
844	>	if (expectedModCount != base.modCount)
845	>	throw new ConcurrentModificationException();
846	>	try {
847	>	int i = cursor;
848	>	outer.add(i, e);
849	>	cursor = i + 1;
850	>	lastRet = -1;
851	>	fence = outer.length;
852	>	expectedModCount = base.modCount;
853	>	} catch (IndexOutOfBoundsException ex) {
854	>	throw new ConcurrentModificationException();
855	>	}
856	>	}
857		}
858
754	–	private void checkForComodification() {
755	–	if (l.modCount != expectedModCount)
756	–	throw new ConcurrentModificationException();
757	–	}
859		}
860
861		class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
862	<	RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
863	<	super(list, fromIndex, toIndex);
862	>	RandomAccessSubList(AbstractList<E> base,
863	>	AbstractList<E> parent, int baseIndex,
864	>	int fromIndex, int toIndex) {
865	>	super(base, parent, baseIndex, fromIndex, toIndex);
866		}
867
868		public List<E> subList(int fromIndex, int toIndex) {
869	<	return new RandomAccessSubList<E>(this, fromIndex, toIndex);
869	>	return new RandomAccessSubList(base, this, fromIndex + baseOffset,
870	>	fromIndex, toIndex);
871		}
872		}
873	+

Diff Legend

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