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