1/* 2 * Copyright (C) 2007 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import com.google.common.annotations.GwtCompatible; 20 21import java.io.InvalidObjectException; 22import java.io.ObjectInputStream; 23import java.io.Serializable; 24import java.util.ArrayList; 25import java.util.Collection; 26import java.util.Collections; 27import java.util.Iterator; 28import java.util.List; 29import java.util.RandomAccess; 30 31import javax.annotation.Nullable; 32 33import static com.google.common.base.Preconditions.checkNotNull; 34 35/** 36 * A high-performance, immutable, random-access {@code List} implementation. 37 * Does not permit null elements. 38 * 39 * <p>Unlike {@link Collections#unmodifiableList}, which is a <i>view</i> of a 40 * separate collection that can still change, an instance of {@code 41 * ImmutableList} contains its own private data and will <i>never</i> change. 42 * {@code ImmutableList} is convenient for {@code public static final} lists 43 * ("constant lists") and also lets you easily make a "defensive copy" of a list 44 * provided to your class by a caller. 45 * 46 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as 47 * it has no public or protected constructors. Thus, instances of this type are 48 * guaranteed to be immutable. 49 * 50 * @see ImmutableMap 51 * @see ImmutableSet 52 * @author Kevin Bourrillion 53 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library) 54 */ 55@GwtCompatible(serializable = true) 56@SuppressWarnings("serial") // we're overriding default serialization 57public abstract class ImmutableList<E> extends ImmutableCollection<E> 58 implements List<E>, RandomAccess { 59 /** 60 * Returns the empty immutable list. This set behaves and performs comparably 61 * to {@link Collections#emptyList}, and is preferable mainly for consistency 62 * and maintainability of your code. 63 */ 64 // Casting to any type is safe because the list will never hold any elements. 65 @SuppressWarnings("unchecked") 66 public static <E> ImmutableList<E> of() { 67 // BEGIN android-changed 68 return (ImmutableList) EmptyImmutableList.INSTANCE; 69 // END android-changed 70 } 71 72 /** 73 * Returns an immutable list containing a single element. This list behaves 74 * and performs comparably to {@link Collections#singleton}, but will not 75 * accept a null element. It is preferable mainly for consistency and 76 * maintainability of your code. 77 * 78 * @throws NullPointerException if {@code element} is null 79 */ 80 public static <E> ImmutableList<E> of(E element) { 81 return new SingletonImmutableList<E>(element); 82 } 83 84 /** 85 * Identical to {@link #of(Object[])}. 86 * 87 * @throws NullPointerException if any element is null 88 */ 89 public static <E> ImmutableList<E> of(E e1, E e2) { 90 return new RegularImmutableList<E>(copyIntoArray(e1, e2)); 91 } 92 93 /** 94 * Identical to {@link #of(Object[])}. 95 * 96 * @throws NullPointerException if any element is null 97 */ 98 public static <E> ImmutableList<E> of(E e1, E e2, E e3) { 99 return new RegularImmutableList<E>(copyIntoArray(e1, e2, e3)); 100 } 101 102 /** 103 * Identical to {@link #of(Object[])}. 104 * 105 * @throws NullPointerException if any element is null 106 */ 107 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4) { 108 return new RegularImmutableList<E>(copyIntoArray(e1, e2, e3, e4)); 109 } 110 111 /** 112 * Identical to {@link #of(Object[])}. 113 * 114 * @throws NullPointerException if any element is null 115 */ 116 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5) { 117 return new RegularImmutableList<E>(copyIntoArray(e1, e2, e3, e4, e5)); 118 } 119 120 /** 121 * Identical to {@link #of(Object[])}. 122 * 123 * @throws NullPointerException if any element is null 124 */ 125 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6) { 126 return new RegularImmutableList<E>(copyIntoArray(e1, e2, e3, e4, e5, e6)); 127 } 128 129 /** 130 * Identical to {@link #of(Object[])}. 131 * 132 * @throws NullPointerException if any element is null 133 */ 134 public static <E> ImmutableList<E> of( 135 E e1, E e2, E e3, E e4, E e5, E e6, E e7) { 136 return new RegularImmutableList<E>( 137 copyIntoArray(e1, e2, e3, e4, e5, e6, e7)); 138 } 139 140 /** 141 * Identical to {@link #of(Object[])}. 142 * 143 * @throws NullPointerException if any element is null 144 */ 145 public static <E> ImmutableList<E> of( 146 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) { 147 return new RegularImmutableList<E>( 148 copyIntoArray(e1, e2, e3, e4, e5, e6, e7, e8)); 149 } 150 151 /** 152 * Identical to {@link #of(Object[])}. 153 * 154 * @throws NullPointerException if any element is null 155 */ 156 public static <E> ImmutableList<E> of( 157 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) { 158 return new RegularImmutableList<E>( 159 copyIntoArray(e1, e2, e3, e4, e5, e6, e7, e8, e9)); 160 } 161 162 /** 163 * Identical to {@link #of(Object[])}. 164 * 165 * @throws NullPointerException if any element is null 166 */ 167 public static <E> ImmutableList<E> of( 168 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) { 169 return new RegularImmutableList<E>( 170 copyIntoArray(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10)); 171 } 172 173 /** 174 * Identical to {@link #of(Object[])}. 175 * 176 * @throws NullPointerException if any element is null 177 */ 178 public static <E> ImmutableList<E> of( 179 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11) { 180 return new RegularImmutableList<E>( 181 copyIntoArray(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11)); 182 } 183 184 // These go up to eleven. After that, you just get the varargs form, and 185 // whatever warnings might come along with it. :( 186 187 /** 188 * Returns an immutable list containing the given elements, in order. 189 * 190 * @throws NullPointerException if any of {@code elements} is null 191 */ 192 public static <E> ImmutableList<E> of(E... elements) { 193 checkNotNull(elements); // for GWT 194 switch (elements.length) { 195 case 0: 196 return ImmutableList.of(); 197 case 1: 198 return new SingletonImmutableList<E>(elements[0]); 199 default: 200 return new RegularImmutableList<E>(copyIntoArray(elements)); 201 } 202 } 203 204 /** 205 * Returns an immutable list containing the given elements, in order. If 206 * {@code elements} is a {@link Collection}, this method behaves exactly as 207 * {@link #copyOf(Collection)}; otherwise, it behaves exactly as {@code 208 * copyOf(elements.iterator()}. 209 * 210 * @throws NullPointerException if any of {@code elements} is null 211 */ 212 @SuppressWarnings("unchecked") // bugs.sun.com/view_bug.do?bug_id=6558557 213 public static <E> ImmutableList<E> copyOf(Iterable<? extends E> elements) { 214 checkNotNull(elements); 215 return (elements instanceof Collection) 216 ? copyOf((Collection<? extends E>) elements) 217 : copyOf(elements.iterator()); 218 } 219 220 /** 221 * Returns an immutable list containing the given elements, in order. 222 * 223 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} 224 * is an {@code ImmutableList}, no copy will actually be performed, and the 225 * given list itself will be returned. 226 * 227 * <p>Note that if {@code list} is a {@code List<String>}, then {@code 228 * ImmutableList.copyOf(list)} returns an {@code ImmutableList<String>} 229 * containing each of the strings in {@code list}, while 230 * ImmutableList.of(list)} returns an {@code ImmutableList<List<String>>} 231 * containing one element (the given list itself). 232 * 233 * <p>This method is safe to use even when {@code elements} is a synchronized 234 * or concurrent collection that is currently being modified by another 235 * thread. 236 * 237 * @throws NullPointerException if any of {@code elements} is null 238 * @since 2010.01.04 <b>stable</b> (Iterable overload existed previously) 239 */ 240 public static <E> ImmutableList<E> copyOf(Collection<? extends E> elements) { 241 checkNotNull(elements); 242 // TODO: Once the ImmutableAsList and ImmutableSortedAsList are 243 // GWT-compatible, return elements.asList() when elements is an 244 // ImmutableCollection. 245 if (elements instanceof ImmutableList) { 246 /* 247 * TODO: When given an ImmutableList that's a sublist, copy the referenced 248 * portion of the array into a new array to save space? 249 */ 250 @SuppressWarnings("unchecked") // all supported methods are covariant 251 ImmutableList<E> list = (ImmutableList<E>) elements; 252 return list; 253 } 254 return copyFromCollection(elements); 255 } 256 257 /** 258 * Returns an immutable list containing the given elements, in order. 259 * 260 * @throws NullPointerException if any of {@code elements} is null 261 */ 262 public static <E> ImmutableList<E> copyOf(Iterator<? extends E> elements) { 263 return copyFromCollection(Lists.newArrayList(elements)); 264 } 265 266 private static <E> ImmutableList<E> copyFromCollection( 267 Collection<? extends E> collection) { 268 Object[] elements = collection.toArray(); 269 switch (elements.length) { 270 case 0: 271 return of(); 272 case 1: 273 @SuppressWarnings("unchecked") // collection had only Es in it 274 ImmutableList<E> list = new SingletonImmutableList<E>((E) elements[0]); 275 return list; 276 default: 277 return new RegularImmutableList<E>(copyIntoArray(elements)); 278 } 279 } 280 281 ImmutableList() {} 282 283 // This declaration is needed to make List.iterator() and 284 // ImmutableCollection.iterator() consistent. 285 @Override public abstract UnmodifiableIterator<E> iterator(); 286 287 // Mark these two methods with @Nullable 288 289 public abstract int indexOf(@Nullable Object object); 290 291 public abstract int lastIndexOf(@Nullable Object object); 292 293 // constrain the return type to ImmutableList<E> 294 295 /** 296 * Returns an immutable list of the elements between the specified {@code 297 * fromIndex}, inclusive, and {@code toIndex}, exclusive. (If {@code 298 * fromIndex} and {@code toIndex} are equal, the empty immutable list is 299 * returned.) 300 */ 301 public abstract ImmutableList<E> subList(int fromIndex, int toIndex); 302 303 /** 304 * Guaranteed to throw an exception and leave the list unmodified. 305 * 306 * @throws UnsupportedOperationException always 307 */ 308 public final boolean addAll(int index, Collection<? extends E> newElements) { 309 throw new UnsupportedOperationException(); 310 } 311 312 /** 313 * Guaranteed to throw an exception and leave the list unmodified. 314 * 315 * @throws UnsupportedOperationException always 316 */ 317 public final E set(int index, E element) { 318 throw new UnsupportedOperationException(); 319 } 320 321 /** 322 * Guaranteed to throw an exception and leave the list unmodified. 323 * 324 * @throws UnsupportedOperationException always 325 */ 326 public final void add(int index, E element) { 327 throw new UnsupportedOperationException(); 328 } 329 330 /** 331 * Guaranteed to throw an exception and leave the list unmodified. 332 * 333 * @throws UnsupportedOperationException always 334 */ 335 public final E remove(int index) { 336 throw new UnsupportedOperationException(); 337 } 338 339 private static Object[] copyIntoArray(Object... source) { 340 Object[] array = new Object[source.length]; 341 int index = 0; 342 for (Object element : source) { 343 if (element == null) { 344 throw new NullPointerException("at index " + index); 345 } 346 array[index++] = element; 347 } 348 return array; 349 } 350 351 /** 352 * Returns this list instance. 353 * 354 * @since 2010.01.04 <b>tentative</b> 355 */ 356 @Override public ImmutableList<E> asList() { 357 return this; 358 } 359 360 /* 361 * Serializes ImmutableLists as their logical contents. This ensures that 362 * implementation types do not leak into the serialized representation. 363 */ 364 private static class SerializedForm implements Serializable { 365 final Object[] elements; 366 SerializedForm(Object[] elements) { 367 this.elements = elements; 368 } 369 Object readResolve() { 370 return of(elements); 371 } 372 private static final long serialVersionUID = 0; 373 } 374 375 private void readObject(ObjectInputStream stream) 376 throws InvalidObjectException { 377 throw new InvalidObjectException("Use SerializedForm"); 378 } 379 380 @Override Object writeReplace() { 381 return new SerializedForm(toArray()); 382 } 383 384 /** 385 * Returns a new builder. The generated builder is equivalent to the builder 386 * created by the {@link Builder} constructor. 387 */ 388 public static <E> Builder<E> builder() { 389 return new Builder<E>(); 390 } 391 392 /** 393 * A builder for creating immutable list instances, especially 394 * {@code public static final} lists ("constant lists"). 395 * 396 * <p>Example: 397 * <pre> {@code 398 * public static final ImmutableList<Color> GOOGLE_COLORS 399 * = new ImmutableList.Builder<Color>() 400 * .addAll(WEBSAFE_COLORS) 401 * .add(new Color(0, 191, 255)) 402 * .build();}</pre> 403 * 404 * <p>Builder instances can be reused - it is safe to call {@link #build} 405 * multiple times to build multiple lists in series. Each new list 406 * contains the one created before it. 407 */ 408 public static final class Builder<E> extends ImmutableCollection.Builder<E> { 409 private final ArrayList<E> contents = Lists.newArrayList(); 410 411 /** 412 * Creates a new builder. The returned builder is equivalent to the builder 413 * generated by {@link ImmutableList#builder}. 414 */ 415 public Builder() {} 416 417 /** 418 * Adds {@code element} to the {@code ImmutableList}. 419 * 420 * @param element the element to add 421 * @return this {@code Builder} object 422 * @throws NullPointerException if {@code element} is null 423 */ 424 @Override public Builder<E> add(E element) { 425 contents.add(checkNotNull(element)); 426 return this; 427 } 428 429 /** 430 * Adds each element of {@code elements} to the {@code ImmutableList}. 431 * 432 * @param elements the {@code Iterable} to add to the {@code ImmutableList} 433 * @return this {@code Builder} object 434 * @throws NullPointerException if {@code elements} is null or contains a 435 * null element 436 */ 437 @Override public Builder<E> addAll(Iterable<? extends E> elements) { 438 if (elements instanceof Collection) { 439 Collection<?> collection = (Collection<?>) elements; 440 contents.ensureCapacity(contents.size() + collection.size()); 441 } 442 super.addAll(elements); 443 return this; 444 } 445 446 /** 447 * Adds each element of {@code elements} to the {@code ImmutableList}. 448 * 449 * @param elements the {@code Iterable} to add to the {@code ImmutableList} 450 * @return this {@code Builder} object 451 * @throws NullPointerException if {@code elements} is null or contains a 452 * null element 453 */ 454 @Override public Builder<E> add(E... elements) { 455 checkNotNull(elements); // for GWT 456 contents.ensureCapacity(contents.size() + elements.length); 457 super.add(elements); 458 return this; 459 } 460 461 /** 462 * Adds each element of {@code elements} to the {@code ImmutableList}. 463 * 464 * @param elements the {@code Iterable} to add to the {@code ImmutableList} 465 * @return this {@code Builder} object 466 * @throws NullPointerException if {@code elements} is null or contains a 467 * null element 468 */ 469 @Override public Builder<E> addAll(Iterator<? extends E> elements) { 470 super.addAll(elements); 471 return this; 472 } 473 474 /** 475 * Returns a newly-created {@code ImmutableList} based on the contents of 476 * the {@code Builder}. 477 */ 478 @Override public ImmutableList<E> build() { 479 return copyOf(contents); 480 } 481 } 482} 483