libjava/java/util/AbstractSequentialList.java

   1 /* AbstractSequentialList.java -- List implementation for sequential access
   2    Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38
  39 package java.util;
  40
  41 /**
  42  * Abstract superclass to make it easier to implement the List interface when
  43  * backed by a sequential-access store, such as a linked list. For random
  44  * access data, use AbstractList. This class implements the random access
  45  * methods (<code>get</code>, <code>set</code>, <code>add</code>, and
  46  * <code>remove</code>) atop the list iterator, opposite of AbstractList's
  47  * approach of implementing the iterator atop random access.
  48  * <p>
  49  *
  50  * To implement a list, you need an implementation for <code>size()</code>
  51  * and <code>listIterator</code>.  With just <code>hasNext</code>,
  52  * <code>next</code>, <code>hasPrevious</code>, <code>previous</code>,
  53  * <code>nextIndex</code>, and <code>previousIndex</code>, you have an
  54  * unmodifiable list. For a modifiable one, add <code>set</code>, and for
  55  * a variable-size list, add <code>add</code> and <code>remove</code>.
  56  * <p>
  57  *
  58  * The programmer should provide a no-argument constructor, and one that
  59  * accepts another Collection, as recommended by the Collection interface.
  60  * Unfortunately, there is no way to enforce this in Java.
  61  *
  62  * @author Original author unknown
  63  * @author Bryce McKinlay
  64  * @author Eric Blake <ebb9@email.byu.edu>
  65  * @see Collection
  66  * @see List
  67  * @see AbstractList
  68  * @see AbstractCollection
  69  * @see ListIterator
  70  * @see LinkedList
  71  * @since 1.2
  72  * @status updated to 1.4
  73  */
  74 public abstract class AbstractSequentialList extends AbstractList
  75 {
  76   /**
  77    * The main constructor, for use by subclasses.
  78    */
  79   protected AbstractSequentialList()
  80   {
  81   }
  82
  83   /**
  84    * Returns a ListIterator over the list, starting from position index.
  85    * Subclasses must provide an implementation of this method.
  86    *
  87    * @param index the starting position of the list
  88    * @return the list iterator
  89    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
  90    */
  91   public abstract ListIterator listIterator(int index);
  92
  93   /**
  94    * Insert an element into the list at a given position (optional operation).
  95    * This shifts all existing elements from that position to the end one
  96    * index to the right. This version of add has no return, since it is
  97    * assumed to always succeed if there is no exception. This iteration
  98    * uses listIterator(index).add(o).
  99    *
 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    */
 110   public void add(int index, Object o)
 111   {
 112     listIterator(index).add(o);
 113   }
 114
 115   /**
 116    * Insert the contents of a collection into the list at a given position
 117    * (optional operation). Shift all elements at that position to the right
 118    * by the number of elements inserted. This operation is undefined if
 119    * this list is modified during the operation (for example, if you try
 120    * to insert a list into itself).
 121    * <p>
 122    *
 123    * This implementation grabs listIterator(index), then proceeds to use add
 124    * for each element returned by c's iterator. Sun's online specs are wrong,
 125    * claiming that this also calls next(): listIterator.add() correctly
 126    * skips the added element.
 127    *
 128    * @param index the location to insert the collection
 129    * @param c the collection to insert
 130    * @return true if the list was modified by this action, that is, if c is
 131    *         non-empty
 132    * @throws UnsupportedOperationException if this list does not support the
 133    *         addAll operation
 134    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 135    * @throws ClassCastException if some element of c cannot be added to this
 136    *         list due to its type
 137    * @throws IllegalArgumentException if some element of c cannot be added
 138    *         to this list for some other reason
 139    * @throws NullPointerException if the specified collection is null
 140    * @see #add(int, Object)
 141    */
 142   public boolean addAll(int index, Collection c)
 143   {
 144     Iterator ci = c.iterator();
 145     int size = c.size();
 146     ListIterator i = listIterator(index);
 147     for (int pos = size; pos > 0; pos--)
 148       i.add(ci.next());
 149     return size > 0;
 150   }
 151
 152   /**
 153    * Get the element at a given index in this list. This implementation
 154    * returns listIterator(index).next().
 155    *
 156    * @param index the index of the element to be returned
 157    * @return the element at index index in this list
 158    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 159    */
 160   public Object get(int index)
 161   {
 162     // This is a legal listIterator position, but an illegal get.
 163     if (index == size())
 164       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 165                                           + size());
 166     return listIterator(index).next();
 167   }
 168
 169   /**
 170    * Obtain an Iterator over this list, whose sequence is the list order. This
 171    * implementation returns listIterator().
 172    *
 173    * @return an Iterator over the elements of this list, in order
 174    */
 175   public Iterator iterator()
 176   {
 177     return listIterator();
 178   }
 179
 180   /**
 181    * Remove the element at a given position in this list (optional operation).
 182    * Shifts all remaining elements to the left to fill the gap. This
 183    * implementation uses listIterator(index) and ListIterator.remove().
 184    *
 185    * @param index the position within the list of the object to remove
 186    * @return the object that was removed
 187    * @throws UnsupportedOperationException if this list does not support the
 188    *         remove operation
 189    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 190    */
 191   public Object remove(int index)
 192   {
 193     // This is a legal listIterator position, but an illegal remove.
 194     if (index == size())
 195       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 196                                           + size());
 197     ListIterator i = listIterator(index);
 198     Object removed = i.next();
 199     i.remove();
 200     return removed;
 201   }
 202
 203   /**
 204    * Replace an element of this list with another object (optional operation).
 205    * This implementation uses listIterator(index) and ListIterator.set(o).
 206    *
 207    * @param index the position within this list of the element to be replaced
 208    * @param o the object to replace it with
 209    * @return the object that was replaced
 210    * @throws UnsupportedOperationException if this list does not support the
 211    *         set operation
 212    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 213    * @throws ClassCastException if o cannot be added to this list due to its
 214    *         type
 215    * @throws IllegalArgumentException if o cannot be added to this list for
 216    *         some other reason
 217    */
 218   public Object set(int index, Object o)
 219   {
 220     // This is a legal listIterator position, but an illegal set.
 221     if (index == size())
 222       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 223                                           + size());
 224     ListIterator i = listIterator(index);
 225     Object old = i.next();
 226     i.set(o);
 227     return old;
 228   }
 229 }