001: /*
002: * @(#)AbstractList.java 1.40 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.util;
029:
030: /**
031: * This class provides a skeletal implementation of the <tt>List</tt>
032: * interface to minimize the effort required to implement this interface
033: * backed by a "random access" data store (such as an array). For sequential
034: * access data (such as a linked list), <tt>AbstractSequentialList</tt> should
035: * be used in preference to this class.<p>
036: *
037: * To implement an unmodifiable list, the programmer needs only to extend this
038: * class and provide implementations for the <tt>get(int index)</tt> and
039: * <tt>size()</tt> methods.<p>
040: *
041: * To implement a modifiable list, the programmer must additionally override
042: * the <tt>set(int index, Object element)</tt> method (which otherwise throws
043: * an <tt>UnsupportedOperationException</tt>. If the list is variable-size
044: * the programmer must additionally override the <tt>add(int index, Object
045: * element)</tt> and <tt>remove(int index)</tt> methods.<p>
046: *
047: * The programmer should generally provide a void (no argument) and collection
048: * constructor, as per the recommendation in the <tt>Collection</tt> interface
049: * specification.<p>
050: *
051: * Unlike the other abstract collection implementations, the programmer does
052: * <i>not</i> have to provide an iterator implementation; the iterator and
053: * list iterator are implemented by this class, on top the "random access"
054: * methods: <tt>get(int index)</tt>, <tt>set(int index, Object element)</tt>,
055: * <tt>set(int index, Object element)</tt>, <tt>add(int index, Object
056: * element)</tt> and <tt>remove(int index)</tt>.<p>
057: *
058: * The documentation for each non-abstract methods in this class describes its
059: * implementation in detail. Each of these methods may be overridden if the
060: * collection being implemented admits a more efficient implementation.<p>
061: *
062: * This class is a member of the
063: * <a href="{@docRoot}/../guide/collections/index.html">
064: * Java Collections Framework</a>.
065: *
066: * @author Josh Bloch
067: * @version 1.31, 02/02/00
068: * @see Collection
069: * @see List
070: * @see AbstractSequentialList
071: * @see AbstractCollection
072: * @since 1.2
073: */
074:
075: public abstract class AbstractList extends AbstractCollection implements
076: List {
077: /**
078: * Sole constructor. (For invocation by subclass constructors, typically
079: * implicit.)
080: */
081: protected AbstractList() {
082: }
083:
084: /**
085: * Appends the specified element to the end of this List (optional
086: * operation). <p>
087: *
088: * This implementation calls <tt>add(size(), o)</tt>.<p>
089: *
090: * Note that this implementation throws an
091: * <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
092: * is overridden.
093: *
094: * @param o element to be appended to this list.
095: *
096: * @return <tt>true</tt> (as per the general contract of
097: * <tt>Collection.add</tt>).
098: *
099: * @throws UnsupportedOperationException if the <tt>add</tt> method is not
100: * supported by this Set.
101: *
102: * @throws ClassCastException if the class of the specified element
103: * prevents it from being added to this set.
104: *
105: * @throws IllegalArgumentException some aspect of this element prevents
106: * it from being added to this collection.
107: */
108: public boolean add(Object o) {
109: add(size(), o);
110: return true;
111: }
112:
113: /**
114: * Returns the element at the specified position in this list.
115: *
116: * @param index index of element to return.
117: *
118: * @return the element at the specified position in this list.
119: * @throws IndexOutOfBoundsException if the given index is out of range
120: * (<tt>index < 0 || index >= size()</tt>).
121: */
122: abstract public Object get(int index);
123:
124: /**
125: * Replaces the element at the specified position in this list with the
126: * specified element (optional operation). <p>
127: *
128: * This implementation always throws an
129: * <tt>UnsupportedOperationException</tt>.
130: *
131: * @param index index of element to replace.
132: * @param element element to be stored at the specified position.
133: * @return the element previously at the specified position.
134: *
135: * @throws UnsupportedOperationException if the <tt>set</tt> method is not
136: * supported by this List.
137: * @throws ClassCastException if the class of the specified element
138: * prevents it from being added to this list.
139: * @throws IllegalArgumentException if some aspect of the specified
140: * element prevents it from being added to this list.
141: *
142: * @throws IndexOutOfBoundsException if the specified index is out of
143: * range (<tt>index < 0 || index >= size()</tt>).
144: */
145:
146: public Object set(int index, Object element) {
147: throw new UnsupportedOperationException();
148: }
149:
150: /**
151: * Inserts the specified element at the specified position in this list
152: * (optional operation). Shifts the element currently at that position
153: * (if any) and any subsequent elements to the right (adds one to their
154: * indices).<p>
155: *
156: * This implementation always throws an UnsupportedOperationException.
157: *
158: * @param index index at which the specified element is to be inserted.
159: * @param element element to be inserted.
160: *
161: * @throws UnsupportedOperationException if the <tt>add</tt> method is not
162: * supported by this list.
163: * @throws ClassCastException if the class of the specified element
164: * prevents it from being added to this list.
165: * @throws IllegalArgumentException if some aspect of the specified
166: * element prevents it from being added to this list.
167: * @throws IndexOutOfBoundsException index is out of range (<tt>index <
168: * 0 || index > size()</tt>).
169: */
170: public void add(int index, Object element) {
171: throw new UnsupportedOperationException();
172: }
173:
174: /**
175: * Removes the element at the specified position in this list (optional
176: * operation). Shifts any subsequent elements to the left (subtracts one
177: * from their indices). Returns the element that was removed from the
178: * list.<p>
179: *
180: * This implementation always throws an
181: * <tt>UnsupportedOperationException</tt>.
182: *
183: * @param index the index of the element to remove.
184: * @return the element previously at the specified position.
185: *
186: * @throws UnsupportedOperationException if the <tt>remove</tt> method is
187: * not supported by this list.
188: * @throws IndexOutOfBoundsException if the specified index is out of
189: * range (<tt>index < 0 || index >= size()</tt>).
190: */
191: public Object remove(int index) {
192: throw new UnsupportedOperationException();
193: }
194:
195: // Search Operations
196:
197: /**
198: * Returns the index in this list of the first occurence of the specified
199: * element, or -1 if the list does not contain this element. More
200: * formally, returns the lowest index <tt>i</tt> such that <tt>(o==null ?
201: * get(i)==null : o.equals(get(i)))</tt>, or -1 if there is no such
202: * index.<p>
203: *
204: * This implementation first gets a list iterator (with
205: * <tt>listIterator()</tt>). Then, it iterates over the list until the
206: * specified element is found or the end of the list is reached.
207: *
208: * @param o element to search for.
209: *
210: * @return the index in this List of the first occurence of the specified
211: * element, or -1 if the List does not contain this element.
212: */
213: public int indexOf(Object o) {
214: ListIterator e = listIterator();
215: if (o == null) {
216: while (e.hasNext())
217: if (e.next() == null)
218: return e.previousIndex();
219: } else {
220: while (e.hasNext())
221: if (o.equals(e.next()))
222: return e.previousIndex();
223: }
224: return -1;
225: }
226:
227: /**
228: * Returns the index in this list of the last occurence of the specified
229: * element, or -1 if the list does not contain this element. More
230: * formally, returns the highest index <tt>i</tt> such that <tt>(o==null ?
231: * get(i)==null : o.equals(get(i)))</tt>, or -1 if there is no such
232: * index.<p>
233: *
234: * This implementation first gets a list iterator that points to the end
235: * of the list (with listIterator(size())). Then, it iterates backwards
236: * over the list until the specified element is found, or the beginning of
237: * the list is reached.
238: *
239: * @param o element to search for.
240: *
241: * @return the index in this list of the last occurence of the specified
242: * element, or -1 if the list does not contain this element.
243: */
244: public int lastIndexOf(Object o) {
245: ListIterator e = listIterator(size());
246: if (o == null) {
247: while (e.hasPrevious())
248: if (e.previous() == null)
249: return e.nextIndex();
250: } else {
251: while (e.hasPrevious())
252: if (o.equals(e.previous()))
253: return e.nextIndex();
254: }
255: return -1;
256: }
257:
258: // Bulk Operations
259:
260: /**
261: * Removes all of the elements from this collection (optional operation).
262: * The collection will be empty after this call returns (unless it throws
263: * an exception).<p>
264: *
265: * This implementation calls <tt>removeRange(0, size())</tt>.<p>
266: *
267: * Note that this implementation throws an
268: * <tt>UnsupportedOperationException</tt> unless <tt>remove(int
269: * index)</tt> or <tt>removeRange(int fromIndex, int toIndex)</tt> is
270: * overridden.
271: *
272: * @throws UnsupportedOperationException if the <tt>clear</tt> method is
273: * not supported by this Collection.
274: */
275: public void clear() {
276: removeRange(0, size());
277: }
278:
279: /**
280: * Inserts all of the elements in the specified collection into this list
281: * at the specified position (optional operation). Shifts the element
282: * currently at that position (if any) and any subsequent elements to the
283: * right (increases their indices). The new elements will appear in the
284: * list in the order that they are returned by the specified collection's
285: * iterator. The behavior of this operation is unspecified if the
286: * specified collection is modified while the operation is in progress.
287: * (Note that this will occur if the specified collection is this list,
288: * and it's nonempty.)<p>
289: *
290: * This implementation gets an iterator over the specified collection and
291: * iterates over it, inserting the elements obtained from the iterator
292: * into this list at the appropriate position, one at a time, using
293: * <tt>add(int, Object)</tt>. Many implementations will override this
294: * method for efficiency.<p>
295: *
296: * Note that this implementation throws an
297: * <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
298: * is overridden.
299: *
300: * @return <tt>true</tt> if this list changed as a result of the call.
301: * @param index index at which to insert the first element from the
302: * specified collection.
303: * @param c elements to be inserted into this List.
304: *
305: * @throws UnsupportedOperationException if the <tt>addAll</tt> method is
306: * not supported by this list.
307: *
308: * @throws ClassCastException if the class of an element of the specified
309: * collection prevents it from being added to this List.
310: *
311: * @throws IllegalArgumentException some aspect an element of the
312: * specified collection prevents it from being added to this
313: * List.
314: *
315: * @throws IndexOutOfBoundsException index out of range (<tt>index < 0
316: * || index > size()</tt>).
317: *
318: * @throws NullPointerException if the specified collection is null.
319: */
320: public boolean addAll(int index, Collection c) {
321: boolean modified = false;
322: Iterator e = c.iterator();
323: while (e.hasNext()) {
324: add(index++, e.next());
325: modified = true;
326: }
327: return modified;
328: }
329:
330: // Iterators
331:
332: /**
333: * Returns an iterator over the elements in this list in proper
334: * sequence. <p>
335: *
336: * This implementation returns a straightforward implementation of the
337: * iterator interface, relying on the backing list's <tt>size()</tt>,
338: * <tt>get(int)</tt>, and <tt>remove(int)</tt> methods.<p>
339: *
340: * Note that the iterator returned by this method will throw an
341: * <tt>UnsupportedOperationException</tt> in response to its
342: * <tt>remove</tt> method unless the list's <tt>remove(int)</tt> method is
343: * overridden.<p>
344: *
345: * This implementation can be made to throw runtime exceptions in the face
346: * of concurrent modification, as described in the specification for the
347: * (protected) <tt>modCount</tt> field.
348: *
349: * @return an iterator over the elements in this list in proper sequence.
350: *
351: * @see #modCount
352: */
353: public Iterator iterator() {
354: return new Itr();
355: }
356:
357: /**
358: * Returns an iterator of the elements in this list (in proper sequence).
359: * This implementation returns <tt>listIterator(0)</tt>.
360: *
361: * @return an iterator of the elements in this list (in proper sequence).
362: *
363: * @see #listIterator(int)
364: */
365: public ListIterator listIterator() {
366: return listIterator(0);
367: }
368:
369: /**
370: * Returns a list iterator of the elements in this list (in proper
371: * sequence), starting at the specified position in the list. The
372: * specified index indicates the first element that would be returned by
373: * an initial call to the <tt>next</tt> method. An initial call to
374: * the <tt>previous</tt> method would return the element with the
375: * specified index minus one.<p>
376: *
377: * This implementation returns a straightforward implementation of the
378: * <tt>ListIterator</tt> interface that extends the implementation of the
379: * <tt>Iterator</tt> interface returned by the <tt>iterator()</tt> method.
380: * The <tt>ListIterator</tt> implementation relies on the backing list's
381: * <tt>get(int)</tt>, <tt>set(int, Object)</tt>, <tt>add(int, Object)</tt>
382: * and <tt>remove(int)</tt> methods.<p>
383: *
384: * Note that the list iterator returned by this implementation will throw
385: * an <tt>UnsupportedOperationException</tt> in response to its
386: * <tt>remove</tt>, <tt>set</tt> and <tt>add</tt> methods unless the
387: * list's <tt>remove(int)</tt>, <tt>set(int, Object)</tt>, and
388: * <tt>add(int, Object)</tt> methods are overridden.<p>
389: *
390: * This implementation can be made to throw runtime exceptions in the
391: * face of concurrent modification, as described in the specification for
392: * the (protected) <tt>modCount</tt> field.
393: *
394: * @param index index of the first element to be returned from the list
395: * iterator (by a call to the <tt>next</tt> method).
396: *
397: * @return a list iterator of the elements in this list (in proper
398: * sequence), starting at the specified position in the list.
399: *
400: * @throws IndexOutOfBoundsException if the specified index is out of
401: * range (<tt>index < 0 || index > size()</tt>).
402: *
403: * @see #modCount
404: */
405: public ListIterator listIterator(final int index) {
406: if (index < 0 || index > size())
407: throw new IndexOutOfBoundsException("Index: " + index);
408:
409: return new ListItr(index);
410: }
411:
412: private class Itr implements Iterator {
413: /**
414: * Index of element to be returned by subsequent call to next.
415: */
416: int cursor = 0;
417:
418: /**
419: * Index of element returned by most recent call to next or
420: * previous. Reset to -1 if this element is deleted by a call
421: * to remove.
422: */
423: int lastRet = -1;
424:
425: /**
426: * The modCount value that the iterator believes that the backing
427: * List should have. If this expectation is violated, the iterator
428: * has detected concurrent modification.
429: */
430: int expectedModCount = modCount;
431:
432: public boolean hasNext() {
433: return cursor != size();
434: }
435:
436: public Object next() {
437: checkForComodification();
438: try {
439: Object next = get(cursor);
440: lastRet = cursor++;
441: return next;
442: } catch (IndexOutOfBoundsException e) {
443: checkForComodification();
444: throw new NoSuchElementException();
445: }
446: }
447:
448: public void remove() {
449: if (lastRet == -1)
450: throw new IllegalStateException();
451: checkForComodification();
452:
453: try {
454: AbstractList.this .remove(lastRet);
455: if (lastRet < cursor)
456: cursor--;
457: lastRet = -1;
458: expectedModCount = modCount;
459: } catch (IndexOutOfBoundsException e) {
460: throw new ConcurrentModificationException();
461: }
462: }
463:
464: final void checkForComodification() {
465: if (modCount != expectedModCount)
466: throw new ConcurrentModificationException();
467: }
468: }
469:
470: private class ListItr extends Itr implements ListIterator {
471: ListItr(int index) {
472: cursor = index;
473: }
474:
475: public boolean hasPrevious() {
476: return cursor != 0;
477: }
478:
479: public Object previous() {
480: checkForComodification();
481: try {
482: int i = cursor - 1;
483: Object previous = get(i);
484: lastRet = cursor = i;
485: return previous;
486: } catch (IndexOutOfBoundsException e) {
487: checkForComodification();
488: throw new NoSuchElementException();
489: }
490: }
491:
492: public int nextIndex() {
493: return cursor;
494: }
495:
496: public int previousIndex() {
497: return cursor - 1;
498: }
499:
500: public void set(Object o) {
501: if (lastRet == -1)
502: throw new IllegalStateException();
503: checkForComodification();
504:
505: try {
506: AbstractList.this .set(lastRet, o);
507: expectedModCount = modCount;
508: } catch (IndexOutOfBoundsException e) {
509: throw new ConcurrentModificationException();
510: }
511: }
512:
513: public void add(Object o) {
514: checkForComodification();
515:
516: try {
517: AbstractList.this .add(cursor++, o);
518: lastRet = -1;
519: expectedModCount = modCount;
520: } catch (IndexOutOfBoundsException e) {
521: throw new ConcurrentModificationException();
522: }
523: }
524: }
525:
526: /**
527: * Returns a view of the portion of this list between <tt>fromIndex</tt>,
528: * inclusive, and <tt>toIndex</tt>, exclusive. (If <tt>fromIndex</tt> and
529: * <tt>toIndex</tt> are equal, the returned list is empty.) The returned
530: * list is backed by this list, so changes in the returned list are
531: * reflected in this list, and vice-versa. The returned list supports all
532: * of the optional list operations supported by this list.<p>
533: *
534: * This method eliminates the need for explicit range operations (of the
535: * sort that commonly exist for arrays). Any operation that expects a
536: * list can be used as a range operation by operating on a subList view
537: * instead of a whole list. For example, the following idiom removes a
538: * range of elements from a list:
539: * <pre>
540: * list.subList(from, to).clear();
541: * </pre>
542: * Similar idioms may be constructed for <tt>indexOf</tt> and
543: * <tt>lastIndexOf</tt>, and all of the algorithms in the
544: * <tt>Collections</tt> class can be applied to a subList.<p>
545: *
546: * The semantics of the list returned by this method become undefined if
547: * the backing list (i.e., this list) is <i>structurally modified</i> in
548: * any way other than via the returned list. (Structural modifications are
549: * those that change the size of the list, or otherwise perturb it in such
550: * a fashion that iterations in progress may yield incorrect results.)<p>
551: *
552: * This implementation returns a list that subclasses
553: * <tt>AbstractList</tt>. The subclass stores, in private fields, the
554: * offset of the subList within the backing list, the size of the subList
555: * (which can change over its lifetime), and the expected
556: * <tt>modCount</tt> value of the backing list. There are two variants
557: * of the subclass, one of which implements <tt>RandomAccess</tt>.
558: * If this list implements <tt>RandomAccess</tt> the returned list will
559: * be an instance of the subclass that implements <tt>RandomAccess</tt>.<p>
560: *
561: * The subclass's <tt>set(int, Object)</tt>, <tt>get(int)</tt>,
562: * <tt>add(int, Object)</tt>, <tt>remove(int)</tt>, <tt>addAll(int,
563: * Collection)</tt> and <tt>removeRange(int, int)</tt> methods all
564: * delegate to the corresponding methods on the backing abstract list,
565: * after bounds-checking the index and adjusting for the offset. The
566: * <tt>addAll(Collection c)</tt> method merely returns <tt>addAll(size,
567: * c)</tt>.<p>
568: *
569: * The <tt>listIterator(int)</tt> method returns a "wrapper object" over a
570: * list iterator on the backing list, which is created with the
571: * corresponding method on the backing list. The <tt>iterator</tt> method
572: * merely returns <tt>listIterator()</tt>, and the <tt>size</tt> method
573: * merely returns the subclass's <tt>size</tt> field.<p>
574: *
575: * All methods first check to see if the actual <tt>modCount</tt> of the
576: * backing list is equal to its expected value, and throw a
577: * <tt>ConcurrentModificationException</tt> if it is not.
578: *
579: * @param fromIndex low endpoint (inclusive) of the subList.
580: * @param toIndex high endpoint (exclusive) of the subList.
581: * @return a view of the specified range within this list.
582: * @throws IndexOutOfBoundsException endpoint index value out of range
583: * <tt>(fromIndex < 0 || toIndex > size)</tt>
584: * @throws IllegalArgumentException endpoint indices out of order
585: * <tt>(fromIndex > toIndex)</tt> */
586: public List subList(int fromIndex, int toIndex) {
587: return (this instanceof RandomAccess ? new RandomAccessSubList(
588: this , fromIndex, toIndex) : new SubList(this ,
589: fromIndex, toIndex));
590: }
591:
592: // Comparison and hashing
593:
594: /**
595: * Compares the specified object with this list for equality. Returns
596: * <tt>true</tt> if and only if the specified object is also a list, both
597: * lists have the same size, and all corresponding pairs of elements in
598: * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and
599: * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
600: * e1.equals(e2))</tt>.) In other words, two lists are defined to be
601: * equal if they contain the same elements in the same order.<p>
602: *
603: * This implementation first checks if the specified object is this
604: * list. If so, it returns <tt>true</tt>; if not, it checks if the
605: * specified object is a list. If not, it returns <tt>false</tt>; if so,
606: * it iterates over both lists, comparing corresponding pairs of elements.
607: * If any comparison returns <tt>false</tt>, this method returns
608: * <tt>false</tt>. If either iterator runs out of elements before the
609: * other it returns <tt>false</tt> (as the lists are of unequal length);
610: * otherwise it returns <tt>true</tt> when the iterations complete.
611: *
612: * @param o the object to be compared for equality with this list.
613: *
614: * @return <tt>true</tt> if the specified object is equal to this list.
615: */
616: public boolean equals(Object o) {
617: if (o == this )
618: return true;
619: if (!(o instanceof List))
620: return false;
621:
622: ListIterator e1 = listIterator();
623: ListIterator e2 = ((List) o).listIterator();
624: while (e1.hasNext() && e2.hasNext()) {
625: Object o1 = e1.next();
626: Object o2 = e2.next();
627: if (!(o1 == null ? o2 == null : o1.equals(o2)))
628: return false;
629: }
630: return !(e1.hasNext() || e2.hasNext());
631: }
632:
633: /**
634: * Returns the hash code value for this list. <p>
635: *
636: * This implementation uses exactly the code that is used to define the
637: * list hash function in the documentation for the <tt>List.hashCode</tt>
638: * method.
639: *
640: * @return the hash code value for this list.
641: */
642: public int hashCode() {
643: int hashCode = 1;
644: Iterator i = iterator();
645: while (i.hasNext()) {
646: Object obj = i.next();
647: hashCode = 31 * hashCode
648: + (obj == null ? 0 : obj.hashCode());
649: }
650: return hashCode;
651: }
652:
653: /**
654: * Removes from this list all of the elements whose index is between
655: * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
656: * Shifts any succeeding elements to the left (reduces their index). This
657: * call shortens the ArrayList by <tt>(toIndex - fromIndex)</tt>
658: * elements. (If <tt>toIndex==fromIndex</tt>, this operation has no
659: * effect.)<p>
660: *
661: * This method is called by the <tt>clear</tt> operation on this list
662: * and its subLists. Overriding this method to take advantage of
663: * the internals of the list implementation can <i>substantially</i>
664: * improve the performance of the <tt>clear</tt> operation on this list
665: * and its subLists.<p>
666: *
667: * This implementation gets a list iterator positioned before
668: * <tt>fromIndex</tt>, and repeatedly calls <tt>ListIterator.next</tt>
669: * followed by <tt>ListIterator.remove</tt> until the entire range has
670: * been removed. <b>Note: if <tt>ListIterator.remove</tt> requires linear
671: * time, this implementation requires quadratic time.</b>
672: *
673: * @param fromIndex index of first element to be removed.
674: * @param toIndex index after last element to be removed.
675: */
676: protected void removeRange(int fromIndex, int toIndex) {
677: ListIterator it = listIterator(fromIndex);
678: for (int i = 0, n = toIndex - fromIndex; i < n; i++) {
679: it.next();
680: it.remove();
681: }
682: }
683:
684: /**
685: * The number of times this list has been <i>structurally modified</i>.
686: * Structural modifications are those that change the size of the
687: * list, or otherwise perturb it in such a fashion that iterations in
688: * progress may yield incorrect results.<p>
689: *
690: * This field is used by the iterator and list iterator implementation
691: * returned by the <tt>iterator</tt> and <tt>listIterator</tt> methods.
692: * If the value of this field changes unexpectedly, the iterator (or list
693: * iterator) will throw a <tt>ConcurrentModificationException</tt> in
694: * response to the <tt>next</tt>, <tt>remove</tt>, <tt>previous</tt>,
695: * <tt>set</tt> or <tt>add</tt> operations. This provides
696: * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
697: * the face of concurrent modification during iteration.<p>
698: *
699: * <b>Use of this field by subclasses is optional.</b> If a subclass
700: * wishes to provide fail-fast iterators (and list iterators), then it
701: * merely has to increment this field in its <tt>add(int, Object)</tt> and
702: * <tt>remove(int)</tt> methods (and any other methods that it overrides
703: * that result in structural modifications to the list). A single call to
704: * <tt>add(int, Object)</tt> or <tt>remove(int)</tt> must add no more than
705: * one to this field, or the iterators (and list iterators) will throw
706: * bogus <tt>ConcurrentModificationExceptions</tt>. If an implementation
707: * does not wish to provide fail-fast iterators, this field may be
708: * ignored.
709: */
710: protected transient int modCount = 0;
711: }
712:
713: class SubList extends AbstractList {
714: private AbstractList l;
715: private int offset;
716: private int size;
717: private int expectedModCount;
718:
719: SubList(AbstractList list, int fromIndex, int toIndex) {
720: if (fromIndex < 0)
721: throw new IndexOutOfBoundsException("fromIndex = "
722: + fromIndex);
723: if (toIndex > list.size())
724: throw new IndexOutOfBoundsException("toIndex = " + toIndex);
725: if (fromIndex > toIndex)
726: throw new IllegalArgumentException("fromIndex(" + fromIndex
727: + ") > toIndex(" + toIndex + ")");
728: l = list;
729: offset = fromIndex;
730: size = toIndex - fromIndex;
731: expectedModCount = l.modCount;
732: }
733:
734: public Object set(int index, Object element) {
735: rangeCheck(index);
736: checkForComodification();
737: return l.set(index + offset, element);
738: }
739:
740: public Object get(int index) {
741: rangeCheck(index);
742: checkForComodification();
743: return l.get(index + offset);
744: }
745:
746: public int size() {
747: checkForComodification();
748: return size;
749: }
750:
751: public void add(int index, Object element) {
752: if (index < 0 || index > size)
753: throw new IndexOutOfBoundsException();
754: checkForComodification();
755: l.add(index + offset, element);
756: expectedModCount = l.modCount;
757: size++;
758: modCount++;
759: }
760:
761: public Object remove(int index) {
762: rangeCheck(index);
763: checkForComodification();
764: Object result = l.remove(index + offset);
765: expectedModCount = l.modCount;
766: size--;
767: modCount++;
768: return result;
769: }
770:
771: protected void removeRange(int fromIndex, int toIndex) {
772: checkForComodification();
773: l.removeRange(fromIndex + offset, toIndex + offset);
774: expectedModCount = l.modCount;
775: size -= (toIndex - fromIndex);
776: modCount++;
777: }
778:
779: public boolean addAll(Collection c) {
780: return addAll(size, c);
781: }
782:
783: public boolean addAll(int index, Collection c) {
784: if (index < 0 || index > size)
785: throw new IndexOutOfBoundsException("Index: " + index
786: + ", Size: " + size);
787: int cSize = c.size();
788: if (cSize == 0)
789: return false;
790:
791: checkForComodification();
792: l.addAll(offset + index, c);
793: expectedModCount = l.modCount;
794: size += cSize;
795: modCount++;
796: return true;
797: }
798:
799: public Iterator iterator() {
800: return listIterator();
801: }
802:
803: public ListIterator listIterator(final int index) {
804: checkForComodification();
805: if (index < 0 || index > size)
806: throw new IndexOutOfBoundsException("Index: " + index
807: + ", Size: " + size);
808:
809: return new ListIterator() {
810: private ListIterator i = l.listIterator(index + offset);
811:
812: public boolean hasNext() {
813: return nextIndex() < size;
814: }
815:
816: public Object next() {
817: if (hasNext())
818: return i.next();
819: else
820: throw new NoSuchElementException();
821: }
822:
823: public boolean hasPrevious() {
824: return previousIndex() >= 0;
825: }
826:
827: public Object previous() {
828: if (hasPrevious())
829: return i.previous();
830: else
831: throw new NoSuchElementException();
832: }
833:
834: public int nextIndex() {
835: return i.nextIndex() - offset;
836: }
837:
838: public int previousIndex() {
839: return i.previousIndex() - offset;
840: }
841:
842: public void remove() {
843: i.remove();
844: expectedModCount = l.modCount;
845: size--;
846: modCount++;
847: }
848:
849: public void set(Object o) {
850: i.set(o);
851: }
852:
853: public void add(Object o) {
854: i.add(o);
855: expectedModCount = l.modCount;
856: size++;
857: modCount++;
858: }
859: };
860: }
861:
862: public List subList(int fromIndex, int toIndex) {
863: return new SubList(this , fromIndex, toIndex);
864: }
865:
866: private void rangeCheck(int index) {
867: if (index < 0 || index >= size)
868: throw new IndexOutOfBoundsException("Index: " + index
869: + ",Size: " + size);
870: }
871:
872: private void checkForComodification() {
873: if (l.modCount != expectedModCount)
874: throw new ConcurrentModificationException();
875: }
876: }
877:
878: class RandomAccessSubList extends SubList implements RandomAccess {
879: RandomAccessSubList(AbstractList list, int fromIndex, int toIndex) {
880: super (list, fromIndex, toIndex);
881: }
882:
883: public List subList(int fromIndex, int toIndex) {
884: return new RandomAccessSubList(this, fromIndex, toIndex);
885: }
886: }
|