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