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