Source code

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<>(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<>(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<>();
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<>(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}