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