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