10888a09821a98ac0680fad765217302858e70fa4Paul Duffin/* 20888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Copyright (C) 2007 The Guava Authors 30888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 40888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 50888a09821a98ac0680fad765217302858e70fa4Paul Duffin * you may not use this file except in compliance with the License. 60888a09821a98ac0680fad765217302858e70fa4Paul Duffin * You may obtain a copy of the License at 70888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 80888a09821a98ac0680fad765217302858e70fa4Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 90888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Unless required by applicable law or agreed to in writing, software 110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * See the License for the specific language governing permissions and 140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * limitations under the License. 150888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 160888a09821a98ac0680fad765217302858e70fa4Paul Duffin 170888a09821a98ac0680fad765217302858e70fa4Paul Duffinpackage com.google.common.collect; 180888a09821a98ac0680fad765217302858e70fa4Paul Duffin 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkArgument; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkNotNull; 210888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkState; 220888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Predicates.equalTo; 230888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Predicates.in; 240888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Predicates.not; 250888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkRemove; 260888a09821a98ac0680fad765217302858e70fa4Paul Duffin 270888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.Beta; 280888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.GwtCompatible; 290888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.base.Function; 300888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.base.Objects; 310888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.base.Optional; 320888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.base.Preconditions; 330888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.base.Predicate; 340888a09821a98ac0680fad765217302858e70fa4Paul Duffin 350888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Arrays; 360888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Collection; 370888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Collections; 380888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Comparator; 390888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Enumeration; 400888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Iterator; 410888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.List; 420888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.ListIterator; 430888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.NoSuchElementException; 440888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.PriorityQueue; 450888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Queue; 460888a09821a98ac0680fad765217302858e70fa4Paul Duffin 470888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport javax.annotation.Nullable; 480888a09821a98ac0680fad765217302858e70fa4Paul Duffin 490888a09821a98ac0680fad765217302858e70fa4Paul Duffin/** 500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * This class contains static utility methods that operate on or return objects 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * of type {@link Iterator}. Except as noted, each method has a corresponding 520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link Iterable}-based method in the {@link Iterables} class. 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterators 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * produced in this class are <i>lazy</i>, which means that they only advance 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the backing iteration when absolutely necessary. 570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>See the Guava User Guide section on <a href= 590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Iterables"> 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code Iterators}</a>. 610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @author Kevin Bourrillion 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @author Jared Levy 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 2.0 (imported from Google Collections Library) 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin@GwtCompatible(emulated = true) 670888a09821a98ac0680fad765217302858e70fa4Paul Duffinpublic final class Iterators { 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin private Iterators() {} 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final UnmodifiableListIterator<Object> EMPTY_LIST_ITERATOR 710888a09821a98ac0680fad765217302858e70fa4Paul Duffin = new UnmodifiableListIterator<Object>() { 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin public Object next() { 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasPrevious() { 820888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 840888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin public Object previous() { 860888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin public int nextIndex() { 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin return 0; 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin public int previousIndex() { 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin return -1; 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 960888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the empty iterator. 1000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The {@link Iterable} equivalent of this method is {@link 1020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableSet#of()}. 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<T> emptyIterator() { 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin return emptyListIterator(); 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1070888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the empty iterator. 1100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The {@link Iterable} equivalent of this method is {@link 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableSet#of()}. 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Casting to any type is safe since there are no actual elements. 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <T> UnmodifiableListIterator<T> emptyListIterator() { 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (UnmodifiableListIterator<T>) EMPTY_LIST_ITERATOR; 1180888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1190888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1200888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final Iterator<Object> EMPTY_MODIFIABLE_ITERATOR = 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin new Iterator<Object>() { 1220888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean hasNext() { 1230888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 1240888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1250888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1260888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Object next() { 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1290888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1300888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void remove() { 1310888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkRemove(false); 1320888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1330888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1350888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1360888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the empty {@code Iterator} that throws 1370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link IllegalStateException} instead of 1380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link UnsupportedOperationException} on a call to 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link Iterator#remove()}. 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1410888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Casting to any type is safe since there are no actual elements. 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <T> Iterator<T> emptyModifiableIterator() { 1440888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (Iterator<T>) EMPTY_MODIFIABLE_ITERATOR; 1450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1460888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** Returns an unmodifiable view of {@code iterator}. */ 1480888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<T> unmodifiableIterator( 1490888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<T> iterator) { 1500888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (iterator instanceof UnmodifiableIterator) { 1520888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (UnmodifiableIterator<T>) iterator; 1530888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1540888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new UnmodifiableIterator<T>() { 1550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 1570888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext(); 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1600888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.next(); 1620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1630888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1650888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1660888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Simply returns its argument. 1680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @deprecated no need to use this 1700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 10.0 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Deprecated public static <T> UnmodifiableIterator<T> unmodifiableIterator( 1730888a09821a98ac0680fad765217302858e70fa4Paul Duffin UnmodifiableIterator<T> iterator) { 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin return checkNotNull(iterator); 1750888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1770888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the number of elements remaining in {@code iterator}. The iterator 1790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * will be left exhausted: its {@code hasNext()} method will return 1800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code false}. 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1820888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static int size(Iterator<?> iterator) { 1830888a09821a98ac0680fad765217302858e70fa4Paul Duffin int count = 0; 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (iterator.hasNext()) { 1850888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.next(); 1860888a09821a98ac0680fad765217302858e70fa4Paul Duffin count++; 1870888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1880888a09821a98ac0680fad765217302858e70fa4Paul Duffin return count; 1890888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1900888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1910888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns {@code true} if {@code iterator} contains {@code element}. 1930888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static boolean contains(Iterator<?> iterator, @Nullable Object element) { 1950888a09821a98ac0680fad765217302858e70fa4Paul Duffin return any(iterator, equalTo(element)); 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Traverses an iterator and removes every element that belongs to the 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * provided collection. The iterator will be left exhausted: its 2010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method will return {@code false}. 2020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param removeFrom the iterator to (potentially) remove elements from 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param elementsToRemove the elements to remove 2050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return {@code true} if any element was removed from {@code iterator} 2060888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2070888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static boolean removeAll( 2080888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<?> removeFrom, Collection<?> elementsToRemove) { 2090888a09821a98ac0680fad765217302858e70fa4Paul Duffin return removeIf(removeFrom, in(elementsToRemove)); 2100888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2110888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2120888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Removes every element that satisfies the provided predicate from the 2140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterator. The iterator will be left exhausted: its {@code hasNext()} 2150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * method will return {@code false}. 2160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param removeFrom the iterator to (potentially) remove elements from 2180888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param predicate a predicate that determines whether an element should 2190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * be removed 2200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return {@code true} if any elements were removed from the iterator 2210888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 2.0 2220888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2230888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> boolean removeIf( 2240888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> removeFrom, Predicate<? super T> predicate) { 2250888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(predicate); 2260888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean modified = false; 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (removeFrom.hasNext()) { 2280888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (predicate.apply(removeFrom.next())) { 2290888a09821a98ac0680fad765217302858e70fa4Paul Duffin removeFrom.remove(); 2300888a09821a98ac0680fad765217302858e70fa4Paul Duffin modified = true; 2310888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2320888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2330888a09821a98ac0680fad765217302858e70fa4Paul Duffin return modified; 2340888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2350888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2360888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Traverses an iterator and removes every element that does not belong to the 2380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * provided collection. The iterator will be left exhausted: its 2390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method will return {@code false}. 2400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2410888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param removeFrom the iterator to (potentially) remove elements from 2420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param elementsToRetain the elements to retain 2430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return {@code true} if any element was removed from {@code iterator} 2440888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2450888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static boolean retainAll( 2460888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<?> removeFrom, Collection<?> elementsToRetain) { 2470888a09821a98ac0680fad765217302858e70fa4Paul Duffin return removeIf(removeFrom, not(in(elementsToRetain))); 2480888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2490888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2500888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Determines whether two iterators contain equal elements in the same order. 2520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * More specifically, this method returns {@code true} if {@code iterator1} 2530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * and {@code iterator2} contain the same number of elements and every element 2540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * of {@code iterator1} is equal to the corresponding element of 2550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterator2}. 2560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Note that this will modify the supplied iterators, since they will have 2580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * been advanced some number of elements forward. 2590888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2600888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static boolean elementsEqual( 2610888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<?> iterator1, Iterator<?> iterator2) { 2620888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (iterator1.hasNext()) { 2630888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!iterator2.hasNext()) { 2640888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 2650888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2660888a09821a98ac0680fad765217302858e70fa4Paul Duffin Object o1 = iterator1.next(); 2670888a09821a98ac0680fad765217302858e70fa4Paul Duffin Object o2 = iterator2.next(); 2680888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!Objects.equal(o1, o2)) { 2690888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 2700888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2710888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2720888a09821a98ac0680fad765217302858e70fa4Paul Duffin return !iterator2.hasNext(); 2730888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2740888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2750888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a string representation of {@code iterator}, with the format 2770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code [e1, e2, ..., en]}. The iterator will be left exhausted: its 2780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method will return {@code false}. 2790888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2800888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static String toString(Iterator<?> iterator) { 2810888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Collections2.STANDARD_JOINER 2820888a09821a98ac0680fad765217302858e70fa4Paul Duffin .appendTo(new StringBuilder().append('['), iterator) 2830888a09821a98ac0680fad765217302858e70fa4Paul Duffin .append(']') 2840888a09821a98ac0680fad765217302858e70fa4Paul Duffin .toString(); 2850888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2860888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2870888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2880888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the single element contained in {@code iterator}. 2890888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws NoSuchElementException if the iterator is empty 2910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if the iterator contains multiple 2920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements. The state of the iterator is unspecified. 2930888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2940888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T getOnlyElement(Iterator<T> iterator) { 2950888a09821a98ac0680fad765217302858e70fa4Paul Duffin T first = iterator.next(); 2960888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!iterator.hasNext()) { 2970888a09821a98ac0680fad765217302858e70fa4Paul Duffin return first; 2980888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2990888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3000888a09821a98ac0680fad765217302858e70fa4Paul Duffin StringBuilder sb = new StringBuilder(); 3010888a09821a98ac0680fad765217302858e70fa4Paul Duffin sb.append("expected one element but was: <" + first); 3020888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 0; i < 4 && iterator.hasNext(); i++) { 3030888a09821a98ac0680fad765217302858e70fa4Paul Duffin sb.append(", " + iterator.next()); 3040888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3050888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (iterator.hasNext()) { 3060888a09821a98ac0680fad765217302858e70fa4Paul Duffin sb.append(", ..."); 3070888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3080888a09821a98ac0680fad765217302858e70fa4Paul Duffin sb.append('>'); 3090888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3100888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new IllegalArgumentException(sb.toString()); 3110888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3120888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3130888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 3140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the single element contained in {@code iterator}, or {@code 3150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * defaultValue} if the iterator is empty. 3160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if the iterator contains multiple 3180888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements. The state of the iterator is unspecified. 3190888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 3200888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable 3210888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T getOnlyElement(Iterator<? extends T> iterator, @Nullable T defaultValue) { 3220888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext() ? getOnlyElement(iterator) : defaultValue; 3230888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3240888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3250888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 3260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Adds all elements in {@code iterator} to {@code collection}. The iterator 3270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * will be left exhausted: its {@code hasNext()} method will return 3280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code false}. 3290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return {@code true} if {@code collection} was modified as a result of this 3310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * operation 3320888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 3330888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> boolean addAll( 3340888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<T> addTo, Iterator<? extends T> iterator) { 3350888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(addTo); 3360888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 3370888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean wasModified = false; 3380888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (iterator.hasNext()) { 3390888a09821a98ac0680fad765217302858e70fa4Paul Duffin wasModified |= addTo.add(iterator.next()); 3400888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3410888a09821a98ac0680fad765217302858e70fa4Paul Duffin return wasModified; 3420888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3430888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3440888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 3450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the number of elements in the specified iterator that equal the 3460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * specified object. The iterator will be left exhausted: its 3470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method will return {@code false}. 3480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @see Collections#frequency 3500888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 3510888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static int frequency(Iterator<?> iterator, @Nullable Object element) { 3520888a09821a98ac0680fad765217302858e70fa4Paul Duffin return size(filter(iterator, equalTo(element))); 3530888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3540888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3550888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 3560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an iterator that cycles indefinitely over the elements of {@code 3570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterable}. 3580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()} if the provided iterator 3600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * does. After {@code remove()} is called, subsequent cycles omit the removed 3610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * element, which is no longer in {@code iterable}. The iterator's 3620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method returns {@code true} until {@code iterable} is 3630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * empty. 3640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an 3660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * infinite loop. You should use an explicit {@code break} or be certain that 3670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * you will eventually remove all the elements. 3680888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 3690888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> cycle(final Iterable<T> iterable) { 3700888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterable); 3710888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Iterator<T>() { 3720888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator = emptyIterator(); 3730888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> removeFrom; 3740888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3750888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3760888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 3770888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!iterator.hasNext()) { 3780888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator = iterable.iterator(); 3790888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3800888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext(); 3810888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3820888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3830888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 3840888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasNext()) { 3850888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 3860888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3870888a09821a98ac0680fad765217302858e70fa4Paul Duffin removeFrom = iterator; 3880888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.next(); 3890888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3910888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void remove() { 3920888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkRemove(removeFrom != null); 3930888a09821a98ac0680fad765217302858e70fa4Paul Duffin removeFrom.remove(); 3940888a09821a98ac0680fad765217302858e70fa4Paul Duffin removeFrom = null; 3950888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3960888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 3970888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3980888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3990888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an iterator that cycles indefinitely over the provided elements. 4010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()}. After {@code remove()} 4030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * is called, subsequent cycles omit the removed 4040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * element, but {@code elements} does not change. The iterator's 4050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method returns {@code true} until all of the original 4060888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements have been removed. 4070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4080888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an 4090888a09821a98ac0680fad765217302858e70fa4Paul Duffin * infinite loop. You should use an explicit {@code break} or be certain that 4100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * you will eventually remove all the elements. 4110888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 4120888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> cycle(T... elements) { 4130888a09821a98ac0680fad765217302858e70fa4Paul Duffin return cycle(Lists.newArrayList(elements)); 4140888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4150888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4160888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Combines two iterators into a single iterator. The returned iterator 4180888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterates across the elements in {@code a}, followed by the elements in 4190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code b}. The source iterators are not polled until necessary. 4200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4210888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()} when the corresponding 4220888a09821a98ac0680fad765217302858e70fa4Paul Duffin * input iterator supports it. 4230888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> the current implementation is not suitable for nested 4250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * concatenated iterators, i.e. the following should be avoided when in a loop: 4260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterator = Iterators.concat(iterator, suffix);}, since iteration over the 4270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * resulting iterator has a cubic complexity to the depth of the nesting. 4280888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 4290888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> concat(Iterator<? extends T> a, 4300888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends T> b) { 4310888a09821a98ac0680fad765217302858e70fa4Paul Duffin return concat(ImmutableList.of(a, b).iterator()); 4320888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4330888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4340888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4350888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Combines three iterators into a single iterator. The returned iterator 4360888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterates across the elements in {@code a}, followed by the elements in 4370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code b}, followed by the elements in {@code c}. The source iterators 4380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * are not polled until necessary. 4390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()} when the corresponding 4410888a09821a98ac0680fad765217302858e70fa4Paul Duffin * input iterator supports it. 4420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> the current implementation is not suitable for nested 4440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * concatenated iterators, i.e. the following should be avoided when in a loop: 4450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterator = Iterators.concat(iterator, suffix);}, since iteration over the 4460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * resulting iterator has a cubic complexity to the depth of the nesting. 4470888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 4480888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> concat(Iterator<? extends T> a, 4490888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends T> b, Iterator<? extends T> c) { 4500888a09821a98ac0680fad765217302858e70fa4Paul Duffin return concat(ImmutableList.of(a, b, c).iterator()); 4510888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4520888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4530888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Combines four iterators into a single iterator. The returned iterator 4550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterates across the elements in {@code a}, followed by the elements in 4560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code b}, followed by the elements in {@code c}, followed by the elements 4570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * in {@code d}. The source iterators are not polled until necessary. 4580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()} when the corresponding 4600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * input iterator supports it. 4610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> the current implementation is not suitable for nested 4630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * concatenated iterators, i.e. the following should be avoided when in a loop: 4640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterator = Iterators.concat(iterator, suffix);}, since iteration over the 4650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * resulting iterator has a cubic complexity to the depth of the nesting. 4660888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 4670888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> concat(Iterator<? extends T> a, 4680888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends T> b, Iterator<? extends T> c, 4690888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends T> d) { 4700888a09821a98ac0680fad765217302858e70fa4Paul Duffin return concat(ImmutableList.of(a, b, c, d).iterator()); 4710888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4720888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4730888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Combines multiple iterators into a single iterator. The returned iterator 4750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterates across the elements of each iterator in {@code inputs}. The input 4760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterators are not polled until necessary. 4770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()} when the corresponding 4790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * input iterator supports it. 4800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> the current implementation is not suitable for nested 4820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * concatenated iterators, i.e. the following should be avoided when in a loop: 4830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterator = Iterators.concat(iterator, suffix);}, since iteration over the 4840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * resulting iterator has a cubic complexity to the depth of the nesting. 4850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4860888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws NullPointerException if any of the provided iterators is null 4870888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 4880888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> concat(Iterator<? extends T>... inputs) { 4890888a09821a98ac0680fad765217302858e70fa4Paul Duffin return concat(ImmutableList.copyOf(inputs).iterator()); 4900888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4910888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4920888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Combines multiple iterators into a single iterator. The returned iterator 4940888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterates across the elements of each iterator in {@code inputs}. The input 4950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterators are not polled until necessary. 4960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()} when the corresponding 4980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * input iterator supports it. The methods of the returned iterator may throw 4990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code NullPointerException} if any of the input iterators is null. 5000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 5010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> the current implementation is not suitable for nested 5020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * concatenated iterators, i.e. the following should be avoided when in a loop: 5030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterator = Iterators.concat(iterator, suffix);}, since iteration over the 5040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * resulting iterator has a cubic complexity to the depth of the nesting. 5050888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 5060888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> concat( 5070888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<? extends Iterator<? extends T>> inputs) { 5080888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(inputs); 5090888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Iterator<T>() { 5100888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends T> current = emptyIterator(); 5110888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends T> removeFrom; 5120888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5130888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5140888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 5150888a09821a98ac0680fad765217302858e70fa4Paul Duffin // http://code.google.com/p/google-collections/issues/detail?id=151 5160888a09821a98ac0680fad765217302858e70fa4Paul Duffin // current.hasNext() might be relatively expensive, worth minimizing. 5170888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean currentHasNext; 5180888a09821a98ac0680fad765217302858e70fa4Paul Duffin // checkNotNull eager for GWT 5190888a09821a98ac0680fad765217302858e70fa4Paul Duffin // note: it must be here & not where 'current' is assigned, 5200888a09821a98ac0680fad765217302858e70fa4Paul Duffin // because otherwise we'll have called inputs.next() before throwing 5210888a09821a98ac0680fad765217302858e70fa4Paul Duffin // the first NPE, and the next time around we'll call inputs.next() 5220888a09821a98ac0680fad765217302858e70fa4Paul Duffin // again, incorrectly moving beyond the error. 5230888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (!(currentHasNext = checkNotNull(current).hasNext()) 5240888a09821a98ac0680fad765217302858e70fa4Paul Duffin && inputs.hasNext()) { 5250888a09821a98ac0680fad765217302858e70fa4Paul Duffin current = inputs.next(); 5260888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5270888a09821a98ac0680fad765217302858e70fa4Paul Duffin return currentHasNext; 5280888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5290888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5300888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 5310888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasNext()) { 5320888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 5330888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5340888a09821a98ac0680fad765217302858e70fa4Paul Duffin removeFrom = current; 5350888a09821a98ac0680fad765217302858e70fa4Paul Duffin return current.next(); 5360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5370888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5380888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void remove() { 5390888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkRemove(removeFrom != null); 5400888a09821a98ac0680fad765217302858e70fa4Paul Duffin removeFrom.remove(); 5410888a09821a98ac0680fad765217302858e70fa4Paul Duffin removeFrom = null; 5420888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5430888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 5440888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5450888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5460888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 5470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Divides an iterator into unmodifiable sublists of the given size (the final 5480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * list may be smaller). For example, partitioning an iterator containing 5490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code [a, b, c, d, e]} with a partition size of 3 yields {@code 5500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * [[a, b, c], [d, e]]} -- an outer iterator containing two inner lists of 5510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * three and two elements, all in the original order. 5520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 5530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned lists implement {@link java.util.RandomAccess}. 5540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 5550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param iterator the iterator to return a partitioned view of 5560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param size the desired size of each partition (the last may be smaller) 5570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return an iterator of immutable lists containing the elements of {@code 5580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterator} divided into partitions 5590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if {@code size} is nonpositive 5600888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 5610888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<List<T>> partition( 5620888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator, int size) { 5630888a09821a98ac0680fad765217302858e70fa4Paul Duffin return partitionImpl(iterator, size, false); 5640888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5650888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5660888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 5670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Divides an iterator into unmodifiable sublists of the given size, padding 5680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the final iterator with null values if necessary. For example, partitioning 5690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * an iterator containing {@code [a, b, c, d, e]} with a partition size of 3 5700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * yields {@code [[a, b, c], [d, e, null]]} -- an outer iterator containing 5710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * two inner lists of three elements each, all in the original order. 5720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 5730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned lists implement {@link java.util.RandomAccess}. 5740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 5750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param iterator the iterator to return a partitioned view of 5760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param size the desired size of each partition 5770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return an iterator of immutable lists containing the elements of {@code 5780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterator} divided into partitions (the final iterable may have 5790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * trailing null elements) 5800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if {@code size} is nonpositive 5810888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 5820888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<List<T>> paddedPartition( 5830888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator, int size) { 5840888a09821a98ac0680fad765217302858e70fa4Paul Duffin return partitionImpl(iterator, size, true); 5850888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5860888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5870888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static <T> UnmodifiableIterator<List<T>> partitionImpl( 5880888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<T> iterator, final int size, final boolean pad) { 5890888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 5900888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument(size > 0); 5910888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new UnmodifiableIterator<List<T>>() { 5920888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5930888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 5940888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext(); 5950888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5960888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5970888a09821a98ac0680fad765217302858e70fa4Paul Duffin public List<T> next() { 5980888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasNext()) { 5990888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 6000888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6010888a09821a98ac0680fad765217302858e70fa4Paul Duffin Object[] array = new Object[size]; 6020888a09821a98ac0680fad765217302858e70fa4Paul Duffin int count = 0; 6030888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (; count < size && iterator.hasNext(); count++) { 6040888a09821a98ac0680fad765217302858e70fa4Paul Duffin array[count] = iterator.next(); 6050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6060888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = count; i < size; i++) { 6070888a09821a98ac0680fad765217302858e70fa4Paul Duffin array[i] = null; // for GWT 6080888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6090888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6100888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // we only put Ts in it 6110888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<T> list = Collections.unmodifiableList( 6120888a09821a98ac0680fad765217302858e70fa4Paul Duffin (List<T>) Arrays.asList(array)); 6130888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (pad || count == size) ? list : list.subList(0, count); 6140888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6150888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 6160888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6170888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6180888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the elements of {@code unfiltered} that satisfy a predicate. 6200888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 6210888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<T> filter( 6220888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<T> unfiltered, final Predicate<? super T> predicate) { 6230888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(unfiltered); 6240888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(predicate); 6250888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new AbstractIterator<T>() { 6260888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected T computeNext() { 6270888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (unfiltered.hasNext()) { 6280888a09821a98ac0680fad765217302858e70fa4Paul Duffin T element = unfiltered.next(); 6290888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (predicate.apply(element)) { 6300888a09821a98ac0680fad765217302858e70fa4Paul Duffin return element; 6310888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6320888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6330888a09821a98ac0680fad765217302858e70fa4Paul Duffin return endOfData(); 6340888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6350888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 6360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6370888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6380888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns {@code true} if one or more elements returned by {@code iterator} 6400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * satisfy the given predicate. 6410888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 6420888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> boolean any( 6430888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator, Predicate<? super T> predicate) { 6440888a09821a98ac0680fad765217302858e70fa4Paul Duffin return indexOf(iterator, predicate) != -1; 6450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6460888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6470888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns {@code true} if every element returned by {@code iterator} 6490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * satisfies the given predicate. If {@code iterator} is empty, {@code true} 6500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * is returned. 6510888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 6520888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> boolean all( 6530888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator, Predicate<? super T> predicate) { 6540888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(predicate); 6550888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (iterator.hasNext()) { 6560888a09821a98ac0680fad765217302858e70fa4Paul Duffin T element = iterator.next(); 6570888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!predicate.apply(element)) { 6580888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 6590888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6600888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6610888a09821a98ac0680fad765217302858e70fa4Paul Duffin return true; 6620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6630888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6640888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the first element in {@code iterator} that satisfies the given 6660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * predicate; use this method only when such an element is known to exist. If 6670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * no such element is found, the iterator will be left exhausted: its {@code 6680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * hasNext()} method will return {@code false}. If it is possible that 6690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <i>no</i> element will match, use {@link #tryFind} or {@link 6700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * #find(Iterator, Predicate, Object)} instead. 6710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 6720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws NoSuchElementException if no element in {@code iterator} matches 6730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the given predicate 6740888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 6750888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T find( 6760888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator, Predicate<? super T> predicate) { 6770888a09821a98ac0680fad765217302858e70fa4Paul Duffin return filter(iterator, predicate).next(); 6780888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6790888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6800888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the first element in {@code iterator} that satisfies the given 6820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * predicate. If no such element is found, {@code defaultValue} will be 6830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * returned from this method and the iterator will be left exhausted: its 6840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method will return {@code false}. Note that this can 6850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * usually be handled more naturally using {@code 6860888a09821a98ac0680fad765217302858e70fa4Paul Duffin * tryFind(iterator, predicate).or(defaultValue)}. 6870888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 6880888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 7.0 6890888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 6900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable 6910888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T find(Iterator<? extends T> iterator, Predicate<? super T> predicate, 6920888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable T defaultValue) { 6930888a09821a98ac0680fad765217302858e70fa4Paul Duffin return getNext(filter(iterator, predicate), defaultValue); 6940888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6950888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6960888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an {@link Optional} containing the first element in {@code 6980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterator} that satisfies the given predicate, if such an element exists. If 6990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * no such element is found, an empty {@link Optional} will be returned from 7000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * this method and the iterator will be left exhausted: its {@code 7010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * hasNext()} method will return {@code false}. 7020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Warning:</b> avoid using a {@code predicate} that matches {@code 7040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * null}. If {@code null} is matched in {@code iterator}, a 7050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * NullPointerException will be thrown. 7060888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 11.0 7080888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 7090888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Optional<T> tryFind( 7100888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator, Predicate<? super T> predicate) { 7110888a09821a98ac0680fad765217302858e70fa4Paul Duffin UnmodifiableIterator<T> filteredIterator = filter(iterator, predicate); 7120888a09821a98ac0680fad765217302858e70fa4Paul Duffin return filteredIterator.hasNext() 7130888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? Optional.of(filteredIterator.next()) 7140888a09821a98ac0680fad765217302858e70fa4Paul Duffin : Optional.<T>absent(); 7150888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7160888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7170888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 7180888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the index in {@code iterator} of the first element that satisfies 7190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the provided {@code predicate}, or {@code -1} if the Iterator has no such 7200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements. 7210888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7220888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>More formally, returns the lowest index {@code i} such that 7230888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code predicate.apply(Iterators.get(iterator, i))} returns {@code true}, 7240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * or {@code -1} if there is no such index. 7250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>If -1 is returned, the iterator will be left exhausted: its 7270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code hasNext()} method will return {@code false}. Otherwise, 7280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the iterator will be set to the element which satisfies the 7290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code predicate}. 7300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 2.0 7320888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 7330888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> int indexOf( 7340888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<T> iterator, Predicate<? super T> predicate) { 7350888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(predicate, "predicate"); 7360888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 0; iterator.hasNext(); i++) { 7370888a09821a98ac0680fad765217302858e70fa4Paul Duffin T current = iterator.next(); 7380888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (predicate.apply(current)) { 7390888a09821a98ac0680fad765217302858e70fa4Paul Duffin return i; 7400888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7410888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7420888a09821a98ac0680fad765217302858e70fa4Paul Duffin return -1; 7430888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7440888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7450888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 7460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an iterator that applies {@code function} to each element of {@code 7470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * fromIterator}. 7480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator supports {@code remove()} if the provided iterator 7500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * does. After a successful {@code remove()} call, {@code fromIterator} no 7510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * longer contains the corresponding element. 7520888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 7530888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <F, T> Iterator<T> transform(final Iterator<F> fromIterator, 7540888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Function<? super F, ? extends T> function) { 7550888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(function); 7560888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new TransformedIterator<F, T>(fromIterator) { 7570888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 7580888a09821a98ac0680fad765217302858e70fa4Paul Duffin T transform(F from) { 7590888a09821a98ac0680fad765217302858e70fa4Paul Duffin return function.apply(from); 7600888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7610888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 7620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7630888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7640888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 7650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Advances {@code iterator} {@code position + 1} times, returning the 7660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * element at the {@code position}th position. 7670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param position position of the element to return 7690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the element at the specified position in {@code iterator} 7700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IndexOutOfBoundsException if {@code position} is negative or 7710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * greater than or equal to the number of elements remaining in 7720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterator} 7730888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 7740888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T get(Iterator<T> iterator, int position) { 7750888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(position); 7760888a09821a98ac0680fad765217302858e70fa4Paul Duffin int skipped = advance(iterator, position); 7770888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!iterator.hasNext()) { 7780888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new IndexOutOfBoundsException("position (" + position 7790888a09821a98ac0680fad765217302858e70fa4Paul Duffin + ") must be less than the number of elements that remained (" 7800888a09821a98ac0680fad765217302858e70fa4Paul Duffin + skipped + ")"); 7810888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7820888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.next(); 7830888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7840888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7850888a09821a98ac0680fad765217302858e70fa4Paul Duffin static void checkNonnegative(int position) { 7860888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (position < 0) { 7870888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new IndexOutOfBoundsException("position (" + position 7880888a09821a98ac0680fad765217302858e70fa4Paul Duffin + ") must not be negative"); 7890888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7900888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7910888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7920888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 7930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Advances {@code iterator} {@code position + 1} times, returning the 7940888a09821a98ac0680fad765217302858e70fa4Paul Duffin * element at the {@code position}th position or {@code defaultValue} 7950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * otherwise. 7960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param position position of the element to return 7980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param defaultValue the default value to return if the iterator is empty 7990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * or if {@code position} is greater than the number of elements 8000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * remaining in {@code iterator} 8010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the element at the specified position in {@code iterator} or 8020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code defaultValue} if {@code iterator} produces fewer than 8030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code position + 1} elements. 8040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IndexOutOfBoundsException if {@code position} is negative 8050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 4.0 8060888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 8070888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable 8080888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T get(Iterator<? extends T> iterator, int position, @Nullable T defaultValue) { 8090888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(position); 8100888a09821a98ac0680fad765217302858e70fa4Paul Duffin advance(iterator, position); 8110888a09821a98ac0680fad765217302858e70fa4Paul Duffin return getNext(iterator, defaultValue); 8120888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8130888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8140888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 8150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the next element in {@code iterator} or {@code defaultValue} if 8160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the iterator is empty. The {@link Iterables} analog to this method is 8170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link Iterables#getFirst}. 8180888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 8190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param defaultValue the default value to return if the iterator is empty 8200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the next element of {@code iterator} or the default value 8210888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 7.0 8220888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 8230888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable 8240888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T getNext(Iterator<? extends T> iterator, @Nullable T defaultValue) { 8250888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext() ? iterator.next() : defaultValue; 8260888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8270888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8280888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 8290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Advances {@code iterator} to the end, returning the last element. 8300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 8310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the last element of {@code iterator} 8320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws NoSuchElementException if the iterator is empty 8330888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 8340888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T getLast(Iterator<T> iterator) { 8350888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (true) { 8360888a09821a98ac0680fad765217302858e70fa4Paul Duffin T current = iterator.next(); 8370888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!iterator.hasNext()) { 8380888a09821a98ac0680fad765217302858e70fa4Paul Duffin return current; 8390888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8400888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8410888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8420888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8430888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 8440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Advances {@code iterator} to the end, returning the last element or 8450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code defaultValue} if the iterator is empty. 8460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 8470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param defaultValue the default value to return if the iterator is empty 8480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the last element of {@code iterator} 8490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 3.0 8500888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 8510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable 8520888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> T getLast(Iterator<? extends T> iterator, @Nullable T defaultValue) { 8530888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext() ? getLast(iterator) : defaultValue; 8540888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8550888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8560888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 8570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Calls {@code next()} on {@code iterator}, either {@code numberToAdvance} times 8580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * or until {@code hasNext()} returns {@code false}, whichever comes first. 8590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 8600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the number of elements the iterator was advanced 8610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 13.0 (since 3.0 as {@code Iterators.skip}) 8620888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 8630888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static int advance(Iterator<?> iterator, int numberToAdvance) { 8640888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 8650888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument(numberToAdvance >= 0, "numberToAdvance must be nonnegative"); 8660888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8670888a09821a98ac0680fad765217302858e70fa4Paul Duffin int i; 8680888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (i = 0; i < numberToAdvance && iterator.hasNext(); i++) { 8690888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.next(); 8700888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8710888a09821a98ac0680fad765217302858e70fa4Paul Duffin return i; 8720888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8730888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8740888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 8750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an iterator returning the first {@code limitSize} elements of the 8760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * given iterator. If the original iterator does not contain that many 8770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements, the returned iterator will have the same behavior as the original 8780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterator. The returned iterator supports {@code remove()} if the original 8790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iterator does. 8800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 8810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param iterator the iterator to limit 8820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param limitSize the maximum number of elements in the returned iterator 8830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if {@code limitSize} is negative 8840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 3.0 8850888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 8860888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> limit( 8870888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<T> iterator, final int limitSize) { 8880888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 8890888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument(limitSize >= 0, "limit is negative"); 8900888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Iterator<T>() { 8910888a09821a98ac0680fad765217302858e70fa4Paul Duffin private int count; 8920888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8930888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 8940888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 8950888a09821a98ac0680fad765217302858e70fa4Paul Duffin return count < limitSize && iterator.hasNext(); 8960888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8970888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8980888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 8990888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 9000888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasNext()) { 9010888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 9020888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9030888a09821a98ac0680fad765217302858e70fa4Paul Duffin count++; 9040888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.next(); 9050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9060888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9070888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 9080888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void remove() { 9090888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.remove(); 9100888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9110888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 9120888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9130888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9140888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a view of the supplied {@code iterator} that removes each element 9160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * from the supplied {@code iterator} as it is returned. 9170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 9180888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The provided iterator must support {@link Iterator#remove()} or 9190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * else the returned iterator will fail on the first call to {@code 9200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * next}. 9210888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 9220888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param iterator the iterator to remove and return elements from 9230888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return an iterator that removes and returns elements from the 9240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * supplied iterator 9250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 2.0 9260888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9270888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Iterator<T> consumingIterator(final Iterator<T> iterator) { 9280888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 9290888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new UnmodifiableIterator<T>() { 9300888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 9310888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 9320888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext(); 9330888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9340888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9350888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 9360888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 9370888a09821a98ac0680fad765217302858e70fa4Paul Duffin T next = iterator.next(); 9380888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.remove(); 9390888a09821a98ac0680fad765217302858e70fa4Paul Duffin return next; 9400888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9410888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9420888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 9430888a09821a98ac0680fad765217302858e70fa4Paul Duffin public String toString() { 9440888a09821a98ac0680fad765217302858e70fa4Paul Duffin return "Iterators.consumingIterator(...)"; 9450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9460888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 9470888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9480888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9490888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Deletes and returns the next value from the iterator, or returns 9510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code null} if there is no such value. 9520888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9530888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable 9540888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <T> T pollNext(Iterator<T> iterator) { 9550888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (iterator.hasNext()) { 9560888a09821a98ac0680fad765217302858e70fa4Paul Duffin T result = iterator.next(); 9570888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.remove(); 9580888a09821a98ac0680fad765217302858e70fa4Paul Duffin return result; 9590888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else { 9600888a09821a98ac0680fad765217302858e70fa4Paul Duffin return null; 9610888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9630888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9640888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Methods only in Iterators, not in Iterables 9650888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9660888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Clears the iterator using its remove method. 9680888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9690888a09821a98ac0680fad765217302858e70fa4Paul Duffin static void clear(Iterator<?> iterator) { 9700888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 9710888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (iterator.hasNext()) { 9720888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.next(); 9730888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.remove(); 9740888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9750888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9760888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9770888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an iterator containing the elements of {@code array} in order. The 9790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * returned iterator is a view of the array; subsequent changes to the array 9800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * will be reflected in the iterator. 9810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 9820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> It is often preferable to represent your data using a 9830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * collection type, for example using {@link Arrays#asList(Object[])}, making 9840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * this method unnecessary. 9850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 9860888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The {@code Iterable} equivalent of this method is either {@link 9870888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Arrays#asList(Object[])}, {@link ImmutableList#copyOf(Object[])}}, 9880888a09821a98ac0680fad765217302858e70fa4Paul Duffin * or {@link ImmutableList#of}. 9890888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9900888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<T> forArray(final T... array) { 9910888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forArray(array, 0, array.length, 0); 9920888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9930888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9940888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a list iterator containing the elements in the specified range of 9960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code array} in order, starting at the specified index. 9970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 9980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The {@code Iterable} equivalent of this method is {@code 9990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Arrays.asList(array).subList(offset, offset + length).listIterator(index)}. 10000888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 10010888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <T> UnmodifiableListIterator<T> forArray( 10020888a09821a98ac0680fad765217302858e70fa4Paul Duffin final T[] array, final int offset, int length, int index) { 10030888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument(length >= 0); 10040888a09821a98ac0680fad765217302858e70fa4Paul Duffin int end = offset + length; 10050888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10060888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Technically we should give a slightly more descriptive error on overflow 10070888a09821a98ac0680fad765217302858e70fa4Paul Duffin Preconditions.checkPositionIndexes(offset, end, array.length); 10080888a09821a98ac0680fad765217302858e70fa4Paul Duffin Preconditions.checkPositionIndex(index, length); 10090888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (length == 0) { 10100888a09821a98ac0680fad765217302858e70fa4Paul Duffin return emptyListIterator(); 10110888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10120888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10130888a09821a98ac0680fad765217302858e70fa4Paul Duffin /* 10140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * We can't use call the two-arg constructor with arguments (offset, end) 10150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * because the returned Iterator is a ListIterator that may be moved back 10160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * past the beginning of the iteration. 10170888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 10180888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new AbstractIndexedListIterator<T>(length, index) { 10190888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected T get(int index) { 10200888a09821a98ac0680fad765217302858e70fa4Paul Duffin return array[offset + index]; 10210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10220888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 10230888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10240888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10250888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 10260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an iterator containing only {@code value}. 10270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 10280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The {@link Iterable} equivalent of this method is {@link 10290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Collections#singleton}. 10300888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 10310888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<T> singletonIterator( 10320888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable final T value) { 10330888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new UnmodifiableIterator<T>() { 10340888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean done; 10350888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10360888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 10370888a09821a98ac0680fad765217302858e70fa4Paul Duffin return !done; 10380888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10390888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10400888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 10410888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (done) { 10420888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 10430888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10440888a09821a98ac0680fad765217302858e70fa4Paul Duffin done = true; 10450888a09821a98ac0680fad765217302858e70fa4Paul Duffin return value; 10460888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10470888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 10480888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10490888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10500888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 10510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Adapts an {@code Enumeration} to the {@code Iterator} interface. 10520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 10530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>This method has no equivalent in {@link Iterables} because viewing an 10540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code Enumeration} as an {@code Iterable} is impossible. However, the 10550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * contents can be <i>copied</i> into a collection using {@link 10560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Collections#list}. 10570888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 10580888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<T> forEnumeration( 10590888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Enumeration<T> enumeration) { 10600888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(enumeration); 10610888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new UnmodifiableIterator<T>() { 10620888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10630888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 10640888a09821a98ac0680fad765217302858e70fa4Paul Duffin return enumeration.hasMoreElements(); 10650888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10660888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10670888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 10680888a09821a98ac0680fad765217302858e70fa4Paul Duffin return enumeration.nextElement(); 10690888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10700888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 10710888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10720888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10730888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 10740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Adapts an {@code Iterator} to the {@code Enumeration} interface. 10750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 10760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The {@code Iterable} equivalent of this method is either {@link 10770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Collections#enumeration} (if you have a {@link Collection}), or 10780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code Iterators.asEnumeration(collection.iterator())}. 10790888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 10800888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> Enumeration<T> asEnumeration(final Iterator<T> iterator) { 10810888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterator); 10820888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Enumeration<T>() { 10830888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10840888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasMoreElements() { 10850888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.hasNext(); 10860888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10870888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10880888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T nextElement() { 10890888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.next(); 10900888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10910888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 10920888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10930888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10940888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 10950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Implementation of PeekingIterator that avoids peeking unless necessary. 10960888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 10970888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class PeekingImpl<E> implements PeekingIterator<E> { 10980888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10990888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final Iterator<? extends E> iterator; 11000888a09821a98ac0680fad765217302858e70fa4Paul Duffin private boolean hasPeeked; 11010888a09821a98ac0680fad765217302858e70fa4Paul Duffin private E peekedElement; 11020888a09821a98ac0680fad765217302858e70fa4Paul Duffin 11030888a09821a98ac0680fad765217302858e70fa4Paul Duffin public PeekingImpl(Iterator<? extends E> iterator) { 11040888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.iterator = checkNotNull(iterator); 11050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11060888a09821a98ac0680fad765217302858e70fa4Paul Duffin 11070888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 11080888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 11090888a09821a98ac0680fad765217302858e70fa4Paul Duffin return hasPeeked || iterator.hasNext(); 11100888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11110888a09821a98ac0680fad765217302858e70fa4Paul Duffin 11120888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 11130888a09821a98ac0680fad765217302858e70fa4Paul Duffin public E next() { 11140888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasPeeked) { 11150888a09821a98ac0680fad765217302858e70fa4Paul Duffin return iterator.next(); 11160888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11170888a09821a98ac0680fad765217302858e70fa4Paul Duffin E result = peekedElement; 11180888a09821a98ac0680fad765217302858e70fa4Paul Duffin hasPeeked = false; 11190888a09821a98ac0680fad765217302858e70fa4Paul Duffin peekedElement = null; 11200888a09821a98ac0680fad765217302858e70fa4Paul Duffin return result; 11210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11220888a09821a98ac0680fad765217302858e70fa4Paul Duffin 11230888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 11240888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void remove() { 11250888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkState(!hasPeeked, "Can't remove after you've peeked at next"); 11260888a09821a98ac0680fad765217302858e70fa4Paul Duffin iterator.remove(); 11270888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11280888a09821a98ac0680fad765217302858e70fa4Paul Duffin 11290888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 11300888a09821a98ac0680fad765217302858e70fa4Paul Duffin public E peek() { 11310888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasPeeked) { 11320888a09821a98ac0680fad765217302858e70fa4Paul Duffin peekedElement = iterator.next(); 11330888a09821a98ac0680fad765217302858e70fa4Paul Duffin hasPeeked = true; 11340888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11350888a09821a98ac0680fad765217302858e70fa4Paul Duffin return peekedElement; 11360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11370888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11380888a09821a98ac0680fad765217302858e70fa4Paul Duffin 11390888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 11400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a {@code PeekingIterator} backed by the given iterator. 11410888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Calls to the {@code peek} method with no intervening calls to {@code 11430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * next} do not affect the iteration, and hence return the same object each 11440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * time. A subsequent call to {@code next} is guaranteed to return the same 11450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * object again. For example: <pre> {@code 11460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * PeekingIterator<String> peekingIterator = 11480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Iterators.peekingIterator(Iterators.forArray("a", "b")); 11490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * String a1 = peekingIterator.peek(); // returns "a" 11500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * String a2 = peekingIterator.peek(); // also returns "a" 11510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * String a3 = peekingIterator.next(); // also returns "a"}</pre> 11520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Any structural changes to the underlying iteration (aside from those 11540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * performed by the iterator's own {@link PeekingIterator#remove()} method) 11550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * will leave the iterator in an undefined state. 11560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned iterator does not support removal after peeking, as 11580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * explained by {@link PeekingIterator#remove()}. 11590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Note: If the given iterator is already a {@code PeekingIterator}, 11610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * it <i>might</i> be returned to the caller, although this is neither 11620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * guaranteed to occur nor required to be consistent. For example, this 11630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * method <i>might</i> choose to pass through recognized implementations of 11640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code PeekingIterator} when the behavior of the implementation is 11650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * known to meet the contract guaranteed by this method. 11660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>There is no {@link Iterable} equivalent to this method, so use this 11680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * method to wrap each individual iterator as it is generated. 11690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param iterator the backing iterator. The {@link PeekingIterator} assumes 11710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ownership of this iterator, so users should cease making direct calls 11720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * to it after calling this method. 11730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return a peeking iterator backed by that iterator. Apart from the 11740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * additional {@link PeekingIterator#peek()} method, this iterator behaves 11750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * exactly the same as {@code iterator}. 11760888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 11770888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> PeekingIterator<T> peekingIterator( 11780888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends T> iterator) { 11790888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (iterator instanceof PeekingImpl) { 11800888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Safe to cast <? extends T> to <T> because PeekingImpl only uses T 11810888a09821a98ac0680fad765217302858e70fa4Paul Duffin // covariantly (and cannot be subclassed to add non-covariant uses). 11820888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") 11830888a09821a98ac0680fad765217302858e70fa4Paul Duffin PeekingImpl<T> peeking = (PeekingImpl<T>) iterator; 11840888a09821a98ac0680fad765217302858e70fa4Paul Duffin return peeking; 11850888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11860888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new PeekingImpl<T>(iterator); 11870888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11880888a09821a98ac0680fad765217302858e70fa4Paul Duffin 11890888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 11900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Simply returns its argument. 11910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 11920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @deprecated no need to use this 11930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 10.0 11940888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 11950888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Deprecated public static <T> PeekingIterator<T> peekingIterator( 11960888a09821a98ac0680fad765217302858e70fa4Paul Duffin PeekingIterator<T> iterator) { 11970888a09821a98ac0680fad765217302858e70fa4Paul Duffin return checkNotNull(iterator); 11980888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 11990888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12000888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 12010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an iterator over the merged contents of all given 12020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code iterators}, traversing every element of the input iterators. 12030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Equivalent entries will not be de-duplicated. 12040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 12050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Callers must ensure that the source {@code iterators} are in 12060888a09821a98ac0680fad765217302858e70fa4Paul Duffin * non-descending order as this method does not sort its input. 12070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 12080888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>For any equivalent elements across all {@code iterators}, it is 12090888a09821a98ac0680fad765217302858e70fa4Paul Duffin * undefined which element is returned first. 12100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 12110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 11.0 12120888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 12130888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Beta 12140888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> UnmodifiableIterator<T> mergeSorted( 12150888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterable<? extends Iterator<? extends T>> iterators, 12160888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super T> comparator) { 12170888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(iterators, "iterators"); 12180888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(comparator, "comparator"); 12190888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12200888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new MergingIterator<T>(iterators, comparator); 12210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12220888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12230888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 12240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * An iterator that performs a lazy N-way merge, calculating the next value 12250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * each time the iterator is polled. This amortizes the sorting cost over the 12260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * iteration and requires less memory than sorting all elements at once. 12270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 12280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Retrieving a single element takes approximately O(log(M)) time, where M 12290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * is the number of iterators. (Retrieving all elements takes approximately 12300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * O(N*log(M)) time, where N is the total number of elements.) 12310888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 12320888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class MergingIterator<T> extends UnmodifiableIterator<T> { 12330888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Queue<PeekingIterator<T>> queue; 12340888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12350888a09821a98ac0680fad765217302858e70fa4Paul Duffin public MergingIterator(Iterable<? extends Iterator<? extends T>> iterators, 12360888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Comparator<? super T> itemComparator) { 12370888a09821a98ac0680fad765217302858e70fa4Paul Duffin // A comparator that's used by the heap, allowing the heap 12380888a09821a98ac0680fad765217302858e70fa4Paul Duffin // to be sorted based on the top of each iterator. 12390888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<PeekingIterator<T>> heapComparator = 12400888a09821a98ac0680fad765217302858e70fa4Paul Duffin new Comparator<PeekingIterator<T>>() { 12410888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 12420888a09821a98ac0680fad765217302858e70fa4Paul Duffin public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) { 12430888a09821a98ac0680fad765217302858e70fa4Paul Duffin return itemComparator.compare(o1.peek(), o2.peek()); 12440888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12450888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 12460888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12470888a09821a98ac0680fad765217302858e70fa4Paul Duffin queue = new PriorityQueue<PeekingIterator<T>>(2, heapComparator); 12480888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12490888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (Iterator<? extends T> iterator : iterators) { 12500888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (iterator.hasNext()) { 12510888a09821a98ac0680fad765217302858e70fa4Paul Duffin queue.add(Iterators.peekingIterator(iterator)); 12520888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12530888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12540888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12550888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12560888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 12570888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean hasNext() { 12580888a09821a98ac0680fad765217302858e70fa4Paul Duffin return !queue.isEmpty(); 12590888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12600888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12610888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 12620888a09821a98ac0680fad765217302858e70fa4Paul Duffin public T next() { 12630888a09821a98ac0680fad765217302858e70fa4Paul Duffin PeekingIterator<T> nextIter = queue.remove(); 12640888a09821a98ac0680fad765217302858e70fa4Paul Duffin T next = nextIter.next(); 12650888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (nextIter.hasNext()) { 12660888a09821a98ac0680fad765217302858e70fa4Paul Duffin queue.add(nextIter); 12670888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12680888a09821a98ac0680fad765217302858e70fa4Paul Duffin return next; 12690888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12700888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12710888a09821a98ac0680fad765217302858e70fa4Paul Duffin 12720888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 12730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 12740888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 12750888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <T> ListIterator<T> cast(Iterator<T> iterator) { 12760888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (ListIterator<T>) iterator; 12770888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 12780888a09821a98ac0680fad765217302858e70fa4Paul Duffin} 1279