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