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