11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect.testing; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A utility for testing an Iterator implementation by comparing its behavior to 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that of a "known good" reference implementation. In order to accomplish this, 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * it's important to test a great variety of sequences of the 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Iterator#next}, {@link Iterator#hasNext} and {@link Iterator#remove} 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * operations. This utility takes the brute-force approach of trying <i>all</i> 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * possible sequences of these operations, up to a given number of steps. So, if 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the caller specifies to use <i>n</i> steps, a total of <i>3^n</i> tests are 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * actually performed. 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>For instance, if <i>steps</i> is 5, one example sequence that will be 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * tested is: 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <ol> 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <li>remove(); 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <li>hasNext() 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <li>hasNext(); 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <li>remove(); 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <li>next(); 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * </ol> 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This particular order of operations may be unrealistic, and testing all 3^5 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of them may be thought of as overkill; however, it's difficult to determine 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which proper subset of this massive set would be sufficient to expose any 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * possible bug. Brute force is simpler. 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>To use this class the concrete subclass must implement the 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link IteratorTester#newTargetIterator()} method. This is because it's 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * impossible to test an Iterator without changing its state, so the tester 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * needs a steady supply of fresh Iterators. 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>If your iterator supports modification through {@code remove()}, you may 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * wish to override the verify() method, which is called <em>after</em> 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * each sequence and is guaranteed to be called using the latest values 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * obtained from {@link IteratorTester#newTargetIterator()}. 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This class is GWT compatible. 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Kevin Bourrillion 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Chris Povirk 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic abstract class IteratorTester<E> extends 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AbstractIteratorTester<E, Iterator<E>> { 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates an IteratorTester. 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param steps how many operations to test for each tested pair of iterators 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param features the features supported by the iterator 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert protected IteratorTester(int steps, 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterable<? extends IteratorFeature> features, 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterable<E> expectedElements, KnownOrder knownOrder) { 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(steps, Collections.<E>singleton(null), features, expectedElements, 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert knownOrder, 0); 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert protected final Iterable<Stimulus<E, Iterator<E>>> getStimulusValues() { 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return iteratorStimuli(); 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 83