KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > AbstractList


1 /*
2  * @(#)AbstractList.java 1.46 04/02/10
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 package java.util;
9
10 /**
11  * This class provides a skeletal implementation of the <tt>List</tt>
12  * interface to minimize the effort required to implement this interface
13  * backed by a "random access" data store (such as an array). For sequential
14  * access data (such as a linked list), <tt>AbstractSequentialList</tt> should
15  * be used in preference to this class.<p>
16  *
17  * To implement an unmodifiable list, the programmer needs only to extend this
18  * class and provide implementations for the <tt>get(int index)</tt> and
19  * <tt>size()</tt> methods.<p>
20  *
21  * To implement a modifiable list, the programmer must additionally override
22  * the <tt>set(int index, Object element)</tt> method (which otherwise throws
23  * an <tt>UnsupportedOperationException</tt>. If the list is variable-size
24  * the programmer must additionally override the <tt>add(int index, Object
25  * element)</tt> and <tt>remove(int index)</tt> methods.<p>
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>
30  *
31  * Unlike the other abstract collection implementations, the programmer does
32  * <i>not</i> have to provide an iterator implementation; the iterator and
33  * list iterator are implemented by this class, on top the "random access"
34  * methods: <tt>get(int index)</tt>, <tt>set(int index, Object element)</tt>,
35  * <tt>set(int index, Object element)</tt>, <tt>add(int index, Object
36  * element)</tt> and <tt>remove(int index)</tt>.<p>
37  *
38  * The documentation for each non-abstract methods in this class describes its
39  * implementation in detail. Each of these methods may be overridden if the
40  * collection being implemented admits a more efficient implementation.<p>
41  *
42  * This class is a member of the
43  * <a HREF="{@docRoot}/../guide/collections/index.html">
44  * Java Collections Framework</a>.
45  *
46  * @author Josh Bloch
47  * @author Neal Gafter
48  * @version 1.37, 01/18/03
49  * @see Collection
50  * @see List
51  * @see AbstractSequentialList
52  * @see AbstractCollection
53  * @since 1.2
54  */

