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