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