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