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.20 by jsr166, Sun May 18 23:59:57 2008 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 <tt>List</tt>
29	>	* This class provides a skeletal implementation of the {@link List}
30		* interface to minimize the effort required to implement this interface
31		* backed by a "random access" data store (such as an array).  For sequential
32	<	* access data (such as a linked list), <tt>AbstractSequentialList</tt> should
33	<	* be used in preference to this class.<p>
32	>	* access data (such as a linked list), {@link AbstractSequentialList} should
33	>	* be used in preference to this class.
34	>	*
35	>	* <p>To implement an unmodifiable list, the programmer needs only to extend
36	>	* this class and provide implementations for the {@link #get(int)} and
37	>	* {@link List#size() size()} methods.
38		*
39	<	* To implement an unmodifiable list, the programmer needs only to extend this
40	<	* class and provide implementations for the <tt>get(int index)</tt> and
41	<	* <tt>size()</tt> methods.<p>
42	<	*
43	<	* To implement a modifiable list, the programmer must additionally override
22	<	* the <tt>set(int index, Object element)</tt> method (which otherwise throws
23	<	* an <tt>UnsupportedOperationException</tt>.  If the list is variable-size
24	<	* the programmer must additionally override the <tt>add(int index, Object
25	<	* element)</tt> and <tt>remove(int index)</tt> methods.<p>
26	<	*
27	<	* The programmer should generally provide a void (no argument) and collection
28	<	* constructor, as per the recommendation in the <tt>Collection</tt> interface
29	<	* specification.<p>
39	>	* <p>To implement a modifiable list, the programmer must additionally
40	>	* override the {@link #set(int, Object) set(int, E)} method (which otherwise
41	>	* throws an {@code UnsupportedOperationException}).  If the list is
42	>	* variable-size the programmer must additionally override the
43	>	* {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods.
44		*
45	<	* Unlike the other abstract collection implementations, the programmer does
45	>	* <p>The programmer should generally provide a void (no argument) and collection
46	>	* constructor, as per the recommendation in the {@link Collection} interface
47	>	* specification.
48	>	*
49	>	* <p>Unlike the other abstract collection implementations, the programmer does
50		* <i>not</i> have to provide an iterator implementation; the iterator and
51		* list iterator are implemented by this class, on top of the "random access"
52	<	* methods: <tt>get(int index)</tt>, <tt>set(int index, E element)</tt>,
53	<	* <tt>add(int index, E element)</tt> and <tt>remove(int index)</tt>.<p>
52	>	* methods:
53	>	* {@link #get(int)},
54	>	* {@link #set(int, Object) set(int, E)},
55	>	* {@link #add(int, Object) add(int, E)} and
56	>	* {@link #remove(int)}.
57		*
58	<	* The documentation for each non-abstract methods in this class describes its
58	>	* <p>The documentation for each non-abstract method in this class describes its
59		* implementation in detail.  Each of these methods may be overridden if the
60	<	* collection being implemented admits a more efficient implementation.<p>
60	>	* collection being implemented admits a more efficient implementation.
61		*
62	<	* This class is a member of the
63	<	* <a href="{@docRoot}/../guide/collections/index.html">
62	>	* <p>This class is a member of the
63	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
64		* Java Collections Framework</a>.
65		*
66		* @author  Josh Bloch
67		* @author  Neal Gafter
47	–	* @version 1.37, 01/18/03
48	–	* @see Collection
49	–	* @see List
50	–	* @see AbstractSequentialList
51	–	* @see AbstractCollection
68		* @since 1.2
69		*/
70
#	Line 71 | Line 87 | public abstract class AbstractList<E> ex
87		* classes should clearly specify in their documentation any restrictions
88		* on what elements may be added.
89		*
90	<	* <p>This implementation calls <tt>add(size(), e)</tt>.
90	>	* <p>This implementation calls {@code add(size(), e)}.
91		*
92		* <p>Note that this implementation throws an
93	<	* <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
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 <tt>true</tt> (as specified by {@link Collection#add})
98	<	* @throws UnsupportedOperationException if the <tt>add</tt> operation
97	>	* @return {@code true} (as specified by {@link Collection#add})
98	>	* @throws UnsupportedOperationException if the {@code add} operation
99		*         is not supported by this list
100		* @throws ClassCastException if the class of the specified element
101		*         prevents it from being added to this list
#	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 104 | Line 120 | public abstract class AbstractList<E> ex
120		* {@inheritDoc}
121		*
122		* <p>This implementation always throws an
123	<	* <tt>UnsupportedOperationException</tt>.
123	>	* {@code UnsupportedOperationException}.
124		*
125		* @throws UnsupportedOperationException {@inheritDoc}
126		* @throws ClassCastException            {@inheritDoc}
#	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		/**
136		* {@inheritDoc}
137		*
138		* <p>This implementation always throws an
139	<	* <tt>UnsupportedOperationException</tt>.
139	>	* {@code UnsupportedOperationException}.
140		*
141		* @throws UnsupportedOperationException {@inheritDoc}
142		* @throws ClassCastException            {@inheritDoc}
#	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		/**
152		* {@inheritDoc}
153		*
154		* <p>This implementation always throws an
155	<	* <tt>UnsupportedOperationException</tt>.
155	>	* {@code UnsupportedOperationException}.
156		*
157		* @throws UnsupportedOperationException {@inheritDoc}
158		* @throws IndexOutOfBoundsException     {@inheritDoc}
159		*/
160		public E remove(int index) {
161	<	throw new UnsupportedOperationException();
161	>	throw new UnsupportedOperationException();
162		}
163
164
#	Line 152 | Line 168 | public abstract class AbstractList<E> ex
168		* {@inheritDoc}
169		*
170		* <p>This implementation first gets a list iterator (with
171	<	* <tt>listIterator()</tt>).  Then, it iterates over the list until the
171	>	* {@code listIterator()}).  Then, it iterates over the list until the
172		* specified element is found or the end of the list is reached.
173		*
174		* @throws ClassCastException   {@inheritDoc}
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		/**
192		* {@inheritDoc}
193		*
194		* <p>This implementation first gets a list iterator that points to the end
195	<	* of the list (with <tt>listIterator(size())</tt>).  Then, it iterates
195	>	* of the list (with {@code listIterator(size())}).  Then, it iterates
196		* backwards over the list until the specified element is found, or the
197		* beginning of the list is reached.
198		*
#	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 204 | Line 220 | public abstract class AbstractList<E> ex
220		* Removes all of the elements from this list (optional operation).
221		* The list will be empty after this call returns.
222		*
223	<	* <p>This implementation calls <tt>removeRange(0, size())</tt>.
223	>	* <p>This implementation calls {@code removeRange(0, size())}.
224		*
225		* <p>Note that this implementation throws an
226	<	* <tt>UnsupportedOperationException</tt> unless <tt>remove(int
227	<	* index)</tt> or <tt>removeRange(int fromIndex, int toIndex)</tt> is
226	>	* {@code UnsupportedOperationException} unless {@code remove(int
227	>	* index)} or {@code removeRange(int fromIndex, int toIndex)} is
228		* overridden.
229		*
230	<	* @throws UnsupportedOperationException if the <tt>clear</tt> operation
230	>	* @throws UnsupportedOperationException if the {@code clear} operation
231		*         is not supported by this list
232		*/
233		public void clear() {
#	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	<	* <tt>add(int, Object)</tt>.  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	<	* <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
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	>	Iterator<? extends E> e = c.iterator();
260	>	while (e.hasNext()) {
261	>	add(index++, e.next());
262	>	modified = true;
263	>	}
264	>	return modified;
265		}
266
267
268		// Iterators
269
270		/**
271	<	* Returns an iterator over the elements in this list in proper
255	<	* sequence. <p>
271	>	* Returns an iterator over the elements in this list in proper sequence.
272		*
273	<	* This implementation returns a straightforward implementation of the
274	<	* iterator interface, relying on the backing list's <tt>size()</tt>,
275	<	* <tt>get(int)</tt>, and <tt>remove(int)</tt> methods.<p>
260	<	*
261	<	* Note that the iterator returned by this method will throw an
262	<	* <tt>UnsupportedOperationException</tt> in response to its
263	<	* <tt>remove</tt> method unless the list's <tt>remove(int)</tt> method is
264	<	* overridden.<p>
265	<	*
266	<	* This implementation can be made to throw runtime exceptions in the face
267	<	* of concurrent modification, as described in the specification for the
268	<	* (protected) <tt>modCount</tt> field.
273	>	* <p>This implementation returns a straightforward implementation of the
274	>	* iterator interface, relying on the backing list's {@code size()},
275	>	* {@code get(int)}, and {@code remove(int)} methods.
276		*
277	<	* @return an iterator over the elements in this list in proper sequence
277	>	* <p>Note that the iterator returned by this method will throw an
278	>	* {@link UnsupportedOperationException} in response to its
279	>	* {@code remove} method unless the list's {@code remove(int)} method is
280	>	* overridden.
281		*
282	<	* @see #modCount
282	>	* <p>This implementation can be made to throw runtime exceptions in the
283	>	* face of concurrent modification, as described in the specification
284	>	* for the (protected) {@link #modCount} field.
285	>	*
286	>	* @return an iterator over the elements in this list in proper sequence
287		*/
288		public Iterator<E> iterator() {
289	<	return new Itr();
289	>	return new Itr();
290		}
291
292		/**
293		* {@inheritDoc}
294		*
295	<	* <p>This implementation returns <tt>listIterator(0)</tt>.
295	>	* <p>This implementation returns {@code listIterator(0)}.
296		*
297		* @see #listIterator(int)
298		*/
299		public ListIterator<E> listIterator() {
300	<	return listIterator(0);
300	>	return listIterator(0);
301		}
302
303		/**
304		* {@inheritDoc}
305		*
306		* <p>This implementation returns a straightforward implementation of the
307	<	* <tt>ListIterator</tt> interface that extends the implementation of the
308	<	* <tt>Iterator</tt> interface returned by the <tt>iterator()</tt> method.
309	<	* The <tt>ListIterator</tt> implementation relies on the backing list's
310	<	* <tt>get(int)</tt>, <tt>set(int, Object)</tt>, <tt>add(int, Object)</tt>
311	<	* and <tt>remove(int)</tt> methods.
307	>	* {@code ListIterator} interface that extends the implementation of the
308	>	* {@code Iterator} interface returned by the {@code iterator()} method.
309	>	* The {@code ListIterator} implementation relies on the backing list's
310	>	* {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
311	>	* and {@code remove(int)} methods.
312		*
313		* <p>Note that the list iterator returned by this implementation will
314	<	* throw an <tt>UnsupportedOperationException</tt> in response to its
315	<	* <tt>remove</tt>, <tt>set</tt> and <tt>add</tt> methods unless the
316	<	* list's <tt>remove(int)</tt>, <tt>set(int, Object)</tt>, and
317	<	* <tt>add(int, Object)</tt> methods are overridden.
314	>	* throw an {@link UnsupportedOperationException} in response to its
315	>	* {@code remove}, {@code set} and {@code add} methods unless the
316	>	* list's {@code remove(int)}, {@code set(int, E)}, and
317	>	* {@code add(int, E)} methods are overridden.
318		*
319		* <p>This implementation can be made to throw runtime exceptions in the
320		* face of concurrent modification, as described in the specification for
321	<	* the (protected) <tt>modCount</tt> field.
321	>	* the (protected) {@link #modCount} field.
322		*
323		* @throws IndexOutOfBoundsException {@inheritDoc}
310	–	*
311	–	* @see #modCount
324		*/
325		public ListIterator<E> listIterator(final int index) {
326	<	if (index<0 || index>size())
315	<	throw new IndexOutOfBoundsException("Index: "+index);
326	>	rangeCheckForAdd(index);
327
328	<	return new ListItr(index);
328	>	return new ListItr(index);
329		}
330
331		private class Itr implements Iterator<E> {
332	<	/**
333	<	* Index of element to be returned by subsequent call to next.
334	<	*/
335	<	int cursor = 0;
336	<
337	<	/**
338	<	* Index of element returned by most recent call to next or
339	<	* previous.  Reset to -1 if this element is deleted by a call
340	<	* to remove.
341	<	*/
342	<	int lastRet = -1;
343	<
344	<	/**
345	<	* The modCount value that the iterator believes that the backing
346	<	* List should have.  If this expectation is violated, the iterator
347	<	* has detected concurrent modification.
348	<	*/
349	<	int expectedModCount = modCount;
332	>	/**
333	>	* Index of element to be returned by subsequent call to next.
334	>	*/
335	>	int cursor = 0;
336	>
337	>	/**
338	>	* Index of element returned by most recent call to next or
339	>	* previous.  Reset to -1 if this element is deleted by a call
340	>	* to remove.
341	>	*/
342	>	int lastRet = -1;
343	>
344	>	/**
345	>	* The modCount value that the iterator believes that the backing
346	>	* List should have.  If this expectation is violated, the iterator
347	>	* has detected concurrent modification.
348	>	*/
349	>	int expectedModCount = modCount;
350
351	<	public boolean hasNext() {
351	>	public boolean hasNext() {
352		return cursor != size();
353	<	}
353	>	}
354
355	<	public E next() {
355	>	public E next() {
356	>	checkForComodification();
357		try {
358		int i = cursor;
359		E next = get(i);
360		lastRet = i;
361		cursor = i + 1;
362		return next;
363	<	} catch (IndexOutOfBoundsException ex) {
363	>	} catch (IndexOutOfBoundsException e) {
364	>	checkForComodification();
365		throw new NoSuchElementException();
366	<	} finally {
367	<	if (expectedModCount != modCount)
368	<	throw new ConcurrentModificationException();
369	<	}
370	<	}
371	<
372	<	public void remove() {
373	<	if (lastRet == -1)
374	<	throw new IllegalStateException();
375	<	if (expectedModCount != modCount)
376	<	throw new ConcurrentModificationException();
377	<	try {
378	<	AbstractList.this.remove(lastRet);
379	<	if (lastRet < cursor)
380	<	cursor--;
381	<	lastRet = -1;
382	<	expectedModCount = modCount;
383	<	} catch (IndexOutOfBoundsException e) {
384	<	throw new ConcurrentModificationException();
385	<	}
386	<	}
366	>	}
367	>	}
368	>
369	>	public void remove() {
370	>	if (lastRet < 0)
371	>	throw new IllegalStateException();
372	>	checkForComodification();
373	>
374	>	try {
375	>	AbstractList.this.remove(lastRet);
376	>	if (lastRet < cursor)
377	>	cursor--;
378	>	lastRet = -1;
379	>	expectedModCount = modCount;
380	>	} catch (IndexOutOfBoundsException e) {
381	>	throw new ConcurrentModificationException();
382	>	}
383	>	}
384	>
385	>	final void checkForComodification() {
386	>	if (modCount != expectedModCount)
387	>	throw new ConcurrentModificationException();
388	>	}
389		}
390	<
390	>
391		private class ListItr extends Itr implements ListIterator<E> {
392	<	ListItr(int index) {
393	<	cursor = index;
394	<	}
395	<
396	<	public boolean hasPrevious() {
397	<	return cursor != 0;
398	<	}
384	<
385	<	public int nextIndex() {
386	<	return cursor;
387	<	}
388	<
389	<	public int previousIndex() {
390	<	return cursor - 1;
391	<	}
392	>	ListItr(int index) {
393	>	cursor = index;
394	>	}
395	>
396	>	public boolean hasPrevious() {
397	>	return cursor != 0;
398	>	}
399
400		public E previous() {
401	+	checkForComodification();
402		try {
403		int i = cursor - 1;
404	<	E prev = get(i);
405	<	lastRet = i;
406	<	cursor = i;
407	<	return prev;
408	<	} catch (IndexOutOfBoundsException ex) {
404	>	E previous = get(i);
405	>	lastRet = cursor = i;
406	>	return previous;
407	>	} catch (IndexOutOfBoundsException e) {
408	>	checkForComodification();
409		throw new NoSuchElementException();
402	–	} finally {
403	–	if (expectedModCount != modCount)
404	–	throw new ConcurrentModificationException();
410		}
411		}
412
413	<	public void set(E e) {
414	<	if (lastRet == -1)
415	<	throw new IllegalStateException();
416	<	if (expectedModCount != modCount)
417	<	throw new ConcurrentModificationException();
418	<	try {
419	<	AbstractList.this.set(lastRet, e);
415	<	expectedModCount = modCount;
416	<	} catch (IndexOutOfBoundsException ex) {
417	<	throw new ConcurrentModificationException();
418	<	}
419	<	}
413	>	public int nextIndex() {
414	>	return cursor;
415	>	}
416	>
417	>	public int previousIndex() {
418	>	return cursor-1;
419	>	}
420
421	<	public void add(E e) {
422	<	if (expectedModCount != modCount)
421	>	public void set(E e) {
422	>	if (lastRet < 0)
423	>	throw new IllegalStateException();
424	>	checkForComodification();
425	>
426	>	try {
427	>	AbstractList.this.set(lastRet, e);
428	>	expectedModCount = modCount;
429	>	} catch (IndexOutOfBoundsException ex) {
430		throw new ConcurrentModificationException();
431	<	try {
431	>	}
432	>	}
433	>
434	>	public void add(E e) {
435	>	checkForComodification();
436	>
437	>	try {
438		int i = cursor;
439	<	AbstractList.this.add(i, e);
439	>	AbstractList.this.add(i, e);
440	>	lastRet = -1;
441		cursor = i + 1;
442	<	lastRet = -1;
443	<	expectedModCount = modCount;
444	<	} catch (IndexOutOfBoundsException ex) {
445	<	throw new ConcurrentModificationException();
446	<	}
433	<	}
442	>	expectedModCount = modCount;
443	>	} catch (IndexOutOfBoundsException ex) {
444	>	throw new ConcurrentModificationException();
445	>	}
446	>	}
447		}
448
449		/**
450		* {@inheritDoc}
451		*
452		* <p>This implementation returns a list that subclasses
453	<	* <tt>AbstractList</tt>.  The subclass stores, in private fields, the
453	>	* {@code AbstractList}.  The subclass stores, in private fields, the
454		* offset of the subList within the backing list, the size of the subList
455		* (which can change over its lifetime), and the expected
456	<	* <tt>modCount</tt> value of the backing list.  There are two variants
457	<	* of the subclass, one of which implements <tt>RandomAccess</tt>.
458	<	* If this list implements <tt>RandomAccess</tt> the returned list will
459	<	* be an instance of the subclass that implements <tt>RandomAccess</tt>.
460	<	*
461	<	* <p>The subclass's <tt>set(int, Object)</tt>, <tt>get(int)</tt>,
462	<	* <tt>add(int, Object)</tt>, <tt>remove(int)</tt>, <tt>addAll(int,
463	<	* Collection)</tt> and <tt>removeRange(int, int)</tt> methods all
456	>	* {@code modCount} value of the backing list.  There are two variants
457	>	* of the subclass, one of which implements {@code RandomAccess}.
458	>	* If this list implements {@code RandomAccess} the returned list will
459	>	* be an instance of the subclass that implements {@code RandomAccess}.
460	>	*
461	>	* <p>The subclass's {@code set(int, E)}, {@code get(int)},
462	>	* {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
463	>	* Collection)} and {@code removeRange(int, int)} methods all
464		* delegate to the corresponding methods on the backing abstract list,
465		* after bounds-checking the index and adjusting for the offset.  The
466	<	* <tt>addAll(Collection c)</tt> method merely returns <tt>addAll(size,
467	<	* c)</tt>.
466	>	* {@code addAll(Collection c)} method merely returns {@code addAll(size,
467	>	* c)}.
468		*
469	<	* <p>The <tt>listIterator(int)</tt> method returns a "wrapper object"
469	>	* <p>The {@code listIterator(int)} method returns a "wrapper object"
470		* over a list iterator on the backing list, which is created with the
471	<	* corresponding method on the backing list.  The <tt>iterator</tt> method
472	<	* merely returns <tt>listIterator()</tt>, and the <tt>size</tt> method
473	<	* merely returns the subclass's <tt>size</tt> field.
471	>	* corresponding method on the backing list.  The {@code iterator} method
472	>	* merely returns {@code listIterator()}, and the {@code size} method
473	>	* merely returns the subclass's {@code size} field.
474		*
475	<	* <p>All methods first check to see if the actual <tt>modCount</tt> of
475	>	* <p>All methods first check to see if the actual {@code modCount} of
476		* the backing list is equal to its expected value, and throw a
477	<	* <tt>ConcurrentModificationException</tt> if it is not.
477	>	* {@code ConcurrentModificationException} if it is not.
478		*
479	<	* @throws IndexOutOfBoundsException endpoint index value out of range
480	<	*         <tt>(fromIndex &lt; 0 || toIndex &gt; size)</tt>
479	>	* @throws IndexOutOfBoundsException if an endpoint index value is out of range
480	>	*         {@code (fromIndex < 0 || toIndex > size)}
481		* @throws IllegalArgumentException if the endpoint indices are out of order
482	<	*         <tt>(fromIndex &gt; toIndex)</tt>
482	>	*         {@code (fromIndex > toIndex)}
483		*/
484		public List<E> subList(int fromIndex, int toIndex) {
485		return (this instanceof RandomAccess ?
#	Line 478 | Line 491 | public abstract class AbstractList<E> ex
491
492		/**
493		* Compares the specified object with this list for equality.  Returns
494	<	* <tt>true</tt> if and only if the specified object is also a list, both
494	>	* {@code true} if and only if the specified object is also a list, both
495		* lists have the same size, and all corresponding pairs of elements in
496	<	* the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
497	<	* <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
498	<	* e1.equals(e2))</tt>.)  In other words, two lists are defined to be
496	>	* the two lists are <i>equal</i>.  (Two elements {@code e1} and
497	>	* {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
498	>	* e1.equals(e2))}.)  In other words, two lists are defined to be
499		* equal if they contain the same elements in the same order.<p>
500		*
501		* This implementation first checks if the specified object is this
502	<	* list. If so, it returns <tt>true</tt>; if not, it checks if the
503	<	* specified object is a list. If not, it returns <tt>false</tt>; if so,
502	>	* list. If so, it returns {@code true}; if not, it checks if the
503	>	* specified object is a list. If not, it returns {@code false}; if so,
504		* it iterates over both lists, comparing corresponding pairs of elements.
505	<	* If any comparison returns <tt>false</tt>, this method returns
506	<	* <tt>false</tt>.  If either iterator runs out of elements before the
507	<	* other it returns <tt>false</tt> (as the lists are of unequal length);
508	<	* otherwise it returns <tt>true</tt> when the iterations complete.
505	>	* If any comparison returns {@code false}, this method returns
506	>	* {@code false}.  If either iterator runs out of elements before the
507	>	* other it returns {@code false} (as the lists are of unequal length);
508	>	* otherwise it returns {@code true} when the iterations complete.
509		*
510		* @param o the object to be compared for equality with this list
511	<	* @return <tt>true</tt> if the specified object is equal to this list
511	>	* @return {@code true} if the specified object is equal to this list
512		*/
513		public boolean equals(Object o) {
514	<	if (o == this)
515	<	return true;
516	<	if (!(o instanceof List))
517	<	return false;
518	<
519	<	ListIterator<E> e1 = listIterator();
520	<	ListIterator e2 = ((List) o).listIterator();
521	<	while(e1.hasNext() && e2.hasNext()) {
522	<	E o1 = e1.next();
523	<	Object o2 = e2.next();
524	<	if (!(o1==null ? o2==null : o1.equals(o2)))
525	<	return false;
526	<	}
527	<	return !(e1.hasNext() || e2.hasNext());
514	>	if (o == this)
515	>	return true;
516	>	if (!(o instanceof List))
517	>	return false;
518	>
519	>	ListIterator<E> e1 = listIterator();
520	>	ListIterator e2 = ((List) o).listIterator();
521	>	while(e1.hasNext() && e2.hasNext()) {
522	>	E o1 = e1.next();
523	>	Object o2 = e2.next();
524	>	if (!(o1==null ? o2==null : o1.equals(o2)))
525	>	return false;
526	>	}
527	>	return !(e1.hasNext() || e2.hasNext());
528		}
529
530		/**
531	<	* Returns the hash code value for this list. <p>
531	>	* Returns the hash code value for this list.
532		*
533	<	* This implementation uses exactly the code that is used to define the
533	>	* <p>This implementation uses exactly the code that is used to define the
534		* list hash function in the documentation for the {@link List#hashCode}
535		* method.
536		*
537		* @return the hash code value for this list
538		*/
539		public int hashCode() {
540	<	int hashCode = 1;
541	<	Iterator<E> i = iterator();
542	<	while (i.hasNext()) {
543	<	E obj = i.next();
531	<	hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
532	<	}
533	<	return hashCode;
540	>	int hashCode = 1;
541	>	for (E e : this)
542	>	hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
543	>	return hashCode;
544		}
545
546		/**
547		* Removes from this list all of the elements whose index is between
548	<	* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
548	>	* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
549		* Shifts any succeeding elements to the left (reduces their index).
550	<	* This call shortens the ArrayList by <tt>(toIndex - fromIndex)</tt>
551	<	* elements.  (If <tt>toIndex==fromIndex</tt>, this operation has no
542	<	* effect.)<p>
550	>	* This call shortens the list by {@code (toIndex - fromIndex)} elements.
551	>	* (If {@code toIndex==fromIndex}, this operation has no effect.)
552		*
553	<	* This method is called by the <tt>clear</tt> operation on this list
553	>	* <p>This method is called by the {@code clear} operation on this list
554		* and its subLists.  Overriding this method to take advantage of
555		* the internals of the list implementation can <i>substantially</i>
556	<	* improve the performance of the <tt>clear</tt> operation on this list
557	<	* and its subLists.<p>
556	>	* improve the performance of the {@code clear} operation on this list
557	>	* and its subLists.
558		*
559	<	* This implementation gets a list iterator positioned before
560	<	* <tt>fromIndex</tt>, and repeatedly calls <tt>ListIterator.next</tt>
561	<	* followed by <tt>ListIterator.remove</tt> until the entire range has
562	<	* been removed.  <b>Note: if <tt>ListIterator.remove</tt> requires linear
559	>	* <p>This implementation gets a list iterator positioned before
560	>	* {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
561	>	* followed by {@code ListIterator.remove} until the entire range has
562	>	* been removed.  <b>Note: if {@code ListIterator.remove} requires linear
563		* time, this implementation requires quadratic time.</b>
564		*
565		* @param fromIndex index of first element to be removed
#	Line 568 | Line 577 | public abstract class AbstractList<E> ex
577		* The number of times this list has been <i>structurally modified</i>.
578		* Structural modifications are those that change the size of the
579		* list, or otherwise perturb it in such a fashion that iterations in
580	<	* progress may yield incorrect results.<p>
580	>	* progress may yield incorrect results.
581		*
582	<	* This field is used by the iterator and list iterator implementation
583	<	* returned by the <tt>iterator</tt> and <tt>listIterator</tt> methods.
582	>	* <p>This field is used by the iterator and list iterator implementation
583	>	* returned by the {@code iterator} and {@code listIterator} methods.
584		* If the value of this field changes unexpectedly, the iterator (or list
585	<	* iterator) will throw a <tt>ConcurrentModificationException</tt> in
586	<	* response to the <tt>next</tt>, <tt>remove</tt>, <tt>previous</tt>,
587	<	* <tt>set</tt> or <tt>add</tt> operations.  This provides
585	>	* iterator) will throw a {@code ConcurrentModificationException} in
586	>	* response to the {@code next}, {@code remove}, {@code previous},
587	>	* {@code set} or {@code add} operations.  This provides
588		* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
589	<	* the face of concurrent modification during iteration.<p>
589	>	* the face of concurrent modification during iteration.
590		*
591	<	* <b>Use of this field by subclasses is optional.</b> If a subclass
591	>	* <p><b>Use of this field by subclasses is optional.</b> If a subclass
592		* wishes to provide fail-fast iterators (and list iterators), then it
593	<	* merely has to increment this field in its <tt>add(int, Object)</tt> and
594	<	* <tt>remove(int)</tt> methods (and any other methods that it overrides
593	>	* merely has to increment this field in its {@code add(int, E)} and
594	>	* {@code remove(int)} methods (and any other methods that it overrides
595		* that result in structural modifications to the list).  A single call to
596	<	* <tt>add(int, Object)</tt> or <tt>remove(int)</tt> must add no more than
596	>	* {@code add(int, E)} or {@code remove(int)} must add no more than
597		* one to this field, or the iterators (and list iterators) will throw
598	<	* bogus <tt>ConcurrentModificationExceptions</tt>.  If an implementation
598	>	* bogus {@code ConcurrentModificationExceptions}.  If an implementation
599		* does not wish to provide fail-fast iterators, this field may be
600		* ignored.
601		*/
602		protected transient int modCount = 0;
603	+
604	+	private void rangeCheckForAdd(int index) {
605	+	if (index < 0 || index > size())
606	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
607	+	}
608	+
609	+	private String outOfBoundsMsg(int index) {
610	+	return "Index: "+index+", Size: "+size();
611	+	}
612		}
613
614		class SubList<E> extends AbstractList<E> {
615	<	private AbstractList<E> l;
616	<	private int offset;
615	>	private final AbstractList<E> l;
616	>	private final int offset;
617		private int size;
600	–	private int expectedModCount;
618
619		SubList(AbstractList<E> list, int fromIndex, int toIndex) {
620		if (fromIndex < 0)
#	Line 610 | Line 627 | class SubList<E> extends AbstractList<E>
627		l = list;
628		offset = fromIndex;
629		size = toIndex - fromIndex;
630	<	expectedModCount = l.modCount;
630	>	this.modCount = l.modCount;
631		}
632
633		public E set(int index, E element) {
#	Line 631 | Line 648 | class SubList<E> extends AbstractList<E>
648		}
649
650		public void add(int index, E element) {
651	<	if (index<0 || index>size)
635	<	throw new IndexOutOfBoundsException();
651	>	rangeCheckForAdd(index);
652		checkForComodification();
653		l.add(index+offset, element);
654	<	expectedModCount = l.modCount;
654	>	this.modCount = l.modCount;
655		size++;
640	–	modCount++;
656		}
657
658		public E remove(int index) {
659		rangeCheck(index);
660		checkForComodification();
661		E result = l.remove(index+offset);
662	<	expectedModCount = l.modCount;
662	>	this.modCount = l.modCount;
663		size--;
649	–	modCount++;
664		return result;
665		}
666
667		protected void removeRange(int fromIndex, int toIndex) {
668		checkForComodification();
669		l.removeRange(fromIndex+offset, toIndex+offset);
670	<	expectedModCount = l.modCount;
670	>	this.modCount = l.modCount;
671		size -= (toIndex-fromIndex);
658	–	modCount++;
672		}
673
674		public boolean addAll(Collection<? extends E> c) {
#	Line 663 | Line 676 | class SubList<E> extends AbstractList<E>
676		}
677
678		public boolean addAll(int index, Collection<? extends E> c) {
679	<	if (index<0 || index>size)
667	<	throw new IndexOutOfBoundsException(
668	<	"Index: "+index+", Size: "+size);
679	>	rangeCheckForAdd(index);
680		int cSize = c.size();
681		if (cSize==0)
682		return false;
683
684		checkForComodification();
685		l.addAll(offset+index, c);
686	<	expectedModCount = l.modCount;
686	>	this.modCount = l.modCount;
687		size += cSize;
677	–	modCount++;
688		return true;
689		}
690
#	Line 684 | Line 694 | class SubList<E> extends AbstractList<E>
694
695		public ListIterator<E> listIterator(final int index) {
696		checkForComodification();
697	<	if (index<0 || index>size)
688	<	throw new IndexOutOfBoundsException(
689	<	"Index: "+index+", Size: "+size);
697	>	rangeCheckForAdd(index);
698
699		return new ListIterator<E>() {
700	<	private ListIterator<E> i = l.listIterator(index+offset);
700	>	private final ListIterator<E> i = l.listIterator(index+offset);
701
702		public boolean hasNext() {
703		return nextIndex() < size;
#	Line 723 | Line 731 | class SubList<E> extends AbstractList<E>
731
732		public void remove() {
733		i.remove();
734	<	expectedModCount = l.modCount;
734	>	SubList.this.modCount = l.modCount;
735		size--;
728	–	modCount++;
736		}
737
738		public void set(E e) {
#	Line 734 | Line 741 | class SubList<E> extends AbstractList<E>
741
742		public void add(E e) {
743		i.add(e);
744	<	expectedModCount = l.modCount;
744	>	SubList.this.modCount = l.modCount;
745		size++;
739	–	modCount++;
746		}
747		};
748		}
#	Line 746 | Line 752 | class SubList<E> extends AbstractList<E>
752		}
753
754		private void rangeCheck(int index) {
755	<	if (index<0 || index>=size)
756	<	throw new IndexOutOfBoundsException("Index: "+index+
757	<	",Size: "+size);
755	>	if (index < 0 || index >= size)
756	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
757	>	}
758	>
759	>	private void rangeCheckForAdd(int index) {
760	>	if (index < 0 || index > size)
761	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
762	>	}
763	>
764	>	private String outOfBoundsMsg(int index) {
765	>	return "Index: "+index+", Size: "+size;
766		}
767
768		private void checkForComodification() {
769	<	if (l.modCount != expectedModCount)
769	>	if (this.modCount != l.modCount)
770		throw new ConcurrentModificationException();
771		}
772		}

Diff Legend

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