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