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