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