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