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.ListIterator; 046import java.util.NoSuchElementException; 047import java.util.PriorityQueue; 048import java.util.Queue; 049import javax.annotation.CheckForNull; 050import org.checkerframework.checker.nullness.qual.NonNull; 051import org.checkerframework.checker.nullness.qual.Nullable; 052 053/** 054 * This class contains static utility methods that operate on or return objects of type {@link 055 * Iterator}. Except as noted, each method has a corresponding {@link Iterable}-based method in the 056 * {@link Iterables} class. 057 * 058 * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterators produced in this class 059 * are <i>lazy</i>, which means that they only advance the backing iteration when absolutely 060 * necessary. 061 * 062 * <p>See the Guava User Guide section on <a href= 063 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#iterables">{@code 064 * Iterators}</a>. 065 * 066 * @author Kevin Bourrillion 067 * @author Jared Levy 068 * @since 2.0 069 */ 070@GwtCompatible(emulated = true) 071@ElementTypesAreNonnullByDefault 072public final class Iterators { 073 private Iterators() {} 074 075 /** 076 * Returns the empty iterator. 077 * 078 * <p>The {@link Iterable} equivalent of this method is {@link ImmutableSet#of()}. 079 */ 080 static <T extends @Nullable Object> UnmodifiableIterator<T> emptyIterator() { 081 return emptyListIterator(); 082 } 083 084 /** 085 * Returns the empty iterator. 086 * 087 * <p>The {@link Iterable} equivalent of this method is {@link ImmutableSet#of()}. 088 */ 089 // Casting to any type is safe since there are no actual elements. 090 @SuppressWarnings("unchecked") 091 static <T extends @Nullable Object> UnmodifiableListIterator<T> emptyListIterator() { 092 return (UnmodifiableListIterator<T>) ArrayItr.EMPTY; 093 } 094 095 /** 096 * This is an enum singleton rather than an anonymous class so ProGuard can figure out it's only 097 * referenced by emptyModifiableIterator(). 098 */ 099 private enum EmptyModifiableIterator implements Iterator<Object> { 100 INSTANCE; 101 102 @Override 103 public boolean hasNext() { 104 return false; 105 } 106 107 @Override 108 public Object next() { 109 throw new NoSuchElementException(); 110 } 111 112 @Override 113 public void remove() { 114 checkRemove(false); 115 } 116 } 117 118 /** 119 * Returns the empty {@code Iterator} that throws {@link IllegalStateException} instead of {@link 120 * UnsupportedOperationException} on a call to {@link Iterator#remove()}. 121 */ 122 // Casting to any type is safe since there are no actual elements. 123 @SuppressWarnings("unchecked") 124 static <T extends @Nullable Object> Iterator<T> emptyModifiableIterator() { 125 return (Iterator<T>) EmptyModifiableIterator.INSTANCE; 126 } 127 128 /** Returns an unmodifiable view of {@code iterator}. */ 129 public static <T extends @Nullable Object> UnmodifiableIterator<T> unmodifiableIterator( 130 Iterator<? extends T> iterator) { 131 checkNotNull(iterator); 132 if (iterator instanceof UnmodifiableIterator) { 133 @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe 134 UnmodifiableIterator<T> result = (UnmodifiableIterator<T>) iterator; 135 return result; 136 } 137 return new UnmodifiableIterator<T>() { 138 @Override 139 public boolean hasNext() { 140 return iterator.hasNext(); 141 } 142 143 @Override 144 @ParametricNullness 145 public T next() { 146 return iterator.next(); 147 } 148 }; 149 } 150 151 /** 152 * Simply returns its argument. 153 * 154 * @deprecated no need to use this 155 * @since 10.0 156 */ 157 @Deprecated 158 public static <T extends @Nullable Object> UnmodifiableIterator<T> unmodifiableIterator( 159 UnmodifiableIterator<T> iterator) { 160 return checkNotNull(iterator); 161 } 162 163 /** 164 * Returns the number of elements remaining in {@code iterator}. The iterator will be left 165 * exhausted: its {@code hasNext()} method will return {@code false}. 166 */ 167 public static int size(Iterator<?> iterator) { 168 long count = 0L; 169 while (iterator.hasNext()) { 170 iterator.next(); 171 count++; 172 } 173 return Ints.saturatedCast(count); 174 } 175 176 /** Returns {@code true} if {@code iterator} contains {@code element}. */ 177 public static boolean contains(Iterator<?> iterator, @CheckForNull Object element) { 178 if (element == null) { 179 while (iterator.hasNext()) { 180 if (iterator.next() == null) { 181 return true; 182 } 183 } 184 } else { 185 while (iterator.hasNext()) { 186 if (element.equals(iterator.next())) { 187 return true; 188 } 189 } 190 } 191 return false; 192 } 193 194 /** 195 * Traverses an iterator and removes every element that belongs to the provided collection. The 196 * iterator will be left exhausted: its {@code hasNext()} method will return {@code false}. 197 * 198 * @param removeFrom the iterator to (potentially) remove elements from 199 * @param elementsToRemove the elements to remove 200 * @return {@code true} if any element was removed from {@code iterator} 201 */ 202 @CanIgnoreReturnValue 203 public static boolean removeAll(Iterator<?> removeFrom, Collection<?> elementsToRemove) { 204 checkNotNull(elementsToRemove); 205 boolean result = false; 206 while (removeFrom.hasNext()) { 207 if (elementsToRemove.contains(removeFrom.next())) { 208 removeFrom.remove(); 209 result = true; 210 } 211 } 212 return result; 213 } 214 215 /** 216 * Removes every element that satisfies the provided predicate from the iterator. The iterator 217 * will be left exhausted: its {@code hasNext()} method will return {@code false}. 218 * 219 * @param removeFrom the iterator to (potentially) remove elements from 220 * @param predicate a predicate that determines whether an element should be removed 221 * @return {@code true} if any elements were removed from the iterator 222 * @since 2.0 223 */ 224 @CanIgnoreReturnValue 225 public static <T extends @Nullable Object> boolean removeIf( 226 Iterator<T> removeFrom, Predicate<? super T> predicate) { 227 checkNotNull(predicate); 228 boolean modified = false; 229 while (removeFrom.hasNext()) { 230 if (predicate.apply(removeFrom.next())) { 231 removeFrom.remove(); 232 modified = true; 233 } 234 } 235 return modified; 236 } 237 238 /** 239 * Traverses an iterator and removes every element that does not belong to the provided 240 * collection. The iterator will be left exhausted: its {@code hasNext()} method will return 241 * {@code false}. 242 * 243 * @param removeFrom the iterator to (potentially) remove elements from 244 * @param elementsToRetain the elements to retain 245 * @return {@code true} if any element was removed from {@code iterator} 246 */ 247 @CanIgnoreReturnValue 248 public static boolean retainAll(Iterator<?> removeFrom, Collection<?> elementsToRetain) { 249 checkNotNull(elementsToRetain); 250 boolean result = false; 251 while (removeFrom.hasNext()) { 252 if (!elementsToRetain.contains(removeFrom.next())) { 253 removeFrom.remove(); 254 result = true; 255 } 256 } 257 return result; 258 } 259 260 /** 261 * Determines whether two iterators contain equal elements in the same order. More specifically, 262 * this method returns {@code true} if {@code iterator1} and {@code iterator2} contain the same 263 * number of elements and every element of {@code iterator1} is equal to the corresponding element 264 * of {@code iterator2}. 265 * 266 * <p>Note that this will modify the supplied iterators, since they will have been advanced some 267 * number of elements forward. 268 */ 269 public static boolean elementsEqual(Iterator<?> iterator1, Iterator<?> iterator2) { 270 while (iterator1.hasNext()) { 271 if (!iterator2.hasNext()) { 272 return false; 273 } 274 Object o1 = iterator1.next(); 275 Object o2 = iterator2.next(); 276 if (!Objects.equal(o1, o2)) { 277 return false; 278 } 279 } 280 return !iterator2.hasNext(); 281 } 282 283 /** 284 * Returns a string representation of {@code iterator}, with the format {@code [e1, e2, ..., en]}. 285 * The iterator will be left exhausted: its {@code hasNext()} method will return {@code false}. 286 */ 287 public static String toString(Iterator<?> iterator) { 288 StringBuilder sb = new StringBuilder().append('['); 289 boolean first = true; 290 while (iterator.hasNext()) { 291 if (!first) { 292 sb.append(", "); 293 } 294 first = false; 295 sb.append(iterator.next()); 296 } 297 return sb.append(']').toString(); 298 } 299 300 /** 301 * Returns the single element contained in {@code iterator}. 302 * 303 * @throws NoSuchElementException if the iterator is empty 304 * @throws IllegalArgumentException if the iterator contains multiple elements. The state of the 305 * iterator is unspecified. 306 */ 307 @ParametricNullness 308 public static <T extends @Nullable Object> T getOnlyElement(Iterator<T> iterator) { 309 T first = iterator.next(); 310 if (!iterator.hasNext()) { 311 return first; 312 } 313 314 StringBuilder sb = new StringBuilder().append("expected one element but was: <").append(first); 315 for (int i = 0; i < 4 && iterator.hasNext(); i++) { 316 sb.append(", ").append(iterator.next()); 317 } 318 if (iterator.hasNext()) { 319 sb.append(", ..."); 320 } 321 sb.append('>'); 322 323 throw new IllegalArgumentException(sb.toString()); 324 } 325 326 /** 327 * Returns the single element contained in {@code iterator}, or {@code defaultValue} if the 328 * iterator is empty. 329 * 330 * @throws IllegalArgumentException if the iterator contains multiple elements. The state of the 331 * iterator is unspecified. 332 */ 333 @ParametricNullness 334 public static <T extends @Nullable Object> T getOnlyElement( 335 Iterator<? extends T> iterator, @ParametricNullness T defaultValue) { 336 return iterator.hasNext() ? getOnlyElement(iterator) : defaultValue; 337 } 338 339 /** 340 * Copies an iterator's elements into an array. The iterator will be left exhausted: its {@code 341 * hasNext()} method will return {@code false}. 342 * 343 * @param iterator the iterator to copy 344 * @param type the type of the elements 345 * @return a newly-allocated array into which all the elements of the iterator have been copied 346 */ 347 @GwtIncompatible // Array.newInstance(Class, int) 348 public static <T extends @Nullable Object> T[] toArray( 349 Iterator<? extends T> iterator, Class<@NonNull T> type) { 350 List<T> list = Lists.newArrayList(iterator); 351 return Iterables.<T>toArray(list, type); 352 } 353 354 /** 355 * Adds all elements in {@code iterator} to {@code collection}. The iterator will be left 356 * exhausted: its {@code hasNext()} method will return {@code false}. 357 * 358 * @return {@code true} if {@code collection} was modified as a result of this operation 359 */ 360 @CanIgnoreReturnValue 361 public static <T extends @Nullable Object> boolean addAll( 362 Collection<T> addTo, Iterator<? extends T> iterator) { 363 checkNotNull(addTo); 364 checkNotNull(iterator); 365 boolean wasModified = false; 366 while (iterator.hasNext()) { 367 wasModified |= addTo.add(iterator.next()); 368 } 369 return wasModified; 370 } 371 372 /** 373 * Returns the number of elements in the specified iterator that equal the specified object. The 374 * iterator will be left exhausted: its {@code hasNext()} method will return {@code false}. 375 * 376 * @see Collections#frequency 377 */ 378 public static int frequency(Iterator<?> iterator, @CheckForNull Object element) { 379 int count = 0; 380 while (contains(iterator, element)) { 381 // Since it lives in the same class, we know contains gets to the element and then stops, 382 // though that isn't currently publicly documented. 383 count++; 384 } 385 return count; 386 } 387 388 /** 389 * Returns an iterator that cycles indefinitely over the elements of {@code iterable}. 390 * 391 * <p>The returned iterator supports {@code remove()} if the provided iterator does. After {@code 392 * remove()} is called, subsequent cycles omit the removed element, which is no longer in {@code 393 * iterable}. The iterator's {@code hasNext()} method returns {@code true} until {@code iterable} 394 * is empty. 395 * 396 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an infinite loop. You 397 * should use an explicit {@code break} or be certain that you will eventually remove all the 398 * elements. 399 */ 400 public static <T extends @Nullable Object> Iterator<T> cycle(Iterable<T> iterable) { 401 checkNotNull(iterable); 402 return new Iterator<T>() { 403 Iterator<T> iterator = emptyModifiableIterator(); 404 405 @Override 406 public boolean hasNext() { 407 /* 408 * Don't store a new Iterator until we know the user can't remove() the last returned 409 * element anymore. Otherwise, when we remove from the old iterator, we may be invalidating 410 * the new one. The result is a ConcurrentModificationException or other bad behavior. 411 * 412 * (If we decide that we really, really hate allocating two Iterators per cycle instead of 413 * one, we can optimistically store the new Iterator and then be willing to throw it out if 414 * the user calls remove().) 415 */ 416 return iterator.hasNext() || iterable.iterator().hasNext(); 417 } 418 419 @Override 420 @ParametricNullness 421 public T next() { 422 if (!iterator.hasNext()) { 423 iterator = iterable.iterator(); 424 if (!iterator.hasNext()) { 425 throw new NoSuchElementException(); 426 } 427 } 428 return iterator.next(); 429 } 430 431 @Override 432 public void remove() { 433 iterator.remove(); 434 } 435 }; 436 } 437 438 /** 439 * Returns an iterator that cycles indefinitely over the provided elements. 440 * 441 * <p>The returned iterator supports {@code remove()}. After {@code remove()} is called, 442 * subsequent cycles omit the removed element, but {@code elements} does not change. The 443 * iterator's {@code hasNext()} method returns {@code true} until all of the original elements 444 * have been removed. 445 * 446 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an infinite loop. You 447 * should use an explicit {@code break} or be certain that you will eventually remove all the 448 * elements. 449 */ 450 @SafeVarargs 451 public static <T extends @Nullable Object> Iterator<T> cycle(T... elements) { 452 return cycle(Lists.newArrayList(elements)); 453 } 454 455 /** 456 * Returns an Iterator that walks the specified array, nulling out elements behind it. This can 457 * avoid memory leaks when an element is no longer necessary. 458 * 459 * <p>This method accepts an array with element type {@code @Nullable T}, but callers must pass an 460 * array whose contents are initially non-null. The {@code @Nullable} annotation indicates that 461 * this method will write nulls into the array during iteration. 462 * 463 * <p>This is mainly just to avoid the intermediate ArrayDeque in ConsumingQueueIterator. 464 */ 465 private static <I extends Iterator<?>> Iterator<I> consumingForArray(@Nullable I... elements) { 466 return new UnmodifiableIterator<I>() { 467 int index = 0; 468 469 @Override 470 public boolean hasNext() { 471 return index < elements.length; 472 } 473 474 @Override 475 public I next() { 476 if (!hasNext()) { 477 throw new NoSuchElementException(); 478 } 479 /* 480 * requireNonNull is safe because our callers always pass non-null arguments. Each element 481 * of the array becomes null only when we iterate past it and then clear it. 482 */ 483 I result = requireNonNull(elements[index]); 484 elements[index] = null; 485 index++; 486 return result; 487 } 488 }; 489 } 490 491 /** 492 * Combines two iterators into a single iterator. The returned iterator iterates across the 493 * elements in {@code a}, followed by the elements in {@code b}. The source iterators are not 494 * polled until necessary. 495 * 496 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator 497 * supports it. 498 */ 499 public static <T extends @Nullable Object> Iterator<T> concat( 500 Iterator<? extends T> a, Iterator<? extends T> b) { 501 checkNotNull(a); 502 checkNotNull(b); 503 return concat(consumingForArray(a, b)); 504 } 505 506 /** 507 * Combines three iterators into a single iterator. The returned iterator iterates across the 508 * elements in {@code a}, followed by the elements in {@code b}, followed by the elements in 509 * {@code c}. The source iterators are not polled until necessary. 510 * 511 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator 512 * supports it. 513 */ 514 public static <T extends @Nullable Object> Iterator<T> concat( 515 Iterator<? extends T> a, Iterator<? extends T> b, Iterator<? extends T> c) { 516 checkNotNull(a); 517 checkNotNull(b); 518 checkNotNull(c); 519 return concat(consumingForArray(a, b, c)); 520 } 521 522 /** 523 * Combines four iterators into a single iterator. The returned iterator iterates across the 524 * elements in {@code a}, followed by the elements in {@code b}, followed by the elements in 525 * {@code c}, followed by the elements in {@code d}. The source iterators are not polled until 526 * necessary. 527 * 528 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator 529 * supports it. 530 */ 531 public static <T extends @Nullable Object> Iterator<T> concat( 532 Iterator<? extends T> a, 533 Iterator<? extends T> b, 534 Iterator<? extends T> c, 535 Iterator<? extends T> d) { 536 checkNotNull(a); 537 checkNotNull(b); 538 checkNotNull(c); 539 checkNotNull(d); 540 return concat(consumingForArray(a, b, c, d)); 541 } 542 543 /** 544 * Combines multiple iterators into a single iterator. The returned iterator iterates across the 545 * elements of each iterator in {@code inputs}. The input iterators are not polled until 546 * necessary. 547 * 548 * <p>The returned iterator supports {@code remove()} when the corresponding input iterator 549 * supports it. 550 * 551 * @throws NullPointerException if any of the provided iterators is null 552 */ 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 forArray(array, 0, array.length, 0); 1060 } 1061 1062 /** 1063 * Returns a list iterator containing the elements in the specified range of {@code array} in 1064 * order, starting at the specified index. 1065 * 1066 * <p>The {@code Iterable} equivalent of this method is {@code 1067 * Arrays.asList(array).subList(offset, offset + length).listIterator(index)}. 1068 */ 1069 static <T extends @Nullable Object> UnmodifiableListIterator<T> forArray( 1070 T[] array, int offset, int length, int index) { 1071 checkArgument(length >= 0); 1072 int end = offset + length; 1073 1074 // Technically we should give a slightly more descriptive error on overflow 1075 Preconditions.checkPositionIndexes(offset, end, array.length); 1076 Preconditions.checkPositionIndex(index, length); 1077 if (length == 0) { 1078 return emptyListIterator(); 1079 } 1080 return new ArrayItr<>(array, offset, length, index); 1081 } 1082 1083 private static final class ArrayItr<T extends @Nullable Object> 1084 extends AbstractIndexedListIterator<T> { 1085 static final UnmodifiableListIterator<Object> EMPTY = new ArrayItr<>(new Object[0], 0, 0, 0); 1086 1087 private final T[] array; 1088 private final int offset; 1089 1090 ArrayItr(T[] array, int offset, int length, int index) { 1091 super(length, index); 1092 this.array = array; 1093 this.offset = offset; 1094 } 1095 1096 @Override 1097 @ParametricNullness 1098 protected T get(int index) { 1099 return array[offset + index]; 1100 } 1101 } 1102 1103 /** 1104 * Returns an iterator containing only {@code value}. 1105 * 1106 * <p>The {@link Iterable} equivalent of this method is {@link Collections#singleton}. 1107 */ 1108 public static <T extends @Nullable Object> UnmodifiableIterator<T> singletonIterator( 1109 @ParametricNullness T value) { 1110 return new UnmodifiableIterator<T>() { 1111 boolean done; 1112 1113 @Override 1114 public boolean hasNext() { 1115 return !done; 1116 } 1117 1118 @Override 1119 @ParametricNullness 1120 public T next() { 1121 if (done) { 1122 throw new NoSuchElementException(); 1123 } 1124 done = true; 1125 return value; 1126 } 1127 }; 1128 } 1129 1130 /** 1131 * Adapts an {@code Enumeration} to the {@code Iterator} interface. 1132 * 1133 * <p>This method has no equivalent in {@link Iterables} because viewing an {@code Enumeration} as 1134 * an {@code Iterable} is impossible. However, the contents can be <i>copied</i> into a collection 1135 * using {@link Collections#list}. 1136 * 1137 * <p><b>Java 9 users:</b> use {@code enumeration.asIterator()} instead, unless it is important to 1138 * return an {@code UnmodifiableIterator} instead of a plain {@code Iterator}. 1139 */ 1140 public static <T extends @Nullable Object> UnmodifiableIterator<T> forEnumeration( 1141 Enumeration<T> enumeration) { 1142 checkNotNull(enumeration); 1143 return new UnmodifiableIterator<T>() { 1144 @Override 1145 public boolean hasNext() { 1146 return enumeration.hasMoreElements(); 1147 } 1148 1149 @Override 1150 @ParametricNullness 1151 public T next() { 1152 return enumeration.nextElement(); 1153 } 1154 }; 1155 } 1156 1157 /** 1158 * Adapts an {@code Iterator} to the {@code Enumeration} interface. 1159 * 1160 * <p>The {@code Iterable} equivalent of this method is either {@link Collections#enumeration} (if 1161 * you have a {@link Collection}), or {@code Iterators.asEnumeration(collection.iterator())}. 1162 */ 1163 public static <T extends @Nullable Object> Enumeration<T> asEnumeration(Iterator<T> iterator) { 1164 checkNotNull(iterator); 1165 return new Enumeration<T>() { 1166 @Override 1167 public boolean hasMoreElements() { 1168 return iterator.hasNext(); 1169 } 1170 1171 @Override 1172 @ParametricNullness 1173 public T nextElement() { 1174 return iterator.next(); 1175 } 1176 }; 1177 } 1178 1179 /** Implementation of PeekingIterator that avoids peeking unless necessary. */ 1180 private static class PeekingImpl<E extends @Nullable Object> implements PeekingIterator<E> { 1181 1182 private final Iterator<? extends E> iterator; 1183 private boolean hasPeeked; 1184 @CheckForNull private E peekedElement; 1185 1186 public PeekingImpl(Iterator<? extends E> iterator) { 1187 this.iterator = checkNotNull(iterator); 1188 } 1189 1190 @Override 1191 public boolean hasNext() { 1192 return hasPeeked || iterator.hasNext(); 1193 } 1194 1195 @Override 1196 @ParametricNullness 1197 public E next() { 1198 if (!hasPeeked) { 1199 return iterator.next(); 1200 } 1201 // The cast is safe because of the hasPeeked check. 1202 E result = uncheckedCastNullableTToT(peekedElement); 1203 hasPeeked = false; 1204 peekedElement = null; 1205 return result; 1206 } 1207 1208 @Override 1209 public void remove() { 1210 checkState(!hasPeeked, "Can't remove after you've peeked at next"); 1211 iterator.remove(); 1212 } 1213 1214 @Override 1215 @ParametricNullness 1216 public E peek() { 1217 if (!hasPeeked) { 1218 peekedElement = iterator.next(); 1219 hasPeeked = true; 1220 } 1221 // The cast is safe because of the hasPeeked check. 1222 return uncheckedCastNullableTToT(peekedElement); 1223 } 1224 } 1225 1226 /** 1227 * Returns a {@code PeekingIterator} backed by the given iterator. 1228 * 1229 * <p>Calls to the {@code peek} method with no intervening calls to {@code next} do not affect the 1230 * iteration, and hence return the same object each time. A subsequent call to {@code next} is 1231 * guaranteed to return the same object again. For example: 1232 * 1233 * <pre>{@code 1234 * PeekingIterator<String> peekingIterator = 1235 * Iterators.peekingIterator(Iterators.forArray("a", "b")); 1236 * String a1 = peekingIterator.peek(); // returns "a" 1237 * String a2 = peekingIterator.peek(); // also returns "a" 1238 * String a3 = peekingIterator.next(); // also returns "a" 1239 * }</pre> 1240 * 1241 * <p>Any structural changes to the underlying iteration (aside from those performed by the 1242 * iterator's own {@link PeekingIterator#remove()} method) will leave the iterator in an undefined 1243 * state. 1244 * 1245 * <p>The returned iterator does not support removal after peeking, as explained by {@link 1246 * PeekingIterator#remove()}. 1247 * 1248 * <p>Note: If the given iterator is already a {@code PeekingIterator}, it <i>might</i> be 1249 * returned to the caller, although this is neither guaranteed to occur nor required to be 1250 * consistent. For example, this method <i>might</i> choose to pass through recognized 1251 * implementations of {@code PeekingIterator} when the behavior of the implementation is known to 1252 * meet the contract guaranteed by this method. 1253 * 1254 * <p>There is no {@link Iterable} equivalent to this method, so use this method to wrap each 1255 * individual iterator as it is generated. 1256 * 1257 * @param iterator the backing iterator. The {@link PeekingIterator} assumes ownership of this 1258 * iterator, so users should cease making direct calls to it after calling this method. 1259 * @return a peeking iterator backed by that iterator. Apart from the additional {@link 1260 * PeekingIterator#peek()} method, this iterator behaves exactly the same as {@code iterator}. 1261 */ 1262 public static <T extends @Nullable Object> PeekingIterator<T> peekingIterator( 1263 Iterator<? extends T> iterator) { 1264 if (iterator instanceof PeekingImpl) { 1265 // Safe to cast <? extends T> to <T> because PeekingImpl only uses T 1266 // covariantly (and cannot be subclassed to add non-covariant uses). 1267 @SuppressWarnings("unchecked") 1268 PeekingImpl<T> peeking = (PeekingImpl<T>) iterator; 1269 return peeking; 1270 } 1271 return new PeekingImpl<>(iterator); 1272 } 1273 1274 /** 1275 * Simply returns its argument. 1276 * 1277 * @deprecated no need to use this 1278 * @since 10.0 1279 */ 1280 @Deprecated 1281 public static <T extends @Nullable Object> PeekingIterator<T> peekingIterator( 1282 PeekingIterator<T> iterator) { 1283 return checkNotNull(iterator); 1284 } 1285 1286 /** 1287 * Returns an iterator over the merged contents of all given {@code iterators}, traversing every 1288 * element of the input iterators. Equivalent entries will not be de-duplicated. 1289 * 1290 * <p>Callers must ensure that the source {@code iterators} are in non-descending order as this 1291 * method does not sort its input. 1292 * 1293 * <p>For any equivalent elements across all {@code iterators}, it is undefined which element is 1294 * returned first. 1295 * 1296 * @since 11.0 1297 */ 1298 public static <T extends @Nullable Object> UnmodifiableIterator<T> mergeSorted( 1299 Iterable<? extends Iterator<? extends T>> iterators, Comparator<? super T> comparator) { 1300 checkNotNull(iterators, "iterators"); 1301 checkNotNull(comparator, "comparator"); 1302 1303 return new MergingIterator<>(iterators, comparator); 1304 } 1305 1306 /** 1307 * An iterator that performs a lazy N-way merge, calculating the next value each time the iterator 1308 * is polled. This amortizes the sorting cost over the iteration and requires less memory than 1309 * sorting all elements at once. 1310 * 1311 * <p>Retrieving a single element takes approximately O(log(M)) time, where M is the number of 1312 * iterators. (Retrieving all elements takes approximately O(N*log(M)) time, where N is the total 1313 * number of elements.) 1314 */ 1315 private static class MergingIterator<T extends @Nullable Object> extends UnmodifiableIterator<T> { 1316 final Queue<PeekingIterator<T>> queue; 1317 1318 public MergingIterator( 1319 Iterable<? extends Iterator<? extends T>> iterators, Comparator<? super T> itemComparator) { 1320 // A comparator that's used by the heap, allowing the heap 1321 // to be sorted based on the top of each iterator. 1322 Comparator<PeekingIterator<T>> heapComparator = 1323 (PeekingIterator<T> o1, PeekingIterator<T> o2) -> 1324 itemComparator.compare(o1.peek(), o2.peek()); 1325 1326 queue = new PriorityQueue<>(2, heapComparator); 1327 1328 for (Iterator<? extends T> iterator : iterators) { 1329 if (iterator.hasNext()) { 1330 queue.add(Iterators.peekingIterator(iterator)); 1331 } 1332 } 1333 } 1334 1335 @Override 1336 public boolean hasNext() { 1337 return !queue.isEmpty(); 1338 } 1339 1340 @Override 1341 @ParametricNullness 1342 public T next() { 1343 PeekingIterator<T> nextIter = queue.remove(); 1344 T next = nextIter.next(); 1345 if (nextIter.hasNext()) { 1346 queue.add(nextIter); 1347 } 1348 return next; 1349 } 1350 } 1351 1352 private static class ConcatenatedIterator<T extends @Nullable Object> implements Iterator<T> { 1353 /* The last iterator to return an element. Calls to remove() go to this iterator. */ 1354 @CheckForNull private Iterator<? extends T> toRemove; 1355 1356 /* The iterator currently returning elements. */ 1357 private Iterator<? extends T> iterator; 1358 1359 /* 1360 * We track the "meta iterators," the iterators-of-iterators, below. Usually, topMetaIterator 1361 * is the only one in use, but if we encounter nested concatenations, we start a deque of 1362 * meta-iterators rather than letting the nesting get arbitrarily deep. This keeps each 1363 * operation O(1). 1364 */ 1365 1366 @CheckForNull private Iterator<? extends Iterator<? extends T>> topMetaIterator; 1367 1368 // Only becomes nonnull if we encounter nested concatenations. 1369 @CheckForNull private Deque<Iterator<? extends Iterator<? extends T>>> metaIterators; 1370 1371 ConcatenatedIterator(Iterator<? extends Iterator<? extends T>> metaIterator) { 1372 iterator = emptyIterator(); 1373 topMetaIterator = checkNotNull(metaIterator); 1374 } 1375 1376 // Returns a nonempty meta-iterator or, if all meta-iterators are empty, null. 1377 @CheckForNull 1378 private Iterator<? extends Iterator<? extends T>> getTopMetaIterator() { 1379 while (topMetaIterator == null || !topMetaIterator.hasNext()) { 1380 if (metaIterators != null && !metaIterators.isEmpty()) { 1381 topMetaIterator = metaIterators.removeFirst(); 1382 } else { 1383 return null; 1384 } 1385 } 1386 return topMetaIterator; 1387 } 1388 1389 @Override 1390 public boolean hasNext() { 1391 while (!checkNotNull(iterator).hasNext()) { 1392 // this weird checkNotNull positioning appears required by our tests, which expect 1393 // both hasNext and next to throw NPE if an input iterator is null. 1394 1395 topMetaIterator = getTopMetaIterator(); 1396 if (topMetaIterator == null) { 1397 return false; 1398 } 1399 1400 iterator = topMetaIterator.next(); 1401 1402 if (iterator instanceof ConcatenatedIterator) { 1403 // Instead of taking linear time in the number of nested concatenations, unpack 1404 // them into the queue 1405 @SuppressWarnings("unchecked") 1406 ConcatenatedIterator<T> topConcat = (ConcatenatedIterator<T>) iterator; 1407 iterator = topConcat.iterator; 1408 1409 // topConcat.topMetaIterator, then topConcat.metaIterators, then this.topMetaIterator, 1410 // then this.metaIterators 1411 1412 if (this.metaIterators == null) { 1413 this.metaIterators = new ArrayDeque<>(); 1414 } 1415 this.metaIterators.addFirst(this.topMetaIterator); 1416 if (topConcat.metaIterators != null) { 1417 while (!topConcat.metaIterators.isEmpty()) { 1418 this.metaIterators.addFirst(topConcat.metaIterators.removeLast()); 1419 } 1420 } 1421 this.topMetaIterator = topConcat.topMetaIterator; 1422 } 1423 } 1424 return true; 1425 } 1426 1427 @Override 1428 @ParametricNullness 1429 public T next() { 1430 if (hasNext()) { 1431 toRemove = iterator; 1432 return iterator.next(); 1433 } else { 1434 throw new NoSuchElementException(); 1435 } 1436 } 1437 1438 @Override 1439 public void remove() { 1440 if (toRemove == null) { 1441 throw new IllegalStateException("no calls to next() since the last call to remove()"); 1442 } 1443 toRemove.remove(); 1444 toRemove = null; 1445 } 1446 } 1447 1448 /** Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 */ 1449 static <T extends @Nullable Object> ListIterator<T> cast(Iterator<T> iterator) { 1450 return (ListIterator<T>) iterator; 1451 } 1452}