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