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
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkState;
20
21import com.google.common.annotations.GwtCompatible;
22
23import 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 * 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
64public 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 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   */
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   */
123  protected final T endOfData() {
124    state = State.DONE;
125    return null;
126  }
127
128  @Override
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
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
152  public final T next() {
153    if (!hasNext()) {
154      throw new NoSuchElementException();
155    }
156    state = State.NOT_READY;
157    return next;
158  }
159
160  /**
161   * Returns the next element in the iteration without advancing the iteration,
162   * according to the contract of {@link PeekingIterator#peek()}.
163   *
164   * <p>Implementations of {@code AbstractIterator} that wish to expose this
165   * functionality should implement {@code PeekingIterator}.
166   */
167  public final T peek() {
168    if (!hasNext()) {
169      throw new NoSuchElementException();
170    }
171    return next;
172  }
173}
174