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