1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkState; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.NoSuchElementException; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This class provides a skeletal implementation of the {@code Iterator} 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * interface, to make this interface easier to implement for certain types of 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * data sources. 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>{@code Iterator} requires its implementations to support querying the 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * end-of-data status without changing the iterator's state, using the {@link 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * #hasNext} method. But many data sources, such as {@link 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * java.io.Reader#read()}, do not expose this information; the only way to 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * discover whether there is any data left is by trying to retrieve it. These 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * types of data sources are ordinarily difficult to write iterators for. But 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * using this class, one must implement only the {@link #computeNext} method, 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and invoke the {@link #endOfData} method when appropriate. 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Another example is an iterator that skips over null elements in a backing 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iterator. This could be implemented as: <pre> {@code 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * public static Iterator<String> skipNulls(final Iterator<String> in) { 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * return new AbstractIterator<String>() { 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * protected String computeNext() { 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * while (in.hasNext()) { 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * String s = in.next(); 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * if (s != null) { 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * return s; 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * } 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * } 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * return endOfData(); 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * } 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * }; 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * }}</pre> 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>This class supports iterators that include null elements. 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert// When making changes to this class, please also update the copy at 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert// com.google.common.base.AbstractIterator 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic abstract class AbstractIterator<T> extends UnmodifiableIterator<T> { 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private State state = State.NOT_READY; 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** Constructor for use by subclasses. */ 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert protected AbstractIterator() {} 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private enum State { 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** We have computed the next element and haven't returned it yet. */ 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson READY, 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** We haven't yet computed or have already returned the element. */ 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson NOT_READY, 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** We have reached the end of the data and are finished. */ 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson DONE, 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** We've suffered an exception and are kaput. */ 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson FAILED, 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private T next; 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the next element. <b>Note:</b> the implementation must call {@link 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * #endOfData()} when there are no elements left in the iteration. Failure to 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * do so could result in an infinite loop. 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this method, as does the first invocation of {@code hasNext} or {@code 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * next} following each successful call to {@code next}. Once the 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation either invokes {@code endOfData} or throws an exception, 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code computeNext} is guaranteed to never be called again. 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If this method throws an exception, it will propagate outward to the 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code hasNext} or {@code next} invocation that invoked this method. Any 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * further attempts to use the iterator will result in an {@link 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * IllegalStateException}. 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The implementation of this method may not invoke the {@code hasNext}, 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code next}, or {@link #peek()} methods on this instance; if it does, an 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code IllegalStateException} will result. 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the next element if there was one. If {@code endOfData} was called 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * during execution, the return value will be ignored. 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws RuntimeException if any unrecoverable error happens. This exception 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * will propagate outward to the {@code hasNext()}, {@code next()}, or 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code peek()} invocation that invoked this method. Any further 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * attempts to use the iterator will result in an 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link IllegalStateException}. 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson protected abstract T computeNext(); 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Implementations of {@link #computeNext} <b>must</b> invoke this method when 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * there are no elements left in the iteration. 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return {@code null}; a convenience so your {@code computeNext} 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation can use the simple statement {@code return endOfData();} 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson protected final T endOfData() { 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson state = State.DONE; 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return null; 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public final boolean hasNext() { 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(state != State.FAILED); 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson switch (state) { 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson case DONE: 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson case READY: 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson default: 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return tryToComputeNext(); 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private boolean tryToComputeNext() { 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson state = State.FAILED; // temporary pessimism 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = computeNext(); 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (state != State.DONE) { 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson state = State.READY; 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public final T next() { 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!hasNext()) { 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson state = State.NOT_READY; 1570888a09821a98ac0680fad765217302858e70fa4Paul Duffin T result = next; 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin next = null; 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin return result; 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the next element in the iteration without advancing the iteration, 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * according to the contract of {@link PeekingIterator#peek()}. 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Implementations of {@code AbstractIterator} that wish to expose this 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * functionality should implement {@code PeekingIterator}. 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public final T peek() { 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!hasNext()) { 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return next; 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 176