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