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