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