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.12 by jsr166, Mon Jun 26 00:46:50 2006 UTC vs.
Revision 1.21 by jsr166, Tue Sep 1 22:28:19 2009 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 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 {@code List}
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), {@code AbstractSequentialList} should
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 this
36	<	* class and provide implementations for the {@code get(int index)} and
37	<	* {@code size()} methods.
38	<	*
39	<	* <p>To implement a modifiable list, the programmer must additionally override
40	<	* the {@code set(int index, Object element)} method (which otherwise throws
41	<	* an {@code UnsupportedOperationException}.  If the list is variable-size
42	<	* the programmer must additionally override the {@code add(int index, Object
43	<	* element)} and {@code remove(int index)} methods.
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	>	* <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		* <p>The programmer should generally provide a void (no argument) and collection
46	<	* constructor, as per the recommendation in the {@code Collection} interface
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: {@code get(int index)}, {@code set(int index, E element)},
53	<	* {@code add(int index, E element)} and {@code remove(int index)}.
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	<	* <p>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.
61		*
#	Line 44 | Line 65 | package java.util;
65		*
66		* @author  Josh Bloch
67		* @author  Neal Gafter
47	–	* @version %I%, %G%
48	–	* @see Collection
49	–	* @see List
50	–	* @see AbstractSequentialList
51	–	* @see AbstractCollection
68		* @since 1.2
69		*/
70
#	Line 74 | Line 90 | public abstract class AbstractList<E> ex
90		* <p>This implementation calls {@code add(size(), e)}.
91		*
92		* <p>Note that this implementation throws an
93	<	* {@code UnsupportedOperationException} unless {@code add(int, Object)}
94	<	* is overridden.
93	>	* {@code UnsupportedOperationException} unless
94	>	* {@link #add(int, Object) add(int, E)} is overridden.
95		*
96		* @param e element to be appended to this list
97		* @return {@code true} (as specified by {@link Collection#add})
#	Line 89 | Line 105 | public abstract class AbstractList<E> ex
105		*         prevents it from being added to this list
106		*/
107		public boolean add(E e) {
108	<	add(size(), e);
109	<	return true;
108	>	add(size(), e);
109	>	return true;
110		}
111
112		/**
#	Line 113 | Line 129 | public abstract class AbstractList<E> ex
129		* @throws IndexOutOfBoundsException     {@inheritDoc}
130		*/
131		public E set(int index, E element) {
132	<	throw new UnsupportedOperationException();
132	>	throw new UnsupportedOperationException();
133		}
134
135		/**
#	Line 129 | Line 145 | public abstract class AbstractList<E> ex
145		* @throws IndexOutOfBoundsException     {@inheritDoc}
146		*/
147		public void add(int index, E element) {
148	<	throw new UnsupportedOperationException();
148	>	throw new UnsupportedOperationException();
149		}
150
151		/**
#	Line 142 | Line 158 | public abstract class AbstractList<E> ex
158		* @throws IndexOutOfBoundsException     {@inheritDoc}
159		*/
160		public E remove(int index) {
161	<	throw new UnsupportedOperationException();
161	>	throw new UnsupportedOperationException();
162		}
163
164
#	Line 159 | Line 175 | public abstract class AbstractList<E> ex
175		* @throws NullPointerException {@inheritDoc}
176		*/
177		public int indexOf(Object o) {
178	<	ListIterator<E> e = listIterator();
179	<	if (o==null) {
180	<	while (e.hasNext())
181	<	if (e.next()==null)
182	<	return e.previousIndex();
183	<	} else {
184	<	while (e.hasNext())
185	<	if (o.equals(e.next()))
186	<	return e.previousIndex();
187	<	}
188	<	return -1;
178	>	ListIterator<E> e = listIterator();
179	>	if (o==null) {
180	>	while (e.hasNext())
181	>	if (e.next()==null)
182	>	return e.previousIndex();
183	>	} else {
184	>	while (e.hasNext())
185	>	if (o.equals(e.next()))
186	>	return e.previousIndex();
187	>	}
188	>	return -1;
189		}
190
191		/**
#	Line 184 | Line 200 | public abstract class AbstractList<E> ex
200		* @throws NullPointerException {@inheritDoc}
201		*/
202		public int lastIndexOf(Object o) {
203	<	ListIterator<E> e = listIterator(size());
204	<	if (o==null) {
205	<	while (e.hasPrevious())
206	<	if (e.previous()==null)
207	<	return e.nextIndex();
208	<	} else {
209	<	while (e.hasPrevious())
210	<	if (o.equals(e.previous()))
211	<	return e.nextIndex();
212	<	}
213	<	return -1;
203	>	ListIterator<E> e = listIterator(size());
204	>	if (o==null) {
205	>	while (e.hasPrevious())
206	>	if (e.previous()==null)
207	>	return e.nextIndex();
208	>	} else {
209	>	while (e.hasPrevious())
210	>	if (o.equals(e.previous()))
211	>	return e.nextIndex();
212	>	}
213	>	return -1;
214		}
215
216
#	Line 221 | Line 237 | public abstract class AbstractList<E> ex
237		/**
238		* {@inheritDoc}
239		*
240	<	* <p>This implementation gets an iterator over the specified collection and
241	<	* iterates over it, inserting the elements obtained from the iterator
242	<	* into this list at the appropriate position, one at a time, using
243	<	* {@code add(int, Object)}.  Many implementations will override this
244	<	* method for efficiency.
240	>	* <p>This implementation gets an iterator over the specified collection
241	>	* and iterates over it, inserting the elements obtained from the
242	>	* iterator into this list at the appropriate position, one at a time,
243	>	* using {@code add(int, E)}.
244	>	* Many implementations will override this method for efficiency.
245		*
246		* <p>Note that this implementation throws an
247	<	* {@code UnsupportedOperationException} unless {@code add(int, Object)}
248	<	* is overridden.
247	>	* {@code UnsupportedOperationException} unless
248	>	* {@link #add(int, Object) add(int, E)} is overridden.
249		*
250		* @throws UnsupportedOperationException {@inheritDoc}
251		* @throws ClassCastException            {@inheritDoc}
#	Line 238 | Line 254 | public abstract class AbstractList<E> ex
254		* @throws IndexOutOfBoundsException     {@inheritDoc}
255		*/
256		public boolean addAll(int index, Collection<? extends E> c) {
257	<	boolean modified = false;
258	<	Iterator<? extends E> e = c.iterator();
259	<	while (e.hasNext()) {
260	<	add(index++, e.next());
261	<	modified = true;
262	<	}
263	<	return modified;
257	>	rangeCheckForAdd(index);
258	>	boolean modified = false;
259	>	for (E e : c) {
260	>	add(index++, e);
261	>	modified = true;
262	>	}
263	>	return modified;
264		}
265
266
267		// Iterators
268
269		/**
270	<	* Returns an iterator over the elements in this list in proper
255	<	* sequence. <p>
270	>	* Returns an iterator over the elements in this list in proper sequence.
271		*
272	<	* This implementation returns a straightforward implementation of the
272	>	* <p>This implementation returns a straightforward implementation of the
273		* iterator interface, relying on the backing list's {@code size()},
274	<	* {@code get(int)}, and {@code remove(int)} methods.<p>
274	>	* {@code get(int)}, and {@code remove(int)} methods.
275		*
276	<	* Note that the iterator returned by this method will throw an
277	<	* {@code UnsupportedOperationException} in response to its
276	>	* <p>Note that the iterator returned by this method will throw an
277	>	* {@link UnsupportedOperationException} in response to its
278		* {@code remove} method unless the list's {@code remove(int)} method is
279	<	* overridden.<p>
279	>	* overridden.
280		*
281	<	* This implementation can be made to throw runtime exceptions in the face
282	<	* of concurrent modification, as described in the specification for the
283	<	* (protected) {@code modCount} field.
281	>	* <p>This implementation can be made to throw runtime exceptions in the
282	>	* face of concurrent modification, as described in the specification
283	>	* for the (protected) {@link #modCount} field.
284		*
285		* @return an iterator over the elements in this list in proper sequence
271	–	*
272	–	* @see #modCount
286		*/
287		public Iterator<E> iterator() {
288	<	return new Itr();
288	>	return new Itr();
289		}
290
291		/**
#	Line 283 | Line 296 | public abstract class AbstractList<E> ex
296		* @see #listIterator(int)
297		*/
298		public ListIterator<E> listIterator() {
299	<	return listIterator(0);
299	>	return listIterator(0);
300		}
301
302		/**
#	Line 293 | Line 306 | public abstract class AbstractList<E> ex
306		* {@code ListIterator} interface that extends the implementation of the
307		* {@code Iterator} interface returned by the {@code iterator()} method.
308		* The {@code ListIterator} implementation relies on the backing list's
309	<	* {@code get(int)}, {@code set(int, Object)}, {@code add(int, Object)}
309	>	* {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
310		* and {@code remove(int)} methods.
311		*
312		* <p>Note that the list iterator returned by this implementation will
313	<	* throw an {@code UnsupportedOperationException} in response to its
313	>	* throw an {@link UnsupportedOperationException} in response to its
314		* {@code remove}, {@code set} and {@code add} methods unless the
315	<	* list's {@code remove(int)}, {@code set(int, Object)}, and
316	<	* {@code add(int, Object)} methods are overridden.
315	>	* list's {@code remove(int)}, {@code set(int, E)}, and
316	>	* {@code add(int, E)} methods are overridden.
317		*
318		* <p>This implementation can be made to throw runtime exceptions in the
319		* face of concurrent modification, as described in the specification for
320	<	* the (protected) {@code modCount} field.
320	>	* the (protected) {@link #modCount} field.
321		*
322		* @throws IndexOutOfBoundsException {@inheritDoc}
310	–	*
311	–	* @see #modCount
323		*/
324		public ListIterator<E> listIterator(final int index) {
325	<	if (index<0 || index>size())
315	<	throw new IndexOutOfBoundsException("Index: "+index);
325	>	rangeCheckForAdd(index);
326
327	<	return new ListItr(index);
327	>	return new ListItr(index);
328		}
329
330		private class Itr implements Iterator<E> {
331	<	/**
332	<	* Index of element to be returned by subsequent call to next.
333	<	*/
334	<	int cursor = 0;
335	<
336	<	/**
337	<	* Index of element returned by most recent call to next or
338	<	* previous.  Reset to -1 if this element is deleted by a call
339	<	* to remove.
340	<	*/
341	<	int lastRet = -1;
342	<
343	<	/**
344	<	* The modCount value that the iterator believes that the backing
345	<	* List should have.  If this expectation is violated, the iterator
346	<	* has detected concurrent modification.
347	<	*/
348	<	int expectedModCount = modCount;
331	>	/**
332	>	* Index of element to be returned by subsequent call to next.
333	>	*/
334	>	int cursor = 0;
335	>
336	>	/**
337	>	* Index of element returned by most recent call to next or
338	>	* previous.  Reset to -1 if this element is deleted by a call
339	>	* to remove.
340	>	*/
341	>	int lastRet = -1;
342	>
343	>	/**
344	>	* The modCount value that the iterator believes that the backing
345	>	* List should have.  If this expectation is violated, the iterator
346	>	* has detected concurrent modification.
347	>	*/
348	>	int expectedModCount = modCount;
349
350	<	public boolean hasNext() {
350	>	public boolean hasNext() {
351		return cursor != size();
352	<	}
352	>	}
353
354	<	public E next() {
354	>	public E next() {
355		checkForComodification();
356	<	try {
357	<	E next = get(cursor);
358	<	lastRet = cursor++;
359	<	return next;
360	<	} catch (IndexOutOfBoundsException e) {
361	<	checkForComodification();
362	<	throw new NoSuchElementException();
363	<	}
364	<	}
365	<
366	<	public void remove() {
367	<	if (lastRet == -1)
368	<	throw new IllegalStateException();
356	>	try {
357	>	int i = cursor;
358	>	E next = get(i);
359	>	lastRet = i;
360	>	cursor = i + 1;
361	>	return next;
362	>	} catch (IndexOutOfBoundsException e) {
363	>	checkForComodification();
364	>	throw new NoSuchElementException();
365	>	}
366	>	}
367	>
368	>	public void remove() {
369	>	if (lastRet < 0)
370	>	throw new IllegalStateException();
371		checkForComodification();
372
373	<	try {
374	<	AbstractList.this.remove(lastRet);
375	<	if (lastRet < cursor)
376	<	cursor--;
377	<	lastRet = -1;
378	<	expectedModCount = modCount;
379	<	} catch (IndexOutOfBoundsException e) {
380	<	throw new ConcurrentModificationException();
381	<	}
382	<	}
383	<
384	<	final void checkForComodification() {
385	<	if (modCount != expectedModCount)
386	<	throw new ConcurrentModificationException();
387	<	}
373	>	try {
374	>	AbstractList.this.remove(lastRet);
375	>	if (lastRet < cursor)
376	>	cursor--;
377	>	lastRet = -1;
378	>	expectedModCount = modCount;
379	>	} catch (IndexOutOfBoundsException e) {
380	>	throw new ConcurrentModificationException();
381	>	}
382	>	}
383	>
384	>	final void checkForComodification() {
385	>	if (modCount != expectedModCount)
386	>	throw new ConcurrentModificationException();
387	>	}
388		}
389
390		private class ListItr extends Itr implements ListIterator<E> {
391	<	ListItr(int index) {
392	<	cursor = index;
393	<	}
394	<
395	<	public boolean hasPrevious() {
396	<	return cursor != 0;
397	<	}
391	>	ListItr(int index) {
392	>	cursor = index;
393	>	}
394	>
395	>	public boolean hasPrevious() {
396	>	return cursor != 0;
397	>	}
398
399		public E previous() {
400		checkForComodification();
#	Line 397 | Line 409 | public abstract class AbstractList<E> ex
409		}
410		}
411
412	<	public int nextIndex() {
413	<	return cursor;
414	<	}
415	<
416	<	public int previousIndex() {
417	<	return cursor-1;
418	<	}
419	<
420	<	public void set(E e) {
421	<	if (lastRet == -1)
422	<	throw new IllegalStateException();
412	>	public int nextIndex() {
413	>	return cursor;
414	>	}
415	>
416	>	public int previousIndex() {
417	>	return cursor-1;
418	>	}
419	>
420	>	public void set(E e) {
421	>	if (lastRet < 0)
422	>	throw new IllegalStateException();
423		checkForComodification();
424
425	<	try {
426	<	AbstractList.this.set(lastRet, e);
427	<	expectedModCount = modCount;
428	<	} catch (IndexOutOfBoundsException ex) {
429	<	throw new ConcurrentModificationException();
430	<	}
431	<	}
425	>	try {
426	>	AbstractList.this.set(lastRet, e);
427	>	expectedModCount = modCount;
428	>	} catch (IndexOutOfBoundsException ex) {
429	>	throw new ConcurrentModificationException();
430	>	}
431	>	}
432
433	<	public void add(E e) {
433	>	public void add(E e) {
434		checkForComodification();
435
436	<	try {
436	>	try {
437		int i = cursor;
438	<	AbstractList.this.add(i, e);
438	>	AbstractList.this.add(i, e);
439	>	lastRet = -1;
440		cursor = i + 1;
441	<	lastRet = -1;
442	<	expectedModCount = modCount;
443	<	} catch (IndexOutOfBoundsException ex) {
444	<	throw new ConcurrentModificationException();
445	<	}
433	<	}
441	>	expectedModCount = modCount;
442	>	} catch (IndexOutOfBoundsException ex) {
443	>	throw new ConcurrentModificationException();
444	>	}
445	>	}
446		}
447
448		/**
#	Line 445 | Line 457 | public abstract class AbstractList<E> ex
457		* If this list implements {@code RandomAccess} the returned list will
458		* be an instance of the subclass that implements {@code RandomAccess}.
459		*
460	<	* <p>The subclass's {@code set(int, Object)}, {@code get(int)},
461	<	* {@code add(int, Object)}, {@code remove(int)}, {@code addAll(int,
460	>	* <p>The subclass's {@code set(int, E)}, {@code get(int)},
461	>	* {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
462		* Collection)} and {@code removeRange(int, int)} methods all
463		* delegate to the corresponding methods on the backing abstract list,
464		* after bounds-checking the index and adjusting for the offset.  The
#	Line 463 | Line 475 | public abstract class AbstractList<E> ex
475		* the backing list is equal to its expected value, and throw a
476		* {@code ConcurrentModificationException} if it is not.
477		*
478	<	* @throws IndexOutOfBoundsException endpoint index value out of range
479	<	*         {@code (fromIndex &lt; 0 || toIndex &gt; size)}
478	>	* @throws IndexOutOfBoundsException if an endpoint index value is out of range
479	>	*         {@code (fromIndex < 0 || toIndex > size)}
480		* @throws IllegalArgumentException if the endpoint indices are out of order
481	<	*         {@code (fromIndex &gt; toIndex)}
481	>	*         {@code (fromIndex > toIndex)}
482		*/
483		public List<E> subList(int fromIndex, int toIndex) {
484		return (this instanceof RandomAccess ?
485	<	new RandomAccessSubList(this, this, fromIndex, fromIndex, toIndex) :
486	<	new SubList(this, this, fromIndex, fromIndex, toIndex));
485	>	new RandomAccessSubList<E>(this, fromIndex, toIndex) :
486	>	new SubList<E>(this, fromIndex, toIndex));
487		}
488
489		// Comparison and hashing
#	Line 498 | Line 510 | public abstract class AbstractList<E> ex
510		* @return {@code true} if the specified object is equal to this list
511		*/
512		public boolean equals(Object o) {
513	<	if (o == this)
514	<	return true;
515	<	if (!(o instanceof List))
516	<	return false;
517	<
518	<	ListIterator<E> e1 = listIterator();
519	<	ListIterator e2 = ((List) o).listIterator();
520	<	while(e1.hasNext() && e2.hasNext()) {
521	<	E o1 = e1.next();
522	<	Object o2 = e2.next();
523	<	if (!(o1==null ? o2==null : o1.equals(o2)))
524	<	return false;
525	<	}
526	<	return !(e1.hasNext() || e2.hasNext());
513	>	if (o == this)
514	>	return true;
515	>	if (!(o instanceof List))
516	>	return false;
517	>
518	>	ListIterator<E> e1 = listIterator();
519	>	ListIterator e2 = ((List) o).listIterator();
520	>	while(e1.hasNext() && e2.hasNext()) {
521	>	E o1 = e1.next();
522	>	Object o2 = e2.next();
523	>	if (!(o1==null ? o2==null : o1.equals(o2)))
524	>	return false;
525	>	}
526	>	return !(e1.hasNext() || e2.hasNext());
527		}
528
529		/**
530	<	* Returns the hash code value for this list. <p>
530	>	* Returns the hash code value for this list.
531		*
532	<	* This implementation uses exactly the code that is used to define the
532	>	* <p>This implementation uses exactly the code that is used to define the
533		* list hash function in the documentation for the {@link List#hashCode}
534		* method.
535		*
536		* @return the hash code value for this list
537		*/
538		public int hashCode() {
539	<	int hashCode = 1;
540	<	Iterator<E> i = iterator();
541	<	while (i.hasNext()) {
542	<	E obj = i.next();
531	<	hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
532	<	}
533	<	return hashCode;
539	>	int hashCode = 1;
540	>	for (E e : this)
541	>	hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
542	>	return hashCode;
543		}
544
545		/**
546		* Removes from this list all of the elements whose index is between
547		* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
548		* Shifts any succeeding elements to the left (reduces their index).
549	<	* This call shortens the ArrayList by {@code (toIndex - fromIndex)}
550	<	* elements.  (If {@code toIndex==fromIndex}, this operation has no
542	<	* effect.)<p>
549	>	* This call shortens the list by {@code (toIndex - fromIndex)} elements.
550	>	* (If {@code toIndex==fromIndex}, this operation has no effect.)
551		*
552	<	* This method is called by the {@code clear} operation on this list
552	>	* <p>This method is called by the {@code clear} operation on this list
553		* and its subLists.  Overriding this method to take advantage of
554		* the internals of the list implementation can <i>substantially</i>
555		* improve the performance of the {@code clear} operation on this list
556	<	* and its subLists.<p>
556	>	* and its subLists.
557		*
558	<	* This implementation gets a list iterator positioned before
558	>	* <p>This implementation gets a list iterator positioned before
559		* {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
560		* followed by {@code ListIterator.remove} until the entire range has
561		* been removed.  <b>Note: if {@code ListIterator.remove} requires linear
#	Line 568 | Line 576 | public abstract class AbstractList<E> ex
576		* The number of times this list has been <i>structurally modified</i>.
577		* Structural modifications are those that change the size of the
578		* list, or otherwise perturb it in such a fashion that iterations in
579	<	* progress may yield incorrect results.<p>
579	>	* progress may yield incorrect results.
580		*
581	<	* This field is used by the iterator and list iterator implementation
581	>	* <p>This field is used by the iterator and list iterator implementation
582		* returned by the {@code iterator} and {@code listIterator} methods.
583		* If the value of this field changes unexpectedly, the iterator (or list
584		* iterator) will throw a {@code ConcurrentModificationException} in
585		* response to the {@code next}, {@code remove}, {@code previous},
586		* {@code set} or {@code add} operations.  This provides
587		* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
588	<	* the face of concurrent modification during iteration.<p>
588	>	* the face of concurrent modification during iteration.
589		*
590	<	* <b>Use of this field by subclasses is optional.</b> If a subclass
590	>	* <p><b>Use of this field by subclasses is optional.</b> If a subclass
591		* wishes to provide fail-fast iterators (and list iterators), then it
592	<	* merely has to increment this field in its {@code add(int, Object)} and
592	>	* merely has to increment this field in its {@code add(int, E)} and
593		* {@code remove(int)} methods (and any other methods that it overrides
594		* that result in structural modifications to the list).  A single call to
595	<	* {@code add(int, Object)} or {@code remove(int)} must add no more than
595	>	* {@code add(int, E)} or {@code remove(int)} must add no more than
596		* one to this field, or the iterators (and list iterators) will throw
597		* bogus {@code ConcurrentModificationExceptions}.  If an implementation
598		* does not wish to provide fail-fast iterators, this field may be
599		* ignored.
600		*/
601		protected transient int modCount = 0;
602	+
603	+	private void rangeCheckForAdd(int index) {
604	+	if (index < 0 || index > size())
605	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
606	+	}
607	+
608	+	private String outOfBoundsMsg(int index) {
609	+	return "Index: "+index+", Size: "+size();
610	+	}
611		}
612
596	–	/**
597	–	* Generic sublists. Non-nested to enable construction by other
598	–	* classes in this package.
599	–	*/
613		class SubList<E> extends AbstractList<E> {
614	<	/*
615	<	* A SubList has both a "base", the ultimate backing list, as well
616	<	* as a "parent", which is the list or sublist creating this
617	<	* sublist. All methods that may cause structural modifications
618	<	* must propagate through the parent link, with O(k) performance
606	<	* where k is sublist depth. For example in the case of a
607	<	* sub-sub-list, invoking remove(x) will result in a chain of
608	<	* three remove calls. However, all other non-structurally
609	<	* modifying methods can bypass this chain, and relay directly to
610	<	* the base list. In particular, doing so signficantly speeds up
611	<	* the performance of iterators for deeply-nested sublists.
612	<	*/
613	<	final AbstractList<E> base;   // Backing list
614	<	final AbstractList<E> parent; // Parent list
615	<	final int baseOffset;         // index wrt base
616	<	final int parentOffset;       // index wrt parent
617	<	int length;                   // Number of elements in this sublist
618	<
619	<	SubList(AbstractList<E> base,
620	<	AbstractList<E> parent,
621	<	int baseIndex,
622	<	int fromIndex,
623	<	int toIndex) {
614	>	private final AbstractList<E> l;
615	>	private final int offset;
616	>	private int size;
617	>
618	>	SubList(AbstractList<E> list, int fromIndex, int toIndex) {
619		if (fromIndex < 0)
620		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
621	<	if (toIndex > parent.size())
621	>	if (toIndex > list.size())
622		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
623		if (fromIndex > toIndex)
624		throw new IllegalArgumentException("fromIndex(" + fromIndex +
625		") > toIndex(" + toIndex + ")");
626	<	this.base = base;
627	<	this.parent = parent;
628	<	this.baseOffset = baseIndex;
629	<	this.parentOffset = fromIndex;
635	<	this.length = toIndex - fromIndex;
636	<	this.modCount = base.modCount;
637	<	}
638	<
639	<	/**
640	<	* Returns an IndexOutOfBoundsException with nicer message
641	<	*/
642	<	private IndexOutOfBoundsException indexError(int index) {
643	<	return new IndexOutOfBoundsException("Index: " + index +
644	<	", Size: " + length);
626	>	l = list;
627	>	offset = fromIndex;
628	>	size = toIndex - fromIndex;
629	>	this.modCount = l.modCount;
630		}
631
632		public E set(int index, E element) {
633	<	if (index < 0 || index >= length)
634	<	throw indexError(index);
635	<	if (base.modCount != modCount)
651	<	throw new ConcurrentModificationException();
652	<	return base.set(index + baseOffset, element);
633	>	rangeCheck(index);
634	>	checkForComodification();
635	>	return l.set(index+offset, element);
636		}
637
638		public E get(int index) {
639	<	if (index < 0 || index >= length)
640	<	throw indexError(index);
641	<	if (base.modCount != modCount)
659	<	throw new ConcurrentModificationException();
660	<	return base.get(index + baseOffset);
639	>	rangeCheck(index);
640	>	checkForComodification();
641	>	return l.get(index+offset);
642		}
643
644		public int size() {
645	<	if (base.modCount != modCount)
646	<	throw new ConcurrentModificationException();
666	<	return length;
645	>	checkForComodification();
646	>	return size;
647		}
648
649		public void add(int index, E element) {
650	<	if (index < 0 || index>length)
651	<	throw indexError(index);
652	<	if (base.modCount != modCount)
653	<	throw new ConcurrentModificationException();
654	<	parent.add(index + parentOffset, element);
675	<	length++;
676	<	modCount = base.modCount;
650	>	rangeCheckForAdd(index);
651	>	checkForComodification();
652	>	l.add(index+offset, element);
653	>	this.modCount = l.modCount;
654	>	size++;
655		}
656
657		public E remove(int index) {
658	<	if (index < 0 || index >= length)
659	<	throw indexError(index);
660	<	if (base.modCount != modCount)
661	<	throw new ConcurrentModificationException();
662	<	E result = parent.remove(index + parentOffset);
685	<	length--;
686	<	modCount = base.modCount;
658	>	rangeCheck(index);
659	>	checkForComodification();
660	>	E result = l.remove(index+offset);
661	>	this.modCount = l.modCount;
662	>	size--;
663		return result;
664		}
665
666		protected void removeRange(int fromIndex, int toIndex) {
667	<	if (base.modCount != modCount)
668	<	throw new ConcurrentModificationException();
669	<	parent.removeRange(fromIndex + parentOffset, toIndex + parentOffset);
670	<	length -= (toIndex-fromIndex);
695	<	modCount = base.modCount;
667	>	checkForComodification();
668	>	l.removeRange(fromIndex+offset, toIndex+offset);
669	>	this.modCount = l.modCount;
670	>	size -= (toIndex-fromIndex);
671		}
672
673		public boolean addAll(Collection<? extends E> c) {
674	<	return addAll(length, c);
674	>	return addAll(size, c);
675		}
676
677		public boolean addAll(int index, Collection<? extends E> c) {
678	<	if (index < 0 || index > length)
704	<	throw indexError(index);
678	>	rangeCheckForAdd(index);
679		int cSize = c.size();
680		if (cSize==0)
681		return false;
682
683	<	if (base.modCount != modCount)
684	<	throw new ConcurrentModificationException();
685	<	parent.addAll(parentOffset + index, c);
686	<	length += cSize;
713	<	modCount = base.modCount;
683	>	checkForComodification();
684	>	l.addAll(offset+index, c);
685	>	this.modCount = l.modCount;
686	>	size += cSize;
687		return true;
688		}
689
717	–	public List<E> subList(int fromIndex, int toIndex) {
718	–	return new SubList(base, this, fromIndex + baseOffset,
719	–	fromIndex, toIndex);
720	–	}
721	–
690		public Iterator<E> iterator() {
691	<	return new SubListIterator(this, 0);
691	>	return listIterator();
692		}
693
694	<	public ListIterator<E> listIterator() {
695	<	return new SubListIterator(this, 0);
696	<	}
729	<
730	<	public ListIterator<E> listIterator(int index) {
731	<	if (index < 0 || index>length)
732	<	throw indexError(index);
733	<	return new SubListIterator(this, index);
734	<	}
694	>	public ListIterator<E> listIterator(final int index) {
695	>	checkForComodification();
696	>	rangeCheckForAdd(index);
697
698	<	/**
699	<	* Generic sublist iterator obeying fastfail semantics via
738	<	* modCount.  The hasNext and next methods locally check for
739	<	* in-range indices before relaying to backing list to get
740	<	* element. If this either encounters an unexpected modCount or
741	<	* fails, the backing list must have been concurrently modified,
742	<	* and is so reported.  The add and remove methods performing
743	<	* structural modifications instead relay them through the
744	<	* sublist.
745	<	*/
746	<	private static final class SubListIterator<E> implements ListIterator<E> {
747	<	final SubList<E> outer;       // Sublist creating this iteraor
748	<	final AbstractList<E> base;   // base list
749	<	final int offset;             // Cursor offset wrt base
750	<	int cursor;                   // Current index
751	<	int fence;                    // Upper bound on cursor
752	<	int lastRet;                  // Index of returned element, or -1
753	<	int expectedModCount;         // Expected modCount of base
754	<
755	<	SubListIterator(SubList<E> list, int index) {
756	<	this.lastRet = -1;
757	<	this.cursor = index;
758	<	this.outer = list;
759	<	this.offset = list.baseOffset;
760	<	this.fence = list.length;
761	<	this.base = list.base;
762	<	this.expectedModCount = base.modCount;
763	<	}
698	>	return new ListIterator<E>() {
699	>	private final ListIterator<E> i = l.listIterator(index+offset);
700
701	<	public boolean hasNext() {
702	<	return cursor < fence;
703	<	}
701	>	public boolean hasNext() {
702	>	return nextIndex() < size;
703	>	}
704
705	<	public boolean hasPrevious() {
706	<	return cursor > 0;
707	<	}
705	>	public E next() {
706	>	if (hasNext())
707	>	return i.next();
708	>	else
709	>	throw new NoSuchElementException();
710	>	}
711
712	<	public int nextIndex() {
713	<	return cursor;
714	<	}
712	>	public boolean hasPrevious() {
713	>	return previousIndex() >= 0;
714	>	}
715
716	<	public int previousIndex() {
717	<	return cursor - 1;
718	<	}
716	>	public E previous() {
717	>	if (hasPrevious())
718	>	return i.previous();
719	>	else
720	>	throw new NoSuchElementException();
721	>	}
722
723	<	public E next() {
724	<	int i = cursor;
783	<	if (cursor >= fence)
784	<	throw new NoSuchElementException();
785	<	if (expectedModCount == base.modCount) {
786	<	try {
787	<	Object next = base.get(i + offset);
788	<	lastRet = i;
789	<	cursor = i + 1;
790	<	return (E)next;
791	<	} catch (IndexOutOfBoundsException fallThrough) {
792	<	}
723	>	public int nextIndex() {
724	>	return i.nextIndex() - offset;
725		}
794	–	throw new ConcurrentModificationException();
795	–	}
726
727	<	public E previous() {
728	<	int i = cursor - 1;
799	<	if (i < 0)
800	<	throw new NoSuchElementException();
801	<	if (expectedModCount == base.modCount) {
802	<	try {
803	<	Object prev = base.get(i + offset);
804	<	lastRet = i;
805	<	cursor = i;
806	<	return (E)prev;
807	<	} catch (IndexOutOfBoundsException fallThrough) {
808	<	}
727	>	public int previousIndex() {
728	>	return i.previousIndex() - offset;
729		}
810	–	throw new ConcurrentModificationException();
811	–	}
730
731	<	public void set(E e) {
732	<	if (lastRet < 0)
733	<	throw new IllegalStateException();
734	<	if (expectedModCount != base.modCount)
817	<	throw new ConcurrentModificationException();
818	<	try {
819	<	outer.set(lastRet, e);
820	<	expectedModCount = base.modCount;
821	<	} catch (IndexOutOfBoundsException ex) {
822	<	throw new ConcurrentModificationException();
731	>	public void remove() {
732	>	i.remove();
733	>	SubList.this.modCount = l.modCount;
734	>	size--;
735		}
824	–	}
736
737	<	public void remove() {
738	<	int i = lastRet;
828	<	if (i < 0)
829	<	throw new IllegalStateException();
830	<	if (expectedModCount != base.modCount)
831	<	throw new ConcurrentModificationException();
832	<	try {
833	<	outer.remove(i);
834	<	if (i < cursor)
835	<	cursor--;
836	<	lastRet = -1;
837	<	fence = outer.length;
838	<	expectedModCount = base.modCount;
839	<	} catch (IndexOutOfBoundsException ex) {
840	<	throw new ConcurrentModificationException();
737	>	public void set(E e) {
738	>	i.set(e);
739		}
842	–	}
740
741	<	public void add(E e) {
742	<	if (expectedModCount != base.modCount)
743	<	throw new ConcurrentModificationException();
744	<	try {
848	<	int i = cursor;
849	<	outer.add(i, e);
850	<	cursor = i + 1;
851	<	lastRet = -1;
852	<	fence = outer.length;
853	<	expectedModCount = base.modCount;
854	<	} catch (IndexOutOfBoundsException ex) {
855	<	throw new ConcurrentModificationException();
741	>	public void add(E e) {
742	>	i.add(e);
743	>	SubList.this.modCount = l.modCount;
744	>	size++;
745		}
746	<	}
746	>	};
747	>	}
748	>
749	>	public List<E> subList(int fromIndex, int toIndex) {
750	>	return new SubList<E>(this, fromIndex, toIndex);
751		}
752
753	+	private void rangeCheck(int index) {
754	+	if (index < 0 || index >= size)
755	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
756	+	}
757	+
758	+	private void rangeCheckForAdd(int index) {
759	+	if (index < 0 || index > size)
760	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
761	+	}
762	+
763	+	private String outOfBoundsMsg(int index) {
764	+	return "Index: "+index+", Size: "+size;
765	+	}
766	+
767	+	private void checkForComodification() {
768	+	if (this.modCount != l.modCount)
769	+	throw new ConcurrentModificationException();
770	+	}
771		}
772
773		class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
774	<	RandomAccessSubList(AbstractList<E> base,
775	<	AbstractList<E> parent, int baseIndex,
865	<	int fromIndex, int toIndex) {
866	<	super(base, parent, baseIndex, fromIndex, toIndex);
774	>	RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
775	>	super(list, fromIndex, toIndex);
776		}
777
778		public List<E> subList(int fromIndex, int toIndex) {
779	<	return new RandomAccessSubList(base, this, fromIndex + baseOffset,
871	<	fromIndex, toIndex);
779	>	return new RandomAccessSubList<E>(this, fromIndex, toIndex);
780		}
781		}
874	–

Diff Legend

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