1 /*
2  * Copyright (C) 2007 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.google.common.collect;
18 
19 import static com.google.common.base.Preconditions.checkState;
20 
21 import com.google.common.annotations.GwtCompatible;
22 
23 import java.util.NoSuchElementException;
24 
25 /**
26  * This class provides a skeletal implementation of the {@code Iterator}
27  * interface, to make this interface easier to implement for certain types of
28  * data sources.
29  *
30  * <p>{@code Iterator} requires its implementations to support querying the
31  * end-of-data status without changing the iterator's state, using the {@link
32  * #hasNext} method. But many data sources, such as {@link
33  * java.io.Reader#read()}, do not expose this information; the only way to
34  * discover whether there is any data left is by trying to retrieve it. These
35  * types of data sources are ordinarily difficult to write iterators for. But
36  * using this class, one must implement only the {@link #computeNext} method,
37  * and invoke the {@link #endOfData} method when appropriate.
38  *
39  * <p>Another example is an iterator that skips over null elements in a backing
40  * iterator. This could be implemented as: <pre>   {@code
41  *
42  *   public static Iterator<String> skipNulls(final Iterator<String> in) {
43  *     return new AbstractIterator<String>() {
44  *       protected String computeNext() {
45  *         while (in.hasNext()) {
46  *           String s = in.next();
47  *           if (s != null) {
48  *             return s;
49  *           }
50  *         }
51  *         return endOfData();
52  *       }
53  *     };
54  *   }}</pre>
55  *
56  * <p>This class supports iterators that include null elements.
57  *
58  * @author Kevin Bourrillion
59  * @since 2.0 (imported from Google Collections Library)
60  */
61 // When making changes to this class, please also update the copy at
62 // com.google.common.base.AbstractIterator
63 @GwtCompatible
64 public abstract class AbstractIterator<T> extends UnmodifiableIterator<T> {
65   private State state = State.NOT_READY;
66 
67   /** Constructor for use by subclasses. */
AbstractIterator()68   protected AbstractIterator() {}
69 
70   private enum State {
71     /** We have computed the next element and haven't returned it yet. */
72     READY,
73 
74     /** We haven't yet computed or have already returned the element. */
75     NOT_READY,
76 
77     /** We have reached the end of the data and are finished. */
78     DONE,
79 
80     /** We've suffered an exception and are kaput. */
81     FAILED,
82   }
83 
84   private T next;
85 
86   /**
87    * Returns the next element. <b>Note:</b> the implementation must call {@link
88    * #endOfData()} when there are no elements left in the iteration. Failure to
89    * do so could result in an infinite loop.
90    *
91    * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls
92    * this method, as does the first invocation of {@code hasNext} or {@code
93    * next} following each successful call to {@code next}. Once the
94    * implementation either invokes {@code endOfData} or throws an exception,
95    * {@code computeNext} is guaranteed to never be called again.
96    *
97    * <p>If this method throws an exception, it will propagate outward to the
98    * {@code hasNext} or {@code next} invocation that invoked this method. Any
99    * further attempts to use the iterator will result in an {@link
100    * IllegalStateException}.
101    *
102    * <p>The implementation of this method may not invoke the {@code hasNext},
103    * {@code next}, or {@link #peek()} methods on this instance; if it does, an
104    * {@code IllegalStateException} will result.
105    *
106    * @return the next element if there was one. If {@code endOfData} was called
107    *     during execution, the return value will be ignored.
108    * @throws RuntimeException if any unrecoverable error happens. This exception
109    *     will propagate outward to the {@code hasNext()}, {@code next()}, or
110    *     {@code peek()} invocation that invoked this method. Any further
111    *     attempts to use the iterator will result in an
112    *     {@link IllegalStateException}.
113    */
computeNext()114   protected abstract T computeNext();
115 
116   /**
117    * Implementations of {@link #computeNext} <b>must</b> invoke this method when
118    * there are no elements left in the iteration.
119    *
120    * @return {@code null}; a convenience so your {@code computeNext}
121    *     implementation can use the simple statement {@code return endOfData();}
122    */
endOfData()123   protected final T endOfData() {
124     state = State.DONE;
125     return null;
126   }
127 
128   @Override
hasNext()129   public final boolean hasNext() {
130     checkState(state != State.FAILED);
131     switch (state) {
132       case DONE:
133         return false;
134       case READY:
135         return true;
136       default:
137     }
138     return tryToComputeNext();
139   }
140 
tryToComputeNext()141   private boolean tryToComputeNext() {
142     state = State.FAILED; // temporary pessimism
143     next = computeNext();
144     if (state != State.DONE) {
145       state = State.READY;
146       return true;
147     }
148     return false;
149   }
150 
151   @Override
next()152   public final T next() {
153     if (!hasNext()) {
154       throw new NoSuchElementException();
155     }
156     state = State.NOT_READY;
157     T result = next;
158     next = null;
159     return result;
160   }
161 
162   /**
163    * Returns the next element in the iteration without advancing the iteration,
164    * according to the contract of {@link PeekingIterator#peek()}.
165    *
166    * <p>Implementations of {@code AbstractIterator} that wish to expose this
167    * functionality should implement {@code PeekingIterator}.
168    */
peek()169   public final T peek() {
170     if (!hasNext()) {
171       throw new NoSuchElementException();
172     }
173     return next;
174   }
175 }
176