1 /* AbstractList.java -- Abstract implementation of most of List
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005
3 Free Software Foundation, Inc.
5 This file is part of GNU Classpath.
7 GNU Classpath is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU Classpath is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Classpath; see the file COPYING. If not, write to the
19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
22 Linking this library statically or dynamically with other modules is
23 making a combined work based on this library. Thus, the terms and
24 conditions of the GNU General Public License cover the whole
27 As a special exception, the copyright holders of this library give you
28 permission to link this library with independent modules to produce an
29 executable, regardless of the license terms of these independent
30 modules, and to copy and distribute the resulting executable under
31 terms of your choice, provided that you also meet, for each linked
32 independent module, the terms and conditions of the license of that
33 module. An independent module is a module which is not derived from
34 or based on this library. If you modify this library, you may extend
35 this exception to your version of the library, but you are not
36 obligated to do so. If you do not wish to do so, delete this
37 exception statement from your version. */
43 * A basic implementation of most of the methods in the List interface to make
44 * it easier to create a List based on a random-access data structure. If
45 * the list is sequential (such as a linked list), use AbstractSequentialList.
46 * To create an unmodifiable list, it is only necessary to override the
47 * size() and get(int) methods (this contrasts with all other abstract
48 * collection classes which require an iterator to be provided). To make the
49 * list modifiable, the set(int, Object) method should also be overridden, and
50 * to make the list resizable, the add(int, Object) and remove(int) methods
51 * should be overridden too. Other methods should be overridden if the
52 * backing data structure allows for a more efficient implementation.
53 * The precise implementation used by AbstractList is documented, so that
54 * subclasses can tell which methods could be implemented more efficiently.
57 * As recommended by Collection and List, the subclass should provide at
58 * least a no-argument and a Collection constructor. This class is not
61 * @author Original author unknown
62 * @author Bryce McKinlay
63 * @author Eric Blake (ebb9@email.byu.edu)
66 * @see AbstractSequentialList
67 * @see AbstractCollection
70 * @status updated to 1.4
72 public abstract class AbstractList
<E
>
73 extends AbstractCollection
<E
>
77 * A count of the number of structural modifications that have been made to
78 * the list (that is, insertions and removals). Structural modifications
79 * are ones which change the list size or affect how iterations would
80 * behave. This field is available for use by Iterator and ListIterator,
81 * in order to throw a {@link ConcurrentModificationException} in response
82 * to the next operation on the iterator. This <i>fail-fast</i> behavior
83 * saves the user from many subtle bugs otherwise possible from concurrent
84 * modification during iteration.
87 * To make lists fail-fast, increment this field by just 1 in the
88 * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
89 * Otherwise, this field may be ignored.
91 protected transient int modCount
;
94 * The main constructor, for use by subclasses.
96 protected AbstractList()
101 * Returns the elements at the specified position in the list.
103 * @param index the element to return
104 * @return the element at that position
105 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
107 public abstract E
get(int index
);
110 * Insert an element into the list at a given position (optional operation).
111 * This shifts all existing elements from that position to the end one
112 * index to the right. This version of add has no return, since it is
113 * assumed to always succeed if there is no exception. This implementation
114 * always throws UnsupportedOperationException, and must be overridden to
115 * make a modifiable List. If you want fail-fast iterators, be sure to
116 * increment modCount when overriding this.
118 * @param index the location to insert the item
119 * @param o the object to insert
120 * @throws UnsupportedOperationException if this list does not support the
122 * @throws IndexOutOfBoundsException if index < 0 || index > size()
123 * @throws ClassCastException if o cannot be added to this list due to its
125 * @throws IllegalArgumentException if o cannot be added to this list for
129 public void add(int index
, E o
)
131 throw new UnsupportedOperationException();
135 * Add an element to the end of the list (optional operation). If the list
136 * imposes restraints on what can be inserted, such as no null elements,
137 * this should be documented. This implementation calls
138 * <code>add(size(), o);</code>, and will fail if that version does.
140 * @param o the object to add
141 * @return true, as defined by Collection for a modified list
142 * @throws UnsupportedOperationException if this list does not support the
144 * @throws ClassCastException if o cannot be added to this list due to its
146 * @throws IllegalArgumentException if o cannot be added to this list for
148 * @see #add(int, Object)
150 public boolean add(E o
)
157 * Insert the contents of a collection into the list at a given position
158 * (optional operation). Shift all elements at that position to the right
159 * by the number of elements inserted. This operation is undefined if
160 * this list is modified during the operation (for example, if you try
161 * to insert a list into itself). This implementation uses the iterator of
162 * the collection, repeatedly calling add(int, Object); this will fail
163 * if add does. This can often be made more efficient.
165 * @param index the location to insert the collection
166 * @param c the collection to insert
167 * @return true if the list was modified by this action, that is, if c is
169 * @throws UnsupportedOperationException if this list does not support the
171 * @throws IndexOutOfBoundsException if index < 0 || index > size()
172 * @throws ClassCastException if some element of c cannot be added to this
173 * list due to its type
174 * @throws IllegalArgumentException if some element of c cannot be added
175 * to this list for some other reason
176 * @throws NullPointerException if the specified collection is null
177 * @see #add(int, Object)
179 public boolean addAll(int index
, Collection
<?
extends E
> c
)
181 Iterator
<?
extends E
> itr
= c
.iterator();
183 for (int pos
= size
; pos
> 0; pos
--)
184 add(index
++, itr
.next());
189 * Clear the list, such that a subsequent call to isEmpty() would return
190 * true (optional operation). This implementation calls
191 * <code>removeRange(0, size())</code>, so it will fail unless remove
192 * or removeRange is overridden.
194 * @throws UnsupportedOperationException if this list does not support the
197 * @see #removeRange(int, int)
201 removeRange(0, size());
205 * Test whether this list is equal to another object. A List is defined to be
206 * equal to an object if and only if that object is also a List, and the two
207 * lists have the same sequence. Two lists l1 and l2 are equal if and only
208 * if <code>l1.size() == l2.size()</code>, and for every integer n between 0
209 * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ?
210 * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
213 * This implementation returns true if the object is this, or false if the
214 * object is not a List. Otherwise, it iterates over both lists (with
215 * iterator()), returning false if two elements compare false or one list
216 * is shorter, and true if the iteration completes successfully.
218 * @param o the object to test for equality with this list
219 * @return true if o is equal to this list
220 * @see Object#equals(Object)
223 public boolean equals(Object o
)
227 if (! (o
instanceof List
))
230 if (size
!= ((List
) o
).size())
233 Iterator
<E
> itr1
= iterator();
234 Iterator itr2
= ((List
) o
).iterator();
237 if (! equals(itr1
.next(), itr2
.next()))
243 * Obtains a hash code for this list. In order to obey the general
244 * contract of the hashCode method of class Object, this value is
245 * calculated as follows:
248 Iterator i = list.iterator();
251 Object obj = i.next();
252 hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
255 * This ensures that the general contract of Object.hashCode() is adhered to.
257 * @return the hash code of this list
259 * @see Object#hashCode()
260 * @see #equals(Object)
262 public int hashCode()
265 Iterator
<E
> itr
= iterator();
268 hashCode
= 31 * hashCode
+ hashCode(itr
.next());
273 * Obtain the first index at which a given object is to be found in this
274 * list. This implementation follows a listIterator() until a match is found,
275 * or returns -1 if the list end is reached.
277 * @param o the object to search for
278 * @return the least integer n such that <code>o == null ? get(n) == null :
279 * o.equals(get(n))</code>, or -1 if there is no such index
281 public int indexOf(Object o
)
283 ListIterator
<E
> itr
= listIterator();
285 for (int pos
= 0; pos
< size
; pos
++)
286 if (equals(o
, itr
.next()))
292 * Obtain an Iterator over this list, whose sequence is the list order.
293 * This implementation uses size(), get(int), and remove(int) of the
294 * backing list, and does not support remove unless the list does. This
295 * implementation is fail-fast if you correctly maintain modCount.
296 * Also, this implementation is specified by Sun to be distinct from
297 * listIterator, although you could easily implement it as
298 * <code>return listIterator(0)</code>.
300 * @return an Iterator over the elements of this list, in order
303 public Iterator
<E
> iterator()
305 // Bah, Sun's implementation forbids using listIterator(0).
306 return new Iterator
<E
>()
309 private int size
= size();
310 private int last
= -1;
311 private int knownMod
= modCount
;
313 // This will get inlined, since it is private.
315 * Checks for modifications made to the list from
316 * elsewhere while iteration is in progress.
318 * @throws ConcurrentModificationException if the
319 * list has been modified elsewhere.
321 private void checkMod()
323 if (knownMod
!= modCount
)
324 throw new ConcurrentModificationException();
328 * Tests to see if there are any more objects to
331 * @return True if the end of the list has not yet been
334 public boolean hasNext()
340 * Retrieves the next object from the list.
342 * @return The next object.
343 * @throws NoSuchElementException if there are
344 * no more objects to retrieve.
345 * @throws ConcurrentModificationException if the
346 * list has been modified elsewhere.
352 throw new NoSuchElementException();
358 * Removes the last object retrieved by <code>next()</code>
359 * from the list, if the list supports object removal.
361 * @throws ConcurrentModificationException if the list
362 * has been modified elsewhere.
363 * @throws IllegalStateException if the iterator is positioned
364 * before the start of the list or the last object has already
366 * @throws UnsupportedOperationException if the list does
367 * not support removing elements.
373 throw new IllegalStateException();
374 AbstractList
.this.remove(last
);
384 * Obtain the last index at which a given object is to be found in this
385 * list. This implementation grabs listIterator(size()), then searches
386 * backwards for a match or returns -1.
388 * @return the greatest integer n such that <code>o == null ? get(n) == null
389 * : o.equals(get(n))</code>, or -1 if there is no such index
391 public int lastIndexOf(Object o
)
394 ListIterator
<E
> itr
= listIterator(pos
);
396 if (equals(o
, itr
.previous()))
402 * Obtain a ListIterator over this list, starting at the beginning. This
403 * implementation returns listIterator(0).
405 * @return a ListIterator over the elements of this list, in order, starting
408 public ListIterator
<E
> listIterator()
410 return listIterator(0);
414 * Obtain a ListIterator over this list, starting at a given position.
415 * A first call to next() would return the same as get(index), and a
416 * first call to previous() would return the same as get(index - 1).
419 * This implementation uses size(), get(int), set(int, Object),
420 * add(int, Object), and remove(int) of the backing list, and does not
421 * support remove, set, or add unless the list does. This implementation
422 * is fail-fast if you correctly maintain modCount.
424 * @param index the position, between 0 and size() inclusive, to begin the
426 * @return a ListIterator over the elements of this list, in order, starting
428 * @throws IndexOutOfBoundsException if index < 0 || index > size()
431 public ListIterator
<E
> listIterator(final int index
)
433 if (index
< 0 || index
> size())
434 throw new IndexOutOfBoundsException("Index: " + index
+ ", Size:"
437 return new ListIterator
<E
>()
439 private int knownMod
= modCount
;
440 private int position
= index
;
441 private int lastReturned
= -1;
442 private int size
= size();
444 // This will get inlined, since it is private.
446 * Checks for modifications made to the list from
447 * elsewhere while iteration is in progress.
449 * @throws ConcurrentModificationException if the
450 * list has been modified elsewhere.
452 private void checkMod()
454 if (knownMod
!= modCount
)
455 throw new ConcurrentModificationException();
459 * Tests to see if there are any more objects to
462 * @return True if the end of the list has not yet been
465 public boolean hasNext()
467 return position
< size
;
471 * Tests to see if there are objects prior to the
472 * current position in the list.
474 * @return True if objects exist prior to the current
475 * position of the iterator.
477 public boolean hasPrevious()
483 * Retrieves the next object from the list.
485 * @return The next object.
486 * @throws NoSuchElementException if there are no
487 * more objects to retrieve.
488 * @throws ConcurrentModificationException if the
489 * list has been modified elsewhere.
494 if (position
== size
)
495 throw new NoSuchElementException();
496 lastReturned
= position
;
497 return get(position
++);
501 * Retrieves the previous object from the list.
503 * @return The next object.
504 * @throws NoSuchElementException if there are no
505 * previous objects to retrieve.
506 * @throws ConcurrentModificationException if the
507 * list has been modified elsewhere.
513 throw new NoSuchElementException();
514 lastReturned
= --position
;
515 return get(lastReturned
);
519 * Returns the index of the next element in the
520 * list, which will be retrieved by <code>next()</code>
522 * @return The index of the next element.
524 public int nextIndex()
530 * Returns the index of the previous element in the
531 * list, which will be retrieved by <code>previous()</code>
533 * @return The index of the previous element.
535 public int previousIndex()
541 * Removes the last object retrieved by <code>next()</code>
542 * or <code>previous()</code> from the list, if the list
543 * supports object removal.
545 * @throws IllegalStateException if the iterator is positioned
546 * before the start of the list or the last object has already
548 * @throws UnsupportedOperationException if the list does
549 * not support removing elements.
550 * @throws ConcurrentModificationException if the list
551 * has been modified elsewhere.
556 if (lastReturned
< 0)
557 throw new IllegalStateException();
558 AbstractList
.this.remove(lastReturned
);
560 position
= lastReturned
;
566 * Replaces the last object retrieved by <code>next()</code>
567 * or <code>previous</code> with o, if the list supports object
568 * replacement and an add or remove operation has not already
571 * @throws IllegalStateException if the iterator is positioned
572 * before the start of the list or the last object has already
574 * @throws UnsupportedOperationException if the list doesn't support
575 * the addition or removal of elements.
576 * @throws ClassCastException if the type of o is not a valid type
578 * @throws IllegalArgumentException if something else related to o
579 * prevents its addition.
580 * @throws ConcurrentModificationException if the list
581 * has been modified elsewhere.
586 if (lastReturned
< 0)
587 throw new IllegalStateException();
588 AbstractList
.this.set(lastReturned
, o
);
592 * Adds the supplied object before the element that would be returned
593 * by a call to <code>next()</code>, if the list supports addition.
595 * @param o The object to add to the list.
596 * @throws UnsupportedOperationException if the list doesn't support
597 * the addition of new elements.
598 * @throws ClassCastException if the type of o is not a valid type
600 * @throws IllegalArgumentException if something else related to o
601 * prevents its addition.
602 * @throws ConcurrentModificationException if the list
603 * has been modified elsewhere.
608 AbstractList
.this.add(position
++, o
);
617 * Remove the element at a given position in this list (optional operation).
618 * Shifts all remaining elements to the left to fill the gap. This
619 * implementation always throws an UnsupportedOperationException.
620 * If you want fail-fast iterators, be sure to increment modCount when
623 * @param index the position within the list of the object to remove
624 * @return the object that was removed
625 * @throws UnsupportedOperationException if this list does not support the
627 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
630 public E
remove(int index
)
632 throw new UnsupportedOperationException();
636 * Remove a subsection of the list. This is called by the clear and
637 * removeRange methods of the class which implements subList, which are
638 * difficult for subclasses to override directly. Therefore, this method
639 * should be overridden instead by the more efficient implementation, if one
640 * exists. Overriding this can reduce quadratic efforts to constant time
644 * This implementation first checks for illegal or out of range arguments. It
645 * then obtains a ListIterator over the list using listIterator(fromIndex).
646 * It then calls next() and remove() on this iterator repeatedly, toIndex -
649 * @param fromIndex the index, inclusive, to remove from.
650 * @param toIndex the index, exclusive, to remove to.
651 * @throws UnsupportedOperationException if the list does
652 * not support removing elements.
654 protected void removeRange(int fromIndex
, int toIndex
)
656 ListIterator
<E
> itr
= listIterator(fromIndex
);
657 for (int index
= fromIndex
; index
< toIndex
; index
++)
665 * Replace an element of this list with another object (optional operation).
666 * This implementation always throws an UnsupportedOperationException.
668 * @param index the position within this list of the element to be replaced
669 * @param o the object to replace it with
670 * @return the object that was replaced
671 * @throws UnsupportedOperationException if this list does not support the
673 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
674 * @throws ClassCastException if o cannot be added to this list due to its
676 * @throws IllegalArgumentException if o cannot be added to this list for
679 public E
set(int index
, E o
)
681 throw new UnsupportedOperationException();
685 * Obtain a List view of a subsection of this list, from fromIndex
686 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
687 * sublist is empty. The returned list should be modifiable if and only
688 * if this list is modifiable. Changes to the returned list should be
689 * reflected in this list. If this list is structurally modified in
690 * any way other than through the returned list, the result of any subsequent
691 * operations on the returned list is undefined.
694 * This implementation returns a subclass of AbstractList. It stores, in
695 * private fields, the offset and size of the sublist, and the expected
696 * modCount of the backing list. If the backing list implements RandomAccess,
697 * the sublist will also.
700 * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
701 * <code>add(int, Object)</code>, <code>remove(int)</code>,
702 * <code>addAll(int, Collection)</code> and
703 * <code>removeRange(int, int)</code> methods all delegate to the
704 * corresponding methods on the backing abstract list, after
705 * bounds-checking the index and adjusting for the offset. The
706 * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
707 * The <code>listIterator(int)</code> method returns a "wrapper object"
708 * over a list iterator on the backing list, which is created with the
709 * corresponding method on the backing list. The <code>iterator()</code>
710 * method merely returns listIterator(), and the <code>size()</code> method
711 * merely returns the subclass's size field.
714 * All methods first check to see if the actual modCount of the backing
715 * list is equal to its expected value, and throw a
716 * ConcurrentModificationException if it is not.
718 * @param fromIndex the index that the returned list should start from
720 * @param toIndex the index that the returned list should go to (exclusive)
721 * @return a List backed by a subsection of this list
722 * @throws IndexOutOfBoundsException if fromIndex < 0
723 * || toIndex > size()
724 * @throws IllegalArgumentException if fromIndex > toIndex
725 * @see ConcurrentModificationException
728 public List
<E
> subList(int fromIndex
, int toIndex
)
730 // This follows the specification of AbstractList, but is inconsistent
731 // with the one in List. Don't you love Sun's inconsistencies?
732 if (fromIndex
> toIndex
)
733 throw new IllegalArgumentException(fromIndex
+ " > " + toIndex
);
734 if (fromIndex
< 0 || toIndex
> size())
735 throw new IndexOutOfBoundsException();
737 if (this instanceof RandomAccess
)
738 return new RandomAccessSubList
<E
>(this, fromIndex
, toIndex
);
739 return new SubList
<E
>(this, fromIndex
, toIndex
);
743 * This class follows the implementation requirements set forth in
744 * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
745 * by using a non-public top-level class in the same package.
747 * @author Original author unknown
748 * @author Eric Blake (ebb9@email.byu.edu)
750 private static class SubList
<E
> extends AbstractList
<E
>
752 // Package visible, for use by iterator.
753 /** The original list. */
754 final AbstractList
<E
> backingList
;
755 /** The index of the first element of the sublist. */
757 /** The size of the sublist. */
761 * Construct the sublist.
763 * @param backing the list this comes from
764 * @param fromIndex the lower bound, inclusive
765 * @param toIndex the upper bound, exclusive
767 SubList(AbstractList
<E
> backing
, int fromIndex
, int toIndex
)
769 backingList
= backing
;
770 modCount
= backing
.modCount
;
772 size
= toIndex
- fromIndex
;
776 * This method checks the two modCount fields to ensure that there has
777 * not been a concurrent modification, returning if all is okay.
779 * @throws ConcurrentModificationException if the backing list has been
780 * modified externally to this sublist
782 // This can be inlined. Package visible, for use by iterator.
785 if (modCount
!= backingList
.modCount
)
786 throw new ConcurrentModificationException();
790 * This method checks that a value is between 0 and size (inclusive). If
791 * it is not, an exception is thrown.
793 * @param index the value to check
794 * @throws IndexOutOfBoundsException if index < 0 || index > size()
796 // This will get inlined, since it is private.
797 private void checkBoundsInclusive(int index
)
799 if (index
< 0 || index
> size
)
800 throw new IndexOutOfBoundsException("Index: " + index
+ ", Size:"
805 * This method checks that a value is between 0 (inclusive) and size
806 * (exclusive). If it is not, an exception is thrown.
808 * @param index the value to check
809 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
811 // This will get inlined, since it is private.
812 private void checkBoundsExclusive(int index
)
814 if (index
< 0 || index
>= size
)
815 throw new IndexOutOfBoundsException("Index: " + index
+ ", Size:"
820 * Specified by AbstractList.subList to return the private field size.
822 * @return the sublist size
823 * @throws ConcurrentModificationException if the backing list has been
824 * modified externally to this sublist
833 * Specified by AbstractList.subList to delegate to the backing list.
835 * @param index the location to modify
836 * @param o the new value
837 * @return the old value
838 * @throws ConcurrentModificationException if the backing list has been
839 * modified externally to this sublist
840 * @throws UnsupportedOperationException if the backing list does not
841 * support the set operation
842 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
843 * @throws ClassCastException if o cannot be added to the backing list due
845 * @throws IllegalArgumentException if o cannot be added to the backing list
846 * for some other reason
848 public E
set(int index
, E o
)
851 checkBoundsExclusive(index
);
852 return backingList
.set(index
+ offset
, o
);
856 * Specified by AbstractList.subList to delegate to the backing list.
858 * @param index the location to get from
859 * @return the object at that location
860 * @throws ConcurrentModificationException if the backing list has been
861 * modified externally to this sublist
862 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
864 public E
get(int index
)
867 checkBoundsExclusive(index
);
868 return backingList
.get(index
+ offset
);
872 * Specified by AbstractList.subList to delegate to the backing list.
874 * @param index the index to insert at
875 * @param o the object to add
876 * @throws ConcurrentModificationException if the backing list has been
877 * modified externally to this sublist
878 * @throws IndexOutOfBoundsException if index < 0 || index > size()
879 * @throws UnsupportedOperationException if the backing list does not
880 * support the add operation.
881 * @throws ClassCastException if o cannot be added to the backing list due
883 * @throws IllegalArgumentException if o cannot be added to the backing
884 * list for some other reason.
886 public void add(int index
, E o
)
889 checkBoundsInclusive(index
);
890 backingList
.add(index
+ offset
, o
);
892 modCount
= backingList
.modCount
;
896 * Specified by AbstractList.subList to delegate to the backing list.
898 * @param index the index to remove
899 * @return the removed object
900 * @throws ConcurrentModificationException if the backing list has been
901 * modified externally to this sublist
902 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
903 * @throws UnsupportedOperationException if the backing list does not
904 * support the remove operation
906 public E
remove(int index
)
909 checkBoundsExclusive(index
);
910 E o
= backingList
.remove(index
+ offset
);
912 modCount
= backingList
.modCount
;
917 * Specified by AbstractList.subList to delegate to the backing list.
918 * This does no bounds checking, as it assumes it will only be called
919 * by trusted code like clear() which has already checked the bounds.
921 * @param fromIndex the lower bound, inclusive
922 * @param toIndex the upper bound, exclusive
923 * @throws ConcurrentModificationException if the backing list has been
924 * modified externally to this sublist
925 * @throws UnsupportedOperationException if the backing list does
926 * not support removing elements.
928 protected void removeRange(int fromIndex
, int toIndex
)
932 backingList
.removeRange(offset
+ fromIndex
, offset
+ toIndex
);
933 size
-= toIndex
- fromIndex
;
934 modCount
= backingList
.modCount
;
938 * Specified by AbstractList.subList to delegate to the backing list.
940 * @param index the location to insert at
941 * @param c the collection to insert
942 * @return true if this list was modified, in other words, c is non-empty
943 * @throws ConcurrentModificationException if the backing list has been
944 * modified externally to this sublist
945 * @throws IndexOutOfBoundsException if index < 0 || index > size()
946 * @throws UnsupportedOperationException if this list does not support the
948 * @throws ClassCastException if some element of c cannot be added to this
949 * list due to its type
950 * @throws IllegalArgumentException if some element of c cannot be added
951 * to this list for some other reason
952 * @throws NullPointerException if the specified collection is null
954 public boolean addAll(int index
, Collection
<?
extends E
> c
)
957 checkBoundsInclusive(index
);
958 int csize
= c
.size();
959 boolean result
= backingList
.addAll(offset
+ index
, c
);
961 modCount
= backingList
.modCount
;
966 * Specified by AbstractList.subList to return addAll(size, c).
968 * @param c the collection to insert
969 * @return true if this list was modified, in other words, c is non-empty
970 * @throws ConcurrentModificationException if the backing list has been
971 * modified externally to this sublist
972 * @throws UnsupportedOperationException if this list does not support the
974 * @throws ClassCastException if some element of c cannot be added to this
975 * list due to its type
976 * @throws IllegalArgumentException if some element of c cannot be added
977 * to this list for some other reason
978 * @throws NullPointerException if the specified collection is null
980 public boolean addAll(Collection
<?
extends E
> c
)
982 return addAll(size
, c
);
986 * Specified by AbstractList.subList to return listIterator().
988 * @return an iterator over the sublist
990 public Iterator
<E
> iterator()
992 return listIterator();
996 * Specified by AbstractList.subList to return a wrapper around the
997 * backing list's iterator.
999 * @param index the start location of the iterator
1000 * @return a list iterator over the sublist
1001 * @throws ConcurrentModificationException if the backing list has been
1002 * modified externally to this sublist
1003 * @throws IndexOutOfBoundsException if the value is out of range
1005 public ListIterator
<E
> listIterator(final int index
)
1008 checkBoundsInclusive(index
);
1010 return new ListIterator
<E
>()
1012 private final ListIterator
<E
> i
1013 = backingList
.listIterator(index
+ offset
);
1014 private int position
= index
;
1017 * Tests to see if there are any more objects to
1020 * @return True if the end of the list has not yet been
1023 public boolean hasNext()
1025 return position
< size
;
1029 * Tests to see if there are objects prior to the
1030 * current position in the list.
1032 * @return True if objects exist prior to the current
1033 * position of the iterator.
1035 public boolean hasPrevious()
1037 return position
> 0;
1041 * Retrieves the next object from the list.
1043 * @return The next object.
1044 * @throws NoSuchElementException if there are no
1045 * more objects to retrieve.
1046 * @throws ConcurrentModificationException if the
1047 * list has been modified elsewhere.
1051 if (position
== size
)
1052 throw new NoSuchElementException();
1058 * Retrieves the previous object from the list.
1060 * @return The next object.
1061 * @throws NoSuchElementException if there are no
1062 * previous objects to retrieve.
1063 * @throws ConcurrentModificationException if the
1064 * list has been modified elsewhere.
1069 throw new NoSuchElementException();
1071 return i
.previous();
1075 * Returns the index of the next element in the
1076 * list, which will be retrieved by <code>next()</code>
1078 * @return The index of the next element.
1080 public int nextIndex()
1082 return i
.nextIndex() - offset
;
1086 * Returns the index of the previous element in the
1087 * list, which will be retrieved by <code>previous()</code>
1089 * @return The index of the previous element.
1091 public int previousIndex()
1093 return i
.previousIndex() - offset
;
1097 * Removes the last object retrieved by <code>next()</code>
1098 * from the list, if the list supports object removal.
1100 * @throws IllegalStateException if the iterator is positioned
1101 * before the start of the list or the last object has already
1103 * @throws UnsupportedOperationException if the list does
1104 * not support removing elements.
1106 public void remove()
1110 position
= nextIndex();
1111 modCount
= backingList
.modCount
;
1116 * Replaces the last object retrieved by <code>next()</code>
1117 * or <code>previous</code> with o, if the list supports object
1118 * replacement and an add or remove operation has not already
1121 * @throws IllegalStateException if the iterator is positioned
1122 * before the start of the list or the last object has already
1124 * @throws UnsupportedOperationException if the list doesn't support
1125 * the addition or removal of elements.
1126 * @throws ClassCastException if the type of o is not a valid type
1128 * @throws IllegalArgumentException if something else related to o
1129 * prevents its addition.
1130 * @throws ConcurrentModificationException if the list
1131 * has been modified elsewhere.
1133 public void set(E o
)
1139 * Adds the supplied object before the element that would be returned
1140 * by a call to <code>next()</code>, if the list supports addition.
1142 * @param o The object to add to the list.
1143 * @throws UnsupportedOperationException if the list doesn't support
1144 * the addition of new elements.
1145 * @throws ClassCastException if the type of o is not a valid type
1147 * @throws IllegalArgumentException if something else related to o
1148 * prevents its addition.
1149 * @throws ConcurrentModificationException if the list
1150 * has been modified elsewhere.
1152 public void add(E o
)
1157 modCount
= backingList
.modCount
;
1160 // Here is the reason why the various modCount fields are mostly
1161 // ignored in this wrapper listIterator.
1162 // If the backing listIterator is failfast, then the following holds:
1163 // Using any other method on this list will call a corresponding
1164 // method on the backing list *after* the backing listIterator
1165 // is created, which will in turn cause a ConcurrentModException
1166 // when this listIterator comes to use the backing one. So it is
1167 // implicitly failfast.
1168 // If the backing listIterator is NOT failfast, then the whole of
1169 // this list isn't failfast, because the modCount field of the
1170 // backing list is not valid. It would still be *possible* to
1171 // make the iterator failfast wrt modifications of the sublist
1172 // only, but somewhat pointless when the list can be changed under
1174 // Either way, no explicit handling of modCount is needed.
1175 // However modCount = backingList.modCount must be executed in add
1176 // and remove, and size must also be updated in these two methods,
1177 // since they do not go through the corresponding methods of the subList.
1183 * This class is a RandomAccess version of SubList, as required by
1184 * {@link AbstractList#subList(int, int)}.
1186 * @author Eric Blake (ebb9@email.byu.edu)
1188 private static final class RandomAccessSubList
<E
> extends SubList
<E
>
1189 implements RandomAccess
1192 * Construct the sublist.
1194 * @param backing the list this comes from
1195 * @param fromIndex the lower bound, inclusive
1196 * @param toIndex the upper bound, exclusive
1198 RandomAccessSubList(AbstractList
<E
> backing
, int fromIndex
, int toIndex
)
1200 super(backing
, fromIndex
, toIndex
);
1202 } // class RandomAccessSubList
1204 } // class AbstractList