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