1 /*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.base.Preconditions.checkState;
22 import static com.google.common.base.Predicates.instanceOf;
23 import static com.google.common.collect.CollectPreconditions.checkRemove;
24
25 import com.google.common.annotations.Beta;
26 import com.google.common.annotations.GwtCompatible;
27 import com.google.common.annotations.GwtIncompatible;
28 import com.google.common.base.Function;
29 import com.google.common.base.Objects;
30 import com.google.common.base.Optional;
31 import com.google.common.base.Preconditions;
32 import com.google.common.base.Predicate;
33 import com.google.common.primitives.Ints;
34 import com.google.errorprone.annotations.CanIgnoreReturnValue;
35 import java.util.ArrayDeque;
36 import java.util.Arrays;
37 import java.util.Collection;
38 import java.util.Collections;
39 import java.util.Comparator;
40 import java.util.Deque;
41 import java.util.Enumeration;
42 import java.util.Iterator;
43 import java.util.List;
44 import java.util.ListIterator;
45 import java.util.NoSuchElementException;
46 import java.util.PriorityQueue;
47 import java.util.Queue;
48 import org.checkerframework.checker.nullness.qual.Nullable;
49
50 /**
51 * This class contains static utility methods that operate on or return objects of type {@link
52 * Iterator}. Except as noted, each method has a corresponding {@link Iterable}-based method in the
53 * {@link Iterables} class.
54 *
55 * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterators produced in this class
56 * are <i>lazy</i>, which means that they only advance the backing iteration when absolutely
57 * necessary.
58 *
59 * <p>See the Guava User Guide section on <a href=
60 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#iterables"> {@code
61 * Iterators}</a>.
62 *
63 * @author Kevin Bourrillion
64 * @author Jared Levy
65 * @since 2.0
66 */
67 @GwtCompatible(emulated = true)
68 public final class Iterators {
69 private Iterators() {}
70
71 /**
72 * Returns the empty iterator.
73 *
74 * <p>The {@link Iterable} equivalent of this method is {@link ImmutableSet#of()}.
75 */
76 static <T> UnmodifiableIterator<T> emptyIterator() {
77 return emptyListIterator();
78 }
79
80 /**
81 * Returns the empty iterator.
82 *
83 * <p>The {@link Iterable} equivalent of this method is {@link ImmutableSet#of()}.
84 */
85 // Casting to any type is safe since there are no actual elements.
86 @SuppressWarnings("unchecked")
87 static <T> UnmodifiableListIterator<T> emptyListIterator() {
88 return (UnmodifiableListIterator<T>) ArrayItr.EMPTY;
89 }
90
91 /**
92 * This is an enum singleton rather than an anonymous class so ProGuard can figure out it's only
93 * referenced by emptyModifiableIterator().
94 */
95 private enum EmptyModifiableIterator implements Iterator<Object> {
96 INSTANCE;
97
98 @Override
99 public boolean hasNext() {
100 return false;
101 }
102
103 @Override
104 public Object next() {
105 throw new NoSuchElementException();
106 }
107
108 @Override
109 public void remove() {
110 checkRemove(false);
111 }
112 }
113
114 /**
115 * Returns the empty {@code Iterator} that throws {@link IllegalStateException} instead of {@link
116 * UnsupportedOperationException} on a call to {@link Iterator#remove()}.
117 */
118 // Casting to any type is safe since there are no actual elements.
119 @SuppressWarnings("unchecked")
120 static <T> Iterator<T> emptyModifiableIterator() {
121 return (Iterator<T>) EmptyModifiableIterator.INSTANCE;
122 }
123
124 /** Returns an unmodifiable view of {@code iterator}. */
125 public static <T> UnmodifiableIterator<T> unmodifiableIterator(
126 final Iterator<? extends T> iterator) {
127 checkNotNull(iterator);
128 if (iterator instanceof UnmodifiableIterator) {
129 @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe
130 UnmodifiableIterator<T> result = (UnmodifiableIterator<T>) iterator;
131 return result;
132 }
133 return new UnmodifiableIterator<T>() {
134 @Override
135 public boolean hasNext() {
136 return iterator.hasNext();
137 }
138
139 @Override
140 public T next() {
141 return iterator.next();
142 }
143 };
144 }
145
146 /**
147 * Simply returns its argument.
148 *
149 * @deprecated no need to use this
150 * @since 10.0
151 */
152 @Deprecated
153 public static <T> UnmodifiableIterator<T> unmodifiableIterator(UnmodifiableIterator<T> iterator) {
154 return checkNotNull(iterator);
155 }
156
157 /**
158 * Returns the number of elements remaining in {@code iterator}. The iterator will be left
159 * exhausted: its {@code hasNext()} method will return {@code false}.
160 */
161 public static int size(Iterator<?> iterator) {
162 long count = 0L;
163 while (iterator.hasNext()) {
164 iterator.next();
165 count++;
166 }
167 return Ints.saturatedCast(count);
168 }
169
170 /** Returns {@code true} if {@code iterator} contains {@code element}. */
171 public static boolean contains(Iterator<?> iterator, @Nullable Object element) {
172 if (element == null) {
173 while (iterator.hasNext()) {
174 if (iterator.next() == null) {
175 return true;
176 }
177 }
178 } else {
179 while (iterator.hasNext()) {
180 if (element.equals(iterator.next())) {
181 return true;
182 }
183 }
184 }
185 return false;
186 }
187
188 /**
189 * Traverses an iterator and removes every element that belongs to the provided collection. The
190 * iterator will be left exhausted: its {@code hasNext()} method will return {@code false}.
191 *
192 * @param removeFrom the iterator to (potentially) remove elements from
193 * @param elementsToRemove the elements to remove
194 * @return {@code true} if any element was removed from {@code iterator}
195 */
196 @CanIgnoreReturnValue
197 public static boolean removeAll(Iterator<?> removeFrom, Collection<?> elementsToRemove) {
198 checkNotNull(elementsToRemove);
199 boolean result = false;
200 while (removeFrom.hasNext()) {
201 if (elementsToRemove.contains(removeFrom.next())) {
202 removeFrom.remove();
203 result = true;
204 }
205 }
206 return result;
207 }
208
209 /**
210 * Removes every element that satisfies the provided predicate from the iterator. The iterator
211 * will be left exhausted: its {@code hasNext()} method will return {@code false}.
212 *
213 * @param removeFrom the iterator to (potentially) remove elements from
214 * @param predicate a predicate that determines whether an element should be removed
215 * @return {@code true} if any elements were removed from the iterator
216 * @since 2.0
217 */
218 @CanIgnoreReturnValue
219 public static <T> boolean removeIf(Iterator<T> removeFrom, Predicate<? super T> predicate) {
220 checkNotNull(predicate);
221 boolean modified = false;
222 while (removeFrom.hasNext()) {
223 if (predicate.apply(removeFrom.next())) {
224 removeFrom.remove();
225 modified = true;
226 }
227 }
228 return modified;
229 }
230
231 /**
232 * Traverses an iterator and removes every element that does not belong to the provided
233 * collection. The iterator will be left exhausted: its {@code hasNext()} method will return
234 * {@code false}.
235 *
236 * @param removeFrom the iterator to (potentially) remove elements from
237 * @param elementsToRetain the elements to retain
238 * @return {@code true} if any element was removed from {@code iterator}
239 */
240 @CanIgnoreReturnValue
241 public static boolean retainAll(Iterator<?> removeFrom, Collection<?> elementsToRetain) {
242 checkNotNull(elementsToRetain);
243 boolean result = false;
244 while (removeFrom.hasNext()) {
245 if (!elementsToRetain.contains(removeFrom.next())) {
246 removeFrom.remove();
247 result = true;
248 }
249 }
250 return result;
251 }
252
253 /**
254 * Determines whether two iterators contain equal elements in the same order. More specifically,
255 * this method returns {@code true} if {@code iterator1} and {@code iterator2} contain the same
256 * number of elements and every element of {@code iterator1} is equal to the corresponding element
257 * of {@code iterator2}.
258 *
259 * <p>Note that this will modify the supplied iterators, since they will have been advanced some
260 * number of elements forward.
261 */
262 public static boolean elementsEqual(Iterator<?> iterator1, Iterator<?> iterator2) {
263 while (iterator1.hasNext()) {
264 if (!iterator2.hasNext()) {
265 return false;
266 }
267 Object o1 = iterator1.next();
268 Object o2 = iterator2.next();
269 if (!Objects.equal(o1, o2)) {
270 return false;
271 }
272 }
273 return !iterator2.hasNext();
274 }
275
276 /**
277 * Returns a string representation of {@code iterator}, with the format {@code [e1, e2, ..., en]}.
278 * The iterator will be left exhausted: its {@code hasNext()} method will return {@code false}.
279 */
280 public static String toString(Iterator<?> iterator) {
281 StringBuilder sb = new StringBuilder().append('[');
282 boolean first = true;
283 while (iterator.hasNext()) {
284 if (!first) {
285 sb.append(", ");
286 }
287 first = false;
288 sb.append(iterator.next());
289 }
290 return sb.append(']').toString();
291 }
292
293 /**
294 * Returns the single element contained in {@code iterator}.
295 *
296 * @throws NoSuchElementException if the iterator is empty
297 * @throws IllegalArgumentException if the iterator contains multiple elements. The state of the
298 * iterator is unspecified.
299 */
300 public static <T> T getOnlyElement(Iterator<T> iterator) {
301 T first = iterator.next();
302 if (!iterator.hasNext()) {
303 return first;
304 }
305
306 StringBuilder sb = new StringBuilder().append("expected one element but was: <").append(first);
307 for (int i = 0; i < 4 && iterator.hasNext(); i++) {
308 sb.append(", ").append(iterator.next());
309 }
310 if (iterator.hasNext()) {
311 sb.append(", ...");
312 }
313 sb.append('>');
314
315 throw new IllegalArgumentException(sb.toString());
316 }
317
318 /**
319 * Returns the single element contained in {@code iterator}, or {@code defaultValue} if the
320 * iterator is empty.
321 *
322 * @throws IllegalArgumentException if the iterator contains multiple elements. The state of the
323 * iterator is unspecified.
324 */
325 public static <T> @Nullable T getOnlyElement(
326 Iterator<? extends T> iterator, @Nullable T defaultValue) {
327 return iterator.hasNext() ? getOnlyElement(iterator) : defaultValue;
328 }
329
330 /**
331 * Copies an iterator's elements into an array. The iterator will be left exhausted: its {@code
332 * hasNext()} method will return {@code false}.
333 *
334 * @param iterator the iterator to copy
335 * @param type the type of the elements
336 * @return a newly-allocated array into which all the elements of the iterator have been copied
337 */
338 @GwtIncompatible // Array.newInstance(Class, int)
339 public static <T> T[] toArray(Iterator<? extends T> iterator, Class<T> type) {
340 List<T> list = Lists.newArrayList(iterator);
341 return Iterables.toArray(list, type);
342 }
343
344 /**
345 * Adds all elements in {@code iterator} to {@code collection}. The iterator will be left
346 * exhausted: its {@code hasNext()} method will return {@code false}.
347 *
348 * @return {@code true} if {@code collection} was modified as a result of this operation
349 */
350 @CanIgnoreReturnValue
351 public static <T> boolean addAll(Collection<T> addTo, Iterator<? extends T> iterator) {
352 checkNotNull(addTo);
353 checkNotNull(iterator);
354 boolean wasModified = false;
355 while (iterator.hasNext()) {
356 wasModified |= addTo.add(iterator.next());
357 }
358 return wasModified;
359 }
360
361 /**
362 * Returns the number of elements in the specified iterator that equal the specified object. The
363 * iterator will be left exhausted: its {@code hasNext()} method will return {@code false}.
364 *
365 * @see Collections#frequency
366 */
367 public static int frequency(Iterator<?> iterator, @Nullable Object element) {
368 int count = 0;
369 while (contains(iterator, element)) {
370 // Since it lives in the same class, we know contains gets to the element and then stops,
371 // though that isn't currently publicly documented.
372 count++;
373 }
374 return count;
375 }
376
377 /**
378 * Returns an iterator that cycles indefinitely over the elements of {@code iterable}.
379 *
380 * <p>The returned iterator supports {@code remove()} if the provided iterator does. After {@code
381 * remove()} is called, subsequent cycles omit the removed element, which is no longer in {@code
382 * iterable}. The iterator's {@code hasNext()} method returns {@code true} until {@code iterable}
383 * is empty.
384 *
385 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an infinite loop. You
386 * should use an explicit {@code break} or be certain that you will eventually remove all the
387 * elements.
388 */
389 public static <T> Iterator<T> cycle(final Iterable<T> iterable) {
390 checkNotNull(iterable);
391 return new Iterator<T>() {
392 Iterator<T> iterator = emptyModifiableIterator();
393
394 @Override
395 public boolean hasNext() {
396 /*
397 * Don't store a new Iterator until we know the user can't remove() the last returned
398 * element anymore. Otherwise, when we remove from the old iterator, we may be invalidating
399 * the new one. The result is a ConcurrentModificationException or other bad behavior.
400 *
401 * (If we decide that we really, really hate allocating two Iterators per cycle instead of
402 * one, we can optimistically store the new Iterator and then be willing to throw it out if
403 * the user calls remove().)
404 */
405 return iterator.hasNext() || iterable.iterator().hasNext();
406 }
407
408 @Override
409 public T next() {
410 if (!iterator.hasNext()) {
411 iterator = iterable.iterator();
412 if (!iterator.hasNext()) {
413 throw new NoSuchElementException();
414 }
415 }
416 return iterator.next();
417 }
418
419 @Override
420 public void remove() {
421 iterator.remove();
422 }
423 };
424 }
425
426 /**
427 * Returns an iterator that cycles indefinitely over the provided elements.
428 *
429 * <p>The returned iterator supports {@code remove()}. After {@code remove()} is called,
430 * subsequent cycles omit the removed element, but {@code elements} does not change. The
431 * iterator's {@code hasNext()} method returns {@code true} until all of the original elements
432 * have been removed.
433 *
434 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an infinite loop. You
435 * should use an explicit {@code break} or be certain that you will eventually remove all the
436 * elements.
437 */
438 @SafeVarargs
439 public static <T> Iterator<T> cycle(T... elements) {
440 return cycle(Lists.newArrayList(elements));
441 }
442
443 /**
444 * Returns an Iterator that walks the specified array, nulling out elements behind it. This can
445 * avoid memory leaks when an element is no longer necessary.
446 *
447 * <p>This is mainly just to avoid the intermediate ArrayDeque in ConsumingQueueIterator.
448 */
449 private static <T> Iterator<T> consumingForArray(final T... elements) {
450 return new UnmodifiableIterator<T>() {
451 int index = 0;
452
453 @Override
454 public boolean hasNext() {
455 return index < elements.length;
456 }
457
458 @Override
459 public T next() {
460 if (!hasNext()) {
461 throw new NoSuchElementException();
462 }
463 T result = elements[index];
464 elements[index] = null;
465 index++;
466 return result;
467 }
468 };
469 }
470
471 /**
472 * Combines two iterators into a single iterator. The returned iterator iterates across the
473 * elements in {@code a}, followed by the elements in {@code b}. The source iterators are not
474 * polled until necessary.
475 *
476 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator
477 * supports it.
478 */
479 public static <T> Iterator<T> concat(Iterator<? extends T> a, Iterator<? extends T> b) {
480 checkNotNull(a);
481 checkNotNull(b);
482 return concat(consumingForArray(a, b));
483 }
484
485 /**
486 * Combines three iterators into a single iterator. The returned iterator iterates across the
487 * elements in {@code a}, followed by the elements in {@code b}, followed by the elements in
488 * {@code c}. The source iterators are not polled until necessary.
489 *
490 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator
491 * supports it.
492 */
493 public static <T> Iterator<T> concat(
494 Iterator<? extends T> a, Iterator<? extends T> b, Iterator<? extends T> c) {
495 checkNotNull(a);
496 checkNotNull(b);
497 checkNotNull(c);
498 return concat(consumingForArray(a, b, c));
499 }
500
501 /**
502 * Combines four iterators into a single iterator. The returned iterator iterates across the
503 * elements in {@code a}, followed by the elements in {@code b}, followed by the elements in
504 * {@code c}, followed by the elements in {@code d}. The source iterators are not polled until
505 * necessary.
506 *
507 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator
508 * supports it.
509 */
510 public static <T> Iterator<T> concat(
511 Iterator<? extends T> a,
512 Iterator<? extends T> b,
513 Iterator<? extends T> c,
514 Iterator<? extends T> d) {
515 checkNotNull(a);
516 checkNotNull(b);
517 checkNotNull(c);
518 checkNotNull(d);
519 return concat(consumingForArray(a, b, c, d));
520 }
521
522 /**
523 * Combines multiple iterators into a single iterator. The returned iterator iterates across the
524 * elements of each iterator in {@code inputs}. The input iterators are not polled until
525 * necessary.
526 *
527 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator
528 * supports it.
529 *
530 * @throws NullPointerException if any of the provided iterators is null
531 */
532 public static <T> Iterator<T> concat(Iterator<? extends T>... inputs) {
533 return concatNoDefensiveCopy(Arrays.copyOf(inputs, inputs.length));
534 }
535
536 /**
537 * Combines multiple iterators into a single iterator. The returned iterator iterates across the
538 * elements of each iterator in {@code inputs}. The input iterators are not polled until
539 * necessary.
540 *
541 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator
542 * supports it. The methods of the returned iterator may throw {@code NullPointerException} if any
543 * of the input iterators is null.
544 */
545 public static <T> Iterator<T> concat(Iterator<? extends Iterator<? extends T>> inputs) {
546 return new ConcatenatedIterator<T>(inputs);
547 }
548
549 /** Concats a varargs array of iterators without making a defensive copy of the array. */
550 static <T> Iterator<T> concatNoDefensiveCopy(Iterator<? extends T>... inputs) {
551 for (Iterator<? extends T> input : checkNotNull(inputs)) {
552 checkNotNull(input);
553 }
554 return concat(consumingForArray(inputs));
555 }
556
557 /**
558 * Divides an iterator into unmodifiable sublists of the given size (the final list may be
559 * smaller). For example, partitioning an iterator containing {@code [a, b, c, d, e]} with a
560 * partition size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer iterator containing two
561 * inner lists of three and two elements, all in the original order.
562 *
563 * <p>The returned lists implement {@link java.util.RandomAccess}.
564 *
565 * @param iterator the iterator to return a partitioned view of
566 * @param size the desired size of each partition (the last may be smaller)
567 * @return an iterator of immutable lists containing the elements of {@code iterator} divided into
568 * partitions
569 * @throws IllegalArgumentException if {@code size} is nonpositive
570 */
571 public static <T> UnmodifiableIterator<List<T>> partition(Iterator<T> iterator, int size) {
572 return partitionImpl(iterator, size, false);
573 }
574
575 /**
576 * Divides an iterator into unmodifiable sublists of the given size, padding the final iterator
577 * with null values if necessary. For example, partitioning an iterator containing {@code [a, b,
578 * c, d, e]} with a partition size of 3 yields {@code [[a, b, c], [d, e, null]]} -- an outer
579 * iterator containing two inner lists of three elements each, all in the original order.
580 *
581 * <p>The returned lists implement {@link java.util.RandomAccess}.
582 *
583 * @param iterator the iterator to return a partitioned view of
584 * @param size the desired size of each partition
585 * @return an iterator of immutable lists containing the elements of {@code iterator} divided into
586 * partitions (the final iterable may have trailing null elements)
587 * @throws IllegalArgumentException if {@code size} is nonpositive
588 */
589 public static <T> UnmodifiableIterator<List<T>> paddedPartition(Iterator<T> iterator, int size) {
590 return partitionImpl(iterator, size, true);
591 }
592
593 private static <T> UnmodifiableIterator<List<T>> partitionImpl(
594 final Iterator<T> iterator, final int size, final boolean pad) {
595 checkNotNull(iterator);
596 checkArgument(size > 0);
597 return new UnmodifiableIterator<List<T>>() {
598 @Override
599 public boolean hasNext() {
600 return iterator.hasNext();
601 }
602
603 @Override
604 public List<T> next() {
605 if (!hasNext()) {
606 throw new NoSuchElementException();
607 }
608 Object[] array = new Object[size];
609 int count = 0;
610 for (; count < size && iterator.hasNext(); count++) {
611 array[count] = iterator.next();
612 }
613 for (int i = count; i < size; i++) {
614 array[i] = null; // for GWT
615 }
616
617 @SuppressWarnings("unchecked") // we only put Ts in it
618 List<T> list = Collections.unmodifiableList((List<T>) Arrays.asList(array));
619 return (pad || count == size) ? list : list.subList(0, count);
620 }
621 };
622 }
623
624 /**
625 * Returns a view of {@code unfiltered} containing all elements that satisfy the input predicate
626 * {@code retainIfTrue}.
627 */
628 public static <T> UnmodifiableIterator<T> filter(
629 final Iterator<T> unfiltered, final Predicate<? super T> retainIfTrue) {
630 checkNotNull(unfiltered);
631 checkNotNull(retainIfTrue);
632 return new AbstractIterator<T>() {
633 @Override
634 protected T computeNext() {
635 while (unfiltered.hasNext()) {
636 T element = unfiltered.next();
637 if (retainIfTrue.apply(element)) {
638 return element;
639 }
640 }
641 return endOfData();
642 }
643 };
644 }
645
646 /**
647 * Returns a view of {@code unfiltered} containing all elements that are of the type {@code
648 * desiredType}.
649 */
650 @SuppressWarnings("unchecked") // can cast to <T> because non-Ts are removed
651 @GwtIncompatible // Class.isInstance
652 public static <T> UnmodifiableIterator<T> filter(Iterator<?> unfiltered, Class<T> desiredType) {
653 return (UnmodifiableIterator<T>) filter(unfiltered, instanceOf(desiredType));
654 }
655
656 /**
657 * Returns {@code true} if one or more elements returned by {@code iterator} satisfy the given
658 * predicate.
659 */
660 public static <T> boolean any(Iterator<T> iterator, Predicate<? super T> predicate) {
661 return indexOf(iterator, predicate) != -1;
662 }
663
664 /**
665 * Returns {@code true} if every element returned by {@code iterator} satisfies the given
666 * predicate. If {@code iterator} is empty, {@code true} is returned.
667 */
668 public static <T> boolean all(Iterator<T> iterator, Predicate<? super T> predicate) {
669 checkNotNull(predicate);
670 while (iterator.hasNext()) {
671 T element = iterator.next();
672 if (!predicate.apply(element)) {
673 return false;
674 }
675 }
676 return true;
677 }
678
679 /**
680 * Returns the first element in {@code iterator} that satisfies the given predicate; use this
681 * method only when such an element is known to exist. If no such element is found, the iterator
682 * will be left exhausted: its {@code hasNext()} method will return {@code false}. If it is
683 * possible that <i>no</i> element will match, use {@link #tryFind} or {@link #find(Iterator,
684 * Predicate, Object)} instead.
685 *
686 * @throws NoSuchElementException if no element in {@code iterator} matches the given predicate
687 */
688 public static <T> T find(Iterator<T> iterator, Predicate<? super T> predicate) {
689 checkNotNull(iterator);
690 checkNotNull(predicate);
691 while (iterator.hasNext()) {
692 T t = iterator.next();
693 if (predicate.apply(t)) {
694 return t;
695 }
696 }
697 throw new NoSuchElementException();
698 }
699
700 /**
701 * Returns the first element in {@code iterator} that satisfies the given predicate. If no such
702 * element is found, {@code defaultValue} will be returned from this method and the iterator will
703 * be left exhausted: its {@code hasNext()} method will return {@code false}. Note that this can
704 * usually be handled more naturally using {@code tryFind(iterator, predicate).or(defaultValue)}.
705 *
706 * @since 7.0
707 */
708 public static <T> @Nullable T find(
709 Iterator<? extends T> iterator, Predicate<? super T> predicate, @Nullable T defaultValue) {
710 checkNotNull(iterator);
711 checkNotNull(predicate);
712 while (iterator.hasNext()) {
713 T t = iterator.next();
714 if (predicate.apply(t)) {
715 return t;
716 }
717 }
718 return defaultValue;
719 }
720
721 /**
722 * Returns an {@link Optional} containing the first element in {@code iterator} that satisfies the
723 * given predicate, if such an element exists. If no such element is found, an empty {@link
724 * Optional} will be returned from this method and the iterator will be left exhausted: its {@code
725 * hasNext()} method will return {@code false}.
726 *
727 * <p><b>Warning:</b> avoid using a {@code predicate} that matches {@code null}. If {@code null}
728 * is matched in {@code iterator}, a NullPointerException will be thrown.
729 *
730 * @since 11.0
731 */
732 public static <T> Optional<T> tryFind(Iterator<T> iterator, Predicate<? super T> predicate) {
733 checkNotNull(iterator);
734 checkNotNull(predicate);
735 while (iterator.hasNext()) {
736 T t = iterator.next();
737 if (predicate.apply(t)) {
738 return Optional.of(t);
739 }
740 }
741 return Optional.absent();
742 }
743
744 /**
745 * Returns the index in {@code iterator} of the first element that satisfies the provided {@code
746 * predicate}, or {@code -1} if the Iterator has no such elements.
747 *
748 * <p>More formally, returns the lowest index {@code i} such that {@code
749 * predicate.apply(Iterators.get(iterator, i))} returns {@code true}, or {@code -1} if there is no
750 * such index.
751 *
752 * <p>If -1 is returned, the iterator will be left exhausted: its {@code hasNext()} method will
753 * return {@code false}. Otherwise, the iterator will be set to the element which satisfies the
754 * {@code predicate}.
755 *
756 * @since 2.0
757 */
758 public static <T> int indexOf(Iterator<T> iterator, Predicate<? super T> predicate) {
759 checkNotNull(predicate, "predicate");
760 for (int i = 0; iterator.hasNext(); i++) {
761 T current = iterator.next();
762 if (predicate.apply(current)) {
763 return i;
764 }
765 }
766 return -1;
767 }
768
769 /**
770 * Returns a view containing the result of applying {@code function} to each element of {@code
771 * fromIterator}.
772 *
773 * <p>The returned iterator supports {@code remove()} if {@code fromIterator} does. After a
774 * successful {@code remove()} call, {@code fromIterator} no longer contains the corresponding
775 * element.
776 */
777 public static <F, T> Iterator<T> transform(
778 final Iterator<F> fromIterator, final Function<? super F, ? extends T> function) {
779 checkNotNull(function);
780 return new TransformedIterator<F, T>(fromIterator) {
781 @Override
782 T transform(F from) {
783 return function.apply(from);
784 }
785 };
786 }
787
788 /**
789 * Advances {@code iterator} {@code position + 1} times, returning the element at the {@code
790 * position}th position.
791 *
792 * @param position position of the element to return
793 * @return the element at the specified position in {@code iterator}
794 * @throws IndexOutOfBoundsException if {@code position} is negative or greater than or equal to
795 * the number of elements remaining in {@code iterator}
796 */
797 public static <T> T get(Iterator<T> iterator, int position) {
798 checkNonnegative(position);
799 int skipped = advance(iterator, position);
800 if (!iterator.hasNext()) {
801 throw new IndexOutOfBoundsException(
802 "position ("
803 + position
804 + ") must be less than the number of elements that remained ("
805 + skipped
806 + ")");
807 }
808 return iterator.next();
809 }
810
811 /**
812 * Advances {@code iterator} {@code position + 1} times, returning the element at the {@code
813 * position}th position or {@code defaultValue} otherwise.
814 *
815 * @param position position of the element to return
816 * @param defaultValue the default value to return if the iterator is empty or if {@code position}
817 * is greater than the number of elements remaining in {@code iterator}
818 * @return the element at the specified position in {@code iterator} or {@code defaultValue} if
819 * {@code iterator} produces fewer than {@code position + 1} elements.
820 * @throws IndexOutOfBoundsException if {@code position} is negative
821 * @since 4.0
822 */
823 public static <T> @Nullable T get(
824 Iterator<? extends T> iterator, int position, @Nullable T defaultValue) {
825 checkNonnegative(position);
826 advance(iterator, position);
827 return getNext(iterator, defaultValue);
828 }
829
830 static void checkNonnegative(int position) {
831 if (position < 0) {
832 throw new IndexOutOfBoundsException("position (" + position + ") must not be negative");
833 }
834 }
835
836 /**
837 * Returns the next element in {@code iterator} or {@code defaultValue} if the iterator is empty.
838 * The {@link Iterables} analog to this method is {@link Iterables#getFirst}.
839 *
840 * @param defaultValue the default value to return if the iterator is empty
841 * @return the next element of {@code iterator} or the default value
842 * @since 7.0
843 */
844 public static <T> @Nullable T getNext(Iterator<? extends T> iterator, @Nullable T defaultValue) {
845 return iterator.hasNext() ? iterator.next() : defaultValue;
846 }
847
848 /**
849 * Advances {@code iterator} to the end, returning the last element.
850 *
851 * @return the last element of {@code iterator}
852 * @throws NoSuchElementException if the iterator is empty
853 */
854 public static <T> T getLast(Iterator<T> iterator) {
855 while (true) {
856 T current = iterator.next();
857 if (!iterator.hasNext()) {
858 return current;
859 }
860 }
861 }
862
863 /**
864 * Advances {@code iterator} to the end, returning the last element or {@code defaultValue} if the
865 * iterator is empty.
866 *
867 * @param defaultValue the default value to return if the iterator is empty
868 * @return the last element of {@code iterator}
869 * @since 3.0
870 */
871 public static <T> @Nullable T getLast(Iterator<? extends T> iterator, @Nullable T defaultValue) {
872 return iterator.hasNext() ? getLast(iterator) : defaultValue;
873 }
874
875 /**
876 * Calls {@code next()} on {@code iterator}, either {@code numberToAdvance} times or until {@code
877 * hasNext()} returns {@code false}, whichever comes first.
878 *
879 * @return the number of elements the iterator was advanced
880 * @since 13.0 (since 3.0 as {@code Iterators.skip})
881 */
882 @CanIgnoreReturnValue
883 public static int advance(Iterator<?> iterator, int numberToAdvance) {
884 checkNotNull(iterator);
885 checkArgument(numberToAdvance >= 0, "numberToAdvance must be nonnegative");
886
887 int i;
888 for (i = 0; i < numberToAdvance && iterator.hasNext(); i++) {
889 iterator.next();
890 }
891 return i;
892 }
893
894 /**
895 * Returns a view containing the first {@code limitSize} elements of {@code iterator}. If {@code
896 * iterator} contains fewer than {@code limitSize} elements, the returned view contains all of its
897 * elements. The returned iterator supports {@code remove()} if {@code iterator} does.
898 *
899 * @param iterator the iterator to limit
900 * @param limitSize the maximum number of elements in the returned iterator
901 * @throws IllegalArgumentException if {@code limitSize} is negative
902 * @since 3.0
903 */
904 public static <T> Iterator<T> limit(final Iterator<T> iterator, final int limitSize) {
905 checkNotNull(iterator);
906 checkArgument(limitSize >= 0, "limit is negative");
907 return new Iterator<T>() {
908 private int count;
909
910 @Override
911 public boolean hasNext() {
912 return count < limitSize && iterator.hasNext();
913 }
914
915 @Override
916 public T next() {
917 if (!hasNext()) {
918 throw new NoSuchElementException();
919 }
920 count++;
921 return iterator.next();
922 }
923
924 @Override
925 public void remove() {
926 iterator.remove();
927 }
928 };
929 }
930
931 /**
932 * Returns a view of the supplied {@code iterator} that removes each element from the supplied
933 * {@code iterator} as it is returned.
934 *
935 * <p>The provided iterator must support {@link Iterator#remove()} or else the returned iterator
936 * will fail on the first call to {@code next}.
937 *
938 * @param iterator the iterator to remove and return elements from
939 * @return an iterator that removes and returns elements from the supplied iterator
940 * @since 2.0
941 */
942 public static <T> Iterator<T> consumingIterator(final Iterator<T> iterator) {
943 checkNotNull(iterator);
944 return new UnmodifiableIterator<T>() {
945 @Override
946 public boolean hasNext() {
947 return iterator.hasNext();
948 }
949
950 @Override
951 public T next() {
952 T next = iterator.next();
953 iterator.remove();
954 return next;
955 }
956
957 @Override
958 public String toString() {
959 return "Iterators.consumingIterator(...)";
960 }
961 };
962 }
963
964 /**
965 * Deletes and returns the next value from the iterator, or returns {@code null} if there is no
966 * such value.
967 */
968 static <T> @Nullable T pollNext(Iterator<T> iterator) {
969 if (iterator.hasNext()) {
970 T result = iterator.next();
971 iterator.remove();
972 return result;
973 } else {
974 return null;
975 }
976 }
977
978 // Methods only in Iterators, not in Iterables
979
980 /** Clears the iterator using its remove method. */
981 static void clear(Iterator<?> iterator) {
982 checkNotNull(iterator);
983 while (iterator.hasNext()) {
984 iterator.next();
985 iterator.remove();
986 }
987 }
988
989 /**
990 * Returns an iterator containing the elements of {@code array} in order. The returned iterator is
991 * a view of the array; subsequent changes to the array will be reflected in the iterator.
992 *
993 * <p><b>Note:</b> It is often preferable to represent your data using a collection type, for
994 * example using {@link Arrays#asList(Object[])}, making this method unnecessary.
995 *
996 * <p>The {@code Iterable} equivalent of this method is either {@link Arrays#asList(Object[])},
997 * {@link ImmutableList#copyOf(Object[])}}, or {@link ImmutableList#of}.
998 */
999 @SafeVarargs
1000 public static <T> UnmodifiableIterator<T> forArray(final T... array) {
1001 return forArray(array, 0, array.length, 0);
1002 }
1003
1004 /**
1005 * Returns a list iterator containing the elements in the specified range of {@code array} in
1006 * order, starting at the specified index.
1007 *
1008 * <p>The {@code Iterable} equivalent of this method is {@code
1009 * Arrays.asList(array).subList(offset, offset + length).listIterator(index)}.
1010 */
1011 static <T> UnmodifiableListIterator<T> forArray(
1012 final T[] array, final int offset, int length, int index) {
1013 checkArgument(length >= 0);
1014 int end = offset + length;
1015
1016 // Technically we should give a slightly more descriptive error on overflow
1017 Preconditions.checkPositionIndexes(offset, end, array.length);
1018 Preconditions.checkPositionIndex(index, length);
1019 if (length == 0) {
1020 return emptyListIterator();
1021 }
1022 return new ArrayItr<T>(array, offset, length, index);
1023 }
1024
1025 private static final class ArrayItr<T> extends AbstractIndexedListIterator<T> {
1026 static final UnmodifiableListIterator<Object> EMPTY = new ArrayItr<>(new Object[0], 0, 0, 0);
1027
1028 private final T[] array;
1029 private final int offset;
1030
1031 ArrayItr(T[] array, int offset, int length, int index) {
1032 super(length, index);
1033 this.array = array;
1034 this.offset = offset;
1035 }
1036
1037 @Override
1038 protected T get(int index) {
1039 return array[offset + index];
1040 }
1041 }
1042
1043 /**
1044 * Returns an iterator containing only {@code value}.
1045 *
1046 * <p>The {@link Iterable} equivalent of this method is {@link Collections#singleton}.
1047 */
1048 public static <T> UnmodifiableIterator<T> singletonIterator(final @Nullable T value) {
1049 return new UnmodifiableIterator<T>() {
1050 boolean done;
1051
1052 @Override
1053 public boolean hasNext() {
1054 return !done;
1055 }
1056
1057 @Override
1058 public T next() {
1059 if (done) {
1060 throw new NoSuchElementException();
1061 }
1062 done = true;
1063 return value;
1064 }
1065 };
1066 }
1067
1068 /**
1069 * Adapts an {@code Enumeration} to the {@code Iterator} interface.
1070 *
1071 * <p>This method has no equivalent in {@link Iterables} because viewing an {@code Enumeration} as
1072 * an {@code Iterable} is impossible. However, the contents can be <i>copied</i> into a collection
1073 * using {@link Collections#list}.
1074 *
1075 * <p><b>Java 9 users:</b> use {@code enumeration.asIterator()} instead, unless it is important to
1076 * return an {@code UnmodifiableIterator} instead of a plain {@code Iterator}.
1077 */
1078 public static <T> UnmodifiableIterator<T> forEnumeration(final Enumeration<T> enumeration) {
1079 checkNotNull(enumeration);
1080 return new UnmodifiableIterator<T>() {
1081 @Override
1082 public boolean hasNext() {
1083 return enumeration.hasMoreElements();
1084 }
1085
1086 @Override
1087 public T next() {
1088 return enumeration.nextElement();
1089 }
1090 };
1091 }
1092
1093 /**
1094 * Adapts an {@code Iterator} to the {@code Enumeration} interface.
1095 *
1096 * <p>The {@code Iterable} equivalent of this method is either {@link Collections#enumeration} (if
1097 * you have a {@link Collection}), or {@code Iterators.asEnumeration(collection.iterator())}.
1098 */
1099 public static <T> Enumeration<T> asEnumeration(final Iterator<T> iterator) {
1100 checkNotNull(iterator);
1101 return new Enumeration<T>() {
1102 @Override
1103 public boolean hasMoreElements() {
1104 return iterator.hasNext();
1105 }
1106
1107 @Override
1108 public T nextElement() {
1109 return iterator.next();
1110 }
1111 };
1112 }
1113
1114 /** Implementation of PeekingIterator that avoids peeking unless necessary. */
1115 private static class PeekingImpl<E> implements PeekingIterator<E> {
1116
1117 private final Iterator<? extends E> iterator;
1118 private boolean hasPeeked;
1119 private @Nullable E peekedElement;
1120
1121 public PeekingImpl(Iterator<? extends E> iterator) {
1122 this.iterator = checkNotNull(iterator);
1123 }
1124
1125 @Override
1126 public boolean hasNext() {
1127 return hasPeeked || iterator.hasNext();
1128 }
1129
1130 @Override
1131 public E next() {
1132 if (!hasPeeked) {
1133 return iterator.next();
1134 }
1135 E result = peekedElement;
1136 hasPeeked = false;
1137 peekedElement = null;
1138 return result;
1139 }
1140
1141 @Override
1142 public void remove() {
1143 checkState(!hasPeeked, "Can't remove after you've peeked at next");
1144 iterator.remove();
1145 }
1146
1147 @Override
1148 public E peek() {
1149 if (!hasPeeked) {
1150 peekedElement = iterator.next();
1151 hasPeeked = true;
1152 }
1153 return peekedElement;
1154 }
1155 }
1156
1157 /**
1158 * Returns a {@code PeekingIterator} backed by the given iterator.
1159 *
1160 * <p>Calls to the {@code peek} method with no intervening calls to {@code next} do not affect the
1161 * iteration, and hence return the same object each time. A subsequent call to {@code next} is
1162 * guaranteed to return the same object again. For example:
1163 *
1164 * <pre>{@code
1165 * PeekingIterator<String> peekingIterator =
1166 * Iterators.peekingIterator(Iterators.forArray("a", "b"));
1167 * String a1 = peekingIterator.peek(); // returns "a"
1168 * String a2 = peekingIterator.peek(); // also returns "a"
1169 * String a3 = peekingIterator.next(); // also returns "a"
1170 * }</pre>
1171 *
1172 * <p>Any structural changes to the underlying iteration (aside from those performed by the
1173 * iterator's own {@link PeekingIterator#remove()} method) will leave the iterator in an undefined
1174 * state.
1175 *
1176 * <p>The returned iterator does not support removal after peeking, as explained by {@link
1177 * PeekingIterator#remove()}.
1178 *
1179 * <p>Note: If the given iterator is already a {@code PeekingIterator}, it <i>might</i> be
1180 * returned to the caller, although this is neither guaranteed to occur nor required to be
1181 * consistent. For example, this method <i>might</i> choose to pass through recognized
1182 * implementations of {@code PeekingIterator} when the behavior of the implementation is known to
1183 * meet the contract guaranteed by this method.
1184 *
1185 * <p>There is no {@link Iterable} equivalent to this method, so use this method to wrap each
1186 * individual iterator as it is generated.
1187 *
1188 * @param iterator the backing iterator. The {@link PeekingIterator} assumes ownership of this
1189 * iterator, so users should cease making direct calls to it after calling this method.
1190 * @return a peeking iterator backed by that iterator. Apart from the additional {@link
1191 * PeekingIterator#peek()} method, this iterator behaves exactly the same as {@code iterator}.
1192 */
1193 public static <T> PeekingIterator<T> peekingIterator(Iterator<? extends T> iterator) {
1194 if (iterator instanceof PeekingImpl) {
1195 // Safe to cast <? extends T> to <T> because PeekingImpl only uses T
1196 // covariantly (and cannot be subclassed to add non-covariant uses).
1197 @SuppressWarnings("unchecked")
1198 PeekingImpl<T> peeking = (PeekingImpl<T>) iterator;
1199 return peeking;
1200 }
1201 return new PeekingImpl<T>(iterator);
1202 }
1203
1204 /**
1205 * Simply returns its argument.
1206 *
1207 * @deprecated no need to use this
1208 * @since 10.0
1209 */
1210 @Deprecated
1211 public static <T> PeekingIterator<T> peekingIterator(PeekingIterator<T> iterator) {
1212 return checkNotNull(iterator);
1213 }
1214
1215 /**
1216 * Returns an iterator over the merged contents of all given {@code iterators}, traversing every
1217 * element of the input iterators. Equivalent entries will not be de-duplicated.
1218 *
1219 * <p>Callers must ensure that the source {@code iterators} are in non-descending order as this
1220 * method does not sort its input.
1221 *
1222 * <p>For any equivalent elements across all {@code iterators}, it is undefined which element is
1223 * returned first.
1224 *
1225 * @since 11.0
1226 */
1227 @Beta
1228 public static <T> UnmodifiableIterator<T> mergeSorted(
1229 Iterable<? extends Iterator<? extends T>> iterators, Comparator<? super T> comparator) {
1230 checkNotNull(iterators, "iterators");
1231 checkNotNull(comparator, "comparator");
1232
1233 return new MergingIterator<T>(iterators, comparator);
1234 }
1235
1236 /**
1237 * An iterator that performs a lazy N-way merge, calculating the next value each time the iterator
1238 * is polled. This amortizes the sorting cost over the iteration and requires less memory than
1239 * sorting all elements at once.
1240 *
1241 * <p>Retrieving a single element takes approximately O(log(M)) time, where M is the number of
1242 * iterators. (Retrieving all elements takes approximately O(N*log(M)) time, where N is the total
1243 * number of elements.)
1244 */
1245 private static class MergingIterator<T> extends UnmodifiableIterator<T> {
1246 final Queue<PeekingIterator<T>> queue;
1247
1248 public MergingIterator(
1249 Iterable<? extends Iterator<? extends T>> iterators,
1250 final Comparator<? super T> itemComparator) {
1251 // A comparator that's used by the heap, allowing the heap
1252 // to be sorted based on the top of each iterator.
1253 Comparator<PeekingIterator<T>> heapComparator =
1254 new Comparator<PeekingIterator<T>>() {
1255 @Override
1256 public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) {
1257 return itemComparator.compare(o1.peek(), o2.peek());
1258 }
1259 };
1260
1261 queue = new PriorityQueue<>(2, heapComparator);
1262
1263 for (Iterator<? extends T> iterator : iterators) {
1264 if (iterator.hasNext()) {
1265 queue.add(Iterators.peekingIterator(iterator));
1266 }
1267 }
1268 }
1269
1270 @Override
1271 public boolean hasNext() {
1272 return !queue.isEmpty();
1273 }
1274
1275 @Override
1276 public T next() {
1277 PeekingIterator<T> nextIter = queue.remove();
1278 T next = nextIter.next();
1279 if (nextIter.hasNext()) {
1280 queue.add(nextIter);
1281 }
1282 return next;
1283 }
1284 }
1285
1286 private static class ConcatenatedIterator<T> implements Iterator<T> {
1287 /* The last iterator to return an element. Calls to remove() go to this iterator. */
1288 private @Nullable Iterator<? extends T> toRemove;
1289
1290 /* The iterator currently returning elements. */
1291 private Iterator<? extends T> iterator;
1292
1293 /*
1294 * We track the "meta iterators," the iterators-of-iterators, below. Usually, topMetaIterator
1295 * is the only one in use, but if we encounter nested concatenations, we start a deque of
1296 * meta-iterators rather than letting the nesting get arbitrarily deep. This keeps each
1297 * operation O(1).
1298 */
1299
1300 private Iterator<? extends Iterator<? extends T>> topMetaIterator;
1301
1302 // Only becomes nonnull if we encounter nested concatenations.
1303 private @Nullable Deque<Iterator<? extends Iterator<? extends T>>> metaIterators;
1304
1305 ConcatenatedIterator(Iterator<? extends Iterator<? extends T>> metaIterator) {
1306 iterator = emptyIterator();
1307 topMetaIterator = checkNotNull(metaIterator);
1308 }
1309
1310 // Returns a nonempty meta-iterator or, if all meta-iterators are empty, null.
1311 private @Nullable Iterator<? extends Iterator<? extends T>> getTopMetaIterator() {
1312 while (topMetaIterator == null || !topMetaIterator.hasNext()) {
1313 if (metaIterators != null && !metaIterators.isEmpty()) {
1314 topMetaIterator = metaIterators.removeFirst();
1315 } else {
1316 return null;
1317 }
1318 }
1319 return topMetaIterator;
1320 }
1321
1322 @Override
1323 public boolean hasNext() {
1324 while (!checkNotNull(iterator).hasNext()) {
1325 // this weird checkNotNull positioning appears required by our tests, which expect
1326 // both hasNext and next to throw NPE if an input iterator is null.
1327
1328 topMetaIterator = getTopMetaIterator();
1329 if (topMetaIterator == null) {
1330 return false;
1331 }
1332
1333 iterator = topMetaIterator.next();
1334
1335 if (iterator instanceof ConcatenatedIterator) {
1336 // Instead of taking linear time in the number of nested concatenations, unpack
1337 // them into the queue
1338 @SuppressWarnings("unchecked")
1339 ConcatenatedIterator<T> topConcat = (ConcatenatedIterator<T>) iterator;
1340 iterator = topConcat.iterator;
1341
1342 // topConcat.topMetaIterator, then topConcat.metaIterators, then this.topMetaIterator,
1343 // then this.metaIterators
1344
1345 if (this.metaIterators == null) {
1346 this.metaIterators = new ArrayDeque<>();
1347 }
1348 this.metaIterators.addFirst(this.topMetaIterator);
1349 if (topConcat.metaIterators != null) {
1350 while (!topConcat.metaIterators.isEmpty()) {
1351 this.metaIterators.addFirst(topConcat.metaIterators.removeLast());
1352 }
1353 }
1354 this.topMetaIterator = topConcat.topMetaIterator;
1355 }
1356 }
1357 return true;
1358 }
1359
1360 @Override
1361 public T next() {
1362 if (hasNext()) {
1363 toRemove = iterator;
1364 return iterator.next();
1365 } else {
1366 throw new NoSuchElementException();
1367 }
1368 }
1369
1370 @Override
1371 public void remove() {
1372 CollectPreconditions.checkRemove(toRemove != null);
1373 toRemove.remove();
1374 toRemove = null;
1375 }
1376 }
1377
1378 /** Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 */
1379 static <T> ListIterator<T> cast(Iterator<T> iterator) {
1380 return (ListIterator<T>) iterator;
1381 }
1382 }