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.checkPositionIndex;
023import static com.google.common.base.Preconditions.checkPositionIndexes;
024import static com.google.common.collect.CollectPreconditions.checkNonnegative;
025import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
026import static com.google.common.collect.RegularImmutableList.EMPTY;
027
028import com.google.common.annotations.GwtCompatible;
029import com.google.common.annotations.GwtIncompatible;
030import com.google.common.annotations.J2ktIncompatible;
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.stream.Collector;
045import javax.annotation.CheckForNull;
046import org.checkerframework.checker.nullness.qual.Nullable;
047
048/**
049 * A {@link List} whose contents will never change, with many other important properties detailed at
050 * {@link ImmutableCollection}.
051 *
052 * <p>See the Guava User Guide article on <a href=
053 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
054 *
055 * @see ImmutableMap
056 * @see ImmutableSet
057 * @author Kevin Bourrillion
058 * @since 2.0
059 */
060@GwtCompatible(serializable = true, emulated = true)
061@SuppressWarnings("serial") // we're overriding default serialization
062@ElementTypesAreNonnullByDefault
063public abstract class ImmutableList<E> extends ImmutableCollection<E>
064    implements List<E>, RandomAccess {
065
066  /**
067   * Returns a {@code Collector} that accumulates the input elements into a new {@code
068   * ImmutableList}, in encounter order.
069   *
070   * @since 33.2.0 (available since 21.0 in guava-jre)
071   */
072  @SuppressWarnings("Java7ApiChecker")
073  @IgnoreJRERequirement // Users will use this only if they're already using streams.
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 construct(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    return (elements.length == 0)
293        ? ImmutableList.<E>of()
294        : ImmutableList.<E>construct(elements.clone());
295  }
296
297  /**
298   * Returns an immutable list containing the given elements, sorted according to their natural
299   * order. The sorting algorithm used is stable, so elements that compare as equal will stay in the
300   * order in which they appear in the input.
301   *
302   * <p>If your data has no duplicates, or you wish to deduplicate elements, use {@code
303   * ImmutableSortedSet.copyOf(elements)}; if you want a {@code List} you can use its {@code
304   * asList()} view.
305   *
306   * <p><b>Java 8+ users:</b> If you want to convert a {@link java.util.stream.Stream} to a sorted
307   * {@code ImmutableList}, use {@code stream.sorted().collect(toImmutableList())}.
308   *
309   * @throws NullPointerException if any element in the input is null
310   * @since 21.0
311   */
312  public static <E extends Comparable<? super E>> ImmutableList<E> sortedCopyOf(
313      Iterable<? extends E> elements) {
314    Comparable<?>[] array = Iterables.toArray(elements, new Comparable<?>[0]);
315    checkElementsNotNull((Object[]) array);
316    Arrays.sort(array);
317    return asImmutableList(array);
318  }
319
320  /**
321   * Returns an immutable list containing the given elements, in sorted order relative to the
322   * specified comparator. The sorting algorithm used is stable, so elements that compare as equal
323   * will stay in the order in which they appear in the input.
324   *
325   * <p>If your data has no duplicates, or you wish to deduplicate elements, use {@code
326   * ImmutableSortedSet.copyOf(comparator, elements)}; if you want a {@code List} you can use its
327   * {@code asList()} view.
328   *
329   * <p><b>Java 8+ users:</b> If you want to convert a {@link java.util.stream.Stream} to a sorted
330   * {@code ImmutableList}, use {@code stream.sorted(comparator).collect(toImmutableList())}.
331   *
332   * @throws NullPointerException if any element in the input is null
333   * @since 21.0
334   */
335  public static <E> ImmutableList<E> sortedCopyOf(
336      Comparator<? super E> comparator, Iterable<? extends E> elements) {
337    checkNotNull(comparator);
338    @SuppressWarnings("unchecked") // all supported methods are covariant
339    E[] array = (E[]) Iterables.toArray(elements);
340    checkElementsNotNull(array);
341    Arrays.sort(array, comparator);
342    return asImmutableList(array);
343  }
344
345  /** Views the array as an immutable list. Checks for nulls; does not copy. */
346  private static <E> ImmutableList<E> construct(Object... elements) {
347    return asImmutableList(checkElementsNotNull(elements));
348  }
349
350  /**
351   * Views the array as an immutable list. Does not check for nulls; does not copy.
352   *
353   * <p>The array must be internally created.
354   */
355  static <E> ImmutableList<E> asImmutableList(Object[] elements) {
356    return asImmutableList(elements, elements.length);
357  }
358
359  /** Views the array as an immutable list. Does not check for nulls. */
360  static <E> ImmutableList<E> asImmutableList(@Nullable Object[] elements, int length) {
361    if (length == 0) {
362      return of();
363    }
364    return new RegularImmutableList<E>(elements, length);
365  }
366
367  ImmutableList() {}
368
369  // This declaration is needed to make List.iterator() and
370  // ImmutableCollection.iterator() consistent.
371  @Override
372  public UnmodifiableIterator<E> iterator() {
373    return listIterator();
374  }
375
376  @Override
377  public UnmodifiableListIterator<E> listIterator() {
378    return listIterator(0);
379  }
380
381  @SuppressWarnings("unchecked")
382  @Override
383  public UnmodifiableListIterator<E> listIterator(int index) {
384    checkPositionIndex(index, size());
385    if (isEmpty()) {
386      return (UnmodifiableListIterator<E>) EMPTY_ITR;
387    } else {
388      return new Itr<E>(this, index);
389    }
390  }
391
392  /** A singleton implementation of iterator() for the empty ImmutableList. */
393  // TODO(b/345814817): Move this to RegularImmutableList?
394  @SuppressWarnings("ClassInitializationDeadlock")
395  private static final UnmodifiableListIterator<Object> EMPTY_ITR =
396      new Itr<Object>(RegularImmutableList.EMPTY, 0);
397
398  static class Itr<E> extends AbstractIndexedListIterator<E> {
399    private final ImmutableList<E> list;
400
401    Itr(ImmutableList<E> list, int index) {
402      super(list.size(), index);
403      this.list = list;
404    }
405
406    @Override
407    protected E get(int index) {
408      return list.get(index);
409    }
410  }
411
412  @Override
413  public int indexOf(@CheckForNull Object object) {
414    return (object == null) ? -1 : Lists.indexOfImpl(this, object);
415  }
416
417  @Override
418  public int lastIndexOf(@CheckForNull Object object) {
419    return (object == null) ? -1 : Lists.lastIndexOfImpl(this, object);
420  }
421
422  @Override
423  public boolean contains(@CheckForNull Object object) {
424    return indexOf(object) >= 0;
425  }
426
427  // constrain the return type to ImmutableList<E>
428
429  /**
430   * Returns an immutable list of the elements between the specified {@code fromIndex}, inclusive,
431   * and {@code toIndex}, exclusive. (If {@code fromIndex} and {@code toIndex} are equal, the empty
432   * immutable list is returned.)
433   *
434   * <p><b>Note:</b> in almost all circumstances, the returned {@link ImmutableList} retains a
435   * strong reference to {@code this}, which may prevent the original list from being garbage
436   * collected. If you want the original list to be eligible for garbage collection, you should
437   * create and use a copy of the sub list (e.g., {@code
438   * ImmutableList.copyOf(originalList.subList(...))}).
439   */
440  @Override
441  public ImmutableList<E> subList(int fromIndex, int toIndex) {
442    checkPositionIndexes(fromIndex, toIndex, size());
443    int length = toIndex - fromIndex;
444    if (length == size()) {
445      return this;
446    } else if (length == 0) {
447      return of();
448    } else {
449      return subListUnchecked(fromIndex, toIndex);
450    }
451  }
452
453  /**
454   * Called by the default implementation of {@link #subList} when {@code toIndex - fromIndex > 1},
455   * after index validation has already been performed.
456   */
457  ImmutableList<E> subListUnchecked(int fromIndex, int toIndex) {
458    return new SubList(fromIndex, toIndex - fromIndex);
459  }
460
461  class SubList extends ImmutableList<E> {
462    final transient int offset;
463    final transient int length;
464
465    SubList(int offset, int length) {
466      this.offset = offset;
467      this.length = length;
468    }
469
470    @Override
471    public int size() {
472      return length;
473    }
474
475    @Override
476    @CheckForNull
477    @Nullable
478    Object[] internalArray() {
479      return ImmutableList.this.internalArray();
480    }
481
482    @Override
483    int internalArrayStart() {
484      return ImmutableList.this.internalArrayStart() + offset;
485    }
486
487    @Override
488    int internalArrayEnd() {
489      return ImmutableList.this.internalArrayStart() + offset + 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   * Returns this list instance.
576   *
577   * @since 2.0
578   * @deprecated There is no reason to use this; it always returns {@code this}.
579   */
580  @InlineMe(replacement = "this")
581  @Deprecated
582  @Override
583  public final ImmutableList<E> asList() {
584    return this;
585  }
586
587  @Override
588  int copyIntoArray(@Nullable Object[] dst, int offset) {
589    // this loop is faster for RandomAccess instances, which ImmutableLists are
590    int size = size();
591    for (int i = 0; i < size; i++) {
592      dst[offset + i] = get(i);
593    }
594    return offset + size;
595  }
596
597  /**
598   * Returns a view of this immutable list in reverse order. For example, {@code ImmutableList.of(1,
599   * 2, 3).reverse()} is equivalent to {@code ImmutableList.of(3, 2, 1)}.
600   *
601   * @return a view of this immutable list in reverse order
602   * @since 7.0
603   */
604  public ImmutableList<E> reverse() {
605    return (size() <= 1) ? this : new ReverseImmutableList<E>(this);
606  }
607
608  private static class ReverseImmutableList<E> extends ImmutableList<E> {
609    private final transient ImmutableList<E> forwardList;
610
611    ReverseImmutableList(ImmutableList<E> backingList) {
612      this.forwardList = backingList;
613    }
614
615    private int reverseIndex(int index) {
616      return (size() - 1) - index;
617    }
618
619    private int reversePosition(int index) {
620      return size() - index;
621    }
622
623    @Override
624    public ImmutableList<E> reverse() {
625      return forwardList;
626    }
627
628    @Override
629    public boolean contains(@CheckForNull Object object) {
630      return forwardList.contains(object);
631    }
632
633    @Override
634    public int indexOf(@CheckForNull Object object) {
635      int index = forwardList.lastIndexOf(object);
636      return (index >= 0) ? reverseIndex(index) : -1;
637    }
638
639    @Override
640    public int lastIndexOf(@CheckForNull Object object) {
641      int index = forwardList.indexOf(object);
642      return (index >= 0) ? reverseIndex(index) : -1;
643    }
644
645    @Override
646    public ImmutableList<E> subList(int fromIndex, int toIndex) {
647      checkPositionIndexes(fromIndex, toIndex, size());
648      return forwardList.subList(reversePosition(toIndex), reversePosition(fromIndex)).reverse();
649    }
650
651    @Override
652    public E get(int index) {
653      checkElementIndex(index, size());
654      return forwardList.get(reverseIndex(index));
655    }
656
657    @Override
658    public int size() {
659      return forwardList.size();
660    }
661
662    @Override
663    boolean isPartialView() {
664      return forwardList.isPartialView();
665    }
666
667    // redeclare to help optimizers with b/310253115
668    @SuppressWarnings("RedundantOverride")
669    @Override
670    @J2ktIncompatible // serialization
671    @GwtIncompatible // serialization
672    Object writeReplace() {
673      return super.writeReplace();
674    }
675  }
676
677  @Override
678  public boolean equals(@CheckForNull Object obj) {
679    return Lists.equalsImpl(this, obj);
680  }
681
682  @Override
683  public int hashCode() {
684    int hashCode = 1;
685    int n = size();
686    for (int i = 0; i < n; i++) {
687      hashCode = 31 * hashCode + get(i).hashCode();
688
689      hashCode = ~~hashCode;
690      // needed to deal with GWT integer overflow
691    }
692    return hashCode;
693  }
694
695  /*
696   * Serializes ImmutableLists as their logical contents. This ensures that
697   * implementation types do not leak into the serialized representation.
698   */
699  @J2ktIncompatible // serialization
700  static class SerializedForm implements Serializable {
701    final Object[] elements;
702
703    SerializedForm(Object[] elements) {
704      this.elements = elements;
705    }
706
707    Object readResolve() {
708      return copyOf(elements);
709    }
710
711    private static final long serialVersionUID = 0;
712  }
713
714  @J2ktIncompatible // serialization
715  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
716    throw new InvalidObjectException("Use SerializedForm");
717  }
718
719  @Override
720  @J2ktIncompatible // serialization
721  @GwtIncompatible // serialization
722  Object writeReplace() {
723    return new SerializedForm(toArray());
724  }
725
726  /**
727   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
728   * Builder} constructor.
729   */
730  public static <E> Builder<E> builder() {
731    return new Builder<>();
732  }
733
734  /**
735   * Returns a new builder, expecting the specified number of elements to be added.
736   *
737   * <p>If {@code expectedSize} is exactly the number of elements added to the builder before {@link
738   * Builder#build} is called, the builder is likely to perform better than an unsized {@link
739   * #builder()} would have.
740   *
741   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
742   * but not exactly, the number of elements added to the builder.
743   *
744   * @since 23.1
745   */
746  public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
747    checkNonnegative(expectedSize, "expectedSize");
748    return new ImmutableList.Builder<>(expectedSize);
749  }
750
751  /**
752   * A builder for creating immutable list instances, especially {@code public static final} lists
753   * ("constant lists"). Example:
754   *
755   * <pre>{@code
756   * public static final ImmutableList<Color> GOOGLE_COLORS
757   *     = new ImmutableList.Builder<Color>()
758   *         .addAll(WEBSAFE_COLORS)
759   *         .add(new Color(0, 191, 255))
760   *         .build();
761   * }</pre>
762   *
763   * <p>Elements appear in the resulting list in the same order they were added to the builder.
764   *
765   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
766   * multiple lists in series. Each new list contains all the elements of the ones created before
767   * it.
768   *
769   * @since 2.0
770   */
771  public static final class Builder<E> extends ImmutableCollection.ArrayBasedBuilder<E> {
772    /**
773     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
774     * ImmutableList#builder}.
775     */
776    public Builder() {
777      this(DEFAULT_INITIAL_CAPACITY);
778    }
779
780    Builder(int capacity) {
781      super(capacity);
782    }
783
784    /**
785     * Adds {@code element} to the {@code ImmutableList}.
786     *
787     * @param element the element to add
788     * @return this {@code Builder} object
789     * @throws NullPointerException if {@code element} is null
790     */
791    @CanIgnoreReturnValue
792    @Override
793    public Builder<E> add(E element) {
794      super.add(element);
795      return this;
796    }
797
798    /**
799     * Adds each element of {@code elements} to the {@code ImmutableList}.
800     *
801     * @param elements the {@code Iterable} to add to the {@code ImmutableList}
802     * @return this {@code Builder} object
803     * @throws NullPointerException if {@code elements} is null or contains a null element
804     */
805    @CanIgnoreReturnValue
806    @Override
807    public Builder<E> add(E... elements) {
808      super.add(elements);
809      return this;
810    }
811
812    /**
813     * Adds each element of {@code elements} to the {@code ImmutableList}.
814     *
815     * @param elements the {@code Iterable} to add to the {@code ImmutableList}
816     * @return this {@code Builder} object
817     * @throws NullPointerException if {@code elements} is null or contains a null element
818     */
819    @CanIgnoreReturnValue
820    @Override
821    public Builder<E> addAll(Iterable<? extends E> elements) {
822      super.addAll(elements);
823      return this;
824    }
825
826    /**
827     * Adds each element of {@code elements} to the {@code ImmutableList}.
828     *
829     * @param elements the {@code Iterator} to add to the {@code ImmutableList}
830     * @return this {@code Builder} object
831     * @throws NullPointerException if {@code elements} is null or contains a null element
832     */
833    @CanIgnoreReturnValue
834    @Override
835    public Builder<E> addAll(Iterator<? extends E> elements) {
836      super.addAll(elements);
837      return this;
838    }
839
840    @CanIgnoreReturnValue
841    Builder<E> combine(Builder<E> other) {
842      addAll(other.contents, other.size);
843      return this;
844    }
845
846    /**
847     * Returns a newly-created {@code ImmutableList} based on the contents of the {@code Builder}.
848     */
849    @Override
850    public ImmutableList<E> build() {
851      forceCopy = true;
852      return asImmutableList(contents, size);
853    }
854
855    /**
856     * Returns a newly-created {@code ImmutableList} based on the contents of the {@code Builder},
857     * sorted according to the specified comparator.
858     */
859    @SuppressWarnings("unchecked")
860    ImmutableList<E> buildSorted(Comparator<? super E> comparator) {
861      // Currently only used by ImmutableListMultimap.Builder.orderValuesBy.
862      // In particular, this implies that the comparator can never get "removed," so this can't
863      // invalidate future builds.
864
865      forceCopy = true;
866      Arrays.sort((E[]) contents, 0, size, comparator);
867      return asImmutableList(contents, size);
868    }
869  }
870
871  private static final long serialVersionUID = 0xcafebabe;
872}