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