001 /*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkState;
020
021 import com.google.common.annotations.GwtCompatible;
022
023 import java.util.NoSuchElementException;
024
025 /**
026 * This class provides a skeletal implementation of the {@code Iterator}
027 * interface, to make this interface easier to implement for certain types of
028 * data sources.
029 *
030 * <p>{@code Iterator} requires its implementations to support querying the
031 * end-of-data status without changing the iterator's state, using the {@link
032 * #hasNext} method. But many data sources, such as {@link
033 * java.io.Reader#read()}, do not expose this information; the only way to
034 * discover whether there is any data left is by trying to retrieve it. These
035 * types of data sources are ordinarily difficult to write iterators for. But
036 * using this class, one must implement only the {@link #computeNext} method,
037 * and invoke the {@link #endOfData} method when appropriate.
038 *
039 * <p>Another example is an iterator that skips over null elements in a backing
040 * iterator. This could be implemented as: <pre> {@code
041 *
042 * public static Iterator<String> skipNulls(final Iterator<String> in) {
043 * return new AbstractIterator<String>() {
044 * protected String computeNext() {
045 * while (in.hasNext()) {
046 * String s = in.next();
047 * if (s != null) {
048 * return s;
049 * }
050 * }
051 * return endOfData();
052 * }
053 * };
054 * }}</pre>
055 *
056 * This class supports iterators that include null elements.
057 *
058 * @author Kevin Bourrillion
059 * @since 2.0 (imported from Google Collections Library)
060 */
061 @GwtCompatible
062 public abstract class AbstractIterator<T> extends UnmodifiableIterator<T> {
063 private State state = State.NOT_READY;
064
065 /** Constructor for use by subclasses. */
066 protected AbstractIterator() {}
067
068 private enum State {
069 /** We have computed the next element and haven't returned it yet. */
070 READY,
071
072 /** We haven't yet computed or have already returned the element. */
073 NOT_READY,
074
075 /** We have reached the end of the data and are finished. */
076 DONE,
077
078 /** We've suffered an exception and are kaput. */
079 FAILED,
080 }
081
082 private T next;
083
084 /**
085 * Returns the next element. <b>Note:</b> the implementation must call {@link
086 * #endOfData()} when there are no elements left in the iteration. Failure to
087 * do so could result in an infinite loop.
088 *
089 * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls
090 * this method, as does the first invocation of {@code hasNext} or {@code
091 * next} following each successful call to {@code next}. Once the
092 * implementation either invokes {@code endOfData} or throws an exception,
093 * {@code computeNext} is guaranteed to never be called again.
094 *
095 * <p>If this method throws an exception, it will propagate outward to the
096 * {@code hasNext} or {@code next} invocation that invoked this method. Any
097 * further attempts to use the iterator will result in an {@link
098 * IllegalStateException}.
099 *
100 * <p>The implementation of this method may not invoke the {@code hasNext},
101 * {@code next}, or {@link #peek()} methods on this instance; if it does, an
102 * {@code IllegalStateException} will result.
103 *
104 * @return the next element if there was one. If {@code endOfData} was called
105 * during execution, the return value will be ignored.
106 * @throws RuntimeException if any unrecoverable error happens. This exception
107 * will propagate outward to the {@code hasNext()}, {@code next()}, or
108 * {@code peek()} invocation that invoked this method. Any further
109 * attempts to use the iterator will result in an
110 * {@link IllegalStateException}.
111 */
112 protected abstract T computeNext();
113
114 /**
115 * Implementations of {@link #computeNext} <b>must</b> invoke this method when
116 * there are no elements left in the iteration.
117 *
118 * @return {@code null}; a convenience so your {@code computeNext}
119 * implementation can use the simple statement {@code return endOfData();}
120 */
121 protected final T endOfData() {
122 state = State.DONE;
123 return null;
124 }
125
126 @Override
127 public final boolean hasNext() {
128 checkState(state != State.FAILED);
129 switch (state) {
130 case DONE:
131 return false;
132 case READY:
133 return true;
134 default:
135 }
136 return tryToComputeNext();
137 }
138
139 private boolean tryToComputeNext() {
140 state = State.FAILED; // temporary pessimism
141 next = computeNext();
142 if (state != State.DONE) {
143 state = State.READY;
144 return true;
145 }
146 return false;
147 }
148
149 @Override
150 public final T next() {
151 if (!hasNext()) {
152 throw new NoSuchElementException();
153 }
154 state = State.NOT_READY;
155 return next;
156 }
157
158 /**
159 * Returns the next element in the iteration without advancing the iteration,
160 * according to the contract of {@link PeekingIterator#peek()}.
161 *
162 * <p>Implementations of {@code AbstractIterator} that wish to expose this
163 * functionality should implement {@code PeekingIterator}.
164 */
165 public final T peek() {
166 if (!hasNext()) {
167 throw new NoSuchElementException();
168 }
169 return next;
170 }
171 }