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