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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkState;
020
021import com.google.common.annotations.GwtCompatible;
022
023import 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 (imported from Google Collections Library)
060 */
061@GwtCompatible
062public 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 {@code 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 {@link #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}