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 }