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.testing; 018 019import com.google.common.annotations.GwtCompatible; 020import java.util.Collections; 021import java.util.Iterator; 022import org.checkerframework.checker.nullness.qual.Nullable; 023 024/** 025 * A utility for testing an Iterator implementation by comparing its behavior to that of a "known 026 * good" reference implementation. In order to accomplish this, it's important to test a great 027 * variety of sequences of the {@link Iterator#next}, {@link Iterator#hasNext} and {@link 028 * Iterator#remove} operations. This utility takes the brute-force approach of trying <i>all</i> 029 * possible sequences of these operations, up to a given number of steps. So, if the caller 030 * specifies to use <i>n</i> steps, a total of <i>3^n</i> tests are actually performed. 031 * 032 * <p>For instance, if <i>steps</i> is 5, one example sequence that will be tested is: 033 * 034 * <ol> 035 * <li>remove(); 036 * <li>hasNext() 037 * <li>hasNext(); 038 * <li>remove(); 039 * <li>next(); 040 * </ol> 041 * 042 * <p>This particular order of operations may be unrealistic, and testing all 3^5 of them may be 043 * thought of as overkill; however, it's difficult to determine which proper subset of this massive 044 * set would be sufficient to expose any possible bug. Brute force is simpler. 045 * 046 * <p>To use this class the concrete subclass must implement the {@link 047 * IteratorTester#newTargetIterator()} method. This is because it's impossible to test an Iterator 048 * without changing its state, so the tester needs a steady supply of fresh Iterators. 049 * 050 * <p>If your iterator supports modification through {@code remove()}, you may wish to override the 051 * verify() method, which is called <em>after</em> each sequence and is guaranteed to be called 052 * using the latest values obtained from {@link IteratorTester#newTargetIterator()}. 053 * 054 * <p>The value you pass to the parameter {@code steps} should be greater than the length of your 055 * iterator, so that this class can check that your iterator behaves correctly when it is exhausted. 056 * 057 * <p>For example, to test {@link java.util.Collections#unmodifiableList(java.util.List) 058 * Collections.unmodifiableList}'s iterator: 059 * 060 * <pre>{@code 061 * List<String> expectedElements = 062 * Arrays.asList("a", "b", "c", "d", "e"); 063 * List<String> actualElements = 064 * Collections.unmodifiableList( 065 * Arrays.asList("a", "b", "c", "d", "e")); 066 * IteratorTester<String> iteratorTester = 067 * new IteratorTester<String>( 068 * 6, 069 * IteratorFeature.UNMODIFIABLE, 070 * expectedElements, 071 * IteratorTester.KnownOrder.KNOWN_ORDER) { 072 * @Override 073 * protected Iterator<String> newTargetIterator() { 074 * return actualElements.iterator(); 075 * } 076 * }; 077 * iteratorTester.test(); 078 * iteratorTester.testForEachRemaining(); 079 * }</pre> 080 * 081 * <p><b>Note</b>: It is necessary to use {@code IteratorTester.KnownOrder} as shown above, rather 082 * than {@code KnownOrder} directly, because otherwise the code cannot be compiled. 083 * 084 * @author Kevin Bourrillion 085 * @author Chris Povirk 086 */ 087@GwtCompatible 088@ElementTypesAreNonnullByDefault 089public abstract class IteratorTester<E extends @Nullable Object> 090 extends AbstractIteratorTester<E, Iterator<E>> { 091 /** 092 * Creates an IteratorTester. 093 * 094 * @param steps how many operations to test for each tested pair of iterators 095 * @param features the features supported by the iterator 096 */ 097 protected IteratorTester( 098 int steps, 099 Iterable<? extends IteratorFeature> features, 100 Iterable<E> expectedElements, 101 KnownOrder knownOrder) { 102 super(steps, Collections.<E>singleton(null), features, expectedElements, knownOrder, 0); 103 } 104 105 @Override 106 protected final Iterable<Stimulus<E, Iterator<E>>> getStimulusValues() { 107 return iteratorStimuli(); 108 } 109}