View Javadoc
1   /*
2    * Copyright (C) 2007 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkArgument;
20  import static com.google.common.base.Preconditions.checkElementIndex;
21  import static com.google.common.base.Preconditions.checkNotNull;
22  import static com.google.common.base.Preconditions.checkPositionIndex;
23  import static com.google.common.base.Preconditions.checkPositionIndexes;
24  import static com.google.common.base.Preconditions.checkState;
25  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
26  import static com.google.common.collect.CollectPreconditions.checkRemove;
27  
28  import com.google.common.annotations.Beta;
29  import com.google.common.annotations.GwtCompatible;
30  import com.google.common.annotations.GwtIncompatible;
31  import com.google.common.annotations.VisibleForTesting;
32  import com.google.common.base.Function;
33  import com.google.common.base.Objects;
34  import com.google.common.math.IntMath;
35  import com.google.common.primitives.Ints;
36  import com.google.errorprone.annotations.CanIgnoreReturnValue;
37  import java.io.Serializable;
38  import java.math.RoundingMode;
39  import java.util.AbstractList;
40  import java.util.AbstractSequentialList;
41  import java.util.ArrayList;
42  import java.util.Arrays;
43  import java.util.Collection;
44  import java.util.Collections;
45  import java.util.Iterator;
46  import java.util.LinkedList;
47  import java.util.List;
48  import java.util.ListIterator;
49  import java.util.NoSuchElementException;
50  import java.util.RandomAccess;
51  import java.util.concurrent.CopyOnWriteArrayList;
52  import java.util.function.Predicate;
53  import javax.annotation.Nullable;
54  
55  /**
56   * Static utility methods pertaining to {@link List} instances. Also see this
57   * class's counterparts {@link Sets}, {@link Maps} and {@link Queues}.
58   *
59   * <p>See the Guava User Guide article on <a href=
60   * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#lists">
61   * {@code Lists}</a>.
62   *
63   * @author Kevin Bourrillion
64   * @author Mike Bostock
65   * @author Louis Wasserman
66   * @since 2.0
67   */
68  @GwtCompatible(emulated = true)
69  public final class Lists {
70    private Lists() {}
71  
72    // ArrayList
73  
74    /**
75     * Creates a <i>mutable</i>, empty {@code ArrayList} instance (for Java 6 and
76     * earlier).
77     *
78     * <p><b>Note:</b> if mutability is not required, use {@link
79     * ImmutableList#of()} instead.
80     *
81     * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and
82     * should be treated as deprecated. Instead, use the {@code ArrayList}
83     * {@linkplain ArrayList#ArrayList() constructor} directly, taking advantage
84     * of the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
85     */
86    @GwtCompatible(serializable = true)
87    public static <E> ArrayList<E> newArrayList() {
88      return new ArrayList<>();
89    }
90  
91    /**
92     * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
93     * elements.
94     *
95     * <p><b>Note:</b> essentially the only reason to use this method is when you
96     * will need to add or remove elements later. Otherwise, for non-null elements
97     * use {@link ImmutableList#of()} (for varargs) or {@link
98     * ImmutableList#copyOf(Object[])} (for an array) instead. If any elements
99     * 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 }