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