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