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