55
56 public abstract class AbstractList<E> extends AbstractCollection JavaDoc<E> implements List JavaDoc<E> {
57     /**
58      * Sole constructor. (For invocation by subclass constructors, typically
59      * implicit.)
60      */

61     protected AbstractList() {
62     }
63
64     /**
65      * Appends the specified element to the end of this List (optional
66      * operation). <p>
67      *
68      * This implementation calls <tt>add(size(), o)</tt>.<p>
69      *
70      * Note that this implementation throws an
71      * <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
72      * is overridden.
73      *
74      * @param o element to be appended to this list.
75      *
76      * @return <tt>true</tt> (as per the general contract of
77      * <tt>Collection.add</tt>).
78      *
79      * @throws UnsupportedOperationException if the <tt>add</tt> method is not
80      * supported by this Set.
81      *
82      * @throws ClassCastException if the class of the specified element
83      * prevents it from being added to this set.
84      *
85      * @throws IllegalArgumentException some aspect of this element prevents
86      * it from being added to this collection.
87      */

88     public boolean add(E o) {
89     add(size(), o);
90     return true;
91     }
92
93     /**
94      * Returns the element at the specified position in this list.
95      *
96      * @param index index of element to return.
97      *
98      * @return the element at the specified position in this list.
99      * @throws IndexOutOfBoundsException if the given index is out of range
100      * (<tt>index &lt; 0 || index &gt;= size()</tt>).
101      */

102     abstract public E get(int index);
103
104     /**
105      * Replaces the element at the specified position in this list with the
106      * specified element (optional operation). <p>
107      *
108      * This implementation always throws an
109      * <tt>UnsupportedOperationException</tt>.
110      *
111      * @param index index of element to replace.
112      * @param element element to be stored at the specified position.
113      * @return the element previously at the specified position.
114      *
115      * @throws UnsupportedOperationException if the <tt>set</tt> method is not
116      * supported by this List.
117      * @throws ClassCastException if the class of the specified element
118      * prevents it from being added to this list.
119      * @throws IllegalArgumentException if some aspect of the specified
120      * element prevents it from being added to this list.
121      *
122      * @throws IndexOutOfBoundsException if the specified index is out of
123      * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
124      */

125     
126     public E set(int index, E element) {
127     throw new UnsupportedOperationException JavaDoc();
128     }
129
130     /**
131      * Inserts the specified element at the specified position in this list
132      * (optional operation). Shifts the element currently at that position
133      * (if any) and any subsequent elements to the right (adds one to their
134      * indices).<p>
135      *
136      * This implementation always throws an UnsupportedOperationException.
137      *
138      * @param index index at which the specified element is to be inserted.
139      * @param element element to be inserted.
140      *
141      * @throws UnsupportedOperationException if the <tt>add</tt> method is not
142      * supported by this list.
143      * @throws ClassCastException if the class of the specified element
144      * prevents it from being added to this list.
145      * @throws IllegalArgumentException if some aspect of the specified
146      * element prevents it from being added to this list.
147      * @throws IndexOutOfBoundsException index is out of range (<tt>index &lt;
148      * 0 || index &gt; size()</tt>).
149      */

150     public void add(int index, E element) {
151     throw new UnsupportedOperationException JavaDoc();
152     }
153
154     /**
155      * Removes the element at the specified position in this list (optional
156      * operation). Shifts any subsequent elements to the left (subtracts one
157      * from their indices). Returns the element that was removed from the
158      * list.<p>
159      *
160      * This implementation always throws an
161      * <tt>UnsupportedOperationException</tt>.
162      *
163      * @param index the index of the element to remove.
164      * @return the element previously at the specified position.
165      *
166      * @throws UnsupportedOperationException if the <tt>remove</tt> method is
167      * not supported by this list.
168      * @throws IndexOutOfBoundsException if the specified index is out of
169      * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
170      */

171     public E remove(int index) {
172     throw new UnsupportedOperationException JavaDoc();
173     }
174
175
176     // Search Operations
177

178     /**
179      * Returns the index in this list of the first occurence of the specified
180      * element, or -1 if the list does not contain this element. More
181      * formally, returns the lowest index <tt>i</tt> such that <tt>(o==null ?
182      * get(i)==null : o.equals(get(i)))</tt>, or -1 if there is no such
183      * index.<p>
184      *
185      * This implementation first gets a list iterator (with
186      * <tt>listIterator()</tt>). Then, it iterates over the list until the
187      * specified element is found or the end of the list is reached.
188      *
189      * @param o element to search for.
190      *
191      * @return the index in this List of the first occurence of the specified
192      * element, or -1 if the List does not contain this element.
193      */

194     public int indexOf(Object JavaDoc o) {
195     ListIterator JavaDoc<E> e = listIterator();
196     if (o==null) {
197         while (e.hasNext())
198         if (e.next()==null)
199             return e.previousIndex();
200     } else {
201         while (e.hasNext())
202         if (o.equals(e.next()))
203             return e.previousIndex();
204     }
205     return -1;
206     }
207
208     /**
209      * Returns the index in this list of the last occurence of the specified
210      * element, or -1 if the list does not contain this element. More
211      * formally, returns the highest index <tt>i</tt> such that <tt>(o==null ?
212      * get(i)==null : o.equals(get(i)))</tt>, or -1 if there is no such
213      * index.<p>
214      *
215      * This implementation first gets a list iterator that points to the end
216      * of the list (with listIterator(size())). Then, it iterates backwards
217      * over the list until the specified element is found, or the beginning of
218      * the list is reached.
219      *
220      * @param o element to search for.
221      *
222      * @return the index in this list of the last occurence of the specified
223      * element, or -1 if the list does not contain this element.
224      */

225     public int lastIndexOf(Object JavaDoc o) {
226     ListIterator JavaDoc<E> e = listIterator(size());
227     if (o==null) {
228         while (e.hasPrevious())
229         if (e.previous()==null)
230             return e.nextIndex();
231     } else {
232         while (e.hasPrevious())
233         if (o.equals(e.previous()))
234             return e.nextIndex();
235     }
236     return -1;
237     }
238
239
240     // Bulk Operations
241

242     /**
243      * Removes all of the elements from this collection (optional operation).
244      * The collection will be empty after this call returns (unless it throws
245      * an exception).<p>
246      *
247      * This implementation calls <tt>removeRange(0, size())</tt>.<p>
248      *
249      * Note that this implementation throws an
250      * <tt>UnsupportedOperationException</tt> unless <tt>remove(int
251      * index)</tt> or <tt>removeRange(int fromIndex, int toIndex)</tt> is
252      * overridden.
253      *
254      * @throws UnsupportedOperationException if the <tt>clear</tt> method is
255      * not supported by this Collection.
256      */

257     public void clear() {
258         removeRange(0, size());
259     }
260
261     /**
262      * Inserts all of the elements in the specified collection into this list
263      * at the specified position (optional operation). Shifts the element
264      * currently at that position (if any) and any subsequent elements to the
265      * right (increases their indices). The new elements will appear in the
266      * list in the order that they are returned by the specified collection's
267      * iterator. The behavior of this operation is unspecified if the
268      * specified collection is modified while the operation is in progress.
269      * (Note that this will occur if the specified collection is this list,
270      * and it's nonempty.)<p>
271      *
272      * This implementation gets an iterator over the specified collection and
273      * iterates over it, inserting the elements obtained from the iterator
274      * into this list at the appropriate position, one at a time, using
275      * <tt>add(int, Object)</tt>. Many implementations will override this
276      * method for efficiency.<p>
277      *
278      * Note that this implementation throws an
279      * <tt>UnsupportedOperationException</tt> unless <tt>add(int, Object)</tt>
280      * is overridden.
281      *
282      * @return <tt>true</tt> if this list changed as a result of the call.
283      * @param index index at which to insert the first element from the
284      * specified collection.
285      * @param c elements to be inserted into this List.
286      *
287      * @throws UnsupportedOperationException if the <tt>addAll</tt> method is
288      * not supported by this list.
289      *
290      * @throws ClassCastException if the class of an element of the specified
291      * collection prevents it from being added to this List.
292      *
293      * @throws IllegalArgumentException some aspect an element of the
294      * specified collection prevents it from being added to this
295      * List.
296      *
297      * @throws IndexOutOfBoundsException index out of range (<tt>index &lt; 0
298      * || index &gt; size()</tt>).
299      *
300      * @throws NullPointerException if the specified collection is null.
301      */

302     public boolean addAll(int index, Collection JavaDoc<? extends E> c) {
303     boolean modified = false;
304     Iterator JavaDoc<? extends E> e = c.iterator();
305     while (e.hasNext()) {
306         add(index++, e.next());
307         modified = true;
308     }
309     return modified;
310     }
311
312
313     // Iterators
314

315     /**
316      * Returns an iterator over the elements in this list in proper
317      * sequence. <p>
318      *
319      * This implementation returns a straightforward implementation of the
320      * iterator interface, relying on the backing list's <tt>size()</tt>,
321      * <tt>get(int)</tt>, and <tt>remove(int)</tt> methods.<p>
322      *
323      * Note that the iterator returned by this method will throw an
324      * <tt>UnsupportedOperationException</tt> in response to its
325      * <tt>remove</tt> method unless the list's <tt>remove(int)</tt> method is
326      * overridden.<p>
327      *
328      * This implementation can be made to throw runtime exceptions in the face
329      * of concurrent modification, as described in the specification for the
330      * (protected) <tt>modCount</tt> field.
331      *
332      * @return an iterator over the elements in this list in proper sequence.
333      *
334      * @see #modCount
335      */

336     public Iterator JavaDoc<E> iterator() {
337     return new Itr();
338     }
339
340     /**
341      * Returns an iterator of the elements in this list (in proper sequence).
342      * This implementation returns <tt>listIterator(0)</tt>.
343      *
344      * @return an iterator of the elements in this list (in proper sequence).
345      *
346      * @see #listIterator(int)
347      */

348     public ListIterator JavaDoc<E> listIterator() {
349     return listIterator(0);
350     }
351
352     /**
353      * Returns a list iterator of the elements in this list (in proper
354      * sequence), starting at the specified position in the list. The
355      * specified index indicates the first element that would be returned by
356      * an initial call to the <tt>next</tt> method. An initial call to
357      * the <tt>previous</tt> method would return the element with the
358      * specified index minus one.<p>
359      *
360      * This implementation returns a straightforward implementation of the
361      * <tt>ListIterator</tt> interface that extends the implementation of the
362      * <tt>Iterator</tt> interface returned by the <tt>iterator()</tt> method.
363      * The <tt>ListIterator</tt> implementation relies on the backing list's
364      * <tt>get(int)</tt>, <tt>set(int, Object)</tt>, <tt>add(int, Object)</tt>
365      * and <tt>remove(int)</tt> methods.<p>
366      *
367      * Note that the list iterator returned by this implementation will throw
368      * an <tt>UnsupportedOperationException</tt> in response to its
369      * <tt>remove</tt>, <tt>set</tt> and <tt>add</tt> methods unless the
370      * list's <tt>remove(int)</tt>, <tt>set(int, Object)</tt>, and
371      * <tt>add(int, Object)</tt> methods are overridden.<p>
372      *
373      * This implementation can be made to throw runtime exceptions in the
374      * face of concurrent modification, as described in the specification for
375      * the (protected) <tt>modCount</tt> field.
376      *
377      * @param index index of the first element to be returned from the list
378      * iterator (by a call to the <tt>next</tt> method).
379      *
380      * @return a list iterator of the elements in this list (in proper
381      * sequence), starting at the specified position in the list.
382      *
383      * @throws IndexOutOfBoundsException if the specified index is out of
384      * range (<tt>index &lt; 0 || index &gt; size()</tt>).
385      *
386      * @see #modCount
387      */

388     public ListIterator JavaDoc<E> listIterator(final int index) {
389     if (index<0 || index>size())
390       throw new IndexOutOfBoundsException JavaDoc("Index: "+index);
391
392     return new ListItr(index);
393     }
394
395     private class Itr implements Iterator JavaDoc<E> {
396     /**
397      * Index of element to be returned by subsequent call to next.
398      */

399     int cursor = 0;
400
401     /**
402      * Index of element returned by most recent call to next or
403      * previous. Reset to -1 if this element is deleted by a call
404      * to remove.
405      */

406     int lastRet = -1;
407
408     /**
409      * The modCount value that the iterator believes that the backing
410      * List should have. If this expectation is violated, the iterator
411      * has detected concurrent modification.
412      */

413     int expectedModCount = modCount;
414
415     public boolean hasNext() {
416             return cursor != size();
417     }
418
419     public E next() {
420             checkForComodification();
421         try {
422         E next = get(cursor);
423         lastRet = cursor++;
424         return next;
425         } catch(IndexOutOfBoundsException JavaDoc e) {
426         checkForComodification();
427         throw new NoSuchElementException JavaDoc();
428         }
429     }
430
431     public void remove() {
432         if (lastRet == -1)
433         throw new IllegalStateException JavaDoc();
434             checkForComodification();
435
436         try {
437         AbstractList.this.remove(lastRet);
438         if (lastRet < cursor)
439             cursor--;
440         lastRet = -1;
441         expectedModCount = modCount;
442         } catch(IndexOutOfBoundsException JavaDoc e) {
443         throw new ConcurrentModificationException JavaDoc();
444         }
445     }
446
447     final void checkForComodification() {
448         if (modCount != expectedModCount)
449         throw new ConcurrentModificationException JavaDoc();
450     }
451     }
452
453     private class ListItr extends Itr implements ListIterator JavaDoc<E> {
454     ListItr(int index) {
455         cursor = index;
456     }
457
458     public boolean hasPrevious() {
459         return cursor != 0;
460     }
461
462         public E previous() {
463             checkForComodification();
464             try {
465                 int i = cursor - 1;
466                 E previous = get(i);
467                 lastRet = cursor = i;
468                 return previous;
469             } catch(IndexOutOfBoundsException JavaDoc e) {
470                 checkForComodification();
471                 throw new NoSuchElementException JavaDoc();
472             }
473         }
474
475     public int nextIndex() {
476         return cursor;
477     }
478
479     public int previousIndex() {
480         return cursor-1;
481     }
482
483     public void set(E o) {
484         if (lastRet == -1)
485         throw new IllegalStateException JavaDoc();
486             checkForComodification();
487
488         try {
489         AbstractList.this.set(lastRet, o);
490         expectedModCount = modCount;
491         } catch(IndexOutOfBoundsException JavaDoc e) {
492         throw new ConcurrentModificationException JavaDoc();
493         }
494     }
495
496     public void add(E o) {
497             checkForComodification();
498
499         try {
500         AbstractList.this.add(cursor++, o);
501         lastRet = -1;
502         expectedModCount = modCount;
503         } catch(IndexOutOfBoundsException JavaDoc e) {
504         throw new ConcurrentModificationException JavaDoc();
505         }
506     }
507     }
508
509     /**
510      * Returns a view of the portion of this list between <tt>fromIndex</tt>,
511      * inclusive, and <tt>toIndex</tt>, exclusive. (If <tt>fromIndex</tt> and
512      * <tt>toIndex</tt> are equal, the returned list is empty.) The returned
513      * list is backed by this list, so changes in the returned list are
514      * reflected in this list, and vice-versa. The returned list supports all
515      * of the optional list operations supported by this list.<p>
516      *
517      * This method eliminates the need for explicit range operations (of the
518      * sort that commonly exist for arrays). Any operation that expects a
519      * list can be used as a range operation by operating on a subList view
520      * instead of a whole list. For example, the following idiom removes a
521      * range of elements from a list:
522      * <pre>
523      * list.subList(from, to).clear();
524      * </pre>
525      * Similar idioms may be constructed for <tt>indexOf</tt> and
526      * <tt>lastIndexOf</tt>, and all of the algorithms in the
527      * <tt>Collections</tt> class can be applied to a subList.<p>
528      *
529      * The semantics of the list returned by this method become undefined if
530      * the backing list (i.e., this list) is <i>structurally modified</i> in
531      * any way other than via the returned list. (Structural modifications are
532      * those that change the size of the list, or otherwise perturb it in such
533      * a fashion that iterations in progress may yield incorrect results.)<p>
534      *
535      * This implementation returns a list that subclasses
536      * <tt>AbstractList</tt>. The subclass stores, in private fields, the
537      * offset of the subList within the backing list, the size of the subList
538      * (which can change over its lifetime), and the expected
539      * <tt>modCount</tt> value of the backing list. There are two variants
540      * of the subclass, one of which implements <tt>RandomAccess</tt>.
541      * If this list implements <tt>RandomAccess</tt> the returned list will
542      * be an instance of the subclass that implements <tt>RandomAccess</tt>.<p>
543      *
544      * The subclass's <tt>set(int, Object)</tt>, <tt>get(int)</tt>,
545      * <tt>add(int, Object)</tt>, <tt>remove(int)</tt>, <tt>addAll(int,
546      * Collection)</tt> and <tt>removeRange(int, int)</tt> methods all
547      * delegate to the corresponding methods on the backing abstract list,
548      * after bounds-checking the index and adjusting for the offset. The
549      * <tt>addAll(Collection c)</tt> method merely returns <tt>addAll(size,
550      * c)</tt>.<p>
551      *
552      * The <tt>listIterator(int)</tt> method returns a "wrapper object" over a
553      * list iterator on the backing list, which is created with the
554      * corresponding method on the backing list. The <tt>iterator</tt> method
555      * merely returns <tt>listIterator()</tt>, and the <tt>size</tt> method
556      * merely returns the subclass's <tt>size</tt> field.<p>
557      *
558      * All methods first check to see if the actual <tt>modCount</tt> of the
559      * backing list is equal to its expected value, and throw a
560      * <tt>ConcurrentModificationException</tt> if it is not.
561      *
562      * @param fromIndex low endpoint (inclusive) of the subList.
563      * @param toIndex high endpoint (exclusive) of the subList.
564      * @return a view of the specified range within this list.
565      * @throws IndexOutOfBoundsException endpoint index value out of range
566      * <tt>(fromIndex &lt; 0 || toIndex &gt; size)</tt>
567      * @throws IllegalArgumentException endpoint indices out of order
568      * <tt>(fromIndex &gt; toIndex)</tt> */

569     public List JavaDoc<E> subList(int fromIndex, int toIndex) {
570         return (this instanceof RandomAccess JavaDoc ?
571                 new RandomAccessSubList<E>(this, fromIndex, toIndex) :
572                 new SubList<E>(this, fromIndex, toIndex));
573     }
574
575     // Comparison and hashing
576

577     /**
578      * Compares the specified object with this list for equality. Returns
579      * <tt>true</tt> if and only if the specified object is also a list, both
580      * lists have the same size, and all corresponding pairs of elements in
581      * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and
582      * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
583      * e1.equals(e2))</tt>.) In other words, two lists are defined to be
584      * equal if they contain the same elements in the same order.<p>
585      *
586      * This implementation first checks if the specified object is this
587      * list. If so, it returns <tt>true</tt>; if not, it checks if the
588      * specified object is a list. If not, it returns <tt>false</tt>; if so,
589      * it iterates over both lists, comparing corresponding pairs of elements.
590      * If any comparison returns <tt>false</tt>, this method returns
591      * <tt>false</tt>. If either iterator runs out of elements before the
592      * other it returns <tt>false</tt> (as the lists are of unequal length);
593      * otherwise it returns <tt>true</tt> when the iterations complete.
594      *
595      * @param o the object to be compared for equality with this list.
596      *
597      * @return <tt>true</tt> if the specified object is equal to this list.
598      */

599     public boolean equals(Object JavaDoc o) {
600     if (o == this)
601         return true;
602     if (!(o instanceof List JavaDoc))
603         return false;
604
605     ListIterator JavaDoc<E> e1 = listIterator();
606     ListIterator JavaDoc e2 = ((List JavaDoc) o).listIterator();
607     while(e1.hasNext() && e2.hasNext()) {
608         E o1 = e1.next();
609         Object JavaDoc o2 = e2.next();
610         if (!(o1==null ? o2==null : o1.equals(o2)))
611         return false;
612     }
613     return !(e1.hasNext() || e2.hasNext());
614     }
615
616     /**
617      * Returns the hash code value for this list. <p>
618      *
619      * This implementation uses exactly the code that is used to define the
620      * list hash function in the documentation for the <tt>List.hashCode</tt>
621      * method.
622      *
623      * @return the hash code value for this list.
624      */

625     public int hashCode() {
626     int hashCode = 1;
627     Iterator JavaDoc<E> i = iterator();
628         while (i.hasNext()) {
629         E obj = i.next();
630         hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
631     }
632     return hashCode;
633     }
634
635     /**
636      * Removes from this list all of the elements whose index is between
637      * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
638      * Shifts any succeeding elements to the left (reduces their index). This
639      * call shortens the ArrayList by <tt>(toIndex - fromIndex)</tt>
640      * elements. (If <tt>toIndex==fromIndex</tt>, this operation has no
641      * effect.)<p>
642      *
643      * This method is called by the <tt>clear</tt> operation on this list
644      * and its subLists. Overriding this method to take advantage of
645      * the internals of the list implementation can <i>substantially</i>
646      * improve the performance of the <tt>clear</tt> operation on this list
647      * and its subLists.<p>
648      *
649      * This implementation gets a list iterator positioned before
650      * <tt>fromIndex</tt>, and repeatedly calls <tt>ListIterator.next</tt>
651      * followed by <tt>ListIterator.remove</tt> until the entire range has
652      * been removed. <b>Note: if <tt>ListIterator.remove</tt> requires linear
653      * time, this implementation requires quadratic time.</b>
654      *
655      * @param fromIndex index of first element to be removed.
656      * @param toIndex index after last element to be removed.
657      */

658     protected void removeRange(int fromIndex, int toIndex) {
659         ListIterator JavaDoc<E> it = listIterator(fromIndex);
660         for (int i=0, n=toIndex-fromIndex; i<n; i++) {
661             it.next();
662             it.remove();
663         }
664     }
665
666     /**
667      * The number of times this list has been <i>structurally modified</i>.
668      * Structural modifications are those that change the size of the
669      * list, or otherwise perturb it in such a fashion that iterations in
670      * progress may yield incorrect results.<p>
671      *
672      * This field is used by the iterator and list iterator implementation
673      * returned by the <tt>iterator</tt> and <tt>listIterator</tt> methods.
674      * If the value of this field changes unexpectedly, the iterator (or list
675      * iterator) will throw a <tt>ConcurrentModificationException</tt> in
676      * response to the <tt>next</tt>, <tt>remove</tt>, <tt>previous</tt>,
677      * <tt>set</tt> or <tt>add</tt> operations. This provides
678      * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
679      * the face of concurrent modification during iteration.<p>
680      *
681      * <b>Use of this field by subclasses is optional.</b> If a subclass
682      * wishes to provide fail-fast iterators (and list iterators), then it
683      * merely has to increment this field in its <tt>add(int, Object)</tt> and
684      * <tt>remove(int)</tt> methods (and any other methods that it overrides
685      * that result in structural modifications to the list). A single call to
686      * <tt>add(int, Object)</tt> or <tt>remove(int)</tt> must add no more than
687      * one to this field, or the iterators (and list iterators) will throw
688      * bogus <tt>ConcurrentModificationExceptions</tt>. If an implementation
689      * does not wish to provide fail-fast iterators, this field may be
690      * ignored.
691      */

692     protected transient int modCount = 0;
693 }
694
695 class SubList<E> extends AbstractList JavaDoc<E> {
696     private AbstractList JavaDoc<E> l;
697     private int offset;
698     private int size;
699     private int expectedModCount;
700
701     SubList(AbstractList JavaDoc<E> list, int fromIndex, int toIndex) {
702         if (fromIndex < 0)
703             throw new IndexOutOfBoundsException JavaDoc("fromIndex = " + fromIndex);
704         if (toIndex > list.size())
705             throw new IndexOutOfBoundsException JavaDoc("toIndex = " + toIndex);
706         if (fromIndex > toIndex)
707             throw new IllegalArgumentException JavaDoc("fromIndex(" + fromIndex +
708                                                ") > toIndex(" + toIndex + ")");
709         l = list;
710         offset = fromIndex;
711         size = toIndex - fromIndex;
712         expectedModCount = l.modCount;
713     }
714
715     public E set(int index, E element) {
716         rangeCheck(index);
717         checkForComodification();
718         return l.set(index+offset, element);
719     }
720
721     public E get(int index) {
722         rangeCheck(index);
723         checkForComodification();
724         return l.get(index+offset);
725     }
726
727     public int size() {
728         checkForComodification();
729         return size;
730     }
731
732     public void add(int index, E element) {
733         if (index<0 || index>size)
734             throw new IndexOutOfBoundsException JavaDoc();
735         checkForComodification();
736         l.add(index+offset, element);
737         expectedModCount = l.modCount;
738         size++;
739         modCount++;
740     }
741
742     public E remove(int index) {
743         rangeCheck(index);
744         checkForComodification();
745         E result = l.remove(index+offset);
746         expectedModCount = l.modCount;
747         size--;
748         modCount++;
749         return result;
750     }
751
752     protected void removeRange(int fromIndex, int toIndex) {
753         checkForComodification();
754         l.removeRange(fromIndex+offset, toIndex+offset);
755         expectedModCount = l.modCount;
756         size -= (toIndex-fromIndex);
757         modCount++;
758     }
759
760     public boolean addAll(Collection JavaDoc<? extends E> c) {
761         return addAll(size, c);
762     }
763
764     public boolean addAll(int index, Collection JavaDoc<? extends E> c) {
765         if (index<0 || index>size)
766             throw new IndexOutOfBoundsException JavaDoc(
767                 "Index: "+index+", Size: "+size);
768         int cSize = c.size();
769         if (cSize==0)
770             return false;
771
772         checkForComodification();
773         l.addAll(offset+index, c);
774         expectedModCount = l.modCount;
775         size += cSize;
776         modCount++;
777         return true;
778     }
779
780     public Iterator JavaDoc<E> iterator() {
781         return listIterator();
782     }
783
784     public ListIterator JavaDoc<E> listIterator(final int index) {
785         checkForComodification();
786         if (index<0 || index>size)
787             throw new IndexOutOfBoundsException JavaDoc(
788                 "Index: "+index+", Size: "+size);
789
790         return new ListIterator JavaDoc<E>() {
791             private ListIterator JavaDoc<E> i = l.listIterator(index+offset);
792
793             public boolean hasNext() {
794                 return nextIndex() < size;
795             }
796
797             public E next() {
798                 if (hasNext())
799                     return i.next();
800                 else
801                     throw new NoSuchElementException JavaDoc();
802             }
803
804             public boolean hasPrevious() {
805                 return previousIndex() >= 0;
806             }
807
808             public E previous() {
809                 if (hasPrevious())
810                     return i.previous();
811                 else
812                     throw new NoSuchElementException JavaDoc();
813             }
814
815             public int nextIndex() {
816                 return i.nextIndex() - offset;
817             }
818
819             public int previousIndex() {
820                 return i.previousIndex() - offset;
821             }
822
823             public void remove() {
824                 i.remove();
825                 expectedModCount = l.modCount;
826                 size--;
827                 modCount++;
828             }
829
830             public void set(E o) {
831                 i.set(o);
832             }
833
834             public void add(E o) {
835                 i.add(o);
836                 expectedModCount = l.modCount;
837                 size++;
838                 modCount++;
839             }
840         };
841     }
842
843     public List JavaDoc<E> subList(int fromIndex, int toIndex) {
844         return new SubList<E>(this, fromIndex, toIndex);
845     }
846
847     private void rangeCheck(int index) {
848         if (index<0 || index>=size)
849             throw new IndexOutOfBoundsException JavaDoc("Index: "+index+
850                                                 ",Size: "+size);
851     }
852
853     private void checkForComodification() {
854         if (l.modCount != expectedModCount)
855             throw new ConcurrentModificationException JavaDoc();
856     }
857 }
858
859 class RandomAccessSubList<E> extends SubList<E> implements RandomAccess JavaDoc {
860     RandomAccessSubList(AbstractList JavaDoc<E> list, int fromIndex, int toIndex) {
861         super(list, fromIndex, toIndex);
862     }
863
864     public List JavaDoc<E> subList(int fromIndex, int toIndex) {
865         return new RandomAccessSubList<E>(this, fromIndex, toIndex);
866     }
867 }
868
Popular Tags