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;
020import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
021
022import com.google.common.annotations.GwtCompatible;
023import com.google.errorprone.annotations.CanIgnoreReturnValue;
024import java.util.NoSuchElementException;
025import javax.annotation.CheckForNull;
026import org.checkerframework.checker.nullness.qual.Nullable;
027
028/**
029 * This class provides a skeletal implementation of the {@code Iterator} interface, to make this
030 * interface easier to implement for certain types of data sources.
031 *
032 * <p>{@code Iterator} requires its implementations to support querying the end-of-data status
033 * without changing the iterator's state, using the {@link #hasNext} method. But many data sources,
034 * such as {@link java.io.Reader#read()}, do not expose this information; the only way to discover
035 * whether there is any data left is by trying to retrieve it. These types of data sources are
036 * ordinarily difficult to write iterators for. But using this class, one must implement only the
037 * {@link #computeNext} method, and invoke the {@link #endOfData} method when appropriate.
038 *
039 * <p>Another example is an iterator that skips over null elements in a backing iterator. This could
040 * be implemented as:
041 *
042 * <pre>{@code
043 * public static Iterator<String> skipNulls(final Iterator<String> in) {
044 *   return new AbstractIterator<String>() {
045 *     protected String computeNext() {
046 *       while (in.hasNext()) {
047 *         String s = in.next();
048 *         if (s != null) {
049 *           return s;
050 *         }
051 *       }
052 *       return endOfData();
053 *     }
054 *   };
055 * }
056 * }</pre>
057 *
058 * <p>This class supports iterators that include null elements.
059 *
060 * @author Kevin Bourrillion
061 * @since 2.0
062 */
063// When making changes to this class, please also update the copy at
064// com.google.common.base.AbstractIterator
065@GwtCompatible
066@ElementTypesAreNonnullByDefault
067public abstract class AbstractIterator<T extends @Nullable Object> extends UnmodifiableIterator<T> {
068  private State state = State.NOT_READY;
069
070  /** Constructor for use by subclasses. */
071  protected AbstractIterator() {}
072
073  private enum State {
074    /** We have computed the next element and haven't returned it yet. */
075    READY,
076
077    /** We haven't yet computed or have already returned the element. */
078    NOT_READY,
079
080    /** We have reached the end of the data and are finished. */
081    DONE,
082
083    /** We've suffered an exception and are kaput. */
084    FAILED,
085  }
086
087  @CheckForNull private T next;
088
089  /**
090   * Returns the next element. <b>Note:</b> the implementation must call {@link #endOfData()} when
091   * there are no elements left in the iteration. Failure to do so could result in an infinite loop.
092   *
093   * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls this method, as does
094   * the first invocation of {@code hasNext} or {@code next} following each successful call to
095   * {@code next}. Once the implementation either invokes {@code endOfData} or throws an exception,
096   * {@code computeNext} is guaranteed to never be called again.
097   *
098   * <p>If this method throws an exception, it will propagate outward to the {@code hasNext} or
099   * {@code next} invocation that invoked this method. Any further attempts to use the iterator will
100   * result in an {@link IllegalStateException}.
101   *
102   * <p>The implementation of this method may not invoke the {@code hasNext}, {@code next}, or
103   * {@link #peek()} methods on this instance; if it does, an {@code IllegalStateException} will
104   * result.
105   *
106   * @return the next element if there was one. If {@code endOfData} was called during execution,
107   *     the return value will be ignored.
108   * @throws RuntimeException if any unrecoverable error happens. This exception will propagate
109   *     outward to the {@code hasNext()}, {@code next()}, or {@code peek()} invocation that invoked
110   *     this method. Any further attempts to use the iterator will result in an {@link
111   *     IllegalStateException}.
112   */
113  @CheckForNull
114  protected abstract T computeNext();
115
116  /**
117   * Implementations of {@link #computeNext} <b>must</b> invoke this method when there are no
118   * elements left in the iteration.
119   *
120   * @return {@code null}; a convenience so your {@code computeNext} implementation can use the
121   *     simple statement {@code return endOfData();}
122   */
123  @CanIgnoreReturnValue
124  @CheckForNull
125  protected final T endOfData() {
126    state = State.DONE;
127    return null;
128  }
129
130  @CanIgnoreReturnValue // TODO(kak): Should we remove this? Some people are using it to prefetch?
131  @Override
132  public final boolean hasNext() {
133    checkState(state != State.FAILED);
134    switch (state) {
135      case DONE:
136        return false;
137      case READY:
138        return true;
139      default:
140    }
141    return tryToComputeNext();
142  }
143
144  private boolean tryToComputeNext() {
145    state = State.FAILED; // temporary pessimism
146    next = computeNext();
147    if (state != State.DONE) {
148      state = State.READY;
149      return true;
150    }
151    return false;
152  }
153
154  @CanIgnoreReturnValue // TODO(kak): Should we remove this?
155  @Override
156  @ParametricNullness
157  public final T next() {
158    if (!hasNext()) {
159      throw new NoSuchElementException();
160    }
161    state = State.NOT_READY;
162    // Safe because hasNext() ensures that tryToComputeNext() has put a T into `next`.
163    T result = uncheckedCastNullableTToT(next);
164    next = null;
165    return result;
166  }
167
168  /**
169   * Returns the next element in the iteration without advancing the iteration, according to the
170   * contract of {@link PeekingIterator#peek()}.
171   *
172   * <p>Implementations of {@code AbstractIterator} that wish to expose this functionality should
173   * implement {@code PeekingIterator}.
174   */
175  @ParametricNullness
176  public final T peek() {
177    if (!hasNext()) {
178      throw new NoSuchElementException();
179    }
180    // Safe because hasNext() ensures that tryToComputeNext() has put a T into `next`.
181    return uncheckedCastNullableTToT(next);
182  }
183}