001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkElementIndex;
021import static com.google.common.base.Preconditions.checkNotNull;
022import static com.google.common.base.Preconditions.checkPositionIndex;
023import static com.google.common.base.Preconditions.checkPositionIndexes;
024import static com.google.common.base.Preconditions.checkState;
025
026import com.google.common.annotations.Beta;
027import com.google.common.annotations.GwtCompatible;
028import com.google.common.annotations.GwtIncompatible;
029import com.google.common.annotations.VisibleForTesting;
030import com.google.common.base.Function;
031import com.google.common.base.Objects;
032import com.google.common.primitives.Ints;
033
034import java.io.Serializable;
035import java.util.AbstractList;
036import java.util.AbstractSequentialList;
037import java.util.ArrayList;
038import java.util.Arrays;
039import java.util.Collection;
040import java.util.Collections;
041import java.util.Iterator;
042import java.util.LinkedList;
043import java.util.List;
044import java.util.ListIterator;
045import java.util.NoSuchElementException;
046import java.util.RandomAccess;
047import java.util.concurrent.CopyOnWriteArrayList;
048
049import 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)
065public 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}