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