001    /* AbstractSequentialList.java -- List implementation for sequential access
002       Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.util;
040    
041    /**
042     * Abstract superclass to make it easier to implement the List interface when
043     * backed by a sequential-access store, such as a linked list. For random
044     * access data, use AbstractList. This class implements the random access
045     * methods (<code>get</code>, <code>set</code>, <code>add</code>, and
046     * <code>remove</code>) atop the list iterator, opposite of AbstractList's
047     * approach of implementing the iterator atop random access.
048     * <p>
049     *
050     * To implement a list, you need an implementation for <code>size()</code>
051     * and <code>listIterator</code>.  With just <code>hasNext</code>,
052     * <code>next</code>, <code>hasPrevious</code>, <code>previous</code>,
053     * <code>nextIndex</code>, and <code>previousIndex</code>, you have an
054     * unmodifiable list. For a modifiable one, add <code>set</code>, and for
055     * a variable-size list, add <code>add</code> and <code>remove</code>.
056     * <p>
057     *
058     * The programmer should provide a no-argument constructor, and one that
059     * accepts another Collection, as recommended by the Collection interface.
060     * Unfortunately, there is no way to enforce this in Java.
061     *
062     * @author Original author unknown
063     * @author Bryce McKinlay
064     * @author Eric Blake (ebb9@email.byu.edu)
065     * @see Collection
066     * @see List
067     * @see AbstractList
068     * @see AbstractCollection
069     * @see ListIterator
070     * @see LinkedList
071     * @since 1.2
072     * @status updated to 1.4
073     */
074    public abstract class AbstractSequentialList<E> extends AbstractList<E>
075    {
076      /**
077       * The main constructor, for use by subclasses.
078       */
079      protected AbstractSequentialList()
080      {
081      }
082    
083      /**
084       * Returns a ListIterator over the list, starting from position index.
085       * Subclasses must provide an implementation of this method.
086       *
087       * @param index the starting position of the list
088       * @return the list iterator
089       * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
090       */
091      public abstract ListIterator<E> listIterator(int index);
092    
093      /**
094       * Insert an element into the list at a given position (optional operation).
095       * This shifts all existing elements from that position to the end one
096       * index to the right. This version of add has no return, since it is
097       * assumed to always succeed if there is no exception. This iteration
098       * uses listIterator(index).add(o).
099       *
100       * @param index the location to insert the item
101       * @param o the object to insert
102       * @throws UnsupportedOperationException if this list does not support the
103       *         add operation
104       * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
105       * @throws ClassCastException if o cannot be added to this list due to its
106       *         type
107       * @throws IllegalArgumentException if o cannot be added to this list for
108       *         some other reason.
109       * @throws NullPointerException if o is null and the list does not permit
110       *         the addition of null values.
111       */
112      public void add(int index, E o)
113      {
114        listIterator(index).add(o);
115      }
116    
117      /**
118       * Insert the contents of a collection into the list at a given position
119       * (optional operation). Shift all elements at that position to the right
120       * by the number of elements inserted. This operation is undefined if
121       * this list is modified during the operation (for example, if you try
122       * to insert a list into itself).
123       * <p>
124       *
125       * This implementation grabs listIterator(index), then proceeds to use add
126       * for each element returned by c's iterator. Sun's online specs are wrong,
127       * claiming that this also calls next(): listIterator.add() correctly
128       * skips the added element.
129       *
130       * @param index the location to insert the collection
131       * @param c the collection to insert
132       * @return true if the list was modified by this action, that is, if c is
133       *         non-empty
134       * @throws UnsupportedOperationException if this list does not support the
135       *         addAll operation
136       * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
137       * @throws ClassCastException if some element of c cannot be added to this
138       *         list due to its type
139       * @throws IllegalArgumentException if some element of c cannot be added
140       *         to this list for some other reason
141       * @throws NullPointerException if the specified collection is null
142       * @throws NullPointerException if an object, o, in c is null and the list
143       *         does not permit the addition of null values.
144       * @see #add(int, Object)
145       */
146      public boolean addAll(int index, Collection<? extends E> c)
147      {
148        Iterator<? extends E> ci = c.iterator();
149        int size = c.size();
150        ListIterator<E> i = listIterator(index);
151        for (int pos = size; pos > 0; pos--)
152          i.add(ci.next());
153        return size > 0;
154      }
155    
156      /**
157       * Get the element at a given index in this list. This implementation
158       * returns listIterator(index).next().
159       *
160       * @param index the index of the element to be returned
161       * @return the element at index index in this list
162       * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
163       */
164      public E get(int index)
165      {
166        // This is a legal listIterator position, but an illegal get.
167        if (index == size())
168          throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
169                                              + size());
170        return listIterator(index).next();
171      }
172    
173      /**
174       * Obtain an Iterator over this list, whose sequence is the list order. This
175       * implementation returns listIterator().
176       *
177       * @return an Iterator over the elements of this list, in order
178       */
179      public Iterator<E> iterator()
180      {
181        return listIterator();
182      }
183    
184      /**
185       * Remove the element at a given position in this list (optional operation).
186       * Shifts all remaining elements to the left to fill the gap. This
187       * implementation uses listIterator(index) and ListIterator.remove().
188       *
189       * @param index the position within the list of the object to remove
190       * @return the object that was removed
191       * @throws UnsupportedOperationException if this list does not support the
192       *         remove operation
193       * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
194       */
195      public E remove(int index)
196      {
197        // This is a legal listIterator position, but an illegal remove.
198        if (index == size())
199          throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
200                                              + size());
201        ListIterator<E> i = listIterator(index);
202        E removed = i.next();
203        i.remove();
204        return removed;
205      }
206    
207      /**
208       * Replace an element of this list with another object (optional operation).
209       * This implementation uses listIterator(index) and ListIterator.set(o).
210       *
211       * @param index the position within this list of the element to be replaced
212       * @param o the object to replace it with
213       * @return the object that was replaced
214       * @throws UnsupportedOperationException if this list does not support the
215       *         set operation
216       * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
217       * @throws ClassCastException if o cannot be added to this list due to its
218       *         type
219       * @throws IllegalArgumentException if o cannot be added to this list for
220       *         some other reason
221       * @throws NullPointerException if o is null and the list does not allow
222       *         a value to be set to null.
223       */
224      public E set(int index, E o)
225      {
226        // This is a legal listIterator position, but an illegal set.
227        if (index == size())
228          throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
229                                              + size());
230        ListIterator<E> i = listIterator(index);
231        E old = i.next();
232        i.set(o);
233        return old;
234      }
235    }