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