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