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