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