    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
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkNotNull;
    020
    021    import com.google.common.annotations.GwtCompatible;
    022    import com.google.common.base.Preconditions;
    023
    024    import java.io.InvalidObjectException;
    025    import java.io.ObjectInputStream;
    026    import java.io.Serializable;
    027    import java.util.ArrayList;
    028    import java.util.Collection;
    029    import java.util.Collections;
    030    import java.util.Iterator;
    031    import java.util.List;
    032    import java.util.RandomAccess;
    033
    034    import 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.0 (imported from Google Collections Library)
    055     */
    056    @GwtCompatible(serializable = true, emulated = true)
    057    @SuppressWarnings("serial") // we're overriding default serialization
    058    public 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.0 (source-compatible since 2.0)
    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.0 (changed from varargs in 3.0)
    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.0
    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.0
    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.0
    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.0 (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    }