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