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