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