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