001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkElementIndex; 021import static com.google.common.base.Preconditions.checkNotNull; 022import static com.google.common.base.Preconditions.checkPositionIndexes; 023import static com.google.common.collect.CollectPreconditions.checkNonnegative; 024import static com.google.common.collect.ObjectArrays.checkElementsNotNull; 025import static com.google.common.collect.RegularImmutableList.EMPTY; 026import static java.util.Objects.requireNonNull; 027 028import com.google.common.annotations.GwtCompatible; 029import com.google.common.annotations.GwtIncompatible; 030import com.google.common.annotations.J2ktIncompatible; 031import com.google.common.annotations.VisibleForTesting; 032import com.google.errorprone.annotations.CanIgnoreReturnValue; 033import com.google.errorprone.annotations.DoNotCall; 034import com.google.errorprone.annotations.InlineMe; 035import java.io.InvalidObjectException; 036import java.io.ObjectInputStream; 037import java.io.Serializable; 038import java.util.Arrays; 039import java.util.Collection; 040import java.util.Collections; 041import java.util.Comparator; 042import java.util.Iterator; 043import java.util.List; 044import java.util.RandomAccess; 045import java.util.Spliterator; 046import java.util.function.Consumer; 047import java.util.function.UnaryOperator; 048import java.util.stream.Collector; 049import javax.annotation.CheckForNull; 050import org.checkerframework.checker.nullness.qual.Nullable; 051 052/** 053 * A {@link List} whose contents will never change, with many other important properties detailed at 054 * {@link ImmutableCollection}. 055 * 056 * <p>See the Guava User Guide article on <a href= 057 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>. 058 * 059 * @see ImmutableMap 060 * @see ImmutableSet 061 * @author Kevin Bourrillion 062 * @since 2.0 063 */ 064@GwtCompatible(serializable = true, emulated = true) 065@SuppressWarnings("serial") // we're overriding default serialization 066@ElementTypesAreNonnullByDefault 067public abstract class ImmutableList<E> extends ImmutableCollection<E> 068 implements List<E>, RandomAccess { 069 070 /** 071 * Returns a {@code Collector} that accumulates the input elements into a new {@code 072 * ImmutableList}, in encounter order. 073 * 074 * @since 21.0 075 */ 076 public static <E> Collector<E, ?, ImmutableList<E>> toImmutableList() { 077 return CollectCollectors.toImmutableList(); 078 } 079 080 /** 081 * Returns the empty immutable list. This list behaves and performs comparably to {@link 082 * Collections#emptyList}, and is preferable mainly for consistency and maintainability of your 083 * code. 084 * 085 * <p><b>Performance note:</b> the instance returned is a singleton. 086 */ 087 // Casting to any type is safe because the list will never hold any elements. 088 @SuppressWarnings("unchecked") 089 public static <E> ImmutableList<E> of() { 090 return (ImmutableList<E>) EMPTY; 091 } 092 093 /** 094 * Returns an immutable list containing a single element. This list behaves and performs 095 * comparably to {@link Collections#singletonList}, but will not accept a null element. It is 096 * preferable mainly for consistency and maintainability of your code. 097 * 098 * @throws NullPointerException if {@code element} is null 099 */ 100 public static <E> ImmutableList<E> of(E element) { 101 return new SingletonImmutableList<E>(element); 102 } 103 104 /** 105 * Returns an immutable list containing the given elements, in order. 106 * 107 * @throws NullPointerException if any element is null 108 */ 109 public static <E> ImmutableList<E> of(E e1, E e2) { 110 return construct(e1, e2); 111 } 112 113 /** 114 * Returns an immutable list containing the given elements, in order. 115 * 116 * @throws NullPointerException if any element is null 117 */ 118 public static <E> ImmutableList<E> of(E e1, E e2, E e3) { 119 return construct(e1, e2, e3); 120 } 121 122 /** 123 * Returns an immutable list containing the given elements, in order. 124 * 125 * @throws NullPointerException if any element is null 126 */ 127 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4) { 128 return construct(e1, e2, e3, e4); 129 } 130 131 /** 132 * Returns an immutable list containing the given elements, in order. 133 * 134 * @throws NullPointerException if any element is null 135 */ 136 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5) { 137 return construct(e1, e2, e3, e4, e5); 138 } 139 140 /** 141 * Returns an immutable list containing the given elements, in order. 142 * 143 * @throws NullPointerException if any element is null 144 */ 145 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6) { 146 return construct(e1, e2, e3, e4, e5, e6); 147 } 148 149 /** 150 * Returns an immutable list containing the given elements, in order. 151 * 152 * @throws NullPointerException if any element is null 153 */ 154 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) { 155 return construct(e1, e2, e3, e4, e5, e6, e7); 156 } 157 158 /** 159 * Returns an immutable list containing the given elements, in order. 160 * 161 * @throws NullPointerException if any element is null 162 */ 163 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) { 164 return construct(e1, e2, e3, e4, e5, e6, e7, e8); 165 } 166 167 /** 168 * Returns an immutable list containing the given elements, in order. 169 * 170 * @throws NullPointerException if any element is null 171 */ 172 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) { 173 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9); 174 } 175 176 /** 177 * Returns an immutable list containing the given elements, in order. 178 * 179 * @throws NullPointerException if any element is null 180 */ 181 public static <E> ImmutableList<E> of( 182 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) { 183 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10); 184 } 185 186 /** 187 * Returns an immutable list containing the given elements, in order. 188 * 189 * @throws NullPointerException if any element is null 190 */ 191 public static <E> ImmutableList<E> of( 192 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11) { 193 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11); 194 } 195 196 // These go up to eleven. After that, you just get the varargs form, and 197 // whatever warnings might come along with it. :( 198 199 /** 200 * Returns an immutable list containing the given elements, in order. 201 * 202 * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 12}. 203 * 204 * @throws NullPointerException if any element is null 205 * @since 3.0 (source-compatible since 2.0) 206 */ 207 @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning. 208 public static <E> ImmutableList<E> of( 209 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11, E e12, E... others) { 210 checkArgument( 211 others.length <= Integer.MAX_VALUE - 12, "the total number of elements must fit in an int"); 212 Object[] array = new Object[12 + others.length]; 213 array[0] = e1; 214 array[1] = e2; 215 array[2] = e3; 216 array[3] = e4; 217 array[4] = e5; 218 array[5] = e6; 219 array[6] = e7; 220 array[7] = e8; 221 array[8] = e9; 222 array[9] = e10; 223 array[10] = e11; 224 array[11] = e12; 225 System.arraycopy(others, 0, array, 12, others.length); 226 return construct(array); 227 } 228 229 /** 230 * Returns an immutable list containing the given elements, in order. If {@code elements} is a 231 * {@link Collection}, this method behaves exactly as {@link #copyOf(Collection)}; otherwise, it 232 * behaves exactly as {@code copyOf(elements.iterator()}. 233 * 234 * @throws NullPointerException if {@code elements} contains a null element 235 */ 236 public static <E> ImmutableList<E> copyOf(Iterable<? extends E> elements) { 237 checkNotNull(elements); // TODO(kevinb): is this here only for GWT? 238 return (elements instanceof Collection) 239 ? copyOf((Collection<? extends E>) elements) 240 : copyOf(elements.iterator()); 241 } 242 243 /** 244 * Returns an immutable list containing the given elements, in order. 245 * 246 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 247 * safe to do so. The exact circumstances under which a copy will or will not be performed are 248 * undocumented and subject to change. 249 * 250 * <p>Note that if {@code list} is a {@code List<String>}, then {@code ImmutableList.copyOf(list)} 251 * returns an {@code ImmutableList<String>} containing each of the strings in {@code list}, while 252 * {@code ImmutableList.of(list)} returns an {@code ImmutableList<List<String>>} containing one 253 * element (the given list itself). 254 * 255 * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent 256 * collection that is currently being modified by another thread. 257 * 258 * @throws NullPointerException if {@code elements} contains a null element 259 */ 260 public static <E> ImmutableList<E> copyOf(Collection<? extends E> elements) { 261 if (elements instanceof ImmutableCollection) { 262 @SuppressWarnings("unchecked") // all supported methods are covariant 263 ImmutableList<E> list = ((ImmutableCollection<E>) elements).asList(); 264 return list.isPartialView() ? ImmutableList.<E>asImmutableList(list.toArray()) : list; 265 } 266 return construct(elements.toArray()); 267 } 268 269 /** 270 * Returns an immutable list containing the given elements, in order. 271 * 272 * @throws NullPointerException if {@code elements} contains a null element 273 */ 274 public static <E> ImmutableList<E> copyOf(Iterator<? extends E> elements) { 275 // We special-case for 0 or 1 elements, but going further is madness. 276 if (!elements.hasNext()) { 277 return of(); 278 } 279 E first = elements.next(); 280 if (!elements.hasNext()) { 281 return of(first); 282 } else { 283 return new ImmutableList.Builder<E>().add(first).addAll(elements).build(); 284 } 285 } 286 287 /** 288 * Returns an immutable list containing the given elements, in order. 289 * 290 * @throws NullPointerException if {@code elements} contains a null element 291 * @since 3.0 292 */ 293 public static <E> ImmutableList<E> copyOf(E[] elements) { 294 switch (elements.length) { 295 case 0: 296 return of(); 297 case 1: 298 return of(elements[0]); 299 default: 300 return construct(elements.clone()); 301 } 302 } 303 304 /** 305 * Returns an immutable list containing the given elements, sorted according to their natural 306 * order. The sorting algorithm used is stable, so elements that compare as equal will stay in the 307 * order in which they appear in the input. 308 * 309 * <p>If your data has no duplicates, or you wish to deduplicate elements, use {@code 310 * ImmutableSortedSet.copyOf(elements)}; if you want a {@code List} you can use its {@code 311 * asList()} view. 312 * 313 * <p><b>Java 8+ users:</b> If you want to convert a {@link java.util.stream.Stream} to a sorted 314 * {@code ImmutableList}, use {@code stream.sorted().collect(toImmutableList())}. 315 * 316 * @throws NullPointerException if any element in the input is null 317 * @since 21.0 318 */ 319 public static <E extends Comparable<? super E>> ImmutableList<E> sortedCopyOf( 320 Iterable<? extends E> elements) { 321 Comparable<?>[] array = Iterables.toArray(elements, new Comparable<?>[0]); 322 checkElementsNotNull((Object[]) array); 323 Arrays.sort(array); 324 return asImmutableList(array); 325 } 326 327 /** 328 * Returns an immutable list containing the given elements, in sorted order relative to the 329 * specified comparator. The sorting algorithm used is stable, so elements that compare as equal 330 * will stay in the order in which they appear in the input. 331 * 332 * <p>If your data has no duplicates, or you wish to deduplicate elements, use {@code 333 * ImmutableSortedSet.copyOf(comparator, elements)}; if you want a {@code List} you can use its 334 * {@code asList()} view. 335 * 336 * <p><b>Java 8+ users:</b> If you want to convert a {@link java.util.stream.Stream} to a sorted 337 * {@code ImmutableList}, use {@code stream.sorted(comparator).collect(toImmutableList())}. 338 * 339 * @throws NullPointerException if any element in the input is null 340 * @since 21.0 341 */ 342 public static <E> ImmutableList<E> sortedCopyOf( 343 Comparator<? super E> comparator, Iterable<? extends E> elements) { 344 checkNotNull(comparator); 345 @SuppressWarnings("unchecked") // all supported methods are covariant 346 E[] array = (E[]) Iterables.toArray(elements); 347 checkElementsNotNull(array); 348 Arrays.sort(array, comparator); 349 return asImmutableList(array); 350 } 351 352 /** Views the array as an immutable list. Checks for nulls; does not copy. */ 353 private static <E> ImmutableList<E> construct(Object... elements) { 354 return asImmutableList(checkElementsNotNull(elements)); 355 } 356 357 /** 358 * Views the array as an immutable list. Does not check for nulls; does not copy. 359 * 360 * <p>The array must be internally created. 361 */ 362 static <E> ImmutableList<E> asImmutableList(Object[] elements) { 363 return asImmutableList(elements, elements.length); 364 } 365 366 /** 367 * Views the array as an immutable list. Copies if the specified range does not cover the complete 368 * array. Does not check for nulls. 369 */ 370 static <E> ImmutableList<E> asImmutableList(@Nullable Object[] elements, int length) { 371 switch (length) { 372 case 0: 373 return of(); 374 case 1: 375 /* 376 * requireNonNull is safe because the callers promise to put non-null objects in the first 377 * `length` array elements. 378 */ 379 @SuppressWarnings("unchecked") // our callers put only E instances into the array 380 E onlyElement = (E) requireNonNull(elements[0]); 381 return of(onlyElement); 382 default: 383 /* 384 * The suppression is safe because the callers promise to put non-null objects in the first 385 * `length` array elements. 386 */ 387 @SuppressWarnings("nullness") 388 Object[] elementsWithoutTrailingNulls = 389 length < elements.length ? Arrays.copyOf(elements, length) : elements; 390 return new RegularImmutableList<E>(elementsWithoutTrailingNulls); 391 } 392 } 393 394 ImmutableList() {} 395 396 // This declaration is needed to make List.iterator() and 397 // ImmutableCollection.iterator() consistent. 398 @Override 399 public UnmodifiableIterator<E> iterator() { 400 return listIterator(); 401 } 402 403 @Override 404 public UnmodifiableListIterator<E> listIterator() { 405 return listIterator(0); 406 } 407 408 @Override 409 public UnmodifiableListIterator<E> listIterator(int index) { 410 return new AbstractIndexedListIterator<E>(size(), index) { 411 @Override 412 protected E get(int index) { 413 return ImmutableList.this.get(index); 414 } 415 }; 416 } 417 418 @Override 419 public void forEach(Consumer<? super E> consumer) { 420 checkNotNull(consumer); 421 int n = size(); 422 for (int i = 0; i < n; i++) { 423 consumer.accept(get(i)); 424 } 425 } 426 427 @Override 428 public int indexOf(@CheckForNull Object object) { 429 return (object == null) ? -1 : Lists.indexOfImpl(this, object); 430 } 431 432 @Override 433 public int lastIndexOf(@CheckForNull Object object) { 434 return (object == null) ? -1 : Lists.lastIndexOfImpl(this, object); 435 } 436 437 @Override 438 public boolean contains(@CheckForNull Object object) { 439 return indexOf(object) >= 0; 440 } 441 442 // constrain the return type to ImmutableList<E> 443 444 /** 445 * Returns an immutable list of the elements between the specified {@code fromIndex}, inclusive, 446 * and {@code toIndex}, exclusive. (If {@code fromIndex} and {@code toIndex} are equal, the empty 447 * immutable list is returned.) 448 * 449 * <p><b>Note:</b> in almost all circumstances, the returned {@link ImmutableList} retains a 450 * strong reference to {@code this}, which may prevent the original list from being garbage 451 * collected. If you want the original list to be eligible for garbage collection, you should 452 * create and use a copy of the sub list (e.g., {@code 453 * ImmutableList.copyOf(originalList.subList(...))}). 454 */ 455 @Override 456 public ImmutableList<E> subList(int fromIndex, int toIndex) { 457 checkPositionIndexes(fromIndex, toIndex, size()); 458 int length = toIndex - fromIndex; 459 if (length == size()) { 460 return this; 461 } else if (length == 0) { 462 return of(); 463 } else if (length == 1) { 464 return of(get(fromIndex)); 465 } else { 466 return subListUnchecked(fromIndex, toIndex); 467 } 468 } 469 470 /** 471 * Called by the default implementation of {@link #subList} when {@code toIndex - fromIndex > 1}, 472 * after index validation has already been performed. 473 */ 474 ImmutableList<E> subListUnchecked(int fromIndex, int toIndex) { 475 return new SubList(fromIndex, toIndex - fromIndex); 476 } 477 478 class SubList extends ImmutableList<E> { 479 final transient int offset; 480 final transient int length; 481 482 SubList(int offset, int length) { 483 this.offset = offset; 484 this.length = length; 485 } 486 487 @Override 488 public int size() { 489 return length; 490 } 491 492 @Override 493 public E get(int index) { 494 checkElementIndex(index, length); 495 return ImmutableList.this.get(index + offset); 496 } 497 498 @Override 499 public ImmutableList<E> subList(int fromIndex, int toIndex) { 500 checkPositionIndexes(fromIndex, toIndex, length); 501 return ImmutableList.this.subList(fromIndex + offset, toIndex + offset); 502 } 503 504 @Override 505 boolean isPartialView() { 506 return true; 507 } 508 509 // redeclare to help optimizers with b/310253115 510 @SuppressWarnings("RedundantOverride") 511 @Override 512 @J2ktIncompatible // serialization 513 @GwtIncompatible // serialization 514 Object writeReplace() { 515 return super.writeReplace(); 516 } 517 } 518 519 /** 520 * Guaranteed to throw an exception and leave the list unmodified. 521 * 522 * @throws UnsupportedOperationException always 523 * @deprecated Unsupported operation. 524 */ 525 @CanIgnoreReturnValue 526 @Deprecated 527 @Override 528 @DoNotCall("Always throws UnsupportedOperationException") 529 public final boolean addAll(int index, Collection<? extends E> newElements) { 530 throw new UnsupportedOperationException(); 531 } 532 533 /** 534 * Guaranteed to throw an exception and leave the list unmodified. 535 * 536 * @throws UnsupportedOperationException always 537 * @deprecated Unsupported operation. 538 */ 539 @CanIgnoreReturnValue 540 @Deprecated 541 @Override 542 @DoNotCall("Always throws UnsupportedOperationException") 543 public final E set(int index, E element) { 544 throw new UnsupportedOperationException(); 545 } 546 547 /** 548 * Guaranteed to throw an exception and leave the list unmodified. 549 * 550 * @throws UnsupportedOperationException always 551 * @deprecated Unsupported operation. 552 */ 553 @Deprecated 554 @Override 555 @DoNotCall("Always throws UnsupportedOperationException") 556 public final void add(int index, E element) { 557 throw new UnsupportedOperationException(); 558 } 559 560 /** 561 * Guaranteed to throw an exception and leave the list unmodified. 562 * 563 * @throws UnsupportedOperationException always 564 * @deprecated Unsupported operation. 565 */ 566 @CanIgnoreReturnValue 567 @Deprecated 568 @Override 569 @DoNotCall("Always throws UnsupportedOperationException") 570 public final E remove(int index) { 571 throw new UnsupportedOperationException(); 572 } 573 574 /** 575 * Guaranteed to throw an exception and leave the list unmodified. 576 * 577 * @throws UnsupportedOperationException always 578 * @deprecated Unsupported operation. 579 */ 580 @Deprecated 581 @Override 582 @DoNotCall("Always throws UnsupportedOperationException") 583 public final void replaceAll(UnaryOperator<E> operator) { 584 throw new UnsupportedOperationException(); 585 } 586 587 /** 588 * Guaranteed to throw an exception and leave the list unmodified. 589 * 590 * @throws UnsupportedOperationException always 591 * @deprecated Unsupported operation. 592 */ 593 @Deprecated 594 @Override 595 @DoNotCall("Always throws UnsupportedOperationException") 596 public final void sort(@Nullable Comparator<? super E> c) { 597 throw new UnsupportedOperationException(); 598 } 599 600 /** 601 * Returns this list instance. 602 * 603 * @since 2.0 604 * @deprecated There is no reason to use this; it always returns {@code this}. 605 */ 606 @InlineMe(replacement = "this") 607 @Deprecated 608 @Override 609 public final ImmutableList<E> asList() { 610 return this; 611 } 612 613 @Override 614 public Spliterator<E> spliterator() { 615 return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get); 616 } 617 618 @Override 619 int copyIntoArray(@Nullable Object[] dst, int offset) { 620 // this loop is faster for RandomAccess instances, which ImmutableLists are 621 int size = size(); 622 for (int i = 0; i < size; i++) { 623 dst[offset + i] = get(i); 624 } 625 return offset + size; 626 } 627 628 /** 629 * Returns a view of this immutable list in reverse order. For example, {@code ImmutableList.of(1, 630 * 2, 3).reverse()} is equivalent to {@code ImmutableList.of(3, 2, 1)}. 631 * 632 * @return a view of this immutable list in reverse order 633 * @since 7.0 634 */ 635 public ImmutableList<E> reverse() { 636 return (size() <= 1) ? this : new ReverseImmutableList<E>(this); 637 } 638 639 private static class ReverseImmutableList<E> extends ImmutableList<E> { 640 private final transient ImmutableList<E> forwardList; 641 642 ReverseImmutableList(ImmutableList<E> backingList) { 643 this.forwardList = backingList; 644 } 645 646 private int reverseIndex(int index) { 647 return (size() - 1) - index; 648 } 649 650 private int reversePosition(int index) { 651 return size() - index; 652 } 653 654 @Override 655 public ImmutableList<E> reverse() { 656 return forwardList; 657 } 658 659 @Override 660 public boolean contains(@CheckForNull Object object) { 661 return forwardList.contains(object); 662 } 663 664 @Override 665 public int indexOf(@CheckForNull Object object) { 666 int index = forwardList.lastIndexOf(object); 667 return (index >= 0) ? reverseIndex(index) : -1; 668 } 669 670 @Override 671 public int lastIndexOf(@CheckForNull Object object) { 672 int index = forwardList.indexOf(object); 673 return (index >= 0) ? reverseIndex(index) : -1; 674 } 675 676 @Override 677 public ImmutableList<E> subList(int fromIndex, int toIndex) { 678 checkPositionIndexes(fromIndex, toIndex, size()); 679 return forwardList.subList(reversePosition(toIndex), reversePosition(fromIndex)).reverse(); 680 } 681 682 @Override 683 public E get(int index) { 684 checkElementIndex(index, size()); 685 return forwardList.get(reverseIndex(index)); 686 } 687 688 @Override 689 public int size() { 690 return forwardList.size(); 691 } 692 693 @Override 694 boolean isPartialView() { 695 return forwardList.isPartialView(); 696 } 697 698 // redeclare to help optimizers with b/310253115 699 @SuppressWarnings("RedundantOverride") 700 @Override 701 @J2ktIncompatible // serialization 702 @GwtIncompatible // serialization 703 Object writeReplace() { 704 return super.writeReplace(); 705 } 706 } 707 708 @Override 709 public boolean equals(@CheckForNull Object obj) { 710 return Lists.equalsImpl(this, obj); 711 } 712 713 @Override 714 public int hashCode() { 715 int hashCode = 1; 716 int n = size(); 717 for (int i = 0; i < n; i++) { 718 hashCode = 31 * hashCode + get(i).hashCode(); 719 720 hashCode = ~~hashCode; 721 // needed to deal with GWT integer overflow 722 } 723 return hashCode; 724 } 725 726 /* 727 * Serializes ImmutableLists as their logical contents. This ensures that 728 * implementation types do not leak into the serialized representation. 729 */ 730 @J2ktIncompatible // serialization 731 static class SerializedForm implements Serializable { 732 final Object[] elements; 733 734 SerializedForm(Object[] elements) { 735 this.elements = elements; 736 } 737 738 Object readResolve() { 739 return copyOf(elements); 740 } 741 742 private static final long serialVersionUID = 0; 743 } 744 745 @J2ktIncompatible // serialization 746 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 747 throw new InvalidObjectException("Use SerializedForm"); 748 } 749 750 @Override 751 @J2ktIncompatible // serialization 752 @GwtIncompatible // serialization 753 Object writeReplace() { 754 return new SerializedForm(toArray()); 755 } 756 757 /** 758 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 759 * Builder} constructor. 760 */ 761 public static <E> Builder<E> builder() { 762 return new Builder<E>(); 763 } 764 765 /** 766 * Returns a new builder, expecting the specified number of elements to be added. 767 * 768 * <p>If {@code expectedSize} is exactly the number of elements added to the builder before {@link 769 * Builder#build} is called, the builder is likely to perform better than an unsized {@link 770 * #builder()} would have. 771 * 772 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to, 773 * but not exactly, the number of elements added to the builder. 774 * 775 * @since 23.1 776 */ 777 public static <E> Builder<E> builderWithExpectedSize(int expectedSize) { 778 checkNonnegative(expectedSize, "expectedSize"); 779 return new ImmutableList.Builder<E>(expectedSize); 780 } 781 782 /** 783 * A builder for creating immutable list instances, especially {@code public static final} lists 784 * ("constant lists"). Example: 785 * 786 * <pre>{@code 787 * public static final ImmutableList<Color> GOOGLE_COLORS 788 * = new ImmutableList.Builder<Color>() 789 * .addAll(WEBSAFE_COLORS) 790 * .add(new Color(0, 191, 255)) 791 * .build(); 792 * }</pre> 793 * 794 * <p>Elements appear in the resulting list in the same order they were added to the builder. 795 * 796 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 797 * multiple lists in series. Each new list contains all the elements of the ones created before 798 * it. 799 * 800 * @since 2.0 801 */ 802 public static final class Builder<E> extends ImmutableCollection.Builder<E> { 803 // The first `size` elements are non-null. 804 @VisibleForTesting @Nullable Object[] contents; 805 private int size; 806 private boolean forceCopy; 807 808 /** 809 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 810 * ImmutableList#builder}. 811 */ 812 public Builder() { 813 this(DEFAULT_INITIAL_CAPACITY); 814 } 815 816 Builder(int capacity) { 817 this.contents = new @Nullable Object[capacity]; 818 this.size = 0; 819 } 820 821 private void getReadyToExpandTo(int minCapacity) { 822 if (contents.length < minCapacity) { 823 this.contents = Arrays.copyOf(contents, expandedCapacity(contents.length, minCapacity)); 824 forceCopy = false; 825 } else if (forceCopy) { 826 contents = Arrays.copyOf(contents, contents.length); 827 forceCopy = false; 828 } 829 } 830 831 /** 832 * Adds {@code element} to the {@code ImmutableList}. 833 * 834 * @param element the element to add 835 * @return this {@code Builder} object 836 * @throws NullPointerException if {@code element} is null 837 */ 838 @CanIgnoreReturnValue 839 @Override 840 public Builder<E> add(E element) { 841 checkNotNull(element); 842 getReadyToExpandTo(size + 1); 843 contents[size++] = element; 844 return this; 845 } 846 847 /** 848 * Adds each element of {@code elements} to the {@code ImmutableList}. 849 * 850 * @param elements the {@code Iterable} to add to the {@code ImmutableList} 851 * @return this {@code Builder} object 852 * @throws NullPointerException if {@code elements} is null or contains a null element 853 */ 854 @CanIgnoreReturnValue 855 @Override 856 public Builder<E> add(E... elements) { 857 checkElementsNotNull(elements); 858 add(elements, elements.length); 859 return this; 860 } 861 862 private void add(@Nullable Object[] elements, int n) { 863 getReadyToExpandTo(size + n); 864 /* 865 * The following call is not statically checked, since arraycopy accepts plain Object for its 866 * parameters. If it were statically checked, the checker would still be OK with it, since 867 * we're copying into a `contents` array whose type allows it to contain nulls. Still, it's 868 * worth noting that we promise not to put nulls into the array in the first `size` elements. 869 * We uphold that promise here because our callers promise that `elements` will not contain 870 * nulls in its first `n` elements. 871 */ 872 System.arraycopy(elements, 0, contents, size, n); 873 size += n; 874 } 875 876 /** 877 * Adds each element of {@code elements} to the {@code ImmutableList}. 878 * 879 * @param elements the {@code Iterable} to add to the {@code ImmutableList} 880 * @return this {@code Builder} object 881 * @throws NullPointerException if {@code elements} is null or contains a null element 882 */ 883 @CanIgnoreReturnValue 884 @Override 885 public Builder<E> addAll(Iterable<? extends E> elements) { 886 checkNotNull(elements); 887 if (elements instanceof Collection) { 888 Collection<?> collection = (Collection<?>) elements; 889 getReadyToExpandTo(size + collection.size()); 890 if (collection instanceof ImmutableCollection) { 891 ImmutableCollection<?> immutableCollection = (ImmutableCollection<?>) collection; 892 size = immutableCollection.copyIntoArray(contents, size); 893 return this; 894 } 895 } 896 super.addAll(elements); 897 return this; 898 } 899 900 /** 901 * Adds each element of {@code elements} to the {@code ImmutableList}. 902 * 903 * @param elements the {@code Iterator} to add to the {@code ImmutableList} 904 * @return this {@code Builder} object 905 * @throws NullPointerException if {@code elements} is null or contains a null element 906 */ 907 @CanIgnoreReturnValue 908 @Override 909 public Builder<E> addAll(Iterator<? extends E> elements) { 910 super.addAll(elements); 911 return this; 912 } 913 914 @CanIgnoreReturnValue 915 Builder<E> combine(Builder<E> builder) { 916 checkNotNull(builder); 917 add(builder.contents, builder.size); 918 return this; 919 } 920 921 /** 922 * Returns a newly-created {@code ImmutableList} based on the contents of the {@code Builder}. 923 */ 924 @Override 925 public ImmutableList<E> build() { 926 forceCopy = true; 927 return asImmutableList(contents, size); 928 } 929 } 930 931 private static final long serialVersionUID = 0xcafebabe; 932}