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