| AbstractList.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE 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 {@link List}
12 * interface to minimize the effort required to implement this interface
13 * backed by a "random access" data store (such as an array). For sequential
14 * access data (such as a linked list), {@link AbstractSequentialList} should
15 * be used in preference to this class.
16 *
17 * <p>To implement an unmodifiable list, the programmer needs only to extend
18 * this class and provide implementations for the {@link #get(int)} and
19 * {@link List#size() size()} methods.
20 *
21 * <p>To implement a modifiable list, the programmer must additionally
22 * override the {@link #set(int, Object) set(int, E)} method (which otherwise
23 * throws an {@code UnsupportedOperationException}). If the list is
24 * variable-size the programmer must additionally override the
25 * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods.
26 *
27 * <p>The programmer should generally provide a void (no argument) and collection
28 * constructor, as per the recommendation in the {@link Collection} interface
29 * specification.
30 *
31 * <p>Unlike the other abstract collection implementations, the programmer does
32 * <i>not</i> have to provide an iterator implementation; the iterator and
33 * list iterator are implemented by this class, on top of the "random access"
34 * methods:
35 * {@link #get(int)},
36 * {@link #set(int, Object) set(int, E)},
37 * {@link #add(int, Object) add(int, E)} and
38 * {@link #remove(int)}.
39 *
40 * <p>The documentation for each non-abstract method in this class describes its
41 * implementation in detail. Each of these methods may be overridden if the
42 * collection being implemented admits a more efficient implementation.
43 *
44 * <p>This class is a member of the
45 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
46 * Java Collections Framework</a>.
47 *
48 * @author Josh Bloch
49 * @author Neal Gafter
50 * @version %I%, %G%
51 * @since 1.2
52 */
53
54 public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
55 /**
56 * Sole constructor. (For invocation by subclass constructors, typically
57 * implicit.)
58 */
59 protected AbstractList() {
60 }
61
62 /**
63 * Appends the specified element to the end of this list (optional
64 * operation).
65 *
66 * <p>Lists that support this operation may place limitations on what
67 * elements may be added to this list. In particular, some
68 * lists will refuse to add null elements, and others will impose
69 * restrictions on the type of elements that may be added. List
70 * classes should clearly specify in their documentation any restrictions
71 * on what elements may be added.
72 *
73 * <p>This implementation calls {@code add(size(), e)}.
74 *
75 * <p>Note that this implementation throws an
76 * {@code UnsupportedOperationException} unless
77 * {@link #add(int, Object) add(int, E)} is overridden.
78 *
79 * @param e element to be appended to this list
80 * @return {@code true} (as specified by {@link Collection#add})
81 * @throws UnsupportedOperationException if the {@code add} operation
82 * is not supported by this list
83 * @throws ClassCastException if the class of the specified element
84 * prevents it from being added to this list
85 * @throws NullPointerException if the specified element is null and this
86 * list does not permit null elements
87 * @throws IllegalArgumentException if some property of this element
88 * prevents it from being added to this list
89 */
90 public boolean add(E e) {
91 add(size(), e);
92 return true;
93 }
94
95 /**
96 * {@inheritDoc}
97 *
98 * @throws IndexOutOfBoundsException {@inheritDoc}
99 */
100 abstract public E get(int index);
101
102 /**
103 * {@inheritDoc}
104 *
105 * <p>This implementation always throws an
106 * {@code UnsupportedOperationException}.
107 *
108 * @throws UnsupportedOperationException {@inheritDoc}
109 * @throws ClassCastException {@inheritDoc}
110 * @throws NullPointerException {@inheritDoc}
111 * @throws IllegalArgumentException {@inheritDoc}
112 * @throws IndexOutOfBoundsException {@inheritDoc}
113 */
114 public E set(int index, E element) {
115 throw new UnsupportedOperationException();
116 }
117
118 /**
119 * {@inheritDoc}
120 *
121 * <p>This implementation always throws an
122 * {@code UnsupportedOperationException}.
123 *
124 * @throws UnsupportedOperationException {@inheritDoc}
125 * @throws ClassCastException {@inheritDoc}
126 * @throws NullPointerException {@inheritDoc}
127 * @throws IllegalArgumentException {@inheritDoc}
128 * @throws IndexOutOfBoundsException {@inheritDoc}
129 */
130 public void add(int index, E element) {
131 throw new UnsupportedOperationException();
132 }
133
134 /**
135 * {@inheritDoc}
136 *
137 * <p>This implementation always throws an
138 * {@code UnsupportedOperationException}.
139 *
140 * @throws UnsupportedOperationException {@inheritDoc}
141 * @throws IndexOutOfBoundsException {@inheritDoc}
142 */
143 public E remove(int index) {
144 throw new UnsupportedOperationException();
145 }
146
147
148 // Search Operations
149
150 /**
151 * {@inheritDoc}
152 *
153 * <p>This implementation first gets a list iterator (with
154 * {@code listIterator()}). Then, it iterates over the list until the
155 * specified element is found or the end of the list is reached.
156 *
157 * @throws ClassCastException {@inheritDoc}
158 * @throws NullPointerException {@inheritDoc}
159 */
160 public int indexOf(Object o) {
161 ListIterator<E> e = listIterator();
162 if (o==null) {
163 while (e.hasNext())
164 if (e.next()==null)
165 return e.previousIndex();
166 } else {
167 while (e.hasNext())
168 if (o.equals(e.next()))
169 return e.previousIndex();
170 }
171 return -1;
172 }
173
174 /**
175 * {@inheritDoc}
176 *
177 * <p>This implementation first gets a list iterator that points to the end
178 * of the list (with {@code listIterator(size())}). Then, it iterates
179 * backwards over the list until the specified element is found, or the
180 * beginning of the list is reached.
181 *
182 * @throws ClassCastException {@inheritDoc}
183 * @throws NullPointerException {@inheritDoc}
184 */
185 public int lastIndexOf(Object o) {
186 ListIterator<E> e = listIterator(size());
187 if (o==null) {
188 while (e.hasPrevious())
189 if (e.previous()==null)
190 return e.nextIndex();
191 } else {
192 while (e.hasPrevious())
193 if (o.equals(e.previous()))
194 return e.nextIndex();
195 }
196 return -1;
197 }
198
199
200 // Bulk Operations
201
202 /**
203 * Removes all of the elements from this list (optional operation).
204 * The list will be empty after this call returns.
205 *
206 * <p>This implementation calls {@code removeRange(0, size())}.
207 *
208 * <p>Note that this implementation throws an
209 * {@code UnsupportedOperationException} unless {@code remove(int
210 * index)} or {@code removeRange(int fromIndex, int toIndex)} is
211 * overridden.
212 *
213 * @throws UnsupportedOperationException if the {@code clear} operation
214 * is not supported by this list
215 */
216 public void clear() {
217 removeRange(0, size());
218 }
219
220 /**
221 * {@inheritDoc}
222 *
223 * <p>This implementation gets an iterator over the specified collection
224 * and iterates over it, inserting the elements obtained from the
225 * iterator into this list at the appropriate position, one at a time,
226 * using {@code add(int, E)}.
227 * Many implementations will override this method for efficiency.
228 *
229 * <p>Note that this implementation throws an
230 * {@code UnsupportedOperationException} unless
231 * {@link #add(int, Object) add(int, E)} is overridden.
232 *
233 * @throws UnsupportedOperationException {@inheritDoc}
234 * @throws ClassCastException {@inheritDoc}
235 * @throws NullPointerException {@inheritDoc}
236 * @throws IllegalArgumentException {@inheritDoc}
237 * @throws IndexOutOfBoundsException {@inheritDoc}
238 */
239 public boolean addAll(int index, Collection<? extends E> c) {
240 boolean modified = false;
241 Iterator<? extends E> e = c.iterator();
242 while (e.hasNext()) {
243 add(index++, e.next());
244 modified = true;
245 }
246 return modified;
247 }
248
249
250 // Iterators
251
252 /**
253 * Returns an iterator over the elements in this list in proper sequence.
254 *
255 * <p>This implementation returns a straightforward implementation of the
256 * iterator interface, relying on the backing list's {@code size()},
257 * {@code get(int)}, and {@code remove(int)} methods.
258 *
259 * <p>Note that the iterator returned by this method will throw an
260 * {@code UnsupportedOperationException} in response to its
261 * {@code remove} method unless the list's {@code remove(int)} method is
262 * overridden.
263 *
264 * <p>This implementation can be made to throw runtime exceptions in the
265 * face of concurrent modification, as described in the specification
266 * for the (protected) {@code modCount} field.
267 *
268 * @return an iterator over the elements in this list in proper sequence
269 *
270 * @see #modCount
271 */
272 public Iterator<E> iterator() {
273 return new Itr();
274 }
275
276 /**
277 * {@inheritDoc}
278 *
279 * <p>This implementation returns {@code listIterator(0)}.
280 *
281 * @see #listIterator(int)
282 */
283 public ListIterator<E> listIterator() {
284 return listIterator(0);
285 }
286
287 /**
288 * {@inheritDoc}
289 *
290 * <p>This implementation returns a straightforward implementation of the
291 * {@code ListIterator} interface that extends the implementation of the
292 * {@code Iterator} interface returned by the {@code iterator()} method.
293 * The {@code ListIterator} implementation relies on the backing list's
294 * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
295 * and {@code remove(int)} methods.
296 *
297 * <p>Note that the list iterator returned by this implementation will
298 * throw an {@code UnsupportedOperationException} in response to its
299 * {@code remove}, {@code set} and {@code add} methods unless the
300 * list's {@code remove(int)}, {@code set(int, E)}, and
301 * {@code add(int, E)} methods are overridden.
302 *
303 * <p>This implementation can be made to throw runtime exceptions in the
304 * face of concurrent modification, as described in the specification for
305 * the (protected) {@code modCount} field.
306 *
307 * @throws IndexOutOfBoundsException {@inheritDoc}
308 *
309 * @see #modCount
310 */
311 public ListIterator<E> listIterator(final int index) {
312 if (index<0 || index>size())
313 throw new IndexOutOfBoundsException("Index: "+index);
314
315 return new ListItr(index);
316 }
317
318 private class Itr implements Iterator<E> {
319 /**
320 * Index of element to be returned by subsequent call to next.
321 */
322 int cursor = 0;
323
324 /**
325 * Index of element returned by most recent call to next or
326 * previous. Reset to -1 if this element is deleted by a call
327 * to remove.
328 */
329 int lastRet = -1;
330
331 /**
332 * The modCount value that the iterator believes that the backing
333 * List should have. If this expectation is violated, the iterator
334 * has detected concurrent modification.
335 */
336 int expectedModCount = modCount;
337
338 public boolean hasNext() {
339 return cursor != size();
340 }
341
342 public E next() {
343 checkForComodification();
344 try {
345 E next = get(cursor);
346 lastRet = cursor++;
347 return next;
348 } catch (IndexOutOfBoundsException e) {
349 checkForComodification();
350 throw new NoSuchElementException();
351 }
352 }
353
354 public void remove() {
355 if (lastRet == -1)
356 throw new IllegalStateException();
357 checkForComodification();
358
359 try {
360 AbstractList.this.remove(lastRet);
361 if (lastRet < cursor)
362 cursor--;
363 lastRet = -1;
364 expectedModCount = modCount;
365 } catch (IndexOutOfBoundsException e) {
366 throw new ConcurrentModificationException();
367 }
368 }
369
370 final void checkForComodification() {
371 if (modCount != expectedModCount)
372 throw new ConcurrentModificationException();
373 }
374 }
375
376 private class ListItr extends Itr implements ListIterator<E> {
377 ListItr(int index) {
378 cursor = index;
379 }
380
381 public boolean hasPrevious() {
382 return cursor != 0;
383 }
384
385 public E previous() {
386 checkForComodification();
387 try {
388 int i = cursor - 1;
389 E previous = get(i);
390 lastRet = cursor = i;
391 return previous;
392 } catch (IndexOutOfBoundsException e) {
393 checkForComodification();
394 throw new NoSuchElementException();
395 }
396 }
397
398 public int nextIndex() {
399 return cursor;
400 }
401
402 public int previousIndex() {
403 return cursor-1;
404 }
405
406 public void set(E e) {
407 if (lastRet == -1)
408 throw new IllegalStateException();
409 checkForComodification();
410
411 try {
412 AbstractList.this.set(lastRet, e);
413 expectedModCount = modCount;
414 } catch (IndexOutOfBoundsException ex) {
415 throw new ConcurrentModificationException();
416 }
417 }
418
419 public void add(E e) {
420 checkForComodification();
421
422 try {
423 AbstractList.this.add(cursor++, e);
424 lastRet = -1;
425 expectedModCount = modCount;
426 } catch (IndexOutOfBoundsException ex) {
427 throw new ConcurrentModificationException();
428 }
429 }
430 }
431
432 /**
433 * {@inheritDoc}
434 *
435 * <p>This implementation returns a list that subclasses
436 * {@code AbstractList}. The subclass stores, in private fields, the
437 * offset of the subList within the backing list, the size of the subList
438 * (which can change over its lifetime), and the expected
439 * {@code modCount} value of the backing list. There are two variants
440 * of the subclass, one of which implements {@code RandomAccess}.
441 * If this list implements {@code RandomAccess} the returned list will
442 * be an instance of the subclass that implements {@code RandomAccess}.
443 *
444 * <p>The subclass's {@code set(int, E)}, {@code get(int)},
445 * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
446 * Collection)} and {@code removeRange(int, int)} methods all
447 * delegate to the corresponding methods on the backing abstract list,
448 * after bounds-checking the index and adjusting for the offset. The
449 * {@code addAll(Collection c)} method merely returns {@code addAll(size,
450 * c)}.
451 *
452 * <p>The {@code listIterator(int)} method returns a "wrapper object"
453 * over a list iterator on the backing list, which is created with the
454 * corresponding method on the backing list. The {@code iterator} method
455 * merely returns {@code listIterator()}, and the {@code size} method
456 * merely returns the subclass's {@code size} field.
457 *
458 * <p>All methods first check to see if the actual {@code modCount} of
459 * the backing list is equal to its expected value, and throw a
460 * {@code ConcurrentModificationException} if it is not.
461 *
462 * @throws IndexOutOfBoundsException endpoint index value out of range
463 * {@code (fromIndex < 0 || toIndex > size)}
464 * @throws IllegalArgumentException if the endpoint indices are out of order
465 * {@code (fromIndex > toIndex)}
466 */
467 public List<E> subList(int fromIndex, int toIndex) {
468 return (this instanceof RandomAccess ?
469 new RandomAccessSubList<E>(this, fromIndex, toIndex) :
470 new SubList<E>(this, fromIndex, toIndex));
471 }
472
473 // Comparison and hashing
474
475 /**
476 * Compares the specified object with this list for equality. Returns
477 * {@code true} if and only if the specified object is also a list, both
478 * lists have the same size, and all corresponding pairs of elements in
479 * the two lists are <i>equal</i>. (Two elements {@code e1} and
480 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
481 * e1.equals(e2))}.) In other words, two lists are defined to be
482 * equal if they contain the same elements in the same order.<p>
483 *
484 * This implementation first checks if the specified object is this
485 * list. If so, it returns {@code true}; if not, it checks if the
486 * specified object is a list. If not, it returns {@code false}; if so,
487 * it iterates over both lists, comparing corresponding pairs of elements.
488 * If any comparison returns {@code false}, this method returns
489 * {@code false}. If either iterator runs out of elements before the
490 * other it returns {@code false} (as the lists are of unequal length);
491 * otherwise it returns {@code true} when the iterations complete.
492 *
493 * @param o the object to be compared for equality with this list
494 * @return {@code true} if the specified object is equal to this list
495 */
496 public boolean equals(Object o) {
497 if (o == this)
498 return true;
499 if (!(o instanceof List))
500 return false;
501
502 ListIterator<E> e1 = listIterator();
503 ListIterator e2 = ((List) o).listIterator();
504 while(e1.hasNext() && e2.hasNext()) {
505 E o1 = e1.next();
506 Object o2 = e2.next();
507 if (!(o1==null ? o2==null : o1.equals(o2)))
508 return false;
509 }
510 return !(e1.hasNext() || e2.hasNext());
511 }
512
513 /**
514 * Returns the hash code value for this list.
515 *
516 * <p>This implementation uses exactly the code that is used to define the
517 * list hash function in the documentation for the {@link List#hashCode}
518 * method.
519 *
520 * @return the hash code value for this list
521 */
522 public int hashCode() {
523 int hashCode = 1;
524 Iterator<E> i = iterator();
525 while (i.hasNext()) {
526 E obj = i.next();
527 hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
528 }
529 return hashCode;
530 }
531
532 /**
533 * Removes from this list all of the elements whose index is between
534 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
535 * Shifts any succeeding elements to the left (reduces their index).
536 * This call shortens the ArrayList by {@code (toIndex - fromIndex)}
537 * elements. (If {@code toIndex==fromIndex}, this operation has no
538 * effect.)
539 *
540 * <p>This method is called by the {@code clear} operation on this list
541 * and its subLists. Overriding this method to take advantage of
542 * the internals of the list implementation can <i>substantially</i>
543 * improve the performance of the {@code clear} operation on this list
544 * and its subLists.
545 *
546 * <p>This implementation gets a list iterator positioned before
547 * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
548 * followed by {@code ListIterator.remove} until the entire range has
549 * been removed. <b>Note: if {@code ListIterator.remove} requires linear
550 * time, this implementation requires quadratic time.</b>
551 *
552 * @param fromIndex index of first element to be removed
553 * @param toIndex index after last element to be removed
554 */
555 protected void removeRange(int fromIndex, int toIndex) {
556 ListIterator<E> it = listIterator(fromIndex);
557 for (int i=0, n=toIndex-fromIndex; i<n; i++) {
558 it.next();
559 it.remove();
560 }
561 }
562
563 /**
564 * The number of times this list has been <i>structurally modified</i>.
565 * Structural modifications are those that change the size of the
566 * list, or otherwise perturb it in such a fashion that iterations in
567 * progress may yield incorrect results.
568 *
569 * <p>This field is used by the iterator and list iterator implementation
570 * returned by the {@code iterator} and {@code listIterator} methods.
571 * If the value of this field changes unexpectedly, the iterator (or list
572 * iterator) will throw a {@code ConcurrentModificationException} in
573 * response to the {@code next}, {@code remove}, {@code previous},
574 * {@code set} or {@code add} operations. This provides
575 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
576 * the face of concurrent modification during iteration.
577 *
578 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
579 * wishes to provide fail-fast iterators (and list iterators), then it
580 * merely has to increment this field in its {@code add(int, E)} and
581 * {@code remove(int)} methods (and any other methods that it overrides
582 * that result in structural modifications to the list). A single call to
583 * {@code add(int, E)} or {@code remove(int)} must add no more than
584 * one to this field, or the iterators (and list iterators) will throw
585 * bogus {@code ConcurrentModificationExceptions}. If an implementation
586 * does not wish to provide fail-fast iterators, this field may be
587 * ignored.
588 */
589 protected transient int modCount = 0;
590 }
591
592 class SubList<E> extends AbstractList<E> {
593 private AbstractList<E> l;
594 private int offset;
595 private int size;
596 private int expectedModCount;
597
598 SubList(AbstractList<E> list, int fromIndex, int toIndex) {
599 if (fromIndex < 0)
600 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
601 if (toIndex > list.size())
602 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
603 if (fromIndex > toIndex)
604 throw new IllegalArgumentException("fromIndex(" + fromIndex +
605 ") > toIndex(" + toIndex + ")");
606 l = list;
607 offset = fromIndex;
608 size = toIndex - fromIndex;
609 expectedModCount = l.modCount;
610 }
611
612 public E set(int index, E element) {
613 rangeCheck(index);
614 checkForComodification();
615 return l.set(index+offset, element);
616 }
617
618 public E get(int index) {
619 rangeCheck(index);
620 checkForComodification();
621 return l.get(index+offset);
622 }
623
624 public int size() {
625 checkForComodification();
626 return size;
627 }
628
629 public void add(int index, E element) {
630 if (index<0 || index>size)
631 throw new IndexOutOfBoundsException();
632 checkForComodification();
633 l.add(index+offset, element);
634 expectedModCount = l.modCount;
635 size++;
636 modCount++;
637 }
638
639 public E remove(int index) {
640 rangeCheck(index);
641 checkForComodification();
642 E result = l.remove(index+offset);
643 expectedModCount = l.modCount;
644 size--;
645 modCount++;
646 return result;
647 }
648
649 protected void removeRange(int fromIndex, int toIndex) {
650 checkForComodification();
651 l.removeRange(fromIndex+offset, toIndex+offset);
652 expectedModCount = l.modCount;
653 size -= (toIndex-fromIndex);
654 modCount++;
655 }
656
657 public boolean addAll(Collection<? extends E> c) {
658 return addAll(size, c);
659 }
660
661 public boolean addAll(int index, Collection<? extends E> c) {
662 if (index<0 || index>size)
663 throw new IndexOutOfBoundsException(
664 "Index: "+index+", Size: "+size);
665 int cSize = c.size();
666 if (cSize==0)
667 return false;
668
669 checkForComodification();
670 l.addAll(offset+index, c);
671 expectedModCount = l.modCount;
672 size += cSize;
673 modCount++;
674 return true;
675 }
676
677 public Iterator<E> iterator() {
678 return listIterator();
679 }
680
681 public ListIterator<E> listIterator(final int index) {
682 checkForComodification();
683 if (index<0 || index>size)
684 throw new IndexOutOfBoundsException(
685 "Index: "+index+", Size: "+size);
686
687 return new ListIterator<E>() {
688 private ListIterator<E> i = l.listIterator(index+offset);
689
690 public boolean hasNext() {
691 return nextIndex() < size;
692 }
693
694 public E next() {
695 if (hasNext())
696 return i.next();
697 else
698 throw new NoSuchElementException();
699 }
700
701 public boolean hasPrevious() {
702 return previousIndex() >= 0;
703 }
704
705 public E previous() {
706 if (hasPrevious())
707 return i.previous();
708 else
709 throw new NoSuchElementException();
710 }
711
712 public int nextIndex() {
713 return i.nextIndex() - offset;
714 }
715
716 public int previousIndex() {
717 return i.previousIndex() - offset;
718 }
719
720 public void remove() {
721 i.remove();
722 expectedModCount = l.modCount;
723 size--;
724 modCount++;
725 }
726
727 public void set(E e) {
728 i.set(e);
729 }
730
731 public void add(E e) {
732 i.add(e);
733 expectedModCount = l.modCount;
734 size++;
735 modCount++;
736 }
737 };
738 }
739
740 public List<E> subList(int fromIndex, int toIndex) {
741 return new SubList<E>(this, fromIndex, toIndex);
742 }
743
744 private void rangeCheck(int index) {
745 if (index<0 || index>=size)
746 throw new IndexOutOfBoundsException("Index: "+index+
747 ",Size: "+size);
748 }
749
750 private void checkForComodification() {
751 if (l.modCount != expectedModCount)
752 throw new ConcurrentModificationException();
753 }
754 }
755
756 class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
757 RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
758 super(list, fromIndex, toIndex);
759 }
760
761 public List<E> subList(int fromIndex, int toIndex) {
762 return new RandomAccessSubList<E>(this, fromIndex, toIndex);
763 }
764 }
765