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;
022import com.google.errorprone.annotations.CanIgnoreReturnValue;
023import java.util.NoSuchElementException;
024import org.checkerframework.checker.nullness.qual.Nullable;
025
026/**
027 * This class provides a skeletal implementation of the {@code Iterator} interface, to make this
028 * interface easier to implement for certain types of data sources.
029 *
030 * <p>{@code Iterator} requires its implementations to support querying the end-of-data status
031 * without changing the iterator's state, using the {@link #hasNext} method. But many data sources,
032 * such as {@link java.io.Reader#read()}, do not expose this information; the only way to discover
033 * whether there is any data left is by trying to retrieve it. These types of data sources are
034 * ordinarily difficult to write iterators for. But using this class, one must implement only the
035 * {@link #computeNext} method, and invoke the {@link #endOfData} method when appropriate.
036 *
037 * <p>Another example is an iterator that skips over null elements in a backing iterator. This could
038 * be implemented as:
039 *
040 * <pre>{@code
041 * public static Iterator<String> skipNulls(final Iterator<String> in) {
042 *   return new AbstractIterator<String>() {
043 *     protected String computeNext() {
044 *       while (in.hasNext()) {
045 *         String s = in.next();
046 *         if (s != null) {
047 *           return s;
048 *         }
049 *       }
050 *       return endOfData();
051 *     }
052 *   };
053 * }
054 * }</pre>
055 *
056 * <p>This class supports iterators that include null elements.
057 *
058 * @author Kevin Bourrillion
059 * @since 2.0
060 */
061// When making changes to this class, please also update the copy at
062// com.google.common.base.AbstractIterator
063@GwtCompatible
064public abstract class AbstractIterator<T> extends UnmodifiableIterator<T> {
065  private State state = State.NOT_READY;
066
067  /** Constructor for use by subclasses. */
068  protected AbstractIterator() {}
069
070  private enum State {
071    /** We have computed the next element and haven't returned it yet. */
072    READY,
073
074    /** We haven't yet computed or have already returned the element. */
075    NOT_READY,
076
077    /** We have reached the end of the data and are finished. */
078    DONE,
079
080    /** We've suffered an exception and are kaput. */
081    FAILED,
082  }
083
084  private @Nullable T next;
085
086  /**
087   * Returns the next element. <b>Note:</b> the implementation must call {@link #endOfData()} when
088   * there are no elements left in the iteration. Failure to do so could result in an infinite loop.
089   *
090   * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls this method, as does
091   * the first invocation of {@code hasNext} or {@code next} following each successful call to
092   * {@code next}. Once the 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 {@code hasNext} or
096   * {@code next} invocation that invoked this method. Any further attempts to use the iterator will
097   * result in an {@link IllegalStateException}.
098   *
099   * <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}