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