--- /dev/null
+/* AbstractList.java -- Abstract implementation of most of List
+ Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005
+ Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING. If not, write to the
+Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library. Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module. An independent module is a module which is not derived from
+or based on this library. If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so. If you do not wish to do so, delete this
+exception statement from your version. */
+
+
+package java.util;
+
+/**
+ * A basic implementation of most of the methods in the List interface to make
+ * it easier to create a List based on a random-access data structure. If
+ * the list is sequential (such as a linked list), use AbstractSequentialList.
+ * To create an unmodifiable list, it is only necessary to override the
+ * size() and get(int) methods (this contrasts with all other abstract
+ * collection classes which require an iterator to be provided). To make the
+ * list modifiable, the set(int, Object) method should also be overridden, and
+ * to make the list resizable, the add(int, Object) and remove(int) methods
+ * should be overridden too. Other methods should be overridden if the
+ * backing data structure allows for a more efficient implementation.
+ * The precise implementation used by AbstractList is documented, so that
+ * subclasses can tell which methods could be implemented more efficiently.
+ * <p>
+ *
+ * As recommended by Collection and List, the subclass should provide at
+ * least a no-argument and a Collection constructor. This class is not
+ * synchronized.
+ *
+ * @author Original author unknown
+ * @author Bryce McKinlay
+ * @author Eric Blake (ebb9@email.byu.edu)
+ * @see Collection
+ * @see List
+ * @see AbstractSequentialList
+ * @see AbstractCollection
+ * @see ListIterator
+ * @since 1.2
+ * @status updated to 1.4
+ */
+public abstract class AbstractList/*<E>*/
+ extends AbstractCollection/*<E>*/
+ implements List/*<E>*/
+{
+ /**
+ * A count of the number of structural modifications that have been made to
+ * the list (that is, insertions and removals). Structural modifications
+ * are ones which change the list size or affect how iterations would
+ * behave. This field is available for use by Iterator and ListIterator,
+ * in order to throw a {@link ConcurrentModificationException} in response
+ * to the next operation on the iterator. This <i>fail-fast</i> behavior
+ * saves the user from many subtle bugs otherwise possible from concurrent
+ * modification during iteration.
+ * <p>
+ *
+ * To make lists fail-fast, increment this field by just 1 in the
+ * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
+ * Otherwise, this field may be ignored.
+ */
+ protected transient int modCount;
+
+ /**
+ * The main constructor, for use by subclasses.
+ */
+ protected AbstractList()
+ {
+ }
+
+ /**
+ * Returns the elements at the specified position in the list.
+ *
+ * @param index the element to return
+ * @return the element at that position
+ * @throws IndexOutOfBoundsException if index < 0 || index >= size()
+ */
+ public abstract Object/*E*/ get(int index);
+
+ /**
+ * Insert an element into the list at a given position (optional operation).
+ * This shifts all existing elements from that position to the end one
+ * index to the right. This version of add has no return, since it is
+ * assumed to always succeed if there is no exception. This implementation
+ * always throws UnsupportedOperationException, and must be overridden to
+ * make a modifiable List. If you want fail-fast iterators, be sure to
+ * increment modCount when overriding this.
+ *
+ * @param index the location to insert the item
+ * @param o the object to insert
+ * @throws UnsupportedOperationException if this list does not support the
+ * add operation
+ * @throws IndexOutOfBoundsException if index < 0 || index > size()
+ * @throws ClassCastException if o cannot be added to this list due to its
+ * type
+ * @throws IllegalArgumentException if o cannot be added to this list for
+ * some other reason
+ * @see #modCount
+ */
+ public void add(int index, Object/*E*/ o)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Add an element to the end of the list (optional operation). If the list
+ * imposes restraints on what can be inserted, such as no null elements,
+ * this should be documented. This implementation calls
+ * <code>add(size(), o);</code>, and will fail if that version does.
+ *
+ * @param o the object to add
+ * @return true, as defined by Collection for a modified list
+ * @throws UnsupportedOperationException if this list does not support the
+ * add operation
+ * @throws ClassCastException if o cannot be added to this list due to its
+ * type
+ * @throws IllegalArgumentException if o cannot be added to this list for
+ * some other reason
+ * @see #add(int, Object)
+ */
+ public boolean add(Object/*E*/ o)
+ {
+ add(size(), o);
+ return true;
+ }
+
+ /**
+ * Insert the contents of a collection into the list at a given position
+ * (optional operation). Shift all elements at that position to the right
+ * by the number of elements inserted. This operation is undefined if
+ * this list is modified during the operation (for example, if you try
+ * to insert a list into itself). This implementation uses the iterator of
+ * the collection, repeatedly calling add(int, Object); this will fail
+ * if add does. This can often be made more efficient.
+ *
+ * @param index the location to insert the collection
+ * @param c the collection to insert
+ * @return true if the list was modified by this action, that is, if c is
+ * non-empty
+ * @throws UnsupportedOperationException if this list does not support the
+ * addAll operation
+ * @throws IndexOutOfBoundsException if index < 0 || index > size()
+ * @throws ClassCastException if some element of c cannot be added to this
+ * list due to its type
+ * @throws IllegalArgumentException if some element of c cannot be added
+ * to this list for some other reason
+ * @throws NullPointerException if the specified collection is null
+ * @see #add(int, Object)
+ */
+ public boolean addAll(int index, Collection/*<? extends E>*/ c)
+ {
+ Iterator/*<? extends E>*/ itr = c.iterator();
+ int size = c.size();
+ for (int pos = size; pos > 0; pos--)
+ add(index++, itr.next());
+ return size > 0;
+ }
+
+ /**
+ * Clear the list, such that a subsequent call to isEmpty() would return
+ * true (optional operation). This implementation calls
+ * <code>removeRange(0, size())</code>, so it will fail unless remove
+ * or removeRange is overridden.
+ *
+ * @throws UnsupportedOperationException if this list does not support the
+ * clear operation
+ * @see #remove(int)
+ * @see #removeRange(int, int)
+ */
+ public void clear()
+ {
+ removeRange(0, size());
+ }
+
+ /**
+ * Test whether this list is equal to another object. A List is defined to be
+ * equal to an object if and only if that object is also a List, and the two
+ * lists have the same sequence. Two lists l1 and l2 are equal if and only
+ * if <code>l1.size() == l2.size()</code>, and for every integer n between 0
+ * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ?
+ * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
+ * <p>
+ *
+ * This implementation returns true if the object is this, or false if the
+ * object is not a List. Otherwise, it iterates over both lists (with
+ * iterator()), returning false if two elements compare false or one list
+ * is shorter, and true if the iteration completes successfully.
+ *
+ * @param o the object to test for equality with this list
+ * @return true if o is equal to this list
+ * @see Object#equals(Object)
+ * @see #hashCode()
+ */
+ public boolean equals(Object o)
+ {
+ if (o == this)
+ return true;
+ if (! (o instanceof List))
+ return false;
+ int size = size();
+ if (size != ((List) o).size())
+ return false;
+
+ Iterator/*<E>*/ itr1 = iterator();
+ Iterator itr2 = ((List) o).iterator();
+
+ while (--size >= 0)
+ if (! equals(itr1.next(), itr2.next()))
+ return false;
+ return true;
+ }
+
+ /**
+ * Obtains a hash code for this list. In order to obey the general
+ * contract of the hashCode method of class Object, this value is
+ * calculated as follows:
+ *
+<pre>hashCode = 1;
+Iterator i = list.iterator();
+while (i.hasNext())
+{
+ Object obj = i.next();
+ hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
+}</pre>
+ *
+ * This ensures that the general contract of Object.hashCode() is adhered to.
+ *
+ * @return the hash code of this list
+ *
+ * @see Object#hashCode()
+ * @see #equals(Object)
+ */
+ public int hashCode()
+ {
+ int hashCode = 1;
+ Iterator/*<E>*/ itr = iterator();
+ int pos = size();
+ while (--pos >= 0)
+ hashCode = 31 * hashCode + hashCode(itr.next());
+ return hashCode;
+ }
+
+ /**
+ * Obtain the first index at which a given object is to be found in this
+ * list. This implementation follows a listIterator() until a match is found,
+ * or returns -1 if the list end is reached.
+ *
+ * @param o the object to search for
+ * @return the least integer n such that <code>o == null ? get(n) == null :
+ * o.equals(get(n))</code>, or -1 if there is no such index
+ */
+ public int indexOf(Object o)
+ {
+ ListIterator/*<E>*/ itr = listIterator();
+ int size = size();
+ for (int pos = 0; pos < size; pos++)
+ if (equals(o, itr.next()))
+ return pos;
+ return -1;
+ }
+
+ /**
+ * Obtain an Iterator over this list, whose sequence is the list order.
+ * This implementation uses size(), get(int), and remove(int) of the
+ * backing list, and does not support remove unless the list does. This
+ * implementation is fail-fast if you correctly maintain modCount.
+ * Also, this implementation is specified by Sun to be distinct from
+ * listIterator, although you could easily implement it as
+ * <code>return listIterator(0)</code>.
+ *
+ * @return an Iterator over the elements of this list, in order
+ * @see #modCount
+ */
+ public Iterator/*<E>*/ iterator()
+ {
+ // Bah, Sun's implementation forbids using listIterator(0).
+ return new Iterator/*<E>*/()
+ {
+ private int pos = 0;
+ private int size = size();
+ private int last = -1;
+ private int knownMod = modCount;
+
+ // This will get inlined, since it is private.
+ /**
+ * Checks for modifications made to the list from
+ * elsewhere while iteration is in progress.
+ *
+ * @throws ConcurrentModificationException if the
+ * list has been modified elsewhere.
+ */
+ private void checkMod()
+ {
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ }
+
+ /**
+ * Tests to see if there are any more objects to
+ * return.
+ *
+ * @return True if the end of the list has not yet been
+ * reached.
+ */
+ public boolean hasNext()
+ {
+ return pos < size;
+ }
+
+ /**
+ * Retrieves the next object from the list.
+ *
+ * @return The next object.
+ * @throws NoSuchElementException if there are
+ * no more objects to retrieve.
+ * @throws ConcurrentModificationException if the
+ * list has been modified elsewhere.
+ */
+ public Object/*E*/ next()
+ {
+ checkMod();
+ if (pos == size)
+ throw new NoSuchElementException();
+ last = pos;
+ return get(pos++);
+ }
+
+ /**
+ * Removes the last object retrieved by <code>next()</code>
+ * from the list, if the list supports object removal.
+ *
+ * @throws ConcurrentModificationException if the list
+ * has been modified elsewhere.
+ * @throws IllegalStateException if the iterator is positioned
+ * before the start of the list or the last object has already
+ * been removed.
+ * @throws UnsupportedOperationException if the list does
+ * not support removing elements.
+ */
+ public void remove()
+ {
+ checkMod();
+ if (last < 0)
+ throw new IllegalStateException();
+ AbstractList.this.remove(last);
+ pos--;
+ size--;
+ last = -1;
+ knownMod = modCount;
+ }
+ };
+ }
+
+ /**
+ * Obtain the last index at which a given object is to be found in this
+ * list. This implementation grabs listIterator(size()), then searches
+ * backwards for a match or returns -1.
+ *
+ * @return the greatest integer n such that <code>o == null ? get(n) == null
+ * : o.equals(get(n))</code>, or -1 if there is no such index
+ */
+ public int lastIndexOf(Object o)
+ {
+ int pos = size();
+ ListIterator/*<E>*/ itr = listIterator(pos);
+ while (--pos >= 0)
+ if (equals(o, itr.previous()))
+ return pos;
+ return -1;
+ }
+
+ /**
+ * Obtain a ListIterator over this list, starting at the beginning. This
+ * implementation returns listIterator(0).
+ *
+ * @return a ListIterator over the elements of this list, in order, starting
+ * at the beginning
+ */
+ public ListIterator/*<E>*/ listIterator()
+ {
+ return listIterator(0);
+ }
+
+ /**
+ * Obtain a ListIterator over this list, starting at a given position.
+ * A first call to next() would return the same as get(index), and a
+ * first call to previous() would return the same as get(index - 1).
+ * <p>
+ *
+ * This implementation uses size(), get(int), set(int, Object),
+ * add(int, Object), and remove(int) of the backing list, and does not
+ * support remove, set, or add unless the list does. This implementation
+ * is fail-fast if you correctly maintain modCount.
+ *
+ * @param index the position, between 0 and size() inclusive, to begin the
+ * iteration from
+ * @return a ListIterator over the elements of this list, in order, starting
+ * at index
+ * @throws IndexOutOfBoundsException if index < 0 || index > size()
+ * @see #modCount
+ */
+ public ListIterator/*<E>*/ listIterator(final int index)
+ {
+ if (index < 0 || index > size())
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+ + size());
+
+ return new ListIterator/*<E>*/()
+ {
+ private int knownMod = modCount;
+ private int position = index;
+ private int lastReturned = -1;
+ private int size = size();
+
+ // This will get inlined, since it is private.
+ /**
+ * Checks for modifications made to the list from
+ * elsewhere while iteration is in progress.
+ *
+ * @throws ConcurrentModificationException if the
+ * list has been modified elsewhere.
+ */
+ private void checkMod()
+ {
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ }
+
+ /**
+ * Tests to see if there are any more objects to
+ * return.
+ *
+ * @return True if the end of the list has not yet been
+ * reached.
+ */
+ public boolean hasNext()
+ {
+ return position < size;
+ }
+
+ /**
+ * Tests to see if there are objects prior to the
+ * current position in the list.
+ *
+ * @return True if objects exist prior to the current
+ * position of the iterator.
+ */
+ public boolean hasPrevious()
+ {
+ return position > 0;
+ }
+
+ /**
+ * Retrieves the next object from the list.
+ *
+ * @return The next object.
+ * @throws NoSuchElementException if there are no
+ * more objects to retrieve.
+ * @throws ConcurrentModificationException if the
+ * list has been modified elsewhere.
+ */
+ public Object/*E*/ next()
+ {
+ checkMod();
+ if (position == size)
+ throw new NoSuchElementException();
+ lastReturned = position;
+ return get(position++);
+ }
+
+ /**
+ * Retrieves the previous object from the list.
+ *
+ * @return The next object.
+ * @throws NoSuchElementException if there are no
+ * previous objects to retrieve.
+ * @throws ConcurrentModificationException if the
+ * list has been modified elsewhere.
+ */
+ public Object/*E*/ previous()
+ {
+ checkMod();
+ if (position == 0)
+ throw new NoSuchElementException();
+ lastReturned = --position;
+ return get(lastReturned);
+ }
+
+ /**
+ * Returns the index of the next element in the
+ * list, which will be retrieved by <code>next()</code>
+ *
+ * @return The index of the next element.
+ */
+ public int nextIndex()
+ {
+ return position;
+ }
+
+ /**
+ * Returns the index of the previous element in the
+ * list, which will be retrieved by <code>previous()</code>
+ *
+ * @return The index of the previous element.
+ */
+ public int previousIndex()
+ {
+ return position - 1;
+ }
+
+ /**
+ * Removes the last object retrieved by <code>next()</code>
+ * or <code>previous()</code> from the list, if the list
+ * supports object removal.
+ *
+ * @throws IllegalStateException if the iterator is positioned
+ * before the start of the list or the last object has already
+ * been removed.
+ * @throws UnsupportedOperationException if the list does
+ * not support removing elements.
+ * @throws ConcurrentModificationException if the list
+ * has been modified elsewhere.
+ */
+ public void remove()
+ {
+ checkMod();
+ if (lastReturned < 0)
+ throw new IllegalStateException();
+ AbstractList.this.remove(lastReturned);
+ size--;
+ position = lastReturned;
+ lastReturned = -1;
+ knownMod = modCount;
+ }
+
+ /**
+ * Replaces the last object retrieved by <code>next()</code>
+ * or <code>previous</code> with o, if the list supports object
+ * replacement and an add or remove operation has not already
+ * been performed.
+ *
+ * @throws IllegalStateException if the iterator is positioned
+ * before the start of the list or the last object has already
+ * been removed.
+ * @throws UnsupportedOperationException if the list doesn't support
+ * the addition or removal of elements.
+ * @throws ClassCastException if the type of o is not a valid type
+ * for this list.
+ * @throws IllegalArgumentException if something else related to o
+ * prevents its addition.
+ * @throws ConcurrentModificationException if the list
+ * has been modified elsewhere.
+ */
+ public void set(Object/*E*/ o)
+ {
+ checkMod();
+ if (lastReturned < 0)
+ throw new IllegalStateException();
+ AbstractList.this.set(lastReturned, o);
+ }
+
+ /**
+ * Adds the supplied object before the element that would be returned
+ * by a call to <code>next()</code>, if the list supports addition.
+ *
+ * @param o The object to add to the list.
+ * @throws UnsupportedOperationException if the list doesn't support
+ * the addition of new elements.
+ * @throws ClassCastException if the type of o is not a valid type
+ * for this list.
+ * @throws IllegalArgumentException if something else related to o
+ * prevents its addition.
+ * @throws ConcurrentModificationException if the list
+ * has been modified elsewhere.
+ */
+ public void add(Object/*E*/ o)
+ {
+ checkMod();
+ AbstractList.this.add(position++, o);
+ size++;
+ lastReturned = -1;
+ knownMod = modCount;
+ }
+ };
+ }
+
+ /**
+ * Remove the element at a given position in this list (optional operation).
+ * Shifts all remaining elements to the left to fill the gap. This
+ * implementation always throws an UnsupportedOperationException.
+ * If you want fail-fast iterators, be sure to increment modCount when
+ * overriding this.
+ *
+ * @param index the position within the list of the object to remove
+ * @return the object that was removed
+ * @throws UnsupportedOperationException if this list does not support the
+ * remove operation
+ * @throws IndexOutOfBoundsException if index < 0 || index >= size()
+ * @see #modCount
+ */
+ public Object/*E*/ remove(int index)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Remove a subsection of the list. This is called by the clear and
+ * removeRange methods of the class which implements subList, which are
+ * difficult for subclasses to override directly. Therefore, this method
+ * should be overridden instead by the more efficient implementation, if one
+ * exists. Overriding this can reduce quadratic efforts to constant time
+ * in some cases!
+ * <p>
+ *
+ * This implementation first checks for illegal or out of range arguments. It
+ * then obtains a ListIterator over the list using listIterator(fromIndex).
+ * It then calls next() and remove() on this iterator repeatedly, toIndex -
+ * fromIndex times.
+ *
+ * @param fromIndex the index, inclusive, to remove from.
+ * @param toIndex the index, exclusive, to remove to.
+ * @throws UnsupportedOperationException if the list does
+ * not support removing elements.
+ */
+ protected void removeRange(int fromIndex, int toIndex)
+ {
+ ListIterator/*<E>*/ itr = listIterator(fromIndex);
+ for (int index = fromIndex; index < toIndex; index++)
+ {
+ itr.next();
+ itr.remove();
+ }
+ }
+
+ /**
+ * Replace an element of this list with another object (optional operation).
+ * This implementation always throws an UnsupportedOperationException.
+ *
+ * @param index the position within this list of the element to be replaced
+ * @param o the object to replace it with
+ * @return the object that was replaced
+ * @throws UnsupportedOperationException if this list does not support the
+ * set operation
+ * @throws IndexOutOfBoundsException if index < 0 || index >= size()
+ * @throws ClassCastException if o cannot be added to this list due to its
+ * type
+ * @throws IllegalArgumentException if o cannot be added to this list for
+ * some other reason
+ */
+ public Object/*E*/ set(int index, Object/*E*/ o)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Obtain a List view of a subsection of this list, from fromIndex
+ * (inclusive) to toIndex (exclusive). If the two indices are equal, the
+ * sublist is empty. The returned list should be modifiable if and only
+ * if this list is modifiable. Changes to the returned list should be
+ * reflected in this list. If this list is structurally modified in
+ * any way other than through the returned list, the result of any subsequent
+ * operations on the returned list is undefined.
+ * <p>
+ *
+ * This implementation returns a subclass of AbstractList. It stores, in
+ * private fields, the offset and size of the sublist, and the expected
+ * modCount of the backing list. If the backing list implements RandomAccess,
+ * the sublist will also.
+ * <p>
+ *
+ * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
+ * <code>add(int, Object)</code>, <code>remove(int)</code>,
+ * <code>addAll(int, Collection)</code> and
+ * <code>removeRange(int, int)</code> methods all delegate to the
+ * corresponding methods on the backing abstract list, after
+ * bounds-checking the index and adjusting for the offset. The
+ * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
+ * The <code>listIterator(int)</code> method returns a "wrapper object"
+ * over a list iterator on the backing list, which is created with the
+ * corresponding method on the backing list. The <code>iterator()</code>
+ * method merely returns listIterator(), and the <code>size()</code> method
+ * merely returns the subclass's size field.
+ * <p>
+ *
+ * All methods first check to see if the actual modCount of the backing
+ * list is equal to its expected value, and throw a
+ * ConcurrentModificationException if it is not.
+ *
+ * @param fromIndex the index that the returned list should start from
+ * (inclusive)
+ * @param toIndex the index that the returned list should go to (exclusive)
+ * @return a List backed by a subsection of this list
+ * @throws IndexOutOfBoundsException if fromIndex < 0
+ * || toIndex > size()
+ * @throws IllegalArgumentException if fromIndex > toIndex
+ * @see ConcurrentModificationException
+ * @see RandomAccess
+ */
+ public List/*<E>*/ subList(int fromIndex, int toIndex)
+ {
+ // This follows the specification of AbstractList, but is inconsistent
+ // with the one in List. Don't you love Sun's inconsistencies?
+// if (fromIndex > toIndex)
+// throw new IllegalArgumentException(fromIndex + " > " + toIndex);
+// if (fromIndex < 0 || toIndex > size())
+// throw new IndexOutOfBoundsException();
+//
+// if (this instanceof RandomAccess)
+// return new RandomAccessSubList/*<E>*/(this, fromIndex, toIndex);
+// return new SubList/*<E>*/(this, fromIndex, toIndex);
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * This class follows the implementation requirements set forth in
+ * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
+ * by using a non-public top-level class in the same package.
+ *
+ * @author Original author unknown
+ * @author Eric Blake (ebb9@email.byu.edu)
+ */
+// private static class SubList/*<E>*/ extends AbstractList/*<E>*/
+// {
+// // Package visible, for use by iterator.
+// /** The original list. */
+// final AbstractList/*<E>*/ backingList;
+// /** The index of the first element of the sublist. */
+// final int offset;
+// /** The size of the sublist. */
+// int size;
+//
+// /**
+// * Construct the sublist.
+// *
+// * @param backing the list this comes from
+// * @param fromIndex the lower bound, inclusive
+// * @param toIndex the upper bound, exclusive
+// */
+// SubList(AbstractList/*<E>*/ backing, int fromIndex, int toIndex)
+// {
+// backingList = backing;
+// modCount = backing.modCount;
+// offset = fromIndex;
+// size = toIndex - fromIndex;
+// }
+//
+// /**
+// * This method checks the two modCount fields to ensure that there has
+// * not been a concurrent modification, returning if all is okay.
+// *
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// */
+// // This can be inlined. Package visible, for use by iterator.
+// void checkMod()
+// {
+// if (modCount != backingList.modCount)
+// throw new ConcurrentModificationException();
+// }
+//
+// /**
+// * This method checks that a value is between 0 and size (inclusive). If
+// * it is not, an exception is thrown.
+// *
+// * @param index the value to check
+// * @throws IndexOutOfBoundsException if index < 0 || index > size()
+// */
+// // This will get inlined, since it is private.
+// private void checkBoundsInclusive(int index)
+// {
+// if (index < 0 || index > size)
+// throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+// + size);
+// }
+//
+// /**
+// * This method checks that a value is between 0 (inclusive) and size
+// * (exclusive). If it is not, an exception is thrown.
+// *
+// * @param index the value to check
+// * @throws IndexOutOfBoundsException if index < 0 || index >= size()
+// */
+// // This will get inlined, since it is private.
+// private void checkBoundsExclusive(int index)
+// {
+// if (index < 0 || index >= size)
+// throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+// + size);
+// }
+//
+// /**
+// * Specified by AbstractList.subList to return the private field size.
+// *
+// * @return the sublist size
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// */
+// public int size()
+// {
+// checkMod();
+// return size;
+// }
+//
+// /**
+// * Specified by AbstractList.subList to delegate to the backing list.
+// *
+// * @param index the location to modify
+// * @param o the new value
+// * @return the old value
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws UnsupportedOperationException if the backing list does not
+// * support the set operation
+// * @throws IndexOutOfBoundsException if index < 0 || index >= size()
+// * @throws ClassCastException if o cannot be added to the backing list due
+// * to its type
+// * @throws IllegalArgumentException if o cannot be added to the backing list
+// * for some other reason
+// */
+// public Object/*E*/ set(int index, Object/*E*/ o)
+// {
+// checkMod();
+// checkBoundsExclusive(index);
+// return backingList.set(index + offset, o);
+// }
+//
+// /**
+// * Specified by AbstractList.subList to delegate to the backing list.
+// *
+// * @param index the location to get from
+// * @return the object at that location
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws IndexOutOfBoundsException if index < 0 || index >= size()
+// */
+// public Object/*E*/ get(int index)
+// {
+// checkMod();
+// checkBoundsExclusive(index);
+// return backingList.get(index + offset);
+// }
+//
+// /**
+// * Specified by AbstractList.subList to delegate to the backing list.
+// *
+// * @param index the index to insert at
+// * @param o the object to add
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws IndexOutOfBoundsException if index < 0 || index > size()
+// * @throws UnsupportedOperationException if the backing list does not
+// * support the add operation.
+// * @throws ClassCastException if o cannot be added to the backing list due
+// * to its type.
+// * @throws IllegalArgumentException if o cannot be added to the backing
+// * list for some other reason.
+// */
+// public void add(int index, Object/*E*/ o)
+// {
+// checkMod();
+// checkBoundsInclusive(index);
+// backingList.add(index + offset, o);
+// size++;
+// modCount = backingList.modCount;
+// }
+//
+// /**
+// * Specified by AbstractList.subList to delegate to the backing list.
+// *
+// * @param index the index to remove
+// * @return the removed object
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws IndexOutOfBoundsException if index < 0 || index >= size()
+// * @throws UnsupportedOperationException if the backing list does not
+// * support the remove operation
+// */
+// public Object/*E*/ remove(int index)
+// {
+// checkMod();
+// checkBoundsExclusive(index);
+// Object/*E*/ o = backingList.remove(index + offset);
+// size--;
+// modCount = backingList.modCount;
+// return o;
+// }
+//
+// /**
+// * Specified by AbstractList.subList to delegate to the backing list.
+// * This does no bounds checking, as it assumes it will only be called
+// * by trusted code like clear() which has already checked the bounds.
+// *
+// * @param fromIndex the lower bound, inclusive
+// * @param toIndex the upper bound, exclusive
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws UnsupportedOperationException if the backing list does
+// * not support removing elements.
+// */
+// protected void removeRange(int fromIndex, int toIndex)
+// {
+// checkMod();
+//
+// backingList.removeRange(offset + fromIndex, offset + toIndex);
+// size -= toIndex - fromIndex;
+// modCount = backingList.modCount;
+// }
+//
+// /**
+// * Specified by AbstractList.subList to delegate to the backing list.
+// *
+// * @param index the location to insert at
+// * @param c the collection to insert
+// * @return true if this list was modified, in other words, c is non-empty
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws IndexOutOfBoundsException if index < 0 || index > size()
+// * @throws UnsupportedOperationException if this list does not support the
+// * addAll operation
+// * @throws ClassCastException if some element of c cannot be added to this
+// * list due to its type
+// * @throws IllegalArgumentException if some element of c cannot be added
+// * to this list for some other reason
+// * @throws NullPointerException if the specified collection is null
+// */
+// public boolean addAll(int index, Collection/*<? extends E>*/ c)
+// {
+// checkMod();
+// checkBoundsInclusive(index);
+// int csize = c.size();
+// boolean result = backingList.addAll(offset + index, c);
+// size += csize;
+// modCount = backingList.modCount;
+// return result;
+// }
+//
+// /**
+// * Specified by AbstractList.subList to return addAll(size, c).
+// *
+// * @param c the collection to insert
+// * @return true if this list was modified, in other words, c is non-empty
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws UnsupportedOperationException if this list does not support the
+// * addAll operation
+// * @throws ClassCastException if some element of c cannot be added to this
+// * list due to its type
+// * @throws IllegalArgumentException if some element of c cannot be added
+// * to this list for some other reason
+// * @throws NullPointerException if the specified collection is null
+// */
+// public boolean addAll(Collection/*<? extends E>*/ c)
+// {
+// return addAll(size, c);
+// }
+//
+// /**
+// * Specified by AbstractList.subList to return listIterator().
+// *
+// * @return an iterator over the sublist
+// */
+// public Iterator/*<E>*/ iterator()
+// {
+// return listIterator();
+// }
+//
+// /**
+// * Specified by AbstractList.subList to return a wrapper around the
+// * backing list's iterator.
+// *
+// * @param index the start location of the iterator
+// * @return a list iterator over the sublist
+// * @throws ConcurrentModificationException if the backing list has been
+// * modified externally to this sublist
+// * @throws IndexOutOfBoundsException if the value is out of range
+// */
+// public ListIterator/*<E>*/ listIterator(final int index)
+// {
+// checkMod();
+// checkBoundsInclusive(index);
+//
+// return new ListIterator/*<E>*/()
+// {
+// private final ListIterator/*<E>*/ i
+// = backingList.listIterator(index + offset);
+// private int position = index;
+//
+// /**
+// * Tests to see if there are any more objects to
+// * return.
+// *
+// * @return True if the end of the list has not yet been
+// * reached.
+// */
+// public boolean hasNext()
+// {
+// return position < size;
+// }
+//
+// /**
+// * Tests to see if there are objects prior to the
+// * current position in the list.
+// *
+// * @return True if objects exist prior to the current
+// * position of the iterator.
+// */
+// public boolean hasPrevious()
+// {
+// return position > 0;
+// }
+//
+// /**
+// * Retrieves the next object from the list.
+// *
+// * @return The next object.
+// * @throws NoSuchElementException if there are no
+// * more objects to retrieve.
+// * @throws ConcurrentModificationException if the
+// * list has been modified elsewhere.
+// */
+// public Object/*E*/ next()
+// {
+// if (position == size)
+// throw new NoSuchElementException();
+// position++;
+// return i.next();
+// }
+//
+// /**
+// * Retrieves the previous object from the list.
+// *
+// * @return The next object.
+// * @throws NoSuchElementException if there are no
+// * previous objects to retrieve.
+// * @throws ConcurrentModificationException if the
+// * list has been modified elsewhere.
+// */
+// public Object/*E*/ previous()
+// {
+// if (position == 0)
+// throw new NoSuchElementException();
+// position--;
+// return i.previous();
+// }
+//
+// /**
+// * Returns the index of the next element in the
+// * list, which will be retrieved by <code>next()</code>
+// *
+// * @return The index of the next element.
+// */
+// public int nextIndex()
+// {
+// return i.nextIndex() - offset;
+// }
+//
+// /**
+// * Returns the index of the previous element in the
+// * list, which will be retrieved by <code>previous()</code>
+// *
+// * @return The index of the previous element.
+// */
+// public int previousIndex()
+// {
+// return i.previousIndex() - offset;
+// }
+//
+// /**
+// * Removes the last object retrieved by <code>next()</code>
+// * from the list, if the list supports object removal.
+// *
+// * @throws IllegalStateException if the iterator is positioned
+// * before the start of the list or the last object has already
+// * been removed.
+// * @throws UnsupportedOperationException if the list does
+// * not support removing elements.
+// */
+// public void remove()
+// {
+// i.remove();
+// size--;
+// position = nextIndex();
+// modCount = backingList.modCount;
+// }
+//
+//
+// /**
+// * Replaces the last object retrieved by <code>next()</code>
+// * or <code>previous</code> with o, if the list supports object
+// * replacement and an add or remove operation has not already
+// * been performed.
+// *
+// * @throws IllegalStateException if the iterator is positioned
+// * before the start of the list or the last object has already
+// * been removed.
+// * @throws UnsupportedOperationException if the list doesn't support
+// * the addition or removal of elements.
+// * @throws ClassCastException if the type of o is not a valid type
+// * for this list.
+// * @throws IllegalArgumentException if something else related to o
+// * prevents its addition.
+// * @throws ConcurrentModificationException if the list
+// * has been modified elsewhere.
+// */
+// public void set(Object/*E*/ o)
+// {
+// i.set(o);
+// }
+//
+// /**
+// * Adds the supplied object before the element that would be returned
+// * by a call to <code>next()</code>, if the list supports addition.
+// *
+// * @param o The object to add to the list.
+// * @throws UnsupportedOperationException if the list doesn't support
+// * the addition of new elements.
+// * @throws ClassCastException if the type of o is not a valid type
+// * for this list.
+// * @throws IllegalArgumentException if something else related to o
+// * prevents its addition.
+// * @throws ConcurrentModificationException if the list
+// * has been modified elsewhere.
+// */
+// public void add(Object/*E*/ o)
+// {
+// i.add(o);
+// size++;
+// position++;
+// modCount = backingList.modCount;
+// }
+//
+// // Here is the reason why the various modCount fields are mostly
+// // ignored in this wrapper listIterator.
+// // If the backing listIterator is failfast, then the following holds:
+// // Using any other method on this list will call a corresponding
+// // method on the backing list *after* the backing listIterator
+// // is created, which will in turn cause a ConcurrentModException
+// // when this listIterator comes to use the backing one. So it is
+// // implicitly failfast.
+// // If the backing listIterator is NOT failfast, then the whole of
+// // this list isn't failfast, because the modCount field of the
+// // backing list is not valid. It would still be *possible* to
+// // make the iterator failfast wrt modifications of the sublist
+// // only, but somewhat pointless when the list can be changed under
+// // us.
+// // Either way, no explicit handling of modCount is needed.
+// // However modCount = backingList.modCount must be executed in add
+// // and remove, and size must also be updated in these two methods,
+// // since they do not go through the corresponding methods of the subList.
+// };
+// }
+// } // class SubList
+
+ /**
+ * This class is a RandomAccess version of SubList, as required by
+ * {@link AbstractList#subList(int, int)}.
+ *
+ * @author Eric Blake (ebb9@email.byu.edu)
+ */
+// private static final class RandomAccessSubList<E> extends SubList<E>
+// implements RandomAccess
+// {
+// /**
+// * Construct the sublist.
+// *
+// * @param backing the list this comes from
+// * @param fromIndex the lower bound, inclusive
+// * @param toIndex the upper bound, exclusive
+// */
+// RandomAccessSubList(AbstractList<E> backing, int fromIndex, int toIndex)
+// {
+// super(backing, fromIndex, toIndex);
+// }
+// } // class RandomAccessSubList
+
+} // class AbstractList
projects / IRC.git / commitdiff