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