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