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}