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
066public abstract class AbstractIterator<T extends @Nullable Object> extends UnmodifiableIterator<T> {
067  private State state = State.NOT_READY;
068
069  /** Constructor for use by subclasses. */
070  protected AbstractIterator() {}
071
072  private enum State {
073    /** We have computed the next element and haven't returned it yet. */
074    READY,
075
076    /** We haven't yet computed or have already returned the element. */
077    NOT_READY,
078
079    /** We have reached the end of the data and are finished. */
080    DONE,
081
082    /** We've suffered an exception and are kaput. */
083    FAILED,
084  }
085
086  @CheckForNull private T next;
087
088  /**
089   * Returns the next element. <b>Note:</b> the implementation must call {@link #endOfData()} when
090   * there are no elements left in the iteration. Failure to do so could result in an infinite loop.
091   *
092   * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls this method, as does
093   * the first invocation of {@code hasNext} or {@code next} following each successful call to
094   * {@code next}. Once the implementation either invokes {@code endOfData} or throws an exception,
095   * {@code computeNext} is guaranteed to never be called again.
096   *
097   * <p>If this method throws an exception, it will propagate outward to the {@code hasNext} or
098   * {@code next} invocation that invoked this method. Any further attempts to use the iterator will
099   * result in an {@link IllegalStateException}.
100   *
101   * <p>The implementation of this method may not invoke the {@code hasNext}, {@code next}, or
102   * {@link #peek()} methods on this instance; if it does, an {@code IllegalStateException} will
103   * result.
104   *
105   * @return the next element if there was one. If {@code endOfData} was called during execution,
106   *     the return value will be ignored.
107   * @throws RuntimeException if any unrecoverable error happens. This exception will propagate
108   *     outward to the {@code hasNext()}, {@code next()}, or {@code peek()} invocation that invoked
109   *     this method. Any further attempts to use the iterator will result in an {@link
110   *     IllegalStateException}.
111   */
112  @CheckForNull
113  protected abstract T computeNext();
114
115  /**
116   * Implementations of {@link #computeNext} <b>must</b> invoke this method when there are no
117   * elements left in the iteration.
118   *
119   * @return {@code null}; a convenience so your {@code computeNext} implementation can use the
120   *     simple statement {@code return endOfData();}
121   */
122  @CanIgnoreReturnValue
123  @CheckForNull
124  protected final T endOfData() {
125    state = State.DONE;
126    return null;
127  }
128
129  @Override
130  public final boolean hasNext() {
131    checkState(state != State.FAILED);
132    switch (state) {
133      case DONE:
134        return false;
135      case READY:
136        return true;
137      default:
138    }
139    return tryToComputeNext();
140  }
141
142  private boolean tryToComputeNext() {
143    state = State.FAILED; // temporary pessimism
144    next = computeNext();
145    if (state != State.DONE) {
146      state = State.READY;
147      return true;
148    }
149    return false;
150  }
151
152  @CanIgnoreReturnValue // TODO(kak): Should we remove this?
153  @Override
154  @ParametricNullness
155  public final T next() {
156    if (!hasNext()) {
157      throw new NoSuchElementException();
158    }
159    state = State.NOT_READY;
160    // Safe because hasNext() ensures that tryToComputeNext() has put a T into `next`.
161    T result = uncheckedCastNullableTToT(next);
162    next = null;
163    return result;
164  }
165
166  /**
167   * Returns the next element in the iteration without advancing the iteration, according to the
168   * contract of {@link PeekingIterator#peek()}.
169   *
170   * <p>Implementations of {@code AbstractIterator} that wish to expose this functionality should
171   * implement {@code PeekingIterator}.
172   */
173  @ParametricNullness
174  public final T peek() {
175    if (!hasNext()) {
176      throw new NoSuchElementException();
177    }
178    // Safe because hasNext() ensures that tryToComputeNext() has put a T into `next`.
179    return uncheckedCastNullableTToT(next);
180  }
181}