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