1/*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkElementIndex;
20import static com.google.common.base.Preconditions.checkNotNull;
21import static com.google.common.base.Preconditions.checkPositionIndexes;
22import static com.google.common.collect.ObjectArrays.arraysCopyOf;
23import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
24
25import com.google.common.annotations.GwtCompatible;
26
27import java.io.InvalidObjectException;
28import java.io.ObjectInputStream;
29import java.io.Serializable;
30import java.util.Collection;
31import java.util.Iterator;
32import java.util.List;
33import java.util.RandomAccess;
34
35import javax.annotation.Nullable;
36
37/**
38 * A high-performance, immutable, random-access {@code List} implementation.
39 * Does not permit null elements.
40 *
41 * <p>Unlike {@link Collections#unmodifiableList}, which is a <i>view</i> of a
42 * separate collection that can still change, an instance of {@code
43 * ImmutableList} contains its own private data and will <i>never</i> change.
44 * {@code ImmutableList} is convenient for {@code public static final} lists
45 * ("constant lists") and also lets you easily make a "defensive copy" of a list
46 * provided to your class by a caller.
47 *
48 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
49 * it has no public or protected constructors. Thus, instances of this type are
50 * guaranteed to be immutable.
51 *
52 * <p>See the Guava User Guide article on <a href=
53 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
54 * immutable collections</a>.
55 *
56 * @see ImmutableMap
57 * @see ImmutableSet
58 * @author Kevin Bourrillion
59 * @since 2.0 (imported from Google Collections Library)
60 */
61@GwtCompatible(serializable = true, emulated = true)
62@SuppressWarnings("serial") // we're overriding default serialization
63public abstract class ImmutableList<E> extends ImmutableCollection<E>
64    implements List<E>, RandomAccess {
65
66  private static final ImmutableList<Object> EMPTY =
67      new RegularImmutableList<Object>(ObjectArrays.EMPTY_ARRAY);
68
69  /**
70   * Returns the empty immutable list. This set behaves and performs comparably
71   * to {@link Collections#emptyList}, and is preferable mainly for consistency
72   * and maintainability of your code.
73   */
74  // Casting to any type is safe because the list will never hold any elements.
75  @SuppressWarnings("unchecked")
76  public static <E> ImmutableList<E> of() {
77    return (ImmutableList<E>) EMPTY;
78  }
79
80  /**
81   * Returns an immutable list containing a single element. This list behaves
82   * and performs comparably to {@link Collections#singleton}, but will not
83   * accept a null element. It is preferable mainly for consistency and
84   * maintainability of your code.
85   *
86   * @throws NullPointerException if {@code element} is null
87   */
88  public static <E> ImmutableList<E> of(E element) {
89    return new SingletonImmutableList<E>(element);
90  }
91
92  /**
93   * Returns an immutable list containing the given elements, in order.
94   *
95   * @throws NullPointerException if any element is null
96   */
97  public static <E> ImmutableList<E> of(E e1, E e2) {
98    return construct(e1, e2);
99  }
100
101  /**
102   * Returns an immutable list containing the given elements, in order.
103   *
104   * @throws NullPointerException if any element is null
105   */
106  public static <E> ImmutableList<E> of(E e1, E e2, E e3) {
107    return construct(e1, e2, e3);
108  }
109
110  /**
111   * Returns an immutable list containing the given elements, in order.
112   *
113   * @throws NullPointerException if any element is null
114   */
115  public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4) {
116    return construct(e1, e2, e3, e4);
117  }
118
119  /**
120   * Returns an immutable list containing the given elements, in order.
121   *
122   * @throws NullPointerException if any element is null
123   */
124  public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5) {
125    return construct(e1, e2, e3, e4, e5);
126  }
127
128  /**
129   * Returns an immutable list containing the given elements, in order.
130   *
131   * @throws NullPointerException if any element is null
132   */
133  public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
134    return construct(e1, e2, e3, e4, e5, e6);
135  }
136
137  /**
138   * Returns an immutable list containing the given elements, in order.
139   *
140   * @throws NullPointerException if any element is null
141   */
142  public static <E> ImmutableList<E> of(
143      E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
144    return construct(e1, e2, e3, e4, e5, e6, e7);
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(
153      E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
154    return construct(e1, e2, e3, e4, e5, e6, e7, e8);
155  }
156
157  /**
158   * Returns an immutable list containing the given elements, in order.
159   *
160   * @throws NullPointerException if any element is null
161   */
162  public static <E> ImmutableList<E> of(
163      E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
164    return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9);
165  }
166
167  /**
168   * Returns an immutable list containing the given elements, in order.
169   *
170   * @throws NullPointerException if any element is null
171   */
172  public static <E> ImmutableList<E> of(
173      E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
174    return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10);
175  }
176
177  /**
178   * Returns an immutable list containing the given elements, in order.
179   *
180   * @throws NullPointerException if any element is null
181   */
182  public static <E> ImmutableList<E> of(
183      E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11) {
184    return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11);
185  }
186
187  // These go up to eleven. After that, you just get the varargs form, and
188  // whatever warnings might come along with it. :(
189
190  /**
191   * Returns an immutable list containing the given elements, in order.
192   *
193   * @throws NullPointerException if any element is null
194   * @since 3.0 (source-compatible since 2.0)
195   */
196  public static <E> ImmutableList<E> of(
197      E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11, E e12,
198      E... others) {
199    Object[] array = new Object[12 + others.length];
200    array[0] = e1;
201    array[1] = e2;
202    array[2] = e3;
203    array[3] = e4;
204    array[4] = e5;
205    array[5] = e6;
206    array[6] = e7;
207    array[7] = e8;
208    array[8] = e9;
209    array[9] = e10;
210    array[10] = e11;
211    array[11] = e12;
212    System.arraycopy(others, 0, array, 12, others.length);
213    return construct(array);
214  }
215
216  /**
217   * Returns an immutable list containing the given elements, in order. If
218   * {@code elements} is a {@link Collection}, this method behaves exactly as
219   * {@link #copyOf(Collection)}; otherwise, it behaves exactly as {@code
220   * copyOf(elements.iterator()}.
221   *
222   * @throws NullPointerException if any of {@code elements} is null
223   */
224  public static <E> ImmutableList<E> copyOf(Iterable<? extends E> elements) {
225    checkNotNull(elements); // TODO(kevinb): is this here only for GWT?
226    return (elements instanceof Collection)
227      ? copyOf((Collection<? extends E>) elements)
228      : copyOf(elements.iterator());
229  }
230
231  /**
232   * Returns an immutable list containing the given elements, in order.
233   *
234   * <p>Despite the method name, this method attempts to avoid actually copying
235   * the data when it is safe to do so. The exact circumstances under which a
236   * copy will or will not be performed are undocumented and subject to change.
237   *
238   * <p>Note that if {@code list} is a {@code List<String>}, then {@code
239   * ImmutableList.copyOf(list)} returns an {@code ImmutableList<String>}
240   * containing each of the strings in {@code list}, while
241   * ImmutableList.of(list)} returns an {@code ImmutableList<List<String>>}
242   * containing one element (the given list itself).
243   *
244   * <p>This method is safe to use even when {@code elements} is a synchronized
245   * or concurrent collection that is currently being modified by another
246   * thread.
247   *
248   * @throws NullPointerException if any of {@code elements} is null
249   */
250  public static <E> ImmutableList<E> copyOf(Collection<? extends E> elements) {
251    if (elements instanceof ImmutableCollection) {
252      @SuppressWarnings("unchecked") // all supported methods are covariant
253      ImmutableList<E> list = ((ImmutableCollection<E>) elements).asList();
254      return list.isPartialView()
255          ? ImmutableList.<E>asImmutableList(list.toArray())
256          : 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 any of {@code elements} is null
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>()
276          .add(first)
277          .addAll(elements)
278          .build();
279    }
280  }
281
282  /**
283   * Returns an immutable list containing the given elements, in order.
284   *
285   * @throws NullPointerException if any of {@code elements} is null
286   * @since 3.0
287   */
288  public static <E> ImmutableList<E> copyOf(E[] elements) {
289    switch (elements.length) {
290      case 0:
291        return ImmutableList.of();
292      case 1:
293        return new SingletonImmutableList<E>(elements[0]);
294      default:
295        return new RegularImmutableList<E>(checkElementsNotNull(elements.clone()));
296    }
297  }
298
299  /**
300   * Views the array as an immutable list.  Checks for nulls; does not copy.
301   */
302  private static <E> ImmutableList<E> construct(Object... elements) {
303    return asImmutableList(checkElementsNotNull(elements));
304  }
305
306  /**
307   * Views the array as an immutable list.  Does not check for nulls; does not copy.
308   *
309   * <p>The array must be internally created.
310   */
311  static <E> ImmutableList<E> asImmutableList(Object[] elements) {
312    return asImmutableList(elements, elements.length);
313  }
314
315  /**
316   * Views the array as an immutable list. Copies if the specified range does not cover the complete
317   * array. Does not check for nulls.
318   */
319  static <E> ImmutableList<E> asImmutableList(Object[] elements, int length) {
320    switch (length) {
321      case 0:
322        return of();
323      case 1:
324        @SuppressWarnings("unchecked") // collection had only Es in it
325        ImmutableList<E> list = new SingletonImmutableList<E>((E) elements[0]);
326        return list;
327      default:
328        if (length < elements.length) {
329          elements = arraysCopyOf(elements, length);
330        }
331        return new RegularImmutableList<E>(elements);
332    }
333  }
334
335  ImmutableList() {}
336
337  // This declaration is needed to make List.iterator() and
338  // ImmutableCollection.iterator() consistent.
339  @Override public UnmodifiableIterator<E> iterator() {
340    return listIterator();
341  }
342
343  @Override public UnmodifiableListIterator<E> listIterator() {
344    return listIterator(0);
345  }
346
347  @Override public UnmodifiableListIterator<E> listIterator(int index) {
348    return new AbstractIndexedListIterator<E>(size(), index) {
349      @Override
350      protected E get(int index) {
351        return ImmutableList.this.get(index);
352      }
353    };
354  }
355
356  @Override
357  public int indexOf(@Nullable Object object) {
358    return (object == null) ? -1 : Lists.indexOfImpl(this, object);
359  }
360
361  @Override
362  public int lastIndexOf(@Nullable Object object) {
363    return (object == null) ? -1 : Lists.lastIndexOfImpl(this, object);
364  }
365
366  @Override
367  public boolean contains(@Nullable Object object) {
368    return indexOf(object) >= 0;
369  }
370
371  // constrain the return type to ImmutableList<E>
372
373  /**
374   * Returns an immutable list of the elements between the specified {@code
375   * fromIndex}, inclusive, and {@code toIndex}, exclusive. (If {@code
376   * fromIndex} and {@code toIndex} are equal, the empty immutable list is
377   * returned.)
378   */
379  @Override
380  public ImmutableList<E> subList(int fromIndex, int toIndex) {
381    checkPositionIndexes(fromIndex, toIndex, size());
382    int length = toIndex - fromIndex;
383    switch (length) {
384      case 0:
385        return of();
386      case 1:
387        return of(get(fromIndex));
388      default:
389        return subListUnchecked(fromIndex, toIndex);
390    }
391  }
392
393  /**
394   * Called by the default implementation of {@link #subList} when {@code
395   * toIndex - fromIndex > 1}, after index validation has already been
396   * performed.
397   */
398  ImmutableList<E> subListUnchecked(int fromIndex, int toIndex) {
399    return new SubList(fromIndex, toIndex - fromIndex);
400  }
401
402  class SubList extends ImmutableList<E> {
403    transient final int offset;
404    transient final int length;
405
406    SubList(int offset, int length) {
407      this.offset = offset;
408      this.length = length;
409    }
410
411    @Override
412    public int size() {
413      return length;
414    }
415
416    @Override
417    public E get(int index) {
418      checkElementIndex(index, length);
419      return ImmutableList.this.get(index + offset);
420    }
421
422    @Override
423    public ImmutableList<E> subList(int fromIndex, int toIndex) {
424      checkPositionIndexes(fromIndex, toIndex, length);
425      return ImmutableList.this.subList(fromIndex + offset, toIndex + offset);
426    }
427
428    @Override
429    boolean isPartialView() {
430      return true;
431    }
432  }
433
434  /**
435   * Guaranteed to throw an exception and leave the list unmodified.
436   *
437   * @throws UnsupportedOperationException always
438   * @deprecated Unsupported operation.
439   */
440  @Deprecated
441  @Override
442  public final boolean addAll(int index, Collection<? extends E> newElements) {
443    throw new UnsupportedOperationException();
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  @Deprecated
453  @Override
454  public final E set(int index, E element) {
455    throw new UnsupportedOperationException();
456  }
457
458  /**
459   * Guaranteed to throw an exception and leave the list unmodified.
460   *
461   * @throws UnsupportedOperationException always
462   * @deprecated Unsupported operation.
463   */
464  @Deprecated
465  @Override
466  public final void add(int index, E element) {
467    throw new UnsupportedOperationException();
468  }
469
470  /**
471   * Guaranteed to throw an exception and leave the list unmodified.
472   *
473   * @throws UnsupportedOperationException always
474   * @deprecated Unsupported operation.
475   */
476  @Deprecated
477  @Override
478  public final E remove(int index) {
479    throw new UnsupportedOperationException();
480  }
481
482  /**
483   * Returns this list instance.
484   *
485   * @since 2.0
486   */
487  @Override public final ImmutableList<E> asList() {
488    return this;
489  }
490
491  @Override
492  int copyIntoArray(Object[] dst, int offset) {
493    // this loop is faster for RandomAccess instances, which ImmutableLists are
494    int size = size();
495    for (int i = 0; i < size; i++) {
496      dst[offset + i] = get(i);
497    }
498    return offset + size;
499  }
500
501  /**
502   * Returns a view of this immutable list in reverse order. For example, {@code
503   * ImmutableList.of(1, 2, 3).reverse()} is equivalent to {@code
504   * ImmutableList.of(3, 2, 1)}.
505   *
506   * @return a view of this immutable list in reverse order
507   * @since 7.0
508   */
509  public ImmutableList<E> reverse() {
510    return new ReverseImmutableList<E>(this);
511  }
512
513  private static class ReverseImmutableList<E> extends ImmutableList<E> {
514    private final transient ImmutableList<E> forwardList;
515
516    ReverseImmutableList(ImmutableList<E> backingList) {
517      this.forwardList = backingList;
518    }
519
520    private int reverseIndex(int index) {
521      return (size() - 1) - index;
522    }
523
524    private int reversePosition(int index) {
525      return size() - index;
526    }
527
528    @Override public ImmutableList<E> reverse() {
529      return forwardList;
530    }
531
532    @Override public boolean contains(@Nullable Object object) {
533      return forwardList.contains(object);
534    }
535
536    @Override public int indexOf(@Nullable Object object) {
537      int index = forwardList.lastIndexOf(object);
538      return (index >= 0) ? reverseIndex(index) : -1;
539    }
540
541    @Override public int lastIndexOf(@Nullable Object object) {
542      int index = forwardList.indexOf(object);
543      return (index >= 0) ? reverseIndex(index) : -1;
544    }
545
546    @Override public ImmutableList<E> subList(int fromIndex, int toIndex) {
547      checkPositionIndexes(fromIndex, toIndex, size());
548      return forwardList.subList(
549          reversePosition(toIndex), reversePosition(fromIndex)).reverse();
550    }
551
552    @Override public E get(int index) {
553      checkElementIndex(index, size());
554      return forwardList.get(reverseIndex(index));
555    }
556
557    @Override public int size() {
558      return forwardList.size();
559    }
560
561    @Override boolean isPartialView() {
562      return forwardList.isPartialView();
563    }
564  }
565
566  @Override public boolean equals(@Nullable Object obj) {
567    return Lists.equalsImpl(this, obj);
568  }
569
570  @Override public int hashCode() {
571    int hashCode = 1;
572    int n = size();
573    for (int i = 0; i < n; i++) {
574      hashCode = 31 * hashCode + get(i).hashCode();
575
576      hashCode = ~~hashCode;
577      // needed to deal with GWT integer overflow
578    }
579    return hashCode;
580  }
581
582  /*
583   * Serializes ImmutableLists as their logical contents. This ensures that
584   * implementation types do not leak into the serialized representation.
585   */
586  static class SerializedForm implements Serializable {
587    final Object[] elements;
588    SerializedForm(Object[] elements) {
589      this.elements = elements;
590    }
591    Object readResolve() {
592      return copyOf(elements);
593    }
594    private static final long serialVersionUID = 0;
595  }
596
597  private void readObject(ObjectInputStream stream)
598      throws InvalidObjectException {
599    throw new InvalidObjectException("Use SerializedForm");
600  }
601
602  @Override Object writeReplace() {
603    return new SerializedForm(toArray());
604  }
605
606  /**
607   * Returns a new builder. The generated builder is equivalent to the builder
608   * created by the {@link Builder} constructor.
609   */
610  public static <E> Builder<E> builder() {
611    return new Builder<E>();
612  }
613
614  /**
615   * A builder for creating immutable list instances, especially {@code public
616   * static final} lists ("constant lists"). Example: <pre>   {@code
617   *
618   *   public static final ImmutableList<Color> GOOGLE_COLORS
619   *       = new ImmutableList.Builder<Color>()
620   *           .addAll(WEBSAFE_COLORS)
621   *           .add(new Color(0, 191, 255))
622   *           .build();}</pre>
623   *
624   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
625   * times to build multiple lists in series. Each new list contains all the
626   * elements of the ones created before it.
627   *
628   * @since 2.0 (imported from Google Collections Library)
629   */
630  public static final class Builder<E> extends ImmutableCollection.ArrayBasedBuilder<E> {
631    /**
632     * Creates a new builder. The returned builder is equivalent to the builder
633     * generated by {@link ImmutableList#builder}.
634     */
635    public Builder() {
636      this(DEFAULT_INITIAL_CAPACITY);
637    }
638
639    // TODO(user): consider exposing this
640    Builder(int capacity) {
641      super(capacity);
642    }
643
644    /**
645     * Adds {@code element} to the {@code ImmutableList}.
646     *
647     * @param element the element to add
648     * @return this {@code Builder} object
649     * @throws NullPointerException if {@code element} is null
650     */
651    @Override public Builder<E> add(E element) {
652      super.add(element);
653      return this;
654    }
655
656    /**
657     * Adds each element of {@code elements} to the {@code ImmutableList}.
658     *
659     * @param elements the {@code Iterable} to add to the {@code ImmutableList}
660     * @return this {@code Builder} object
661     * @throws NullPointerException if {@code elements} is null or contains a
662     *     null element
663     */
664    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
665      super.addAll(elements);
666      return this;
667    }
668
669    /**
670     * Adds each element of {@code elements} to the {@code ImmutableList}.
671     *
672     * @param elements the {@code Iterable} to add to the {@code ImmutableList}
673     * @return this {@code Builder} object
674     * @throws NullPointerException if {@code elements} is null or contains a
675     *     null element
676     */
677    @Override public Builder<E> add(E... elements) {
678      super.add(elements);
679      return this;
680    }
681
682    /**
683     * Adds each element of {@code elements} to the {@code ImmutableList}.
684     *
685     * @param elements the {@code Iterable} to add to the {@code ImmutableList}
686     * @return this {@code Builder} object
687     * @throws NullPointerException if {@code elements} is null or contains a
688     *     null element
689     */
690    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
691      super.addAll(elements);
692      return this;
693    }
694
695    /**
696     * Returns a newly-created {@code ImmutableList} based on the contents of
697     * the {@code Builder}.
698     */
699    @Override public ImmutableList<E> build() {
700      return asImmutableList(contents, size);
701    }
702  }
703}
704