Source code

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