001 /* List.java -- An ordered collection which allows indexed access 002 Copyright (C) 1998, 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 * An ordered collection (also known as a list). This collection allows 043 * access to elements by position, as well as control on where elements 044 * are inserted. Unlike sets, duplicate elements are permitted by this 045 * general contract (if a subclass forbids duplicates, this should be 046 * documented). 047 * <p> 048 * 049 * List places additional requirements on <code>iterator</code>, 050 * <code>add</code>, <code>remove</code>, <code>equals</code>, and 051 * <code>hashCode</code>, in addition to requiring more methods. List 052 * indexing is 0-based (like arrays), although some implementations may 053 * require time proportional to the index to obtain an arbitrary element. 054 * The List interface is incompatible with Set; you cannot implement both 055 * simultaneously. 056 * <p> 057 * 058 * Lists also provide a <code>ListIterator</code> which allows bidirectional 059 * traversal and other features atop regular iterators. Lists can be 060 * searched for arbitrary elements, and allow easy insertion and removal 061 * of multiple elements in one method call. 062 * <p> 063 * 064 * Note: While lists may contain themselves as elements, this leads to 065 * undefined (usually infinite recursive) behavior for some methods like 066 * hashCode or equals. 067 * 068 * @author Original author unknown 069 * @author Eric Blake (ebb9@email.byu.edu) 070 * @see Collection 071 * @see Set 072 * @see ArrayList 073 * @see LinkedList 074 * @see Vector 075 * @see Arrays#asList(Object[]) 076 * @see Collections#nCopies(int, Object) 077 * @see Collections#EMPTY_LIST 078 * @see AbstractList 079 * @see AbstractSequentialList 080 * @since 1.2 081 * @status updated to 1.4 082 */ 083 public interface List<E> extends Collection<E> 084 { 085 /** 086 * Insert an element into the list at a given position (optional operation). 087 * This shifts all existing elements from that position to the end one 088 * index to the right. This version of add has no return, since it is 089 * assumed to always succeed if there is no exception. 090 * 091 * @param index the location to insert the item 092 * @param o the object to insert 093 * @throws UnsupportedOperationException if this list does not support the 094 * add operation 095 * @throws IndexOutOfBoundsException if index < 0 || index > size() 096 * @throws ClassCastException if o cannot be added to this list due to its 097 * type 098 * @throws IllegalArgumentException if o cannot be added to this list for 099 * 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index >= 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 < 0 421 * || toIndex > size() || fromIndex > 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 }