libjava/classpath/java/util/List.java

   1 /* List.java -- An ordered collection which allows indexed access
   2    Copyright (C) 1998, 2001, 2004, 2005 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., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 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  * An ordered collection (also known as a list). This collection allows
  43  * access to elements by position, as well as control on where elements
  44  * are inserted. Unlike sets, duplicate elements are permitted by this
  45  * general contract (if a subclass forbids duplicates, this should be
  46  * documented).
  47  * <p>
  48  *
  49  * List places additional requirements on <code>iterator</code>,
  50  * <code>add</code>, <code>remove</code>, <code>equals</code>, and
  51  * <code>hashCode</code>, in addition to requiring more methods. List
  52  * indexing is 0-based (like arrays), although some implementations may
  53  * require time proportional to the index to obtain an arbitrary element.
  54  * The List interface is incompatible with Set; you cannot implement both
  55  * simultaneously.
  56  * <p>
  57  *
  58  * Lists also provide a <code>ListIterator</code> which allows bidirectional
  59  * traversal and other features atop regular iterators. Lists can be
  60  * searched for arbitrary elements, and allow easy insertion and removal
  61  * of multiple elements in one method call.
  62  * <p>
  63  *
  64  * Note: While lists may contain themselves as elements, this leads to
  65  * undefined (usually infinite recursive) behavior for some methods like
  66  * hashCode or equals.
  67  *
  68  * @author Original author unknown
  69  * @author Eric Blake (ebb9@email.byu.edu)
  70  * @see Collection
  71  * @see Set
  72  * @see ArrayList
  73  * @see LinkedList
  74  * @see Vector
  75  * @see Arrays#asList(Object[])
  76  * @see Collections#nCopies(int, Object)
  77  * @see Collections#EMPTY_LIST
  78  * @see AbstractList
  79  * @see AbstractSequentialList
  80  * @since 1.2
  81  * @status updated to 1.4
  82  */
  83 public interface List<E> extends Collection<E>
  84 {
  85   /**
  86    * Insert an element into the list at a given position (optional operation).
  87    * This shifts all existing elements from that position to the end one
  88    * index to the right. This version of add has no return, since it is
  89    * assumed to always succeed if there is no exception.
  90    *
  91    * @param index the location to insert the item
  92    * @param o the object to insert
  93    * @throws UnsupportedOperationException if this list does not support the
  94    *         add operation
  95    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
  96    * @throws ClassCastException if o cannot be added to this list due to its
  97    *         type
  98    * @throws IllegalArgumentException if o cannot be added to this list for
  99    *         some other reason
 100    * @throws NullPointerException if o is null and this list doesn't support
 101    *         the addition of null values.
 102    */
 103   void add(int index, E o);
 104
 105   /**
 106    * Add an element to the end of the list (optional operation). If the list
 107    * imposes restraints on what can be inserted, such as no null elements,
 108    * this should be documented.
 109    *
 110    * @param o the object to add
 111    * @return true, as defined by Collection for a modified list
 112    * @throws UnsupportedOperationException if this list does not support the
 113    *         add operation
 114    * @throws ClassCastException if o cannot be added to this list due to its
 115    *         type
 116    * @throws IllegalArgumentException if o cannot be added to this list for
 117    *         some other reason
 118    * @throws NullPointerException if o is null and this list doesn't support
 119    *         the addition of null values.
 120    */
 121   boolean add(E o);
 122
 123   /**
 124    * Insert the contents of a collection into the list at a given position
 125    * (optional operation). Shift all elements at that position to the right
 126    * by the number of elements inserted. This operation is undefined if
 127    * this list is modified during the operation (for example, if you try
 128    * to insert a list into itself).
 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 some element of c is null and this list
 142    *         doesn't support the addition of null values.
 143    * @throws NullPointerException if the specified collection is null
 144    * @see #add(int, Object)
 145    */
 146   boolean addAll(int index, Collection<? extends E> c);
 147
 148   /**
 149    * Add the contents of a collection to the end of the list (optional
 150    * operation).  This operation is undefined if this list is modified
 151    * during the operation (for example, if you try to insert a list into
 152    * itself).
 153    *
 154    * @param c the collection to add
 155    * @return true if the list was modified by this action, that is, if c is
 156    *         non-empty
 157    * @throws UnsupportedOperationException if this list does not support the
 158    *         addAll operation
 159    * @throws ClassCastException if some element of c cannot be added to this
 160    *         list due to its type
 161    * @throws IllegalArgumentException if some element of c cannot be added
 162    *         to this list for some other reason
 163    * @throws NullPointerException if the specified collection is null
 164    * @throws NullPointerException if some element of c is null and this list
 165    *         doesn't support the addition of null values.
 166    * @see #add(Object)
 167    */
 168   boolean addAll(Collection<? extends E> c);
 169
 170   /**
 171    * Clear the list, such that a subsequent call to isEmpty() would return
 172    * true (optional operation).
 173    *
 174    * @throws UnsupportedOperationException if this list does not support the
 175    *         clear operation
 176    */
 177   void clear();
 178
 179   /**
 180    * Test whether this list contains a given object as one of its elements.
 181    * This is defined as the existence of an element e such that
 182    * <code>o == null ? e == null : o.equals(e)</code>.
 183    *
 184    * @param o the element to look for
 185    * @return true if this list contains the element
 186    * @throws ClassCastException if the type of o is not a valid type
 187    *         for this list.
 188    * @throws NullPointerException if o is null and the list doesn't
 189    *         support null values.
 190    */
 191   boolean contains(Object o);
 192
 193   /**
 194    * Test whether this list contains every element in a given collection.
 195    *
 196    * @param c the collection to test for
 197    * @return true if for every element o in c, contains(o) would return true
 198    * @throws NullPointerException if the collection is null
 199    * @throws ClassCastException if the type of any element in c is not a valid
 200    *         type for this list.
 201    * @throws NullPointerException if some element of c is null and this
 202    *         list does not support null values.
 203    * @see #contains(Object)
 204    */
 205   boolean containsAll(Collection<?> c);
 206
 207   /**
 208    * Test whether this list is equal to another object. A List is defined to be
 209    * equal to an object if and only if that object is also a List, and the two
 210    * lists have the same sequence. Two lists l1 and l2 are equal if and only
 211    * if <code>l1.size() == l2.size()</code>, and for every integer n between 0
 212    * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ?
 213    * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
 214    *
 215    * @param o the object to test for equality with this list
 216    * @return true if o is equal to this list
 217    * @see Object#equals(Object)
 218    * @see #hashCode()
 219    */
 220   boolean equals(Object o);
 221
 222   /**
 223    * Get the element at a given index in this list.
 224    *
 225    * @param index the index of the element to be returned
 226    * @return the element at index index in this list
 227    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 228    */
 229   E get(int index);
 230
 231   /**
 232    * Obtains a hash code for this list. In order to obey the general
 233    * contract of the hashCode method of class Object, this value is
 234    * calculated as follows:
 235    *
 236 <p><pre>hashCode = 1;
 237 Iterator i = list.iterator();
 238 while (i.hasNext())
 239 {
 240   Object obj = i.next();
 241   hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
 242 }</pre>
 243    *
 244    * <p>This ensures that the general contract of Object.hashCode()
 245    * is adhered to.
 246    *
 247    * @return the hash code of this list
 248    * @see Object#hashCode()
 249    * @see #equals(Object)
 250    */
 251   int hashCode();
 252
 253   /**
 254    * Obtain the first index at which a given object is to be found in this
 255    * list.
 256    *
 257    * @param o the object to search for
 258    * @return the least integer n such that <code>o == null ? get(n) == null :
 259    *         o.equals(get(n))</code>, or -1 if there is no such index.
 260    * @throws ClassCastException if the type of o is not a valid
 261    *         type for this list.
 262    * @throws NullPointerException if o is null and this
 263    *         list does not support null values.
 264    */
 265   int indexOf(Object o);
 266
 267   /**
 268    * Test whether this list is empty, that is, if size() == 0.
 269    *
 270    * @return true if this list contains no elements
 271    */
 272   boolean isEmpty();
 273
 274   /**
 275    * Obtain an Iterator over this list, whose sequence is the list order.
 276    *
 277    * @return an Iterator over the elements of this list, in order
 278    */
 279   Iterator<E> iterator();
 280
 281   /**
 282    * Obtain the last index at which a given object is to be found in this
 283    * list.
 284    *
 285    * @return the greatest integer n such that <code>o == null ? get(n) == null
 286    *         : o.equals(get(n))</code>, or -1 if there is no such index.
 287    * @throws ClassCastException if the type of o is not a valid
 288    *         type for this list.
 289    * @throws NullPointerException if o is null and this
 290    *         list does not support null values.
 291    */
 292   int lastIndexOf(Object o);
 293
 294   /**
 295    * Obtain a ListIterator over this list, starting at the beginning.
 296    *
 297    * @return a ListIterator over the elements of this list, in order, starting
 298    *         at the beginning
 299    */
 300   ListIterator<E> listIterator();
 301
 302   /**
 303    * Obtain a ListIterator over this list, starting at a given position.
 304    * A first call to next() would return the same as get(index), and a
 305    * first call to previous() would return the same as get(index - 1).
 306    *
 307    * @param index the position, between 0 and size() inclusive, to begin the
 308    *        iteration from
 309    * @return a ListIterator over the elements of this list, in order, starting
 310    *         at index
 311    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 312    */
 313   ListIterator<E> listIterator(int index);
 314
 315   /**
 316    * Remove the element at a given position in this list (optional operation).
 317    * Shifts all remaining elements to the left to fill the gap.
 318    *
 319    * @param index the position within the list of the object to remove
 320    * @return the object that was removed
 321    * @throws UnsupportedOperationException if this list does not support the
 322    *         remove operation
 323    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 324    */
 325   E remove(int index);
 326
 327   /**
 328    * Remove the first occurence of an object from this list (optional
 329    * operation). That is, remove the first element e such that
 330    * <code>o == null ? e == null : o.equals(e)</code>.
 331    *
 332    * @param o the object to remove
 333    * @return true if the list changed as a result of this call, that is, if
 334    *         the list contained at least one occurrence of o
 335    * @throws UnsupportedOperationException if this list does not support the
 336    *         remove operation
 337    * @throws ClassCastException if the type of o is not a valid
 338    *         type for this list.
 339    * @throws NullPointerException if o is null and this
 340    *         list does not support removing null values.
 341    */
 342   boolean remove(Object o);
 343
 344   /**
 345    * Remove all elements of a given collection from this list (optional
 346    * operation). That is, remove every element e such that c.contains(e).
 347    *
 348    * @param c the collection to filter out
 349    * @return true if this list was modified as a result of this call
 350    * @throws UnsupportedOperationException if this list does not support the
 351    *         removeAll operation
 352    * @throws NullPointerException if the collection is null
 353    * @throws ClassCastException if the type of any element in c is not a valid
 354    *         type for this list.
 355    * @throws NullPointerException if some element of c is null and this
 356    *         list does not support removing null values.
 357    * @see #remove(Object)
 358    * @see #contains(Object)
 359    */
 360   boolean removeAll(Collection<?> c);
 361
 362   /**
 363    * Remove all elements of this list that are not contained in a given
 364    * collection (optional operation). That is, remove every element e such
 365    * that !c.contains(e).
 366    *
 367    * @param c the collection to retain
 368    * @return true if this list was modified as a result of this call
 369    * @throws UnsupportedOperationException if this list does not support the
 370    *         retainAll operation
 371    * @throws NullPointerException if the collection is null
 372    * @throws ClassCastException if the type of any element in c is not a valid
 373    *         type for this list.
 374    * @throws NullPointerException if some element of c is null and this
 375    *         list does not support retaining null values.
 376    * @see #remove(Object)
 377    * @see #contains(Object)
 378    */
 379   boolean retainAll(Collection<?> c);
 380
 381   /**
 382    * Replace an element of this list with another object (optional operation).
 383    *
 384    * @param index the position within this list of the element to be replaced
 385    * @param o the object to replace it with
 386    * @return the object that was replaced
 387    * @throws UnsupportedOperationException if this list does not support the
 388    *         set operation
 389    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 390    * @throws ClassCastException if o cannot be added to this list due to its
 391    *         type
 392    * @throws IllegalArgumentException if o cannot be added to this list for
 393    *         some other reason
 394    * @throws NullPointerException if o is null and this
 395    *         list does not support null values.
 396    */
 397   E set(int index, E o);
 398
 399   /**
 400    * Get the number of elements in this list. If the list contains more
 401    * than Integer.MAX_VALUE elements, return Integer.MAX_VALUE.
 402    *
 403    * @return the number of elements in the list
 404    */
 405   int size();
 406
 407   /**
 408    * Obtain a List view of a subsection of this list, from fromIndex
 409    * (inclusive) to toIndex (exclusive). If the two indices are equal, the
 410    * sublist is empty. The returned list should be modifiable if and only
 411    * if this list is modifiable. Changes to the returned list should be
 412    * reflected in this list. If this list is structurally modified in
 413    * any way other than through the returned list, the result of any subsequent
 414    * operations on the returned list is undefined.
 415    *
 416    * @param fromIndex the index that the returned list should start from
 417    *        (inclusive)
 418    * @param toIndex the index that the returned list should go to (exclusive)
 419    * @return a List backed by a subsection of this list
 420    * @throws IndexOutOfBoundsException if fromIndex &lt; 0
 421    *         || toIndex &gt; size() || fromIndex &gt; toIndex
 422    */
 423   List<E> subList(int fromIndex, int toIndex);
 424
 425   /**
 426    * Copy the current contents of this list into an array.
 427    *
 428    * @return an array of type Object[] and length equal to the length of this
 429    *         list, containing the elements currently in this list, in order
 430    */
 431   Object[] toArray();
 432
 433   /**
 434    * Copy the current contents of this list into an array. If the array passed
 435    * as an argument has length less than that of this list, an array of the
 436    * same run-time type as a, and length equal to the length of this list, is
 437    * allocated using Reflection. Otherwise, a itself is used. The elements of
 438    * this list are copied into it, and if there is space in the array, the
 439    * following element is set to null. The resultant array is returned.
 440    * Note: The fact that the following element is set to null is only useful
 441    * if it is known that this list does not contain any null elements.
 442    *
 443    * @param a the array to copy this list into
 444    * @return an array containing the elements currently in this list, in
 445    *         order
 446    * @throws ArrayStoreException if the type of any element of the
 447    *         collection is not a subtype of the element type of a
 448    * @throws NullPointerException if the specified array is null
 449    */
 450   <T> T[] toArray(T[] a);
 451 }