    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    import static com.google.common.base.Preconditions.checkState;
    022
    023    import com.google.common.annotations.Beta;
    024    import com.google.common.annotations.GwtCompatible;
    025    import com.google.common.annotations.GwtIncompatible;
    026    import com.google.common.base.Function;
    027    import com.google.common.base.Objects;
    028    import com.google.common.base.Preconditions;
    029    import com.google.common.base.Predicate;
    030    import com.google.common.base.Predicates;
    031
    032    import java.util.Arrays;
    033    import java.util.Collection;
    034    import java.util.Collections;
    035    import java.util.Enumeration;
    036    import java.util.Iterator;
    037    import java.util.List;
    038    import java.util.NoSuchElementException;
    039
    040    import javax.annotation.Nullable;
    041
    042    /**
    043     * This class contains static utility methods that operate on or return objects
    044     * of type {@link Iterator}. Except as noted, each method has a corresponding
    045     * {@link Iterable}-based method in the {@link Iterables} class.
    046     *
    047     * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterators
    048     * produced in this class are <i>lazy</i>, which means that they only advance
    049     * the backing iteration when absolutely necessary.
    050     *
    051     * @author Kevin Bourrillion
    052     * @author Jared Levy
    053     * @since 2.0 (imported from Google Collections Library)
    054     */
    055    @GwtCompatible(emulated = true)
    056    public final class Iterators {
    057      private Iterators() {}
    058
    059      static final UnmodifiableIterator<Object> EMPTY_ITERATOR
    060          = new UnmodifiableIterator<Object>() {
    061            @Override
    062            public boolean hasNext() {
    063              return false;
    064            }
    065            @Override
    066            public Object next() {
    067              throw new NoSuchElementException();
    068            }
    069          };
    070
    071      /**
    072       * Returns the empty iterator.
    073       *
    074       * <p>The {@link Iterable} equivalent of this method is {@link
    075       * Collections#emptySet}.
    076       */
    077      // Casting to any type is safe since there are no actual elements.
    078      @SuppressWarnings("unchecked")
    079      public static <T> UnmodifiableIterator<T> emptyIterator() {
    080        return (UnmodifiableIterator<T>) EMPTY_ITERATOR;
    081      }
    082
    083      private static final Iterator<Object> EMPTY_MODIFIABLE_ITERATOR =
    084          new Iterator<Object>() {
    085            @Override public boolean hasNext() {
    086              return false;
    087            }
    088
    089            @Override public Object next() {
    090              throw new NoSuchElementException();
    091            }
    092
    093            @Override public void remove() {
    094              throw new IllegalStateException();
    095            }
    096          };
    097
    098      /**
    099       * Returns the empty {@code Iterator} that throws
    100       * {@link IllegalStateException} instead of
    101       * {@link UnsupportedOperationException} on a call to
    102       * {@link Iterator#remove()}.
    103       */
    104      // Casting to any type is safe since there are no actual elements.
    105      @SuppressWarnings("unchecked")
    106      static <T> Iterator<T> emptyModifiableIterator() {
    107        return (Iterator<T>) EMPTY_MODIFIABLE_ITERATOR;
    108      }
    109
    110      /** Returns an unmodifiable view of {@code iterator}. */
    111      public static <T> UnmodifiableIterator<T> unmodifiableIterator(
    112          final Iterator<T> iterator) {
    113        checkNotNull(iterator);
    114        if (iterator instanceof UnmodifiableIterator) {
    115          return (UnmodifiableIterator<T>) iterator;
    116        }
    117        return new UnmodifiableIterator<T>() {
    118          @Override
    119          public boolean hasNext() {
    120            return iterator.hasNext();
    121          }
    122          @Override
    123          public T next() {
    124            return iterator.next();
    125          }
    126        };
    127      }
    128
    129      /**
    130       * Simply returns its argument.
    131       *
    132       * @deprecated no need to use this
    133       * @since 10.0
    134       */
    135      @Deprecated public static <T> UnmodifiableIterator<T> unmodifiableIterator(
    136          UnmodifiableIterator<T> iterator) {
    137        return checkNotNull(iterator);
    138      }
    139
    140      /**
    141       * Returns the number of elements remaining in {@code iterator}. The iterator
    142       * will be left exhausted: its {@code hasNext()} method will return
    143       * {@code false}.
    144       */
    145      public static int size(Iterator<?> iterator) {
    146        int count = 0;
    147        while (iterator.hasNext()) {
    148          iterator.next();
    149          count++;
    150        }
    151        return count;
    152      }
    153
    154      /**
    155       * Returns {@code true} if {@code iterator} contains {@code element}.
    156       */
    157      public static boolean contains(Iterator<?> iterator, @Nullable Object element)
    158      {
    159        if (element == null) {
    160          while (iterator.hasNext()) {
    161            if (iterator.next() == null) {
    162              return true;
    163            }
    164          }
    165        } else {
    166          while (iterator.hasNext()) {
    167            if (element.equals(iterator.next())) {
    168              return true;
    169            }
    170          }
    171        }
    172        return false;
    173      }
    174
    175      /**
    176       * Traverses an iterator and removes every element that belongs to the
    177       * provided collection. The iterator will be left exhausted: its
    178       * {@code hasNext()} method will return {@code false}.
    179       *
    180       * @param removeFrom the iterator to (potentially) remove elements from
    181       * @param elementsToRemove the elements to remove
    182       * @return {@code true} if any element was removed from {@code iterator}
    183       */
    184      public static boolean removeAll(
    185          Iterator<?> removeFrom, Collection<?> elementsToRemove) {
    186        checkNotNull(elementsToRemove);
    187        boolean modified = false;
    188        while (removeFrom.hasNext()) {
    189          if (elementsToRemove.contains(removeFrom.next())) {
    190            removeFrom.remove();
    191            modified = true;
    192          }
    193        }
    194        return modified;
    195      }
    196
    197      /**
    198       * Removes every element that satisfies the provided predicate from the
    199       * iterator. The iterator will be left exhausted: its {@code hasNext()}
    200       * method will return {@code false}.
    201       *
    202       * @param removeFrom the iterator to (potentially) remove elements from
    203       * @param predicate a predicate that determines whether an element should
    204       *     be removed
    205       * @return {@code true} if any elements were removed from the iterator
    206       * @since 2.0
    207       */
    208      public static <T> boolean removeIf(
    209          Iterator<T> removeFrom, Predicate<? super T> predicate) {
    210        checkNotNull(predicate);
    211        boolean modified = false;
    212        while (removeFrom.hasNext()) {
    213          if (predicate.apply(removeFrom.next())) {
    214            removeFrom.remove();
    215            modified = true;
    216          }
    217        }
    218        return modified;
    219      }
    220
    221      /**
    222       * Traverses an iterator and removes every element that does not belong to the
    223       * provided collection. The iterator will be left exhausted: its
    224       * {@code hasNext()} method will return {@code false}.
    225       *
    226       * @param removeFrom the iterator to (potentially) remove elements from
    227       * @param elementsToRetain the elements to retain
    228       * @return {@code true} if any element was removed from {@code iterator}
    229       */
    230      public static boolean retainAll(
    231          Iterator<?> removeFrom, Collection<?> elementsToRetain) {
    232        checkNotNull(elementsToRetain);
    233        boolean modified = false;
    234        while (removeFrom.hasNext()) {
    235          if (!elementsToRetain.contains(removeFrom.next())) {
    236            removeFrom.remove();
    237            modified = true;
    238          }
    239        }
    240        return modified;
    241      }
    242
    243      /**
    244       * Determines whether two iterators contain equal elements in the same order.
    245       * More specifically, this method returns {@code true} if {@code iterator1}
    246       * and {@code iterator2} contain the same number of elements and every element
    247       * of {@code iterator1} is equal to the corresponding element of
    248       * {@code iterator2}.
    249       *
    250       * <p>Note that this will modify the supplied iterators, since they will have
    251       * been advanced some number of elements forward.
    252       */
    253      public static boolean elementsEqual(
    254          Iterator<?> iterator1, Iterator<?> iterator2) {
    255        while (iterator1.hasNext()) {
    256          if (!iterator2.hasNext()) {
    257            return false;
    258          }
    259          Object o1 = iterator1.next();
    260          Object o2 = iterator2.next();
    261          if (!Objects.equal(o1, o2)) {
    262            return false;
    263          }
    264        }
    265        return !iterator2.hasNext();
    266      }
    267
    268      /**
    269       * Returns a string representation of {@code iterator}, with the format
    270       * {@code [e1, e2, ..., en]}. The iterator will be left exhausted: its
    271       * {@code hasNext()} method will return {@code false}.
    272       */
    273      public static String toString(Iterator<?> iterator) {
    274        if (!iterator.hasNext()) {
    275          return "[]";
    276        }
    277        StringBuilder builder = new StringBuilder();
    278        builder.append('[').append(iterator.next());
    279        while (iterator.hasNext()) {
    280          builder.append(", ").append(iterator.next());
    281        }
    282        return builder.append(']').toString();
    283      }
    284
    285      /**
    286       * Returns the single element contained in {@code iterator}.
    287       *
    288       * @throws NoSuchElementException if the iterator is empty
    289       * @throws IllegalArgumentException if the iterator contains multiple
    290       *     elements.  The state of the iterator is unspecified.
    291       */
    292      public static <T> T getOnlyElement(Iterator<T> iterator) {
    293        T first = iterator.next();
    294        if (!iterator.hasNext()) {
    295          return first;
    296        }
    297
    298        StringBuilder sb = new StringBuilder();
    299        sb.append("expected one element but was: <" + first);
    300        for (int i = 0; i < 4 && iterator.hasNext(); i++) {
    301          sb.append(", " + iterator.next());
    302        }
    303        if (iterator.hasNext()) {
    304          sb.append(", ...");
    305        }
    306        sb.append('>');
    307
    308        throw new IllegalArgumentException(sb.toString());
    309      }
    310
    311      /**
    312       * Returns the single element contained in {@code iterator}, or {@code
    313       * defaultValue} if the iterator is empty.
    314       *
    315       * @throws IllegalArgumentException if the iterator contains multiple
    316       *     elements.  The state of the iterator is unspecified.
    317       */
    318      public static <T> T getOnlyElement(
    319          Iterator<T> iterator, @Nullable T defaultValue) {
    320        return iterator.hasNext() ? getOnlyElement(iterator) : defaultValue;
    321      }
    322
    323      /**
    324       * Copies an iterator's elements into an array. The iterator will be left
    325       * exhausted: its {@code hasNext()} method will return {@code false}.
    326       *
    327       * @param iterator the iterator to copy
    328       * @param type the type of the elements
    329       * @return a newly-allocated array into which all the elements of the iterator
    330       *         have been copied
    331       */
    332      @GwtIncompatible("Array.newInstance(Class, int)")
    333      public static <T> T[] toArray(
    334          Iterator<? extends T> iterator, Class<T> type) {
    335        List<T> list = Lists.newArrayList(iterator);
    336        return Iterables.toArray(list, type);
    337      }
    338
    339      /**
    340       * Adds all elements in {@code iterator} to {@code collection}. The iterator
    341       * will be left exhausted: its {@code hasNext()} method will return
    342       * {@code false}.
    343       *
    344       * @return {@code true} if {@code collection} was modified as a result of this
    345       *         operation
    346       */
    347      public static <T> boolean addAll(
    348          Collection<T> addTo, Iterator<? extends T> iterator) {
    349        checkNotNull(addTo);
    350        boolean wasModified = false;
    351        while (iterator.hasNext()) {
    352          wasModified |= addTo.add(iterator.next());
    353        }
    354        return wasModified;
    355      }
    356
    357      /**
    358       * Returns the number of elements in the specified iterator that equal the
    359       * specified object. The iterator will be left exhausted: its
    360       * {@code hasNext()} method will return {@code false}.
    361       *
    362       * @see Collections#frequency
    363       */
    364      public static int frequency(Iterator<?> iterator, @Nullable Object element) {
    365        int result = 0;
    366        if (element == null) {
    367          while (iterator.hasNext()) {
    368            if (iterator.next() == null) {
    369              result++;
    370            }
    371          }
    372        } else {
    373          while (iterator.hasNext()) {
    374            if (element.equals(iterator.next())) {
    375              result++;
    376            }
    377          }
    378        }
    379        return result;
    380      }
    381
    382      /**
    383       * Returns an iterator that cycles indefinitely over the elements of {@code
    384       * iterable}.
    385       *
    386       * <p>The returned iterator supports {@code remove()} if the provided iterator
    387       * does. After {@code remove()} is called, subsequent cycles omit the removed
    388       * element, which is no longer in {@code iterable}. The iterator's
    389       * {@code hasNext()} method returns {@code true} until {@code iterable} is
    390       * empty.
    391       *
    392       * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
    393       * infinite loop. You should use an explicit {@code break} or be certain that
    394       * you will eventually remove all the elements.
    395       */
    396      public static <T> Iterator<T> cycle(final Iterable<T> iterable) {
    397        checkNotNull(iterable);
    398        return new Iterator<T>() {
    399          Iterator<T> iterator = emptyIterator();
    400          Iterator<T> removeFrom;
    401
    402          @Override
    403          public boolean hasNext() {
    404            if (!iterator.hasNext()) {
    405              iterator = iterable.iterator();
    406            }
    407            return iterator.hasNext();
    408          }
    409          @Override
    410          public T next() {
    411            if (!hasNext()) {
    412              throw new NoSuchElementException();
    413            }
    414            removeFrom = iterator;
    415            return iterator.next();
    416          }
    417          @Override
    418          public void remove() {
    419            checkState(removeFrom != null,
    420                "no calls to next() since last call to remove()");
    421            removeFrom.remove();
    422            removeFrom = null;
    423          }
    424        };
    425      }
    426
    427      /**
    428       * Returns an iterator that cycles indefinitely over the provided elements.
    429       *
    430       * <p>The returned iterator supports {@code remove()} if the provided iterator
    431       * does. After {@code remove()} is called, subsequent cycles omit the removed
    432       * element, but {@code elements} does not change. The iterator's
    433       * {@code hasNext()} method returns {@code true} until all of the original
    434       * elements have been removed.
    435       *
    436       * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
    437       * infinite loop. You should use an explicit {@code break} or be certain that
    438       * you will eventually remove all the elements.
    439       */
    440      public static <T> Iterator<T> cycle(T... elements) {
    441        return cycle(Lists.newArrayList(elements));
    442      }
    443
    444      /**
    445       * Combines two iterators into a single iterator. The returned iterator
    446       * iterates across the elements in {@code a}, followed by the elements in
    447       * {@code b}. The source iterators are not polled until necessary.
    448       *
    449       * <p>The returned iterator supports {@code remove()} when the corresponding
    450       * input iterator supports it.
    451       */
    452      @SuppressWarnings("unchecked")
    453      public static <T> Iterator<T> concat(Iterator<? extends T> a,
    454          Iterator<? extends T> b) {
    455        checkNotNull(a);
    456        checkNotNull(b);
    457        return concat(Arrays.asList(a, b).iterator());
    458      }
    459
    460      /**
    461       * Combines three iterators into a single iterator. The returned iterator
    462       * iterates across the elements in {@code a}, followed by the elements in
    463       * {@code b}, followed by the elements in {@code c}. The source iterators
    464       * are not polled until necessary.
    465       *
    466       * <p>The returned iterator supports {@code remove()} when the corresponding
    467       * input iterator supports it.
    468       */
    469      @SuppressWarnings("unchecked")
    470      public static <T> Iterator<T> concat(Iterator<? extends T> a,
    471          Iterator<? extends T> b, Iterator<? extends T> c) {
    472        checkNotNull(a);
    473        checkNotNull(b);
    474        checkNotNull(c);
    475        return concat(Arrays.asList(a, b, c).iterator());
    476      }
    477
    478      /**
    479       * Combines four iterators into a single iterator. The returned iterator
    480       * iterates across the elements in {@code a}, followed by the elements in
    481       * {@code b}, followed by the elements in {@code c}, followed by the elements
    482       * in {@code d}. The source iterators are not polled until necessary.
    483       *
    484       * <p>The returned iterator supports {@code remove()} when the corresponding
    485       * input iterator supports it.
    486       */
    487      @SuppressWarnings("unchecked")
    488      public static <T> Iterator<T> concat(Iterator<? extends T> a,
    489          Iterator<? extends T> b, Iterator<? extends T> c,
    490          Iterator<? extends T> d) {
    491        checkNotNull(a);
    492        checkNotNull(b);
    493        checkNotNull(c);
    494        checkNotNull(d);
    495        return concat(Arrays.asList(a, b, c, d).iterator());
    496      }
    497
    498      /**
    499       * Combines multiple iterators into a single iterator. The returned iterator
    500       * iterates across the elements of each iterator in {@code inputs}. The input
    501       * iterators are not polled until necessary.
    502       *
    503       * <p>The returned iterator supports {@code remove()} when the corresponding
    504       * input iterator supports it.
    505       *
    506       * @throws NullPointerException if any of the provided iterators is null
    507       */
    508      public static <T> Iterator<T> concat(Iterator<? extends T>... inputs) {
    509        return concat(ImmutableList.copyOf(inputs).iterator());
    510      }
    511
    512      /**
    513       * Combines multiple iterators into a single iterator. The returned iterator
    514       * iterates across the elements of each iterator in {@code inputs}. The input
    515       * iterators are not polled until necessary.
    516       *
    517       * <p>The returned iterator supports {@code remove()} when the corresponding
    518       * input iterator supports it. The methods of the returned iterator may throw
    519       * {@code NullPointerException} if any of the input iterators is null.
    520       */
    521      public static <T> Iterator<T> concat(
    522          final Iterator<? extends Iterator<? extends T>> inputs) {
    523        checkNotNull(inputs);
    524        return new Iterator<T>() {
    525          Iterator<? extends T> current = emptyIterator();
    526          Iterator<? extends T> removeFrom;
    527
    528          @Override
    529          public boolean hasNext() {
    530            // http://code.google.com/p/google-collections/issues/detail?id=151
    531            // current.hasNext() might be relatively expensive, worth minimizing.
    532            boolean currentHasNext;
    533            // checkNotNull eager for GWT
    534            // note: it must be here & not where 'current' is assigned,
    535            // because otherwise we'll have called inputs.next() before throwing
    536            // the first NPE, and the next time around we'll call inputs.next()
    537            // again, incorrectly moving beyond the error.
    538            while (!(currentHasNext = checkNotNull(current).hasNext())
    539                && inputs.hasNext()) {
    540              current = inputs.next();
    541            }
    542            return currentHasNext;
    543          }
    544          @Override
    545          public T next() {
    546            if (!hasNext()) {
    547              throw new NoSuchElementException();
    548            }
    549            removeFrom = current;
    550            return current.next();
    551          }
    552          @Override
    553          public void remove() {
    554            checkState(removeFrom != null,
    555                "no calls to next() since last call to remove()");
    556            removeFrom.remove();
    557            removeFrom = null;
    558          }
    559        };
    560      }
    561
    562      /**
    563       * Divides an iterator into unmodifiable sublists of the given size (the final
    564       * list may be smaller). For example, partitioning an iterator containing
    565       * {@code [a, b, c, d, e]} with a partition size of 3 yields {@code
    566       * [[a, b, c], [d, e]]} -- an outer iterator containing two inner lists of
    567       * three and two elements, all in the original order.
    568       *
    569       * <p>The returned lists implement {@link java.util.RandomAccess}.
    570       *
    571       * @param iterator the iterator to return a partitioned view of
    572       * @param size the desired size of each partition (the last may be smaller)
    573       * @return an iterator of immutable lists containing the elements of {@code
    574       *     iterator} divided into partitions
    575       * @throws IllegalArgumentException if {@code size} is nonpositive
    576       */
    577      public static <T> UnmodifiableIterator<List<T>> partition(
    578          Iterator<T> iterator, int size) {
    579        return partitionImpl(iterator, size, false);
    580      }
    581
    582      /**
    583       * Divides an iterator into unmodifiable sublists of the given size, padding
    584       * the final iterator with null values if necessary. For example, partitioning
    585       * an iterator containing {@code [a, b, c, d, e]} with a partition size of 3
    586       * yields {@code [[a, b, c], [d, e, null]]} -- an outer iterator containing
    587       * two inner lists of three elements each, all in the original order.
    588       *
    589       * <p>The returned lists implement {@link java.util.RandomAccess}.
    590       *
    591       * @param iterator the iterator to return a partitioned view of
    592       * @param size the desired size of each partition
    593       * @return an iterator of immutable lists containing the elements of {@code
    594       *     iterator} divided into partitions (the final iterable may have
    595       *     trailing null elements)
    596       * @throws IllegalArgumentException if {@code size} is nonpositive
    597       */
    598      public static <T> UnmodifiableIterator<List<T>> paddedPartition(
    599          Iterator<T> iterator, int size) {
    600        return partitionImpl(iterator, size, true);
    601      }
    602
    603      private static <T> UnmodifiableIterator<List<T>> partitionImpl(
    604          final Iterator<T> iterator, final int size, final boolean pad) {
    605        checkNotNull(iterator);
    606        checkArgument(size > 0);
    607        return new UnmodifiableIterator<List<T>>() {
    608          @Override
    609          public boolean hasNext() {
    610            return iterator.hasNext();
    611          }
    612          @Override
    613          public List<T> next() {
    614            if (!hasNext()) {
    615              throw new NoSuchElementException();
    616            }
    617            Object[] array = new Object[size];
    618            int count = 0;
    619            for (; count < size && iterator.hasNext(); count++) {
    620              array[count] = iterator.next();
    621            }
    622            for (int i = count; i < size; i++) {
    623              array[i] = null; // for GWT
    624            }
    625
    626            @SuppressWarnings("unchecked") // we only put Ts in it
    627            List<T> list = Collections.unmodifiableList(
    628                (List<T>) Arrays.asList(array));
    629            return (pad || count == size) ? list : list.subList(0, count);
    630          }
    631        };
    632      }
    633
    634      /**
    635       * Returns the elements of {@code unfiltered} that satisfy a predicate.
    636       */
    637      public static <T> UnmodifiableIterator<T> filter(
    638          final Iterator<T> unfiltered, final Predicate<? super T> predicate) {
    639        checkNotNull(unfiltered);
    640        checkNotNull(predicate);
    641        return new AbstractIterator<T>() {
    642          @Override protected T computeNext() {
    643            while (unfiltered.hasNext()) {
    644              T element = unfiltered.next();
    645              if (predicate.apply(element)) {
    646                return element;
    647              }
    648            }
    649            return endOfData();
    650          }
    651        };
    652      }
    653
    654      /**
    655       * Returns all instances of class {@code type} in {@code unfiltered}. The
    656       * returned iterator has elements whose class is {@code type} or a subclass of
    657       * {@code type}.
    658       *
    659       * @param unfiltered an iterator containing objects of any type
    660       * @param type the type of elements desired
    661       * @return an unmodifiable iterator containing all elements of the original
    662       *     iterator that were of the requested type
    663       */
    664      @SuppressWarnings("unchecked") // can cast to <T> because non-Ts are removed
    665      @GwtIncompatible("Class.isInstance")
    666      public static <T> UnmodifiableIterator<T> filter(
    667          Iterator<?> unfiltered, Class<T> type) {
    668        return (UnmodifiableIterator<T>)
    669            filter(unfiltered, Predicates.instanceOf(type));
    670      }
    671
    672      /**
    673       * Returns {@code true} if one or more elements returned by {@code iterator}
    674       * satisfy the given predicate.
    675       */
    676      public static <T> boolean any(
    677          Iterator<T> iterator, Predicate<? super T> predicate) {
    678        checkNotNull(predicate);
    679        while (iterator.hasNext()) {
    680          T element = iterator.next();
    681          if (predicate.apply(element)) {
    682            return true;
    683          }
    684        }
    685        return false;
    686      }
    687
    688      /**
    689       * Returns {@code true} if every element returned by {@code iterator}
    690       * satisfies the given predicate. If {@code iterator} is empty, {@code true}
    691       * is returned.
    692       */
    693      public static <T> boolean all(
    694          Iterator<T> iterator, Predicate<? super T> predicate) {
    695        checkNotNull(predicate);
    696        while (iterator.hasNext()) {
    697          T element = iterator.next();
    698          if (!predicate.apply(element)) {
    699            return false;
    700          }
    701        }
    702        return true;
    703      }
    704
    705      /**
    706       * Returns the first element in {@code iterator} that satisfies the given
    707       * predicate.  If no such element is found, the iterator will be left
    708       * exhausted: its {@code hasNext()} method will return {@code false}.
    709       *
    710       * @throws NoSuchElementException if no element in {@code iterator} matches
    711       *     the given predicate
    712       */
    713      public static <T> T find(
    714          Iterator<T> iterator, Predicate<? super T> predicate) {
    715        return filter(iterator, predicate).next();
    716      }
    717
    718      /**
    719       * Returns the first element in {@code iterator} that satisfies the given
    720       * predicate.  If no such element is found, {@code defaultValue} will be
    721       * returned from this method and the iterator will be left exhausted: its
    722       * {@code hasNext()} method will return {@code false}.
    723       *
    724       * @since 7.0
    725       */
    726      public static <T> T find(Iterator<T> iterator, Predicate<? super T> predicate,
    727          @Nullable T defaultValue) {
    728        UnmodifiableIterator<T> filteredIterator = filter(iterator, predicate);
    729        return filteredIterator.hasNext() ? filteredIterator.next() : defaultValue;
    730      }
    731
    732      /**
    733       * Returns the index in {@code iterator} of the first element that satisfies
    734       * the provided {@code predicate}, or {@code -1} if the Iterator has no such
    735       * elements.
    736       *
    737       * <p>More formally, returns the lowest index {@code i} such that
    738       * {@code predicate.apply(Iterators.get(iterator, i))} returns {@code true},
    739       * or {@code -1} if there is no such index.
    740       *
    741       * <p>If -1 is returned, the iterator will be left exhausted: its
    742       * {@code hasNext()} method will return {@code false}.  Otherwise,
    743       * the iterator will be set to the element which satisfies the
    744       * {@code predicate}.
    745       *
    746       * @since 2.0
    747       */
    748      public static <T> int indexOf(
    749          Iterator<T> iterator, Predicate<? super T> predicate) {
    750        checkNotNull(predicate, "predicate");
    751        int i = 0;
    752        while (iterator.hasNext()) {
    753          T current = iterator.next();
    754          if (predicate.apply(current)) {
    755            return i;
    756          }
    757          i++;
    758        }
    759        return -1;
    760      }
    761
    762      /**
    763       * Returns an iterator that applies {@code function} to each element of {@code
    764       * fromIterator}.
    765       *
    766       * <p>The returned iterator supports {@code remove()} if the provided iterator
    767       * does. After a successful {@code remove()} call, {@code fromIterator} no
    768       * longer contains the corresponding element.
    769       */
    770      public static <F, T> Iterator<T> transform(final Iterator<F> fromIterator,
    771          final Function<? super F, ? extends T> function) {
    772        checkNotNull(fromIterator);
    773        checkNotNull(function);
    774        return new Iterator<T>() {
    775          @Override
    776          public boolean hasNext() {
    777            return fromIterator.hasNext();
    778          }
    779          @Override
    780          public T next() {
    781            F from = fromIterator.next();
    782            return function.apply(from);
    783          }
    784          @Override
    785          public void remove() {
    786            fromIterator.remove();
    787          }
    788        };
    789      }
    790
    791      /**
    792       * Advances {@code iterator} {@code position + 1} times, returning the
    793       * element at the {@code position}th position.
    794       *
    795       * @param position position of the element to return
    796       * @return the element at the specified position in {@code iterator}
    797       * @throws IndexOutOfBoundsException if {@code position} is negative or
    798       *     greater than or equal to the number of elements remaining in
    799       *     {@code iterator}
    800       */
    801      public static <T> T get(Iterator<T> iterator, int position) {
    802        checkNonnegative(position);
    803
    804        int skipped = 0;
    805        while (iterator.hasNext()) {
    806          T t = iterator.next();
    807          if (skipped++ == position) {
    808            return t;
    809          }
    810        }
    811
    812        throw new IndexOutOfBoundsException("position (" + position
    813            + ") must be less than the number of elements that remained ("
    814            + skipped + ")");
    815      }
    816
    817      private static void checkNonnegative(int position) {
    818        if (position < 0) {
    819          throw new IndexOutOfBoundsException("position (" + position
    820              + ") must not be negative");
    821        }
    822      }
    823
    824      /**
    825       * Advances {@code iterator} {@code position + 1} times, returning the
    826       * element at the {@code position}th position or {@code defaultValue}
    827       * otherwise.
    828       *
    829       * @param position position of the element to return
    830       * @param defaultValue the default value to return if the iterator is empty
    831       *     or if {@code position} is greater than the number of elements
    832       *     remaining in {@code iterator}
    833       * @return the element at the specified position in {@code iterator} or
    834       *     {@code defaultValue} if {@code iterator} produces fewer than
    835       *     {@code position + 1} elements.
    836       * @throws IndexOutOfBoundsException if {@code position} is negative
    837       * @since 4.0
    838       */
    839      public static <T> T get(Iterator<T> iterator, int position,
    840          @Nullable T defaultValue) {
    841        checkNonnegative(position);
    842
    843        try {
    844          return get(iterator, position);
    845        } catch (IndexOutOfBoundsException e) {
    846          return defaultValue;
    847        }
    848      }
    849
    850      /**
    851       * Returns the next element in {@code iterator} or {@code defaultValue} if
    852       * the iterator is empty.  The {@link Iterables} analog to this method is
    853       * {@link Iterables#getFirst}.
    854       *
    855       * @param defaultValue the default value to return if the iterator is empty
    856       * @return the next element of {@code iterator} or the default value
    857       * @since 7.0
    858       */
    859      public static <T> T getNext(Iterator<T> iterator, @Nullable T defaultValue) {
    860        return iterator.hasNext() ? iterator.next() : defaultValue;
    861      }
    862
    863      /**
    864       * Advances {@code iterator} to the end, returning the last element.
    865       *
    866       * @return the last element of {@code iterator}
    867       * @throws NoSuchElementException if the iterator is empty
    868       */
    869      public static <T> T getLast(Iterator<T> iterator) {
    870        while (true) {
    871          T current = iterator.next();
    872          if (!iterator.hasNext()) {
    873            return current;
    874          }
    875        }
    876      }
    877
    878      /**
    879       * Advances {@code iterator} to the end, returning the last element or
    880       * {@code defaultValue} if the iterator is empty.
    881       *
    882       * @param defaultValue the default value to return if the iterator is empty
    883       * @return the last element of {@code iterator}
    884       * @since 3.0
    885       */
    886      public static <T> T getLast(Iterator<T> iterator, @Nullable T defaultValue) {
    887        return iterator.hasNext() ? getLast(iterator) : defaultValue;
    888      }
    889
    890      /**
    891       * Calls {@code next()} on {@code iterator}, either {@code numberToSkip} times
    892       * or until {@code hasNext()} returns {@code false}, whichever comes first.
    893       *
    894       * @return the number of elements skipped
    895       * @since 3.0
    896       */
    897      @Beta
    898      public static <T> int skip(Iterator<T> iterator, int numberToSkip) {
    899        checkNotNull(iterator);
    900        checkArgument(numberToSkip >= 0, "number to skip cannot be negative");
    901
    902        int i;
    903        for (i = 0; i < numberToSkip && iterator.hasNext(); i++) {
    904          iterator.next();
    905        }
    906        return i;
    907      }
    908
    909      /**
    910       * Creates an iterator returning the first {@code limitSize} elements of the
    911       * given iterator. If the original iterator does not contain that many
    912       * elements, the returned iterator will have the same behavior as the original
    913       * iterator. The returned iterator supports {@code remove()} if the original
    914       * iterator does.
    915       *
    916       * @param iterator the iterator to limit
    917       * @param limitSize the maximum number of elements in the returned iterator
    918       * @throws IllegalArgumentException if {@code limitSize} is negative
    919       * @since 3.0
    920       */
    921      public static <T> Iterator<T> limit(
    922          final Iterator<T> iterator, final int limitSize) {
    923        checkNotNull(iterator);
    924        checkArgument(limitSize >= 0, "limit is negative");
    925        return new Iterator<T>() {
    926          private int count;
    927
    928          @Override
    929          public boolean hasNext() {
    930            return count < limitSize && iterator.hasNext();
    931          }
    932
    933          @Override
    934          public T next() {
    935            if (!hasNext()) {
    936              throw new NoSuchElementException();
    937            }
    938            count++;
    939            return iterator.next();
    940          }
    941
    942          @Override
    943          public void remove() {
    944            iterator.remove();
    945          }
    946        };
    947      }
    948
    949      /**
    950       * Returns a view of the supplied {@code iterator} that removes each element
    951       * from the supplied {@code iterator} as it is returned.
    952       *
    953       * <p>The provided iterator must support {@link Iterator#remove()} or
    954       * else the returned iterator will fail on the first call to {@code
    955       * next}.
    956       *
    957       * @param iterator the iterator to remove and return elements from
    958       * @return an iterator that removes and returns elements from the
    959       *     supplied iterator
    960       * @since 2.0
    961       */
    962      public static <T> Iterator<T> consumingIterator(final Iterator<T> iterator) {
    963        checkNotNull(iterator);
    964        return new UnmodifiableIterator<T>() {
    965          @Override
    966          public boolean hasNext() {
    967            return iterator.hasNext();
    968          }
    969
    970          @Override
    971          public T next() {
    972            T next = iterator.next();
    973            iterator.remove();
    974            return next;
    975          }
    976        };
    977      }
    978
    979      // Methods only in Iterators, not in Iterables
    980
    981      /**
    982       * Clears the iterator using its remove method.
    983       */
    984      static void clear(Iterator<?> iterator) {
    985        checkNotNull(iterator);
    986        while (iterator.hasNext()) {
    987          iterator.next();
    988          iterator.remove();
    989        }
    990      }
    991
    992      /**
    993       * Returns an iterator containing the elements of {@code array} in order. The
    994       * returned iterator is a view of the array; subsequent changes to the array
    995       * will be reflected in the iterator.
    996       *
    997       * <p><b>Note:</b> It is often preferable to represent your data using a
    998       * collection type, for example using {@link Arrays#asList(Object[])}, making
    999       * this method unnecessary.
    1000       *
    1001       * <p>The {@code Iterable} equivalent of this method is either {@link
    1002       * Arrays#asList(Object[])}, {@link ImmutableList#copyOf(Object[])}},
    1003       * or {@link ImmutableList#of}.
    1004       */
    1005      public static <T> UnmodifiableIterator<T> forArray(final T... array) {
    1006        // TODO(kevinb): compare performance with Arrays.asList(array).iterator().
    1007        checkNotNull(array);  // eager for GWT.
    1008        return new AbstractIndexedListIterator<T>(array.length) {
    1009          @Override protected T get(int index) {
    1010            return array[index];
    1011          }
    1012        };
    1013      }
    1014
    1015      /**
    1016       * Returns an iterator containing the elements in the specified range of
    1017       * {@code array} in order. The returned iterator is a view of the array;
    1018       * subsequent changes to the array will be reflected in the iterator.
    1019       *
    1020       * <p>The {@code Iterable} equivalent of this method is {@code
    1021       * Arrays.asList(array).subList(offset, offset + length)}.
    1022       *
    1023       * @param array array to read elements out of
    1024       * @param offset index of first array element to retrieve
    1025       * @param length number of elements in iteration
    1026       * @throws IndexOutOfBoundsException if {@code offset} is negative, {@code
    1027       *     length} is negative, or {@code offset + length > array.length}
    1028       */
    1029      static <T> UnmodifiableIterator<T> forArray(
    1030          final T[] array, final int offset, int length) {
    1031        checkArgument(length >= 0);
    1032        int end = offset + length;
    1033
    1034        // Technically we should give a slightly more descriptive error on overflow
    1035        Preconditions.checkPositionIndexes(offset, end, array.length);
    1036
    1037        /*
    1038         * We can't use call the two-arg constructor with arguments (offset, end)
    1039         * because the returned Iterator is a ListIterator that may be moved back
    1040         * past the beginning of the iteration.
    1041         */
    1042        return new AbstractIndexedListIterator<T>(length) {
    1043          @Override protected T get(int index) {
    1044            return array[offset + index];
    1045          }
    1046        };
    1047      }
    1048
    1049      /**
    1050       * Returns an iterator containing only {@code value}.
    1051       *
    1052       * <p>The {@link Iterable} equivalent of this method is {@link
    1053       * Collections#singleton}.
    1054       */
    1055      public static <T> UnmodifiableIterator<T> singletonIterator(
    1056          @Nullable final T value) {
    1057        return new UnmodifiableIterator<T>() {
    1058          boolean done;
    1059          @Override
    1060          public boolean hasNext() {
    1061            return !done;
    1062          }
    1063          @Override
    1064          public T next() {
    1065            if (done) {
    1066              throw new NoSuchElementException();
    1067            }
    1068            done = true;
    1069            return value;
    1070          }
    1071        };
    1072      }
    1073
    1074      /**
    1075       * Adapts an {@code Enumeration} to the {@code Iterator} interface.
    1076       *
    1077       * <p>This method has no equivalent in {@link Iterables} because viewing an
    1078       * {@code Enumeration} as an {@code Iterable} is impossible. However, the
    1079       * contents can be <i>copied</i> into a collection using {@link
    1080       * Collections#list}.
    1081       */
    1082      public static <T> UnmodifiableIterator<T> forEnumeration(
    1083          final Enumeration<T> enumeration) {
    1084        checkNotNull(enumeration);
    1085        return new UnmodifiableIterator<T>() {
    1086          @Override
    1087          public boolean hasNext() {
    1088            return enumeration.hasMoreElements();
    1089          }
    1090          @Override
    1091          public T next() {
    1092            return enumeration.nextElement();
    1093          }
    1094        };
    1095      }
    1096
    1097      /**
    1098       * Adapts an {@code Iterator} to the {@code Enumeration} interface.
    1099       *
    1100       * <p>The {@code Iterable} equivalent of this method is either {@link
    1101       * Collections#enumeration} (if you have a {@link Collection}), or
    1102       * {@code Iterators.asEnumeration(collection.iterator())}.
    1103       */
    1104      public static <T> Enumeration<T> asEnumeration(final Iterator<T> iterator) {
    1105        checkNotNull(iterator);
    1106        return new Enumeration<T>() {
    1107          @Override
    1108          public boolean hasMoreElements() {
    1109            return iterator.hasNext();
    1110          }
    1111          @Override
    1112          public T nextElement() {
    1113            return iterator.next();
    1114          }
    1115        };
    1116      }
    1117
    1118      /**
    1119       * Implementation of PeekingIterator that avoids peeking unless necessary.
    1120       */
    1121      private static class PeekingImpl<E> implements PeekingIterator<E> {
    1122
    1123        private final Iterator<? extends E> iterator;
    1124        private boolean hasPeeked;
    1125        private E peekedElement;
    1126
    1127        public PeekingImpl(Iterator<? extends E> iterator) {
    1128          this.iterator = checkNotNull(iterator);
    1129        }
    1130
    1131        @Override
    1132        public boolean hasNext() {
    1133          return hasPeeked || iterator.hasNext();
    1134        }
    1135
    1136        @Override
    1137        public E next() {
    1138          if (!hasPeeked) {
    1139            return iterator.next();
    1140          }
    1141          E result = peekedElement;
    1142          hasPeeked = false;
    1143          peekedElement = null;
    1144          return result;
    1145        }
    1146
    1147        @Override
    1148        public void remove() {
    1149          checkState(!hasPeeked, "Can't remove after you've peeked at next");
    1150          iterator.remove();
    1151        }
    1152
    1153        @Override
    1154        public E peek() {
    1155          if (!hasPeeked) {
    1156            peekedElement = iterator.next();
    1157            hasPeeked = true;
    1158          }
    1159          return peekedElement;
    1160        }
    1161      }
    1162
    1163      /**
    1164       * Returns a {@code PeekingIterator} backed by the given iterator.
    1165       *
    1166       * <p>Calls to the {@code peek} method with no intervening calls to {@code
    1167       * next} do not affect the iteration, and hence return the same object each
    1168       * time. A subsequent call to {@code next} is guaranteed to return the same
    1169       * object again. For example: <pre>   {@code
    1170       *
    1171       *   PeekingIterator<String> peekingIterator =
    1172       *       Iterators.peekingIterator(Iterators.forArray("a", "b"));
    1173       *   String a1 = peekingIterator.peek(); // returns "a"
    1174       *   String a2 = peekingIterator.peek(); // also returns "a"
    1175       *   String a3 = peekingIterator.next(); // also returns "a"}</pre>
    1176       *
    1177       * Any structural changes to the underlying iteration (aside from those
    1178       * performed by the iterator's own {@link PeekingIterator#remove()} method)
    1179       * will leave the iterator in an undefined state.
    1180       *
    1181       * <p>The returned iterator does not support removal after peeking, as
    1182       * explained by {@link PeekingIterator#remove()}.
    1183       *
    1184       * <p>Note: If the given iterator is already a {@code PeekingIterator},
    1185       * it <i>might</i> be returned to the caller, although this is neither
    1186       * guaranteed to occur nor required to be consistent.  For example, this
    1187       * method <i>might</i> choose to pass through recognized implementations of
    1188       * {@code PeekingIterator} when the behavior of the implementation is
    1189       * known to meet the contract guaranteed by this method.
    1190       *
    1191       * <p>There is no {@link Iterable} equivalent to this method, so use this
    1192       * method to wrap each individual iterator as it is generated.
    1193       *
    1194       * @param iterator the backing iterator. The {@link PeekingIterator} assumes
    1195       *     ownership of this iterator, so users should cease making direct calls
    1196       *     to it after calling this method.
    1197       * @return a peeking iterator backed by that iterator. Apart from the
    1198       *     additional {@link PeekingIterator#peek()} method, this iterator behaves
    1199       *     exactly the same as {@code iterator}.
    1200       */
    1201      public static <T> PeekingIterator<T> peekingIterator(
    1202          Iterator<? extends T> iterator) {
    1203        if (iterator instanceof PeekingImpl) {
    1204          // Safe to cast <? extends T> to <T> because PeekingImpl only uses T
    1205          // covariantly (and cannot be subclassed to add non-covariant uses).
    1206          @SuppressWarnings("unchecked")
    1207          PeekingImpl<T> peeking = (PeekingImpl<T>) iterator;
    1208          return peeking;
    1209        }
    1210        return new PeekingImpl<T>(iterator);
    1211      }
    1212
    1213      /**
    1214       * Simply returns its argument.
    1215       *
    1216       * @deprecated no need to use this
    1217       * @since 10.0
    1218       */
    1219      @Deprecated public static <T> PeekingIterator<T> peekingIterator(
    1220          PeekingIterator<T> iterator) {
    1221        return checkNotNull(iterator);
    1222      }
    1223    }