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.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkRemove; 022 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.annotations.GwtIncompatible; 025import com.google.common.base.Function; 026import com.google.common.base.Optional; 027import com.google.common.base.Predicate; 028import com.google.common.base.Predicates; 029import com.google.errorprone.annotations.CanIgnoreReturnValue; 030import java.util.Collection; 031import java.util.Comparator; 032import java.util.Iterator; 033import java.util.List; 034import java.util.NoSuchElementException; 035import java.util.Queue; 036import java.util.RandomAccess; 037import java.util.Set; 038import javax.annotation.CheckForNull; 039import org.checkerframework.checker.nullness.qual.NonNull; 040import org.checkerframework.checker.nullness.qual.Nullable; 041 042/** 043 * An assortment of mainly legacy static utility methods that operate on or return objects of type 044 * {@code Iterable}. Except as noted, each method has a corresponding {@link Iterator}-based method 045 * in the {@link Iterators} class. 046 * 047 * <p><b>Java 8+ users:</b> several common uses for this class are now more comprehensively 048 * addressed by the new {@link java.util.stream.Stream} library. Read the method documentation below 049 * for comparisons. This class is not being deprecated, but we gently encourage you to migrate to 050 * streams. 051 * 052 * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterables produced in this class 053 * are <i>lazy</i>, which means that their iterators only advance the backing iteration when 054 * absolutely necessary. 055 * 056 * <p>See the Guava User Guide article on <a href= 057 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#iterables">{@code 058 * Iterables}</a>. 059 * 060 * @author Kevin Bourrillion 061 * @author Jared Levy 062 * @since 2.0 063 */ 064@GwtCompatible(emulated = true) 065public final class Iterables { 066 private Iterables() {} 067 068 /** Returns an unmodifiable view of {@code iterable}. */ 069 public static <T extends @Nullable Object> Iterable<T> unmodifiableIterable( 070 final Iterable<? extends T> iterable) { 071 checkNotNull(iterable); 072 if (iterable instanceof UnmodifiableIterable || iterable instanceof ImmutableCollection) { 073 @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe 074 Iterable<T> result = (Iterable<T>) iterable; 075 return result; 076 } 077 return new UnmodifiableIterable<>(iterable); 078 } 079 080 /** 081 * Simply returns its argument. 082 * 083 * @deprecated no need to use this 084 * @since 10.0 085 */ 086 @Deprecated 087 public static <E> Iterable<E> unmodifiableIterable(ImmutableCollection<E> iterable) { 088 return checkNotNull(iterable); 089 } 090 091 private static final class UnmodifiableIterable<T extends @Nullable Object> 092 extends FluentIterable<T> { 093 private final Iterable<? extends T> iterable; 094 095 private UnmodifiableIterable(Iterable<? extends T> iterable) { 096 this.iterable = iterable; 097 } 098 099 @Override 100 public Iterator<T> iterator() { 101 return Iterators.unmodifiableIterator(iterable.iterator()); 102 } 103 104 @Override 105 public String toString() { 106 return iterable.toString(); 107 } 108 // no equals and hashCode; it would break the contract! 109 } 110 111 /** Returns the number of elements in {@code iterable}. */ 112 public static int size(Iterable<?> iterable) { 113 return (iterable instanceof Collection) 114 ? ((Collection<?>) iterable).size() 115 : Iterators.size(iterable.iterator()); 116 } 117 118 /** 119 * Returns {@code true} if {@code iterable} contains any element {@code o} for which {@code 120 * Objects.equals(o, element)} would return {@code true}. Otherwise returns {@code false}, even in 121 * cases where {@link Collection#contains} might throw {@link NullPointerException} or {@link 122 * ClassCastException}. 123 */ 124 // <? extends @Nullable Object> instead of <?> because of Kotlin b/189937072, discussed in Joiner. 125 public static boolean contains( 126 Iterable<? extends @Nullable Object> iterable, @CheckForNull Object element) { 127 if (iterable instanceof Collection) { 128 Collection<?> collection = (Collection<?>) iterable; 129 return Collections2.safeContains(collection, element); 130 } 131 return Iterators.contains(iterable.iterator(), element); 132 } 133 134 /** 135 * Removes, from an iterable, every element that belongs to the provided collection. 136 * 137 * <p>This method calls {@link Collection#removeAll} if {@code iterable} is a collection, and 138 * {@link Iterators#removeAll} otherwise. 139 * 140 * @param removeFrom the iterable to (potentially) remove elements from 141 * @param elementsToRemove the elements to remove 142 * @return {@code true} if any element was removed from {@code iterable} 143 */ 144 @CanIgnoreReturnValue 145 public static boolean removeAll(Iterable<?> removeFrom, Collection<?> elementsToRemove) { 146 return (removeFrom instanceof Collection) 147 ? ((Collection<?>) removeFrom).removeAll(checkNotNull(elementsToRemove)) 148 : Iterators.removeAll(removeFrom.iterator(), elementsToRemove); 149 } 150 151 /** 152 * Removes, from an iterable, every element that does not belong to the provided collection. 153 * 154 * <p>This method calls {@link Collection#retainAll} if {@code iterable} is a collection, and 155 * {@link Iterators#retainAll} otherwise. 156 * 157 * @param removeFrom the iterable to (potentially) remove elements from 158 * @param elementsToRetain the elements to retain 159 * @return {@code true} if any element was removed from {@code iterable} 160 */ 161 @CanIgnoreReturnValue 162 public static boolean retainAll(Iterable<?> removeFrom, Collection<?> elementsToRetain) { 163 return (removeFrom instanceof Collection) 164 ? ((Collection<?>) removeFrom).retainAll(checkNotNull(elementsToRetain)) 165 : Iterators.retainAll(removeFrom.iterator(), elementsToRetain); 166 } 167 168 /** 169 * Removes, from an iterable, every element that satisfies the provided predicate. 170 * 171 * <p>Removals may or may not happen immediately as each element is tested against the predicate. 172 * The behavior of this method is not specified if {@code predicate} is dependent on {@code 173 * removeFrom}. 174 * 175 * <p><b>Java 8+ users:</b> if {@code removeFrom} is a {@link Collection}, use {@code 176 * removeFrom.removeIf(predicate)} instead. 177 * 178 * @param removeFrom the iterable to (potentially) remove elements from 179 * @param predicate a predicate that determines whether an element should be removed 180 * @return {@code true} if any elements were removed from the iterable 181 * @throws UnsupportedOperationException if the iterable does not support {@code remove()}. 182 * @since 2.0 183 */ 184 @CanIgnoreReturnValue 185 public static <T extends @Nullable Object> boolean removeIf( 186 Iterable<T> removeFrom, Predicate<? super T> predicate) { 187 if (removeFrom instanceof RandomAccess && removeFrom instanceof List) { 188 return removeIfFromRandomAccessList((List<T>) removeFrom, checkNotNull(predicate)); 189 } 190 return Iterators.removeIf(removeFrom.iterator(), predicate); 191 } 192 193 private static <T extends @Nullable Object> boolean removeIfFromRandomAccessList( 194 List<T> list, Predicate<? super T> predicate) { 195 // Note: Not all random access lists support set(). Additionally, it's possible 196 // for a list to reject setting an element, such as when the list does not permit 197 // duplicate elements. For both of those cases, we need to fall back to a slower 198 // implementation. 199 int from = 0; 200 int to = 0; 201 202 for (; from < list.size(); from++) { 203 T element = list.get(from); 204 if (!predicate.apply(element)) { 205 if (from > to) { 206 try { 207 list.set(to, element); 208 } catch (UnsupportedOperationException e) { 209 slowRemoveIfForRemainingElements(list, predicate, to, from); 210 return true; 211 } catch (IllegalArgumentException e) { 212 slowRemoveIfForRemainingElements(list, predicate, to, from); 213 return true; 214 } 215 } 216 to++; 217 } 218 } 219 220 // Clear the tail of any remaining items 221 list.subList(to, list.size()).clear(); 222 return from != to; 223 } 224 225 private static <T extends @Nullable Object> void slowRemoveIfForRemainingElements( 226 List<T> list, Predicate<? super T> predicate, int to, int from) { 227 // Here we know that: 228 // * (to < from) and that both are valid indices. 229 // * Everything with (index < to) should be kept. 230 // * Everything with (to <= index < from) should be removed. 231 // * The element with (index == from) should be kept. 232 // * Everything with (index > from) has not been checked yet. 233 234 // Check from the end of the list backwards (minimize expected cost of 235 // moving elements when remove() is called). Stop before 'from' because 236 // we already know that should be kept. 237 for (int n = list.size() - 1; n > from; n--) { 238 if (predicate.apply(list.get(n))) { 239 list.remove(n); 240 } 241 } 242 // And now remove everything in the range [to, from) (going backwards). 243 for (int n = from - 1; n >= to; n--) { 244 list.remove(n); 245 } 246 } 247 248 /** Removes and returns the first matching element, or returns {@code null} if there is none. */ 249 @CheckForNull 250 static <T extends @Nullable Object> T removeFirstMatching( 251 Iterable<T> removeFrom, Predicate<? super T> predicate) { 252 checkNotNull(predicate); 253 Iterator<T> iterator = removeFrom.iterator(); 254 while (iterator.hasNext()) { 255 T next = iterator.next(); 256 if (predicate.apply(next)) { 257 iterator.remove(); 258 return next; 259 } 260 } 261 return null; 262 } 263 264 /** 265 * Determines whether two iterables contain equal elements in the same order. More specifically, 266 * this method returns {@code true} if {@code iterable1} and {@code iterable2} contain the same 267 * number of elements and every element of {@code iterable1} is equal to the corresponding element 268 * of {@code iterable2}. 269 */ 270 public static boolean elementsEqual(Iterable<?> iterable1, Iterable<?> iterable2) { 271 if (iterable1 instanceof Collection && iterable2 instanceof Collection) { 272 Collection<?> collection1 = (Collection<?>) iterable1; 273 Collection<?> collection2 = (Collection<?>) iterable2; 274 if (collection1.size() != collection2.size()) { 275 return false; 276 } 277 } 278 return Iterators.elementsEqual(iterable1.iterator(), iterable2.iterator()); 279 } 280 281 /** 282 * Returns a string representation of {@code iterable}, with the format {@code [e1, e2, ..., en]} 283 * (that is, identical to {@link java.util.Arrays Arrays}{@code 284 * .toString(Iterables.toArray(iterable))}). Note that for <i>most</i> implementations of {@link 285 * Collection}, {@code collection.toString()} also gives the same result, but that behavior is not 286 * generally guaranteed. 287 */ 288 public static String toString(Iterable<?> iterable) { 289 return Iterators.toString(iterable.iterator()); 290 } 291 292 /** 293 * Returns the single element contained in {@code iterable}. 294 * 295 * <p><b>Java 8+ users:</b> the {@code Stream} equivalent to this method is {@code 296 * stream.collect(MoreCollectors.onlyElement())}. 297 * 298 * @throws NoSuchElementException if the iterable is empty 299 * @throws IllegalArgumentException if the iterable contains multiple elements 300 */ 301 @ParametricNullness 302 public static <T extends @Nullable Object> T getOnlyElement(Iterable<T> iterable) { 303 return Iterators.getOnlyElement(iterable.iterator()); 304 } 305 306 /** 307 * Returns the single element contained in {@code iterable}, or {@code defaultValue} if the 308 * iterable is empty. 309 * 310 * <p><b>Java 8+ users:</b> the {@code Stream} equivalent to this method is {@code 311 * stream.collect(MoreCollectors.toOptional()).orElse(defaultValue)}. 312 * 313 * @throws IllegalArgumentException if the iterator contains multiple elements 314 */ 315 @ParametricNullness 316 public static <T extends @Nullable Object> T getOnlyElement( 317 Iterable<? extends T> iterable, @ParametricNullness T defaultValue) { 318 return Iterators.getOnlyElement(iterable.iterator(), defaultValue); 319 } 320 321 /** 322 * Copies an iterable's elements into an array. 323 * 324 * @param iterable the iterable to copy 325 * @param type the type of the elements 326 * @return a newly-allocated array into which all the elements of the iterable have been copied 327 */ 328 @GwtIncompatible // Array.newInstance(Class, int) 329 public static <T extends @Nullable Object> T[] toArray( 330 Iterable<? extends T> iterable, Class<@NonNull T> type) { 331 return toArray(iterable, ObjectArrays.newArray(type, 0)); 332 } 333 334 static <T extends @Nullable Object> T[] toArray(Iterable<? extends T> iterable, T[] array) { 335 Collection<? extends T> collection = castOrCopyToCollection(iterable); 336 return collection.toArray(array); 337 } 338 339 /** 340 * Copies an iterable's elements into an array. 341 * 342 * @param iterable the iterable to copy 343 * @return a newly-allocated array into which all the elements of the iterable have been copied 344 */ 345 static @Nullable Object[] toArray(Iterable<?> iterable) { 346 return castOrCopyToCollection(iterable).toArray(); 347 } 348 349 /** 350 * Converts an iterable into a collection. If the iterable is already a collection, it is 351 * returned. Otherwise, an {@link java.util.ArrayList} is created with the contents of the 352 * iterable in the same iteration order. 353 */ 354 private static <E extends @Nullable Object> Collection<E> castOrCopyToCollection( 355 Iterable<E> iterable) { 356 return (iterable instanceof Collection) 357 ? (Collection<E>) iterable 358 : Lists.newArrayList(iterable.iterator()); 359 } 360 361 /** 362 * Adds all elements in {@code iterable} to {@code collection}. 363 * 364 * @return {@code true} if {@code collection} was modified as a result of this operation. 365 */ 366 @CanIgnoreReturnValue 367 public static <T extends @Nullable Object> boolean addAll( 368 Collection<T> addTo, Iterable<? extends T> elementsToAdd) { 369 if (elementsToAdd instanceof Collection) { 370 Collection<? extends T> c = (Collection<? extends T>) elementsToAdd; 371 return addTo.addAll(c); 372 } 373 return Iterators.addAll(addTo, checkNotNull(elementsToAdd).iterator()); 374 } 375 376 /** 377 * Returns the number of elements in the specified iterable that equal the specified object. This 378 * implementation avoids a full iteration when the iterable is a {@link Multiset} or {@link Set}. 379 * 380 * <p><b>Java 8+ users:</b> In most cases, the {@code Stream} equivalent of this method is {@code 381 * stream.filter(element::equals).count()}. If {@code element} might be null, use {@code 382 * stream.filter(Predicate.isEqual(element)).count()} instead. 383 * 384 * @see java.util.Collections#frequency(Collection, Object) Collections.frequency(Collection, 385 * Object) 386 */ 387 public static int frequency(Iterable<?> iterable, @CheckForNull Object element) { 388 if ((iterable instanceof Multiset)) { 389 return ((Multiset<?>) iterable).count(element); 390 } else if ((iterable instanceof Set)) { 391 return ((Set<?>) iterable).contains(element) ? 1 : 0; 392 } 393 return Iterators.frequency(iterable.iterator(), element); 394 } 395 396 /** 397 * Returns an iterable whose iterators cycle indefinitely over the elements of {@code iterable}. 398 * 399 * <p>That iterator supports {@code remove()} if {@code iterable.iterator()} does. After {@code 400 * remove()} is called, subsequent cycles omit the removed element, which is no longer in {@code 401 * iterable}. The iterator's {@code hasNext()} method returns {@code true} until {@code iterable} 402 * is empty. 403 * 404 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an infinite loop. You 405 * should use an explicit {@code break} or be certain that you will eventually remove all the 406 * elements. 407 * 408 * <p>To cycle over the iterable {@code n} times, use the following: {@code 409 * Iterables.concat(Collections.nCopies(n, iterable))} 410 * 411 * <p><b>Java 8+ users:</b> The {@code Stream} equivalent of this method is {@code 412 * Stream.generate(() -> iterable).flatMap(Streams::stream)}. 413 */ 414 public static <T extends @Nullable Object> Iterable<T> cycle(final Iterable<T> iterable) { 415 checkNotNull(iterable); 416 return new FluentIterable<T>() { 417 @Override 418 public Iterator<T> iterator() { 419 return Iterators.cycle(iterable); 420 } 421 422 @Override 423 public String toString() { 424 return iterable.toString() + " (cycled)"; 425 } 426 }; 427 } 428 429 /** 430 * Returns an iterable whose iterators cycle indefinitely over the provided elements. 431 * 432 * <p>After {@code remove} is invoked on a generated iterator, the removed element will no longer 433 * appear in either that iterator or any other iterator created from the same source iterable. 434 * That is, this method behaves exactly as {@code Iterables.cycle(Lists.newArrayList(elements))}. 435 * The iterator's {@code hasNext} method returns {@code true} until all of the original elements 436 * have been removed. 437 * 438 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an infinite loop. You 439 * should use an explicit {@code break} or be certain that you will eventually remove all the 440 * elements. 441 * 442 * <p>To cycle over the elements {@code n} times, use the following: {@code 443 * Iterables.concat(Collections.nCopies(n, Arrays.asList(elements)))} 444 * 445 * <p><b>Java 8+ users:</b> If passing a single element {@code e}, the {@code Stream} equivalent 446 * of this method is {@code Stream.generate(() -> e)}. Otherwise, put the elements in a collection 447 * and use {@code Stream.generate(() -> collection).flatMap(Collection::stream)}. 448 */ 449 @SafeVarargs 450 public static <T extends @Nullable Object> Iterable<T> cycle(T... elements) { 451 return cycle(Lists.newArrayList(elements)); 452 } 453 454 /** 455 * Combines two iterables into a single iterable. The returned iterable has an iterator that 456 * traverses the elements in {@code a}, followed by the elements in {@code b}. The source 457 * iterators are not polled until necessary. 458 * 459 * <p>The returned iterable's iterator supports {@code remove()} when the corresponding input 460 * iterator supports it. 461 * 462 * <p><b>Java 8+ users:</b> The {@code Stream} equivalent of this method is {@code 463 * Stream.concat(a, b)}. 464 */ 465 public static <T extends @Nullable Object> Iterable<T> concat( 466 Iterable<? extends T> a, Iterable<? extends T> b) { 467 return FluentIterable.concat(a, b); 468 } 469 470 /** 471 * Combines three iterables into a single iterable. The returned iterable has an iterator that 472 * traverses the elements in {@code a}, followed by the elements in {@code b}, followed by the 473 * elements in {@code c}. The source iterators are not polled until necessary. 474 * 475 * <p>The returned iterable's iterator supports {@code remove()} when the corresponding input 476 * iterator supports it. 477 * 478 * <p><b>Java 8+ users:</b> The {@code Stream} equivalent of this method is {@code 479 * Streams.concat(a, b, c)}. 480 */ 481 public static <T extends @Nullable Object> Iterable<T> concat( 482 Iterable<? extends T> a, Iterable<? extends T> b, Iterable<? extends T> c) { 483 return FluentIterable.concat(a, b, c); 484 } 485 486 /** 487 * Combines four iterables into a single iterable. The returned iterable has an iterator that 488 * traverses the elements in {@code a}, followed by the elements in {@code b}, followed by the 489 * elements in {@code c}, followed by the elements in {@code d}. The source iterators are not 490 * polled until necessary. 491 * 492 * <p>The returned iterable's iterator supports {@code remove()} when the corresponding input 493 * iterator supports it. 494 * 495 * <p><b>Java 8+ users:</b> The {@code Stream} equivalent of this method is {@code 496 * Streams.concat(a, b, c, d)}. 497 */ 498 public static <T extends @Nullable Object> Iterable<T> concat( 499 Iterable<? extends T> a, 500 Iterable<? extends T> b, 501 Iterable<? extends T> c, 502 Iterable<? extends T> d) { 503 return FluentIterable.concat(a, b, c, d); 504 } 505 506 /** 507 * Combines multiple iterables into a single iterable. The returned iterable has an iterator that 508 * traverses the elements of each iterable in {@code inputs}. The input iterators are not polled 509 * until necessary. 510 * 511 * <p>The returned iterable's iterator supports {@code remove()} when the corresponding input 512 * iterator supports it. 513 * 514 * <p><b>Java 8+ users:</b> The {@code Stream} equivalent of this method is {@code 515 * Streams.concat(...)}. 516 * 517 * @throws NullPointerException if any of the provided iterables is null 518 */ 519 @SafeVarargs 520 public static <T extends @Nullable Object> Iterable<T> concat(Iterable<? extends T>... inputs) { 521 return FluentIterable.concat(inputs); 522 } 523 524 /** 525 * Combines multiple iterables into a single iterable. The returned iterable has an iterator that 526 * traverses the elements of each iterable in {@code inputs}. The input iterators are not polled 527 * until necessary. 528 * 529 * <p>The returned iterable's iterator supports {@code remove()} when the corresponding input 530 * iterator supports it. The methods of the returned iterable may throw {@code 531 * NullPointerException} if any of the input iterators is null. 532 * 533 * <p><b>Java 8+ users:</b> The {@code Stream} equivalent of this method is {@code 534 * streamOfStreams.flatMap(s -> s)}. 535 */ 536 public static <T extends @Nullable Object> Iterable<T> concat( 537 Iterable<? extends Iterable<? extends T>> inputs) { 538 return FluentIterable.concat(inputs); 539 } 540 541 /** 542 * Divides an iterable into unmodifiable sublists of the given size (the final iterable may be 543 * smaller). For example, partitioning an iterable containing {@code [a, b, c, d, e]} with a 544 * partition size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer iterable containing two 545 * inner lists of three and two elements, all in the original order. 546 * 547 * <p>Iterators returned by the returned iterable do not support the {@link Iterator#remove()} 548 * method. The returned lists implement {@link RandomAccess}, whether or not the input list does. 549 * 550 * <p><b>Note:</b> The current implementation eagerly allocates storage for {@code size} elements. 551 * As a consequence, passing values like {@code Integer.MAX_VALUE} can lead to {@link 552 * OutOfMemoryError}. 553 * 554 * <p><b>Note:</b> if {@code iterable} is a {@link List}, use {@link Lists#partition(List, int)} 555 * instead. 556 * 557 * @param iterable the iterable to return a partitioned view of 558 * @param size the desired size of each partition (the last may be smaller) 559 * @return an iterable of unmodifiable lists containing the elements of {@code iterable} divided 560 * into partitions 561 * @throws IllegalArgumentException if {@code size} is nonpositive 562 */ 563 public static <T extends @Nullable Object> Iterable<List<T>> partition( 564 final Iterable<T> iterable, final int size) { 565 checkNotNull(iterable); 566 checkArgument(size > 0); 567 return new FluentIterable<List<T>>() { 568 @Override 569 public Iterator<List<T>> iterator() { 570 return Iterators.partition(iterable.iterator(), size); 571 } 572 }; 573 } 574 575 /** 576 * Divides an iterable into unmodifiable sublists of the given size, padding the final iterable 577 * with null values if necessary. For example, partitioning an iterable containing {@code [a, b, 578 * c, d, e]} with a partition size of 3 yields {@code [[a, b, c], [d, e, null]]} -- an outer 579 * iterable containing two inner lists of three elements each, all in the original order. 580 * 581 * <p>Iterators returned by the returned iterable do not support the {@link Iterator#remove()} 582 * method. 583 * 584 * @param iterable the iterable to return a partitioned view of 585 * @param size the desired size of each partition 586 * @return an iterable of unmodifiable lists containing the elements of {@code iterable} divided 587 * into partitions (the final iterable may have trailing null elements) 588 * @throws IllegalArgumentException if {@code size} is nonpositive 589 */ 590 public static <T extends @Nullable Object> Iterable<List<@Nullable T>> paddedPartition( 591 final Iterable<T> iterable, final int size) { 592 checkNotNull(iterable); 593 checkArgument(size > 0); 594 return new FluentIterable<List<@Nullable T>>() { 595 @Override 596 public Iterator<List<@Nullable T>> iterator() { 597 return Iterators.paddedPartition(iterable.iterator(), size); 598 } 599 }; 600 } 601 602 /** 603 * Returns a view of {@code unfiltered} containing all elements that satisfy the input predicate 604 * {@code retainIfTrue}. The returned iterable's iterator does not support {@code remove()}. 605 * 606 * <p><b>{@code Stream} equivalent:</b> {@link Stream#filter}. 607 */ 608 public static <T extends @Nullable Object> Iterable<T> filter( 609 final Iterable<T> unfiltered, final Predicate<? super T> retainIfTrue) { 610 checkNotNull(unfiltered); 611 checkNotNull(retainIfTrue); 612 return new FluentIterable<T>() { 613 @Override 614 public Iterator<T> iterator() { 615 return Iterators.filter(unfiltered.iterator(), retainIfTrue); 616 } 617 }; 618 } 619 620 /** 621 * Returns a view of {@code unfiltered} containing all elements that are of the type {@code 622 * desiredType}. The returned iterable's iterator does not support {@code remove()}. 623 * 624 * <p><b>{@code Stream} equivalent:</b> {@code stream.filter(type::isInstance).map(type::cast)}. 625 * This does perform a little more work than necessary, so another option is to insert an 626 * unchecked cast at some later point: 627 * 628 * <pre> 629 * {@code @SuppressWarnings("unchecked") // safe because of ::isInstance check 630 * ImmutableList<NewType> result = 631 * (ImmutableList) stream.filter(NewType.class::isInstance).collect(toImmutableList());} 632 * </pre> 633 */ 634 @SuppressWarnings("unchecked") 635 @GwtIncompatible // Class.isInstance 636 public static <T> Iterable<T> filter(final Iterable<?> unfiltered, final Class<T> desiredType) { 637 checkNotNull(unfiltered); 638 checkNotNull(desiredType); 639 return (Iterable<T>) filter(unfiltered, Predicates.instanceOf(desiredType)); 640 } 641 642 /** 643 * Returns {@code true} if any element in {@code iterable} satisfies the predicate. 644 * 645 * <p><b>{@code Stream} equivalent:</b> {@link Stream#anyMatch}. 646 */ 647 public static <T extends @Nullable Object> boolean any( 648 Iterable<T> iterable, Predicate<? super T> predicate) { 649 return Iterators.any(iterable.iterator(), predicate); 650 } 651 652 /** 653 * Returns {@code true} if every element in {@code iterable} satisfies the predicate. If {@code 654 * iterable} is empty, {@code true} is returned. 655 * 656 * <p><b>{@code Stream} equivalent:</b> {@link Stream#allMatch}. 657 */ 658 public static <T extends @Nullable Object> boolean all( 659 Iterable<T> iterable, Predicate<? super T> predicate) { 660 return Iterators.all(iterable.iterator(), predicate); 661 } 662 663 /** 664 * Returns the first element in {@code iterable} that satisfies the given predicate; use this 665 * method only when such an element is known to exist. If it is possible that <i>no</i> element 666 * will match, use {@link #tryFind} or {@link #find(Iterable, Predicate, Object)} instead. 667 * 668 * <p><b>{@code Stream} equivalent:</b> {@code stream.filter(predicate).findFirst().get()} 669 * 670 * @throws NoSuchElementException if no element in {@code iterable} matches the given predicate 671 */ 672 @ParametricNullness 673 public static <T extends @Nullable Object> T find( 674 Iterable<T> iterable, Predicate<? super T> predicate) { 675 return Iterators.find(iterable.iterator(), predicate); 676 } 677 678 /** 679 * Returns the first element in {@code iterable} that satisfies the given predicate, or {@code 680 * defaultValue} if none found. Note that this can usually be handled more naturally using {@code 681 * tryFind(iterable, predicate).or(defaultValue)}. 682 * 683 * <p><b>{@code Stream} equivalent:</b> {@code 684 * stream.filter(predicate).findFirst().orElse(defaultValue)} 685 * 686 * @since 7.0 687 */ 688 // The signature we really want here is... 689 // 690 // <T extends @Nullable Object> @JointlyNullable T find( 691 // Iterable<? extends T> iterable, 692 // Predicate<? super T> predicate, 693 // @JointlyNullable T defaultValue); 694 // 695 // ...where "@JointlyNullable" is similar to @PolyNull but slightly different: 696 // 697 // - @PolyNull means "@Nullable or @Nonnull" 698 // (That would be unsound for an input Iterable<@Nullable Foo>. So, if we wanted to use 699 // @PolyNull, we would have to restrict this method to non-null <T>. But it has users who pass 700 // iterables with null elements.) 701 // 702 // - @JointlyNullable means "@Nullable or no annotation" 703 @CheckForNull 704 public static <T extends @Nullable Object> T find( 705 Iterable<? extends T> iterable, 706 Predicate<? super T> predicate, 707 @CheckForNull T defaultValue) { 708 return Iterators.<T>find(iterable.iterator(), predicate, defaultValue); 709 } 710 711 /** 712 * Returns an {@link Optional} containing the first element in {@code iterable} that satisfies the 713 * given predicate, if such an element exists. 714 * 715 * <p><b>Warning:</b> avoid using a {@code predicate} that matches {@code null}. If {@code null} 716 * is matched in {@code iterable}, a NullPointerException will be thrown. 717 * 718 * <p><b>{@code Stream} equivalent:</b> {@code stream.filter(predicate).findFirst()} 719 * 720 * @since 11.0 721 */ 722 public static <T> Optional<T> tryFind(Iterable<T> iterable, Predicate<? super T> predicate) { 723 return Iterators.tryFind(iterable.iterator(), predicate); 724 } 725 726 /** 727 * Returns the index in {@code iterable} of the first element that satisfies the provided {@code 728 * predicate}, or {@code -1} if the Iterable has no such elements. 729 * 730 * <p>More formally, returns the lowest index {@code i} such that {@code 731 * predicate.apply(Iterables.get(iterable, i))} returns {@code true}, or {@code -1} if there is no 732 * such index. 733 * 734 * @since 2.0 735 */ 736 public static <T extends @Nullable Object> int indexOf( 737 Iterable<T> iterable, Predicate<? super T> predicate) { 738 return Iterators.indexOf(iterable.iterator(), predicate); 739 } 740 741 /** 742 * Returns a view containing the result of applying {@code function} to each element of {@code 743 * fromIterable}. 744 * 745 * <p>The returned iterable's iterator supports {@code remove()} if {@code fromIterable}'s 746 * iterator does. After a successful {@code remove()} call, {@code fromIterable} no longer 747 * contains the corresponding element. 748 * 749 * <p>If the input {@code Iterable} is known to be a {@code List} or other {@code Collection}, 750 * consider {@link Lists#transform} and {@link Collections2#transform}. 751 * 752 * <p><b>{@code Stream} equivalent:</b> {@link Stream#map} 753 */ 754 public static <F extends @Nullable Object, T extends @Nullable Object> Iterable<T> transform( 755 final Iterable<F> fromIterable, final Function<? super F, ? extends T> function) { 756 checkNotNull(fromIterable); 757 checkNotNull(function); 758 return new FluentIterable<T>() { 759 @Override 760 public Iterator<T> iterator() { 761 return Iterators.transform(fromIterable.iterator(), function); 762 } 763 }; 764 } 765 766 /** 767 * Returns the element at the specified position in an iterable. 768 * 769 * <p><b>{@code Stream} equivalent:</b> {@code stream.skip(position).findFirst().get()} (throws 770 * {@code NoSuchElementException} if out of bounds) 771 * 772 * @param position position of the element to return 773 * @return the element at the specified position in {@code iterable} 774 * @throws IndexOutOfBoundsException if {@code position} is negative or greater than or equal to 775 * the size of {@code iterable} 776 */ 777 @ParametricNullness 778 public static <T extends @Nullable Object> T get(Iterable<T> iterable, int position) { 779 checkNotNull(iterable); 780 return (iterable instanceof List) 781 ? ((List<T>) iterable).get(position) 782 : Iterators.get(iterable.iterator(), position); 783 } 784 785 /** 786 * Returns the element at the specified position in an iterable or a default value otherwise. 787 * 788 * <p><b>{@code Stream} equivalent:</b> {@code 789 * stream.skip(position).findFirst().orElse(defaultValue)} (returns the default value if the index 790 * is out of bounds) 791 * 792 * @param position position of the element to return 793 * @param defaultValue the default value to return if {@code position} is greater than or equal to 794 * the size of the iterable 795 * @return the element at the specified position in {@code iterable} or {@code defaultValue} if 796 * {@code iterable} contains fewer than {@code position + 1} elements. 797 * @throws IndexOutOfBoundsException if {@code position} is negative 798 * @since 4.0 799 */ 800 @ParametricNullness 801 public static <T extends @Nullable Object> T get( 802 Iterable<? extends T> iterable, int position, @ParametricNullness T defaultValue) { 803 checkNotNull(iterable); 804 Iterators.checkNonnegative(position); 805 if (iterable instanceof List) { 806 List<? extends T> list = (List<? extends T>) iterable; 807 return (position < list.size()) ? list.get(position) : defaultValue; 808 } else { 809 Iterator<? extends T> iterator = iterable.iterator(); 810 Iterators.advance(iterator, position); 811 return Iterators.getNext(iterator, defaultValue); 812 } 813 } 814 815 /** 816 * Returns the first element in {@code iterable} or {@code defaultValue} if the iterable is empty. 817 * The {@link Iterators} analog to this method is {@link Iterators#getNext}. 818 * 819 * <p>If no default value is desired (and the caller instead wants a {@link 820 * NoSuchElementException} to be thrown), it is recommended that {@code 821 * iterable.iterator().next()} is used instead. 822 * 823 * <p>To get the only element in a single-element {@code Iterable}, consider using {@link 824 * #getOnlyElement(Iterable)} or {@link #getOnlyElement(Iterable, Object)} instead. 825 * 826 * <p><b>{@code Stream} equivalent:</b> {@code stream.findFirst().orElse(defaultValue)} 827 * 828 * @param defaultValue the default value to return if the iterable is empty 829 * @return the first element of {@code iterable} or the default value 830 * @since 7.0 831 */ 832 @ParametricNullness 833 public static <T extends @Nullable Object> T getFirst( 834 Iterable<? extends T> iterable, @ParametricNullness T defaultValue) { 835 return Iterators.getNext(iterable.iterator(), defaultValue); 836 } 837 838 /** 839 * Returns the last element of {@code iterable}. If {@code iterable} is a {@link List} with {@link 840 * RandomAccess} support, then this operation is guaranteed to be {@code O(1)}. 841 * 842 * <p><b>{@code Stream} equivalent:</b> {@link Streams#findLast Streams.findLast(stream).get()} 843 * 844 * @return the last element of {@code iterable} 845 * @throws NoSuchElementException if the iterable is empty 846 */ 847 @ParametricNullness 848 public static <T extends @Nullable Object> T getLast(Iterable<T> iterable) { 849 // TODO(kevinb): Support a concurrently modified collection? 850 if (iterable instanceof List) { 851 List<T> list = (List<T>) iterable; 852 if (list.isEmpty()) { 853 throw new NoSuchElementException(); 854 } 855 return getLastInNonemptyList(list); 856 } 857 858 return Iterators.getLast(iterable.iterator()); 859 } 860 861 /** 862 * Returns the last element of {@code iterable} or {@code defaultValue} if the iterable is empty. 863 * If {@code iterable} is a {@link List} with {@link RandomAccess} support, then this operation is 864 * guaranteed to be {@code O(1)}. 865 * 866 * <p><b>{@code Stream} equivalent:</b> {@code Streams.findLast(stream).orElse(defaultValue)} 867 * 868 * @param defaultValue the value to return if {@code iterable} is empty 869 * @return the last element of {@code iterable} or the default value 870 * @since 3.0 871 */ 872 @ParametricNullness 873 public static <T extends @Nullable Object> T getLast( 874 Iterable<? extends T> iterable, @ParametricNullness T defaultValue) { 875 if (iterable instanceof Collection) { 876 Collection<? extends T> c = (Collection<? extends T>) iterable; 877 if (c.isEmpty()) { 878 return defaultValue; 879 } else if (iterable instanceof List) { 880 return getLastInNonemptyList((List<? extends T>) iterable); 881 } 882 } 883 884 return Iterators.getLast(iterable.iterator(), defaultValue); 885 } 886 887 @ParametricNullness 888 private static <T extends @Nullable Object> T getLastInNonemptyList(List<T> list) { 889 return list.get(list.size() - 1); 890 } 891 892 /** 893 * Returns a view of {@code iterable} that skips its first {@code numberToSkip} elements. If 894 * {@code iterable} contains fewer than {@code numberToSkip} elements, the returned iterable skips 895 * all of its elements. 896 * 897 * <p>Modifications to the underlying {@link Iterable} before a call to {@code iterator()} are 898 * reflected in the returned iterator. That is, the iterator skips the first {@code numberToSkip} 899 * elements that exist when the {@code Iterator} is created, not when {@code skip()} is called. 900 * 901 * <p>The returned iterable's iterator supports {@code remove()} if the iterator of the underlying 902 * iterable supports it. Note that it is <i>not</i> possible to delete the last skipped element by 903 * immediately calling {@code remove()} on that iterator, as the {@code Iterator} contract states 904 * that a call to {@code remove()} before a call to {@code next()} will throw an {@link 905 * IllegalStateException}. 906 * 907 * <p><b>{@code Stream} equivalent:</b> {@link Stream#skip} 908 * 909 * @since 3.0 910 */ 911 public static <T extends @Nullable Object> Iterable<T> skip( 912 final Iterable<T> iterable, final int numberToSkip) { 913 checkNotNull(iterable); 914 checkArgument(numberToSkip >= 0, "number to skip cannot be negative"); 915 916 return new FluentIterable<T>() { 917 @Override 918 public Iterator<T> iterator() { 919 if (iterable instanceof List) { 920 final List<T> list = (List<T>) iterable; 921 int toSkip = Math.min(list.size(), numberToSkip); 922 return list.subList(toSkip, list.size()).iterator(); 923 } 924 final Iterator<T> iterator = iterable.iterator(); 925 926 Iterators.advance(iterator, numberToSkip); 927 928 /* 929 * We can't just return the iterator because an immediate call to its 930 * remove() method would remove one of the skipped elements instead of 931 * throwing an IllegalStateException. 932 */ 933 return new Iterator<T>() { 934 boolean atStart = true; 935 936 @Override 937 public boolean hasNext() { 938 return iterator.hasNext(); 939 } 940 941 @Override 942 @ParametricNullness 943 public T next() { 944 T result = iterator.next(); 945 atStart = false; // not called if next() fails 946 return result; 947 } 948 949 @Override 950 public void remove() { 951 checkRemove(!atStart); 952 iterator.remove(); 953 } 954 }; 955 } 956 }; 957 } 958 959 /** 960 * Returns a view of {@code iterable} containing its first {@code limitSize} elements. If {@code 961 * iterable} contains fewer than {@code limitSize} elements, the returned view contains all of its 962 * elements. The returned iterable's iterator supports {@code remove()} if {@code iterable}'s 963 * iterator does. 964 * 965 * <p><b>{@code Stream} equivalent:</b> {@link Stream#limit} 966 * 967 * @param iterable the iterable to limit 968 * @param limitSize the maximum number of elements in the returned iterable 969 * @throws IllegalArgumentException if {@code limitSize} is negative 970 * @since 3.0 971 */ 972 public static <T extends @Nullable Object> Iterable<T> limit( 973 final Iterable<T> iterable, final int limitSize) { 974 checkNotNull(iterable); 975 checkArgument(limitSize >= 0, "limit is negative"); 976 return new FluentIterable<T>() { 977 @Override 978 public Iterator<T> iterator() { 979 return Iterators.limit(iterable.iterator(), limitSize); 980 } 981 }; 982 } 983 984 /** 985 * Returns a view of the supplied iterable that wraps each generated {@link Iterator} through 986 * {@link Iterators#consumingIterator(Iterator)}. 987 * 988 * <p>Note: If {@code iterable} is a {@link Queue}, the returned iterable will instead use {@link 989 * Queue#isEmpty} and {@link Queue#remove()}, since {@link Queue}'s iteration order is undefined. 990 * Calling {@link Iterator#hasNext()} on a generated iterator from the returned iterable may cause 991 * an item to be immediately dequeued for return on a subsequent call to {@link Iterator#next()}. 992 * 993 * <p>Whether the input {@code iterable} is a {@link Queue} or not, the returned {@code Iterable} 994 * is not thread-safe. 995 * 996 * @param iterable the iterable to wrap 997 * @return a view of the supplied iterable that wraps each generated iterator through {@link 998 * Iterators#consumingIterator(Iterator)}; for queues, an iterable that generates iterators 999 * that return and consume the queue's elements in queue order 1000 * @see Iterators#consumingIterator(Iterator) 1001 * @since 2.0 1002 */ 1003 public static <T extends @Nullable Object> Iterable<T> consumingIterable( 1004 final Iterable<T> iterable) { 1005 checkNotNull(iterable); 1006 1007 return new FluentIterable<T>() { 1008 @Override 1009 public Iterator<T> iterator() { 1010 return (iterable instanceof Queue) 1011 ? new ConsumingQueueIterator<>((Queue<T>) iterable) 1012 : Iterators.consumingIterator(iterable.iterator()); 1013 } 1014 1015 @Override 1016 public String toString() { 1017 return "Iterables.consumingIterable(...)"; 1018 } 1019 }; 1020 } 1021 1022 // Methods only in Iterables, not in Iterators 1023 1024 /** 1025 * Determines if the given iterable contains no elements. 1026 * 1027 * <p>There is no precise {@link Iterator} equivalent to this method, since one can only ask an 1028 * iterator whether it has any elements <i>remaining</i> (which one does using {@link 1029 * Iterator#hasNext}). 1030 * 1031 * <p><b>{@code Stream} equivalent:</b> {@code !stream.findAny().isPresent()} 1032 * 1033 * @return {@code true} if the iterable contains no elements 1034 */ 1035 public static boolean isEmpty(Iterable<?> iterable) { 1036 if (iterable instanceof Collection) { 1037 return ((Collection<?>) iterable).isEmpty(); 1038 } 1039 return !iterable.iterator().hasNext(); 1040 } 1041 1042 /** 1043 * Returns an iterable over the merged contents of all given {@code iterables}. Equivalent entries 1044 * will not be de-duplicated. 1045 * 1046 * <p>Callers must ensure that the source {@code iterables} are in non-descending order as this 1047 * method does not sort its input. 1048 * 1049 * <p>For any equivalent elements across all {@code iterables}, it is undefined which element is 1050 * returned first. 1051 * 1052 * @since 11.0 1053 */ 1054 public static <T extends @Nullable Object> Iterable<T> mergeSorted( 1055 final Iterable<? extends Iterable<? extends T>> iterables, 1056 final Comparator<? super T> comparator) { 1057 checkNotNull(iterables, "iterables"); 1058 checkNotNull(comparator, "comparator"); 1059 Iterable<T> iterable = 1060 new FluentIterable<T>() { 1061 @Override 1062 public Iterator<T> iterator() { 1063 return Iterators.mergeSorted( 1064 Iterables.transform(iterables, Iterable::iterator), comparator); 1065 } 1066 }; 1067 return new UnmodifiableIterable<>(iterable); 1068 } 1069}