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 import com.google.errorprone.annotations.CanIgnoreReturnValue;
23 import java.util.NoSuchElementException;
24 import org.checkerframework.checker.nullness.qual.Nullable;
25
26 /**
27 * This class provides a skeletal implementation of the {@code Iterator} interface, to make this
28 * interface easier to implement for certain types of data sources.
29 *
30 * <p>{@code Iterator} requires its implementations to support querying the end-of-data status
31 * without changing the iterator's state, using the {@link #hasNext} method. But many data sources,
32 * such as {@link java.io.Reader#read()}, do not expose this information; the only way to discover
33 * whether there is any data left is by trying to retrieve it. These types of data sources are
34 * ordinarily difficult to write iterators for. But using this class, one must implement only the
35 * {@link #computeNext} method, and invoke the {@link #endOfData} method when appropriate.
36 *
37 * <p>Another example is an iterator that skips over null elements in a backing iterator. This could
38 * be implemented as:
39 *
40 * <pre>{@code
41 * public static Iterator<String> skipNulls(final Iterator<String> in) {
42 * return new AbstractIterator<String>() {
43 * protected String computeNext() {
44 * while (in.hasNext()) {
45 * String s = in.next();
46 * if (s != null) {
47 * return s;
48 * }
49 * }
50 * return endOfData();
51 * }
52 * };
53 * }
54 * }</pre>
55 *
56 * <p>This class supports iterators that include null elements.
57 *
58 * @author Kevin Bourrillion
59 * @since 2.0
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. */
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 @Nullable T next;
85
86 /**
87 * Returns the next element. <b>Note:</b> the implementation must call {@link #endOfData()} when
88 * there are no elements left in the iteration. Failure to do so could result in an infinite loop.
89 *
90 * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls this method, as does
91 * the first invocation of {@code hasNext} or {@code next} following each successful call to
92 * {@code next}. Once the implementation either invokes {@code endOfData} or throws an exception,
93 * {@code computeNext} is guaranteed to never be called again.
94 *
95 * <p>If this method throws an exception, it will propagate outward to the {@code hasNext} or
96 * {@code next} invocation that invoked this method. Any further attempts to use the iterator will
97 * result in an {@link IllegalStateException}.
98 *
99 * <p>The implementation of this method may not invoke the {@code hasNext}, {@code next}, or
100 * {@link #peek()} methods on this instance; if it does, an {@code IllegalStateException} will
101 * result.
102 *
103 * @return the next element if there was one. If {@code endOfData} was called during execution,
104 * the return value will be ignored.
105 * @throws RuntimeException if any unrecoverable error happens. This exception will propagate
106 * outward to the {@code hasNext()}, {@code next()}, or {@code peek()} invocation that invoked
107 * this method. Any further attempts to use the iterator will result in an {@link
108 * IllegalStateException}.
109 */
110 protected abstract T computeNext();
111
112 /**
113 * Implementations of {@link #computeNext} <b>must</b> invoke this method when there are no
114 * elements left in the iteration.
115 *
116 * @return {@code null}; a convenience so your {@code computeNext} implementation can use the
117 * simple statement {@code return endOfData();}
118 */
119 @CanIgnoreReturnValue
120 protected final T endOfData() {
121 state = State.DONE;
122 return null;
123 }
124
125 @CanIgnoreReturnValue // TODO(kak): Should we remove this? Some people are using it to prefetch?
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 @CanIgnoreReturnValue // TODO(kak): Should we remove this?
150 @Override
151 public final T next() {
152 if (!hasNext()) {
153 throw new NoSuchElementException();
154 }
155 state = State.NOT_READY;
156 T result = next;
157 next = null;
158 return result;
159 }
160
161 /**
162 * Returns the next element in the iteration without advancing the iteration, according to the
163 * contract of {@link PeekingIterator#peek()}.
164 *
165 * <p>Implementations of {@code AbstractIterator} that wish to expose this functionality should
166 * implement {@code PeekingIterator}.
167 */
168 public final T peek() {
169 if (!hasNext()) {
170 throw new NoSuchElementException();
171 }
172 return next;
173 }
174 }