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