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 @Override 131 public final boolean hasNext() { 132 checkState(state != State.FAILED); 133 switch (state) { 134 case DONE: 135 return false; 136 case READY: 137 return true; 138 default: 139 } 140 return tryToComputeNext(); 141 } 142 143 private boolean tryToComputeNext() { 144 state = State.FAILED; // temporary pessimism 145 next = computeNext(); 146 if (state != State.DONE) { 147 state = State.READY; 148 return true; 149 } 150 return false; 151 } 152 153 @CanIgnoreReturnValue // TODO(kak): Should we remove this? 154 @Override 155 @ParametricNullness 156 public final T next() { 157 if (!hasNext()) { 158 throw new NoSuchElementException(); 159 } 160 state = State.NOT_READY; 161 // Safe because hasNext() ensures that tryToComputeNext() has put a T into `next`. 162 T result = uncheckedCastNullableTToT(next); 163 next = null; 164 return result; 165 } 166 167 /** 168 * Returns the next element in the iteration without advancing the iteration, according to the 169 * contract of {@link PeekingIterator#peek()}. 170 * 171 * <p>Implementations of {@code AbstractIterator} that wish to expose this functionality should 172 * implement {@code PeekingIterator}. 173 */ 174 @ParametricNullness 175 public final T peek() { 176 if (!hasNext()) { 177 throw new NoSuchElementException(); 178 } 179 // Safe because hasNext() ensures that tryToComputeNext() has put a T into `next`. 180 return uncheckedCastNullableTToT(next); 181 } 182}