    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.checkArgument;
    020    import static com.google.common.base.Preconditions.checkElementIndex;
    021    import static com.google.common.base.Preconditions.checkNotNull;
    022    import static com.google.common.base.Preconditions.checkPositionIndex;
    023    import static com.google.common.base.Preconditions.checkPositionIndexes;
    024    import static com.google.common.base.Preconditions.checkState;
    025
    026    import com.google.common.annotations.Beta;
    027    import com.google.common.annotations.GwtCompatible;
    028    import com.google.common.annotations.VisibleForTesting;
    029    import com.google.common.base.Function;
    030    import com.google.common.base.Objects;
    031    import com.google.common.primitives.Ints;
    032
    033    import java.io.Serializable;
    034    import java.util.AbstractList;
    035    import java.util.AbstractSequentialList;
    036    import java.util.ArrayList;
    037    import java.util.Arrays;
    038    import java.util.Collection;
    039    import java.util.Collections;
    040    import java.util.Iterator;
    041    import java.util.LinkedList;
    042    import java.util.List;
    043    import java.util.ListIterator;
    044    import java.util.NoSuchElementException;
    045    import java.util.RandomAccess;
    046
    047    import javax.annotation.Nullable;
    048
    049    /**
    050     * Static utility methods pertaining to {@link List} instances. Also see this
    051     * class's counterparts {@link Sets} and {@link Maps}.
    052     *
    053     * @author Kevin Bourrillion
    054     * @author Mike Bostock
    055     * @author Louis Wasserman
    056     * @since 2.0 (imported from Google Collections Library)
    057     */
    058    @GwtCompatible
    059    public final class Lists {
    060      private Lists() {}
    061
    062      // ArrayList
    063
    064      /**
    065       * Creates a <i>mutable</i>, empty {@code ArrayList} instance.
    066       *
    067       * <p><b>Note:</b> if mutability is not required, use {@link
    068       * ImmutableList#of()} instead.
    069       *
    070       * @return a new, empty {@code ArrayList}
    071       */
    072      @GwtCompatible(serializable = true)
    073      public static <E> ArrayList<E> newArrayList() {
    074        return new ArrayList<E>();
    075      }
    076
    077      /**
    078       * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
    079       * elements.
    080       *
    081       * <p><b>Note:</b> if mutability is not required and the elements are
    082       * non-null, use an overload of {@link ImmutableList#of()} (for varargs) or
    083       * {@link ImmutableList#copyOf(Object[])} (for an array) instead.
    084       *
    085       * @param elements the elements that the list should contain, in order
    086       * @return a new {@code ArrayList} containing those elements
    087       */
    088      @GwtCompatible(serializable = true)
    089      public static <E> ArrayList<E> newArrayList(E... elements) {
    090        checkNotNull(elements); // for GWT
    091        // Avoid integer overflow when a large array is passed in
    092        int capacity = computeArrayListCapacity(elements.length);
    093        ArrayList<E> list = new ArrayList<E>(capacity);
    094        Collections.addAll(list, elements);
    095        return list;
    096      }
    097
    098      @VisibleForTesting static int computeArrayListCapacity(int arraySize) {
    099        checkArgument(arraySize >= 0);
    100
    101        // TODO(kevinb): Figure out the right behavior, and document it
    102        return Ints.saturatedCast(5L + arraySize + (arraySize / 10));
    103      }
    104
    105      /**
    106       * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
    107       * elements.
    108       *
    109       * <p><b>Note:</b> if mutability is not required and the elements are
    110       * non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
    111       *
    112       * @param elements the elements that the list should contain, in order
    113       * @return a new {@code ArrayList} containing those elements
    114       */
    115      @GwtCompatible(serializable = true)
    116      public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
    117        checkNotNull(elements); // for GWT
    118        // Let ArrayList's sizing logic work, if possible
    119        return (elements instanceof Collection)
    120            ? new ArrayList<E>(Collections2.cast(elements))
    121            : newArrayList(elements.iterator());
    122      }
    123
    124      /**
    125       * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
    126       * elements.
    127       *
    128       * <p><b>Note:</b> if mutability is not required and the elements are
    129       * non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
    130       *
    131       * @param elements the elements that the list should contain, in order
    132       * @return a new {@code ArrayList} containing those elements
    133       */
    134      @GwtCompatible(serializable = true)
    135      public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) {
    136        checkNotNull(elements); // for GWT
    137        ArrayList<E> list = newArrayList();
    138        while (elements.hasNext()) {
    139          list.add(elements.next());
    140        }
    141        return list;
    142      }
    143
    144      /**
    145       * Creates an {@code ArrayList} instance backed by an array of the
    146       * <i>exact</i> size specified; equivalent to
    147       * {@link ArrayList#ArrayList(int)}.
    148       *
    149       * <p><b>Note:</b> if you know the exact size your list will be, consider
    150       * using a fixed-size list ({@link Arrays#asList(Object[])}) or an {@link
    151       * ImmutableList} instead of a growable {@link ArrayList}.
    152       *
    153       * <p><b>Note:</b> If you have only an <i>estimate</i> of the eventual size of
    154       * the list, consider padding this estimate by a suitable amount, or simply
    155       * use {@link #newArrayListWithExpectedSize(int)} instead.
    156       *
    157       * @param initialArraySize the exact size of the initial backing array for
    158       *     the returned array list ({@code ArrayList} documentation calls this
    159       *     value the "capacity")
    160       * @return a new, empty {@code ArrayList} which is guaranteed not to resize
    161       *     itself unless its size reaches {@code initialArraySize + 1}
    162       * @throws IllegalArgumentException if {@code initialArraySize} is negative
    163       */
    164      @GwtCompatible(serializable = true)
    165      public static <E> ArrayList<E> newArrayListWithCapacity(
    166          int initialArraySize) {
    167        checkArgument(initialArraySize >= 0);  // for GWT.
    168        return new ArrayList<E>(initialArraySize);
    169      }
    170
    171      /**
    172       * Creates an {@code ArrayList} instance sized appropriately to hold an
    173       * <i>estimated</i> number of elements without resizing. A small amount of
    174       * padding is added in case the estimate is low.
    175       *
    176       * <p><b>Note:</b> If you know the <i>exact</i> number of elements the list
    177       * will hold, or prefer to calculate your own amount of padding, refer to
    178       * {@link #newArrayListWithCapacity(int)}.
    179       *
    180       * @param estimatedSize an estimate of the eventual {@link List#size()} of
    181       *     the new list
    182       * @return a new, empty {@code ArrayList}, sized appropriately to hold the
    183       *     estimated number of elements
    184       * @throws IllegalArgumentException if {@code estimatedSize} is negative
    185       */
    186      @GwtCompatible(serializable = true)
    187      public static <E> ArrayList<E> newArrayListWithExpectedSize(
    188          int estimatedSize) {
    189        return new ArrayList<E>(computeArrayListCapacity(estimatedSize));
    190      }
    191
    192      // LinkedList
    193
    194      /**
    195       * Creates an empty {@code LinkedList} instance.
    196       *
    197       * <p><b>Note:</b> if you need an immutable empty {@link List}, use
    198       * {@link Collections#emptyList} instead.
    199       *
    200       * @return a new, empty {@code LinkedList}
    201       */
    202      @GwtCompatible(serializable = true)
    203      public static <E> LinkedList<E> newLinkedList() {
    204        return new LinkedList<E>();
    205      }
    206
    207      /**
    208       * Creates a {@code LinkedList} instance containing the given elements.
    209       *
    210       * @param elements the elements that the list should contain, in order
    211       * @return a new {@code LinkedList} containing those elements
    212       */
    213      @GwtCompatible(serializable = true)
    214      public static <E> LinkedList<E> newLinkedList(
    215          Iterable<? extends E> elements) {
    216        LinkedList<E> list = newLinkedList();
    217        for (E element : elements) {
    218          list.add(element);
    219        }
    220        return list;
    221      }
    222
    223      /**
    224       * Returns an unmodifiable list containing the specified first element and
    225       * backed by the specified array of additional elements. Changes to the {@code
    226       * rest} array will be reflected in the returned list. Unlike {@link
    227       * Arrays#asList}, the returned list is unmodifiable.
    228       *
    229       * <p>This is useful when a varargs method needs to use a signature such as
    230       * {@code (Foo firstFoo, Foo... moreFoos)}, in order to avoid overload
    231       * ambiguity or to enforce a minimum argument count.
    232       *
    233       * <p>The returned list is serializable and implements {@link RandomAccess}.
    234       *
    235       * @param first the first element
    236       * @param rest an array of additional elements, possibly empty
    237       * @return an unmodifiable list containing the specified elements
    238       */
    239      public static <E> List<E> asList(@Nullable E first, E[] rest) {
    240        return new OnePlusArrayList<E>(first, rest);
    241      }
    242
    243      /** @see Lists#asList(Object, Object[]) */
    244      private static class OnePlusArrayList<E> extends AbstractList<E>
    245          implements Serializable, RandomAccess {
    246        final E first;
    247        final E[] rest;
    248
    249        OnePlusArrayList(@Nullable E first, E[] rest) {
    250          this.first = first;
    251          this.rest = checkNotNull(rest);
    252        }
    253        @Override public int size() {
    254          return rest.length + 1;
    255        }
    256        @Override public E get(int index) {
    257          // check explicitly so the IOOBE will have the right message
    258          checkElementIndex(index, size());
    259          return (index == 0) ? first : rest[index - 1];
    260        }
    261        private static final long serialVersionUID = 0;
    262      }
    263
    264      /**
    265       * Returns an unmodifiable list containing the specified first and second
    266       * element, and backed by the specified array of additional elements. Changes
    267       * to the {@code rest} array will be reflected in the returned list. Unlike
    268       * {@link Arrays#asList}, the returned list is unmodifiable.
    269       *
    270       * <p>This is useful when a varargs method needs to use a signature such as
    271       * {@code (Foo firstFoo, Foo secondFoo, Foo... moreFoos)}, in order to avoid
    272       * overload ambiguity or to enforce a minimum argument count.
    273       *
    274       * <p>The returned list is serializable and implements {@link RandomAccess}.
    275       *
    276       * @param first the first element
    277       * @param second the second element
    278       * @param rest an array of additional elements, possibly empty
    279       * @return an unmodifiable list containing the specified elements
    280       */
    281      public static <E> List<E> asList(
    282          @Nullable E first, @Nullable E second, E[] rest) {
    283        return new TwoPlusArrayList<E>(first, second, rest);
    284      }
    285
    286      /** @see Lists#asList(Object, Object, Object[]) */
    287      private static class TwoPlusArrayList<E> extends AbstractList<E>
    288          implements Serializable, RandomAccess {
    289        final E first;
    290        final E second;
    291        final E[] rest;
    292
    293        TwoPlusArrayList(@Nullable E first, @Nullable E second, E[] rest) {
    294          this.first = first;
    295          this.second = second;
    296          this.rest = checkNotNull(rest);
    297        }
    298        @Override public int size() {
    299          return rest.length + 2;
    300        }
    301        @Override public E get(int index) {
    302          switch (index) {
    303            case 0:
    304              return first;
    305            case 1:
    306              return second;
    307            default:
    308              // check explicitly so the IOOBE will have the right message
    309              checkElementIndex(index, size());
    310              return rest[index - 2];
    311          }
    312        }
    313        private static final long serialVersionUID = 0;
    314      }
    315
    316      /**
    317       * Returns a list that applies {@code function} to each element of {@code
    318       * fromList}. The returned list is a transformed view of {@code fromList};
    319       * changes to {@code fromList} will be reflected in the returned list and vice
    320       * versa.
    321       *
    322       * <p>Since functions are not reversible, the transform is one-way and new
    323       * items cannot be stored in the returned list. The {@code add},
    324       * {@code addAll} and {@code set} methods are unsupported in the returned
    325       * list.
    326       *
    327       * <p>The function is applied lazily, invoked when needed. This is necessary
    328       * for the returned list to be a view, but it means that the function will be
    329       * applied many times for bulk operations like {@link List#contains} and
    330       * {@link List#hashCode}. For this to perform well, {@code function} should be
    331       * fast. To avoid lazy evaluation when the returned list doesn't need to be a
    332       * view, copy the returned list into a new list of your choosing.
    333       *
    334       * <p>If {@code fromList} implements {@link RandomAccess}, so will the
    335       * returned list. The returned list always implements {@link Serializable},
    336       * but serialization will succeed only when {@code fromList} and
    337       * {@code function} are serializable. The returned list is threadsafe if the
    338       * supplied list and function are.
    339       *
    340       * <p>If only a {@code Collection} or {@code Iterable} input is available, use
    341       * {@link Collections2#transform} or {@link Iterables#transform}.
    342       */
    343      public static <F, T> List<T> transform(
    344          List<F> fromList, Function<? super F, ? extends T> function) {
    345        return (fromList instanceof RandomAccess)
    346            ? new TransformingRandomAccessList<F, T>(fromList, function)
    347            : new TransformingSequentialList<F, T>(fromList, function);
    348      }
    349
    350      /**
    351       * Implementation of a sequential transforming list.
    352       *
    353       * @see Lists#transform
    354       */
    355      private static class TransformingSequentialList<F, T>
    356          extends AbstractSequentialList<T> implements Serializable {
    357        final List<F> fromList;
    358        final Function<? super F, ? extends T> function;
    359
    360        TransformingSequentialList(
    361            List<F> fromList, Function<? super F, ? extends T> function) {
    362          this.fromList = checkNotNull(fromList);
    363          this.function = checkNotNull(function);
    364        }
    365        /**
    366         * The default implementation inherited is based on iteration and removal of
    367         * each element which can be overkill. That's why we forward this call
    368         * directly to the backing list.
    369         */
    370        @Override public void clear() {
    371          fromList.clear();
    372        }
    373        @Override public int size() {
    374          return fromList.size();
    375        }
    376        @Override public ListIterator<T> listIterator(final int index) {
    377          final ListIterator<F> delegate = fromList.listIterator(index);
    378          return new ListIterator<T>() {
    379            @Override
    380            public void add(T e) {
    381              throw new UnsupportedOperationException();
    382            }
    383
    384            @Override
    385            public boolean hasNext() {
    386              return delegate.hasNext();
    387            }
    388
    389            @Override
    390            public boolean hasPrevious() {
    391              return delegate.hasPrevious();
    392            }
    393
    394            @Override
    395            public T next() {
    396              return function.apply(delegate.next());
    397            }
    398
    399            @Override
    400            public int nextIndex() {
    401              return delegate.nextIndex();
    402            }
    403
    404            @Override
    405            public T previous() {
    406              return function.apply(delegate.previous());
    407            }
    408
    409            @Override
    410            public int previousIndex() {
    411              return delegate.previousIndex();
    412            }
    413
    414            @Override
    415            public void remove() {
    416              delegate.remove();
    417            }
    418
    419            @Override
    420            public void set(T e) {
    421              throw new UnsupportedOperationException("not supported");
    422            }
    423          };
    424        }
    425
    426        private static final long serialVersionUID = 0;
    427      }
    428
    429      /**
    430       * Implementation of a transforming random access list. We try to make as many
    431       * of these methods pass-through to the source list as possible so that the
    432       * performance characteristics of the source list and transformed list are
    433       * similar.
    434       *
    435       * @see Lists#transform
    436       */
    437      private static class TransformingRandomAccessList<F, T>
    438          extends AbstractList<T> implements RandomAccess, Serializable {
    439        final List<F> fromList;
    440        final Function<? super F, ? extends T> function;
    441
    442        TransformingRandomAccessList(
    443            List<F> fromList, Function<? super F, ? extends T> function) {
    444          this.fromList = checkNotNull(fromList);
    445          this.function = checkNotNull(function);
    446        }
    447        @Override public void clear() {
    448          fromList.clear();
    449        }
    450        @Override public T get(int index) {
    451          return function.apply(fromList.get(index));
    452        }
    453        @Override public boolean isEmpty() {
    454          return fromList.isEmpty();
    455        }
    456        @Override public T remove(int index) {
    457          return function.apply(fromList.remove(index));
    458        }
    459        @Override public int size() {
    460          return fromList.size();
    461        }
    462        private static final long serialVersionUID = 0;
    463      }
    464
    465      /**
    466       * Returns consecutive {@linkplain List#subList(int, int) sublists} of a list,
    467       * each of the same size (the final list may be smaller). For example,
    468       * partitioning a list containing {@code [a, b, c, d, e]} with a partition
    469       * size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing
    470       * two inner lists of three and two elements, all in the original order.
    471       *
    472       * <p>The outer list is unmodifiable, but reflects the latest state of the
    473       * source list. The inner lists are sublist views of the original list,
    474       * produced on demand using {@link List#subList(int, int)}, and are subject
    475       * to all the usual caveats about modification as explained in that API.
    476       *
    477       * @param list the list to return consecutive sublists of
    478       * @param size the desired size of each sublist (the last may be
    479       *     smaller)
    480       * @return a list of consecutive sublists
    481       * @throws IllegalArgumentException if {@code partitionSize} is nonpositive
    482       */
    483      public static <T> List<List<T>> partition(List<T> list, int size) {
    484        checkNotNull(list);
    485        checkArgument(size > 0);
    486        return (list instanceof RandomAccess)
    487            ? new RandomAccessPartition<T>(list, size)
    488            : new Partition<T>(list, size);
    489      }
    490
    491      private static class Partition<T> extends AbstractList<List<T>> {
    492        final List<T> list;
    493        final int size;
    494
    495        Partition(List<T> list, int size) {
    496          this.list = list;
    497          this.size = size;
    498        }
    499
    500        @Override public List<T> get(int index) {
    501          int listSize = size();
    502          checkElementIndex(index, listSize);
    503          int start = index * size;
    504          int end = Math.min(start + size, list.size());
    505          return list.subList(start, end);
    506        }
    507
    508        @Override public int size() {
    509          // TODO(user): refactor to common.math.IntMath.divide
    510          int result = list.size() / size;
    511          if (result * size != list.size()) {
    512            result++;
    513          }
    514          return result;
    515        }
    516
    517        @Override public boolean isEmpty() {
    518          return list.isEmpty();
    519        }
    520      }
    521
    522      private static class RandomAccessPartition<T> extends Partition<T>
    523          implements RandomAccess {
    524        RandomAccessPartition(List<T> list, int size) {
    525          super(list, size);
    526        }
    527      }
    528
    529      /**
    530       * Returns a view of the specified string as an immutable list of {@code
    531       * Character} values.
    532       *
    533       * @since 7.0
    534       */
    535      @Beta public static ImmutableList<Character> charactersOf(String string) {
    536        return new StringAsImmutableList(checkNotNull(string));
    537      }
    538
    539      @SuppressWarnings("serial") // serialized using ImmutableList serialization
    540      private static final class StringAsImmutableList
    541          extends ImmutableList<Character> {
    542
    543        private final String string;
    544
    545        StringAsImmutableList(String string) {
    546          this.string = string;
    547        }
    548
    549        @Override public boolean contains(@Nullable Object object) {
    550          return indexOf(object) >= 0;
    551        }
    552
    553        @Override public int indexOf(@Nullable Object object) {
    554          return (object instanceof Character)
    555              ? string.indexOf((Character) object) : -1;
    556        }
    557
    558        @Override public int lastIndexOf(@Nullable Object object) {
    559          return (object instanceof Character)
    560              ? string.lastIndexOf((Character) object) : -1;
    561        }
    562
    563        @Override public UnmodifiableListIterator<Character> listIterator(
    564            int index) {
    565          return new AbstractIndexedListIterator<Character>(size(), index) {
    566            @Override protected Character get(int index) {
    567              return string.charAt(index);
    568            }
    569          };
    570        }
    571
    572        @Override public ImmutableList<Character> subList(
    573            int fromIndex, int toIndex) {
    574          return charactersOf(string.substring(fromIndex, toIndex));
    575        }
    576
    577        @Override boolean isPartialView() {
    578          return false;
    579        }
    580
    581        @Override public Character get(int index) {
    582          return string.charAt(index);
    583        }
    584
    585        @Override public int size() {
    586          return string.length();
    587        }
    588
    589        @Override public boolean equals(@Nullable Object obj) {
    590          if (!(obj instanceof List)) {
    591            return false;
    592          }
    593          List<?> list = (List<?>) obj;
    594          int n = string.length();
    595          if (n != list.size()) {
    596            return false;
    597          }
    598          Iterator<?> iterator = list.iterator();
    599          for (int i = 0; i < n; i++) {
    600            Object elem = iterator.next();
    601            if (!(elem instanceof Character)
    602                || ((Character) elem).charValue() != string.charAt(i)) {
    603              return false;
    604            }
    605          }
    606          return true;
    607        }
    608
    609        int hash = 0;
    610
    611        @Override public int hashCode() {
    612          int h = hash;
    613          if (h == 0) {
    614            h = 1;
    615            for (int i = 0; i < string.length(); i++) {
    616              h = h * 31 + string.charAt(i);
    617            }
    618            hash = h;
    619          }
    620          return h;
    621        }
    622      }
    623
    624      /**
    625       * Returns a view of the specified {@code CharSequence} as a {@code
    626       * List<Character>}, viewing {@code sequence} as a sequence of Unicode code
    627       * units. The view does not support any modification operations, but reflects
    628       * any changes to the underlying character sequence.
    629       *
    630       * @param sequence the character sequence to view as a {@code List} of
    631       *        characters
    632       * @return an {@code List<Character>} view of the character sequence
    633       * @since 7.0
    634       */
    635      @Beta public static List<Character> charactersOf(CharSequence sequence) {
    636        return new CharSequenceAsList(checkNotNull(sequence));
    637      }
    638
    639      private static final class CharSequenceAsList
    640          extends AbstractList<Character> {
    641        private final CharSequence sequence;
    642
    643        CharSequenceAsList(CharSequence sequence) {
    644          this.sequence = sequence;
    645        }
    646
    647        @Override public Character get(int index) {
    648          return sequence.charAt(index);
    649        }
    650
    651        @Override public boolean contains(@Nullable Object o) {
    652          return indexOf(o) >= 0;
    653        }
    654
    655        @Override public int indexOf(@Nullable Object o) {
    656          if (o instanceof Character) {
    657            char c = (Character) o;
    658            for (int i = 0; i < sequence.length(); i++) {
    659              if (sequence.charAt(i) == c) {
    660                return i;
    661              }
    662            }
    663          }
    664          return -1;
    665        }
    666
    667        @Override public int lastIndexOf(@Nullable Object o) {
    668          if (o instanceof Character) {
    669            char c = ((Character) o).charValue();
    670            for (int i = sequence.length() - 1; i >= 0; i--) {
    671              if (sequence.charAt(i) == c) {
    672                return i;
    673              }
    674            }
    675          }
    676          return -1;
    677        }
    678
    679        @Override public int size() {
    680          return sequence.length();
    681        }
    682
    683        @Override public List<Character> subList(int fromIndex, int toIndex) {
    684          return charactersOf(sequence.subSequence(fromIndex, toIndex));
    685        }
    686
    687        @Override public int hashCode() {
    688          int hash = 1;
    689          for (int i = 0; i < sequence.length(); i++) {
    690            hash = hash * 31 + sequence.charAt(i);
    691          }
    692          return hash;
    693        }
    694
    695        @Override public boolean equals(@Nullable Object o) {
    696          if (!(o instanceof List)) {
    697            return false;
    698          }
    699          List<?> list = (List<?>) o;
    700          int n = sequence.length();
    701          if (n != list.size()) {
    702            return false;
    703          }
    704          Iterator<?> iterator = list.iterator();
    705          for (int i = 0; i < n; i++) {
    706            Object elem = iterator.next();
    707            if (!(elem instanceof Character)
    708                || ((Character) elem).charValue() != sequence.charAt(i)) {
    709              return false;
    710            }
    711          }
    712          return true;
    713        }
    714      }
    715
    716      /**
    717       * Returns a reversed view of the specified list. For example, {@code
    718       * Lists.reverse(Arrays.asList(1, 2, 3))} returns a list containing {@code 3,
    719       * 2, 1}. The returned list is backed by this list, so changes in the returned
    720       * list are reflected in this list, and vice-versa. The returned list supports
    721       * all of the optional list operations supported by this list.
    722       *
    723       * <p>The returned list is random-access if the specified list is random
    724       * access.
    725       *
    726       * @since 7.0
    727       */
    728      public static <T> List<T> reverse(List<T> list) {
    729        if (list instanceof ReverseList) {
    730          return ((ReverseList<T>) list).getForwardList();
    731        } else if (list instanceof RandomAccess) {
    732          return new RandomAccessReverseList<T>(list);
    733        } else {
    734          return new ReverseList<T>(list);
    735        }
    736      }
    737
    738      private static class ReverseList<T> extends AbstractList<T> {
    739        private final List<T> forwardList;
    740
    741        ReverseList(List<T> forwardList) {
    742          this.forwardList = checkNotNull(forwardList);
    743        }
    744
    745        List<T> getForwardList() {
    746          return forwardList;
    747        }
    748
    749        private int reverseIndex(int index) {
    750          int size = size();
    751          checkElementIndex(index, size);
    752          return (size - 1) - index;
    753        }
    754
    755        private int reversePosition(int index) {
    756          int size = size();
    757          checkPositionIndex(index, size);
    758          return size - index;
    759        }
    760
    761        @Override public void add(int index, @Nullable T element) {
    762          forwardList.add(reversePosition(index), element);
    763        }
    764
    765        @Override public void clear() {
    766          forwardList.clear();
    767        }
    768
    769        @Override public T remove(int index) {
    770          return forwardList.remove(reverseIndex(index));
    771        }
    772
    773        @Override protected void removeRange(int fromIndex, int toIndex) {
    774          subList(fromIndex, toIndex).clear();
    775        }
    776
    777        @Override public T set(int index, @Nullable T element) {
    778          return forwardList.set(reverseIndex(index), element);
    779        }
    780
    781        @Override public T get(int index) {
    782          return forwardList.get(reverseIndex(index));
    783        }
    784
    785        @Override public boolean isEmpty() {
    786          return forwardList.isEmpty();
    787        }
    788
    789        @Override public int size() {
    790          return forwardList.size();
    791        }
    792
    793        @Override public boolean contains(@Nullable Object o) {
    794          return forwardList.contains(o);
    795        }
    796
    797        @Override public boolean containsAll(Collection<?> c) {
    798          return forwardList.containsAll(c);
    799        }
    800
    801        @Override public List<T> subList(int fromIndex, int toIndex) {
    802          checkPositionIndexes(fromIndex, toIndex, size());
    803          return reverse(forwardList.subList(
    804              reversePosition(toIndex), reversePosition(fromIndex)));
    805        }
    806
    807        @Override public int indexOf(@Nullable Object o) {
    808          int index = forwardList.lastIndexOf(o);
    809          return (index >= 0) ? reverseIndex(index) : -1;
    810        }
    811
    812        @Override public int lastIndexOf(@Nullable Object o) {
    813          int index = forwardList.indexOf(o);
    814          return (index >= 0) ? reverseIndex(index) : -1;
    815        }
    816
    817        @Override public Iterator<T> iterator() {
    818          return listIterator();
    819        }
    820
    821        @Override public ListIterator<T> listIterator(int index) {
    822          int start = reversePosition(index);
    823          final ListIterator<T> forwardIterator = forwardList.listIterator(start);
    824          return new ListIterator<T>() {
    825
    826            boolean canRemove;
    827            boolean canSet;
    828
    829            @Override public void add(T e) {
    830              forwardIterator.add(e);
    831              forwardIterator.previous();
    832              canSet = canRemove = false;
    833            }
    834
    835            @Override public boolean hasNext() {
    836              return forwardIterator.hasPrevious();
    837            }
    838
    839            @Override public boolean hasPrevious() {
    840              return forwardIterator.hasNext();
    841            }
    842
    843            @Override public T next() {
    844              if (!hasNext()) {
    845                throw new NoSuchElementException();
    846              }
    847              canSet = canRemove = true;
    848              return forwardIterator.previous();
    849            }
    850
    851            @Override public int nextIndex() {
    852              return reversePosition(forwardIterator.nextIndex());
    853            }
    854
    855            @Override public T previous() {
    856              if (!hasPrevious()) {
    857                throw new NoSuchElementException();
    858              }
    859              canSet = canRemove = true;
    860              return forwardIterator.next();
    861            }
    862
    863            @Override public int previousIndex() {
    864              return nextIndex() - 1;
    865            }
    866
    867            @Override public void remove() {
    868              checkState(canRemove);
    869              forwardIterator.remove();
    870              canRemove = canSet = false;
    871            }
    872
    873            @Override public void set(T e) {
    874              checkState(canSet);
    875              forwardIterator.set(e);
    876            }
    877          };
    878        }
    879      }
    880
    881      private static class RandomAccessReverseList<T> extends ReverseList<T>
    882          implements RandomAccess {
    883        RandomAccessReverseList(List<T> forwardList) {
    884          super(forwardList);
    885        }
    886      }
    887
    888      /**
    889       * An implementation of {@link List#hashCode()}.
    890       */
    891      static int hashCodeImpl(List<?> list){
    892        int hashCode = 1;
    893        for (Object o : list) {
    894          hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
    895        }
    896        return hashCode;
    897      }
    898
    899      /**
    900       * An implementation of {@link List#equals(Object)}.
    901       */
    902      static boolean equalsImpl(List<?> list, @Nullable Object object) {
    903        if (object == checkNotNull(list)) {
    904          return true;
    905        }
    906        if (!(object instanceof List)) {
    907          return false;
    908        }
    909
    910        List<?> o = (List<?>) object;
    911
    912        return list.size() == o.size()
    913            && Iterators.elementsEqual(list.iterator(), o.iterator());
    914      }
    915
    916      /**
    917       * An implementation of {@link List#addAll(int, Collection)}.
    918       */
    919      static <E> boolean addAllImpl(
    920          List<E> list, int index, Iterable<? extends E> elements) {
    921        boolean changed = false;
    922        ListIterator<E> listIterator = list.listIterator(index);
    923        for (E e : elements) {
    924          listIterator.add(e);
    925          changed = true;
    926        }
    927        return changed;
    928      }
    929
    930      /**
    931       * An implementation of {@link List#indexOf(Object)}.
    932       */
    933      static int indexOfImpl(List<?> list, @Nullable Object element){
    934        ListIterator<?> listIterator = list.listIterator();
    935        while (listIterator.hasNext()) {
    936          if (Objects.equal(element, listIterator.next())) {
    937            return listIterator.previousIndex();
    938          }
    939        }
    940        return -1;
    941      }
    942
    943      /**
    944       * An implementation of {@link List#lastIndexOf(Object)}.
    945       */
    946      static int lastIndexOfImpl(List<?> list, @Nullable Object element){
    947        ListIterator<?> listIterator = list.listIterator(list.size());
    948        while (listIterator.hasPrevious()) {
    949          if (Objects.equal(element, listIterator.previous())) {
    950            return listIterator.nextIndex();
    951          }
    952        }
    953        return -1;
    954      }
    955
    956      /**
    957       * Returns an implementation of {@link List#listIterator(int)}.
    958       */
    959      static <E> ListIterator<E> listIteratorImpl(List<E> list, int index) {
    960        return new AbstractListWrapper<E>(list).listIterator(index);
    961      }
    962
    963      /**
    964       * An implementation of {@link List#subList(int, int)}.
    965       */
    966      static <E> List<E> subListImpl(
    967          final List<E> list, int fromIndex, int toIndex) {
    968        List<E> wrapper;
    969        if (list instanceof RandomAccess) {
    970          wrapper = new RandomAccessListWrapper<E>(list) {
    971            @Override public ListIterator<E> listIterator(int index) {
    972              return backingList.listIterator(index);
    973            }
    974
    975            private static final long serialVersionUID = 0;
    976          };
    977        } else {
    978          wrapper = new AbstractListWrapper<E>(list) {
    979            @Override public ListIterator<E> listIterator(int index) {
    980              return backingList.listIterator(index);
    981            }
    982
    983            private static final long serialVersionUID = 0;
    984          };
    985        }
    986        return wrapper.subList(fromIndex, toIndex);
    987      }
    988
    989      private static class AbstractListWrapper<E> extends AbstractList<E> {
    990        final List<E> backingList;
    991
    992        AbstractListWrapper(List<E> backingList) {
    993          this.backingList = checkNotNull(backingList);
    994        }
    995
    996        @Override public void add(int index, E element) {
    997          backingList.add(index, element);
    998        }
    999
    1000        @Override public boolean addAll(int index, Collection<? extends E> c) {
    1001          return backingList.addAll(index, c);
    1002        }
    1003
    1004        @Override public E get(int index) {
    1005          return backingList.get(index);
    1006        }
    1007
    1008        @Override public E remove(int index) {
    1009          return backingList.remove(index);
    1010        }
    1011
    1012        @Override public E set(int index, E element) {
    1013          return backingList.set(index, element);
    1014        }
    1015
    1016        @Override public boolean contains(Object o) {
    1017          return backingList.contains(o);
    1018        }
    1019
    1020        @Override public int size() {
    1021          return backingList.size();
    1022        }
    1023      }
    1024
    1025      private static class RandomAccessListWrapper<E>
    1026          extends AbstractListWrapper<E> implements RandomAccess {
    1027        RandomAccessListWrapper(List<E> backingList) {
    1028          super(backingList);
    1029        }
    1030      }
    1031    }