guava-testlib/src/com/google/common/collect/testing/AbstractIteratorTester.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2008 The Guava Authors
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.google.common.collect.testing;

 import static junit.framework.Assert.assertEquals;
 import static junit.framework.Assert.fail;

 import com.google.common.annotations.GwtCompatible;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.NoSuchElementException;
 import java.util.Set;
 import java.util.Stack;
 import junit.framework.AssertionFailedError;

 /**
  * Most of the logic for {@link IteratorTester} and {@link ListIteratorTester}.
  *
  * @param <E> the type of element returned by the iterator
  * @param <I> the type of the iterator ({@link Iterator} or {@link ListIterator})
  * @author Kevin Bourrillion
  * @author Chris Povirk
  */
 @GwtCompatible
 abstract class AbstractIteratorTester<E, I extends Iterator<E>> {
   private Stimulus<E, ? super I>[] stimuli;
   private final Iterator<E> elementsToInsert;
   private final Set<IteratorFeature> features;
   private final List<E> expectedElements;
   private final int startIndex;
   private final KnownOrder knownOrder;

   /**
    * Meta-exception thrown by {@link AbstractIteratorTester.MultiExceptionListIterator} instead of
    * throwing any particular exception type.
    */
   private abstract static class PermittedMetaException extends RuntimeException {
     static final PermittedMetaException UOE_OR_ISE =
         new PermittedMetaException("UnsupportedOperationException or IllegalStateException") {
           @Override
           boolean isPermitted(RuntimeException exception) {
             return exception instanceof UnsupportedOperationException
                 || exception instanceof IllegalStateException;
           }
         };
     static final PermittedMetaException UOE =
         new PermittedMetaException("UnsupportedOperationException") {
           @Override
           boolean isPermitted(RuntimeException exception) {
             return exception instanceof UnsupportedOperationException;
           }
         };
     static final PermittedMetaException ISE =
         new PermittedMetaException("IllegalStateException") {
           @Override
           boolean isPermitted(RuntimeException exception) {
             return exception instanceof IllegalStateException;
           }
         };
     static final PermittedMetaException NSEE =
         new PermittedMetaException("NoSuchElementException") {
           @Override
           boolean isPermitted(RuntimeException exception) {
             return exception instanceof NoSuchElementException;
           }
         };

     private PermittedMetaException(String message) {
       super(message);
     }

     abstract boolean isPermitted(RuntimeException exception);

     void assertPermitted(RuntimeException exception) {
       if (!isPermitted(exception)) {
         String message =
             "Exception "
                 + exception.getClass().getSimpleName()
                 + " was thrown; expected "
                 + getMessage();
         Helpers.fail(exception, message);
       }
     }

     private static final long serialVersionUID = 0;
   }

   private static final class UnknownElementException extends RuntimeException {
     private UnknownElementException(Collection<?> expected, Object actual) {
       super("Returned value '" + actual + "' not found. Remaining elements: " + expected);
     }

     private static final long serialVersionUID = 0;
   }

   /**
    * Quasi-implementation of {@link ListIterator} that works from a list of elements and a set of
    * features to support (from the enclosing {@link AbstractIteratorTester} instance). Instead of
    * throwing exceptions like {@link NoSuchElementException} at the appropriate times, it throws
    * {@link PermittedMetaException} instances, which wrap a set of all exceptions that the iterator
    * could throw during the invocation of that method. This is necessary because, e.g., a call to
    * {@code iterator().remove()} of an unmodifiable list could throw either {@link
    * IllegalStateException} or {@link UnsupportedOperationException}. Note that iterator
    * implementations should always throw one of the exceptions in a {@code PermittedExceptions}
    * instance, since {@code PermittedExceptions} is thrown only when a method call is invalid.
    *
    * <p>This class is accessible but not supported in GWT as it references {@link
    * PermittedMetaException}.
    */
   protected final class MultiExceptionListIterator implements ListIterator<E> {
     // TODO: track seen elements when order isn't guaranteed
     // TODO: verify contents afterward
     // TODO: something shiny and new instead of Stack
     // TODO: test whether null is supported (create a Feature)
     /**
      * The elements to be returned by future calls to {@code next()}, with the first at the top of
      * the stack.
      */
     final Stack<E> nextElements = new Stack<E>();
     /**
      * The elements to be returned by future calls to {@code previous()}, with the first at the top
      * of the stack.
      */
     final Stack<E> previousElements = new Stack<E>();
     /**
      * {@link #nextElements} if {@code next()} was called more recently then {@code previous},
      * {@link #previousElements} if the reverse is true, or -- overriding both of these -- {@code
      * null} if {@code remove()} or {@code add()} has been called more recently than either. We use
      * this to determine which stack to pop from on a call to {@code remove()} (or to pop from and
      * push to on a call to {@code set()}.
      */
     Stack<E> stackWithLastReturnedElementAtTop = null;

     MultiExceptionListIterator(List<E> expectedElements) {
       Helpers.addAll(nextElements, Helpers.reverse(expectedElements));
       for (int i = 0; i < startIndex; i++) {
         previousElements.push(nextElements.pop());
       }
     }

     @Override
     public void add(E e) {
       if (!features.contains(IteratorFeature.SUPPORTS_ADD)) {
         throw PermittedMetaException.UOE;
       }

       previousElements.push(e);
       stackWithLastReturnedElementAtTop = null;
     }

     @Override
     public boolean hasNext() {
       return !nextElements.isEmpty();
     }

     @Override
     public boolean hasPrevious() {
       return !previousElements.isEmpty();
     }

     @Override
     public E next() {
       return transferElement(nextElements, previousElements);
     }

     @Override
     public int nextIndex() {
       return previousElements.size();
     }

     @Override
     public E previous() {
       return transferElement(previousElements, nextElements);
     }

     @Override
     public int previousIndex() {
       return nextIndex() - 1;
     }

     @Override
     public void remove() {
       throwIfInvalid(IteratorFeature.SUPPORTS_REMOVE);

       stackWithLastReturnedElementAtTop.pop();
       stackWithLastReturnedElementAtTop = null;
     }

     @Override
     public void set(E e) {
       throwIfInvalid(IteratorFeature.SUPPORTS_SET);

       stackWithLastReturnedElementAtTop.pop();
       stackWithLastReturnedElementAtTop.push(e);
     }

     /**
      * Moves the given element from its current position in {@link #nextElements} to the top of the
      * stack so that it is returned by the next call to {@link Iterator#next()}. If the element is
      * not in {@link #nextElements}, this method throws an {@link UnknownElementException}.
      *
      * <p>This method is used when testing iterators without a known ordering. We poll the target
      * iterator's next element and pass it to the reference iterator through this method so it can
      * return the same element. This enables the assertion to pass and the reference iterator to
      * properly update its state.
      */
     void promoteToNext(E e) {
       if (nextElements.remove(e)) {
         nextElements.push(e);
       } else {
         throw new UnknownElementException(nextElements, e);
       }
     }

     private E transferElement(Stack<E> source, Stack<E> destination) {
       if (source.isEmpty()) {
         throw PermittedMetaException.NSEE;
       }

       destination.push(source.pop());
       stackWithLastReturnedElementAtTop = destination;
       return destination.peek();
     }

     private void throwIfInvalid(IteratorFeature methodFeature) {
       if (!features.contains(methodFeature)) {
         if (stackWithLastReturnedElementAtTop == null) {
           throw PermittedMetaException.UOE_OR_ISE;
         } else {
           throw PermittedMetaException.UOE;
         }
       } else if (stackWithLastReturnedElementAtTop == null) {
         throw PermittedMetaException.ISE;
       }
     }

     private List<E> getElements() {
       List<E> elements = new ArrayList<E>();
       Helpers.addAll(elements, previousElements);
       Helpers.addAll(elements, Helpers.reverse(nextElements));
       return elements;
     }
   }

   public enum KnownOrder {
     KNOWN_ORDER,
     UNKNOWN_ORDER
   }

   @SuppressWarnings("unchecked") // creating array of generic class Stimulus
   AbstractIteratorTester(
       int steps,
       Iterable<E> elementsToInsertIterable,
       Iterable<? extends IteratorFeature> features,
       Iterable<E> expectedElements,
       KnownOrder knownOrder,
       int startIndex) {
     // periodically we should manually try (steps * 3 / 2) here; all tests but
     // one should still pass (testVerifyGetsCalled()).
     stimuli = new Stimulus[steps];
     if (!elementsToInsertIterable.iterator().hasNext()) {
       throw new IllegalArgumentException();
     }
     elementsToInsert = Helpers.cycle(elementsToInsertIterable);
     this.features = Helpers.copyToSet(features);
     this.expectedElements = Helpers.copyToList(expectedElements);
     this.knownOrder = knownOrder;
     this.startIndex = startIndex;
   }

   /**
    * I'd like to make this a parameter to the constructor, but I can't because the stimulus
    * instances refer to {@code this}.
    */
   protected abstract Iterable<? extends Stimulus<E, ? super I>> getStimulusValues();

   /**
    * Returns a new target iterator each time it's called. This is the iterator you are trying to
    * test. This must return an Iterator that returns the expected elements passed to the constructor
    * in the given order. Warning: it is not enough to simply pull multiple iterators from the same
    * source Iterable, unless that Iterator is unmodifiable.
    */
   protected abstract I newTargetIterator();

   /**
    * Override this to verify anything after running a list of Stimuli.
    *
    * <p>For example, verify that calls to remove() actually removed the correct elements.
    *
    * @param elements the expected elements passed to the constructor, as mutated by {@code
    *     remove()}, {@code set()}, and {@code add()} calls
    */
   protected void verify(List<E> elements) {}

   /** Executes the test. */
   public final void test() {
     try {
       recurse(0);
     } catch (RuntimeException e) {
       throw new RuntimeException(Arrays.toString(stimuli), e);
     }
   }

   public void testForEachRemaining() {
     for (int i = 0; i < expectedElements.size() - 1; i++) {
       List<E> targetElements = new ArrayList<E>();
       Iterator<E> iterator = newTargetIterator();
       for (int j = 0; j < i; j++) {
         targetElements.add(iterator.next());
       }
       iterator.forEachRemaining(targetElements::add);
       if (knownOrder == KnownOrder.KNOWN_ORDER) {
         assertEquals(expectedElements, targetElements);
       } else {
         Helpers.assertEqualIgnoringOrder(expectedElements, targetElements);
       }
     }
   }

   private void recurse(int level) {
     // We're going to reuse the stimuli array 3^steps times by overwriting it
     // in a recursive loop.  Sneaky.
     if (level == stimuli.length) {
       // We've filled the array.
       compareResultsForThisListOfStimuli();
     } else {
       // Keep recursing to fill the array.
       for (Stimulus<E, ? super I> stimulus : getStimulusValues()) {
         stimuli[level] = stimulus;
         recurse(level + 1);
       }
     }
   }

   private void compareResultsForThisListOfStimuli() {
     int removes = Collections.frequency(Arrays.asList(stimuli), remove);
     if ((!features.contains(IteratorFeature.SUPPORTS_REMOVE) && removes > 1)
         || (stimuli.length >= 5 && removes > 2)) {
       // removes are the most expensive thing to test, since they often throw exceptions with stack
       // traces, so we test them a bit less aggressively
       return;
     }

     MultiExceptionListIterator reference = new MultiExceptionListIterator(expectedElements);
     I target = newTargetIterator();
     for (int i = 0; i < stimuli.length; i++) {
       try {
         stimuli[i].executeAndCompare(reference, target);
         verify(reference.getElements());
       } catch (AssertionFailedError cause) {
         Helpers.fail(cause, "failed with stimuli " + subListCopy(stimuli, i + 1));
       }
     }
   }

   private static List<Object> subListCopy(Object[] source, int size) {
     final Object[] copy = new Object[size];
     System.arraycopy(source, 0, copy, 0, size);
     return Arrays.asList(copy);
   }

   private interface IteratorOperation {
     Object execute(Iterator<?> iterator);
   }

   /**
    * Apply this method to both iterators and return normally only if both produce the same response.
    *
    * @see Stimulus#executeAndCompare(ListIterator, Iterator)
    */
   private <T extends Iterator<E>> void internalExecuteAndCompare(
       T reference, T target, IteratorOperation method) {
     Object referenceReturnValue = null;
     PermittedMetaException referenceException = null;
     Object targetReturnValue = null;
     RuntimeException targetException = null;

     try {
       targetReturnValue = method.execute(target);
     } catch (RuntimeException e) {
       targetException = e;
     }

     try {
       if (method == NEXT_METHOD
           && targetException == null
           && knownOrder == KnownOrder.UNKNOWN_ORDER) {
         /*
          * We already know the iterator is an Iterator<E>, and now we know that
          * we called next(), so the returned element must be of type E.
          */
         @SuppressWarnings("unchecked")
         E targetReturnValueFromNext = (E) targetReturnValue;
         /*
          * We have an Iterator<E> and want to cast it to
          * MultiExceptionListIterator. Because we're inside an
          * AbstractIteratorTester<E>, that's implicitly a cast to
          * AbstractIteratorTester<E>.MultiExceptionListIterator. The runtime
          * won't be able to verify the AbstractIteratorTester<E> part, so it's
          * an unchecked cast. We know, however, that the only possible value for
          * the type parameter is <E>, since otherwise the
          * MultiExceptionListIterator wouldn't be an Iterator<E>. The cast is
          * safe, even though javac can't tell.
          *
          * Sun bug 6665356 is an additional complication. Until OpenJDK 7, javac
          * doesn't recognize this kind of cast as unchecked cast. Neither does
          * Eclipse 3.4. Right now, this suppression is mostly unnecessary.
          */
         MultiExceptionListIterator multiExceptionListIterator =
             (MultiExceptionListIterator) reference;
         multiExceptionListIterator.promoteToNext(targetReturnValueFromNext);
       }

       referenceReturnValue = method.execute(reference);
     } catch (PermittedMetaException e) {
       referenceException = e;
     } catch (UnknownElementException e) {
       Helpers.fail(e, e.getMessage());
     }

     if (referenceException == null) {
       if (targetException != null) {
         Helpers.fail(targetException, "Target threw exception when reference did not");
       }

       /*
        * Reference iterator returned a value, so we should expect the
        * same value from the target
        */
       assertEquals(referenceReturnValue, targetReturnValue);

       return;
     }

     if (targetException == null) {
       fail("Target failed to throw " + referenceException);
     }

     /*
      * Reference iterator threw an exception, so we should expect an acceptable
      * exception from the target.
      */
     referenceException.assertPermitted(targetException);
   }

   private static final IteratorOperation REMOVE_METHOD =
       new IteratorOperation() {
         @Override
         public Object execute(Iterator<?> iterator) {
           iterator.remove();
           return null;
         }
       };

   private static final IteratorOperation NEXT_METHOD =
       new IteratorOperation() {
         @Override
         public Object execute(Iterator<?> iterator) {
           return iterator.next();
         }
       };

   private static final IteratorOperation PREVIOUS_METHOD =
       new IteratorOperation() {
         @Override
         public Object execute(Iterator<?> iterator) {
           return ((ListIterator<?>) iterator).previous();
         }
       };

   private final IteratorOperation newAddMethod() {
     final Object toInsert = elementsToInsert.next();
     return new IteratorOperation() {
       @Override
       public Object execute(Iterator<?> iterator) {
         @SuppressWarnings("unchecked")
         ListIterator<Object> rawIterator = (ListIterator<Object>) iterator;
         rawIterator.add(toInsert);
         return null;
       }
     };
   }

   private final IteratorOperation newSetMethod() {
     final E toInsert = elementsToInsert.next();
     return new IteratorOperation() {
       @Override
       public Object execute(Iterator<?> iterator) {
         @SuppressWarnings("unchecked")
         ListIterator<E> li = (ListIterator<E>) iterator;
         li.set(toInsert);
         return null;
       }
     };
   }

   abstract static class Stimulus<E, T extends Iterator<E>> {
     private final String toString;

     protected Stimulus(String toString) {
       this.toString = toString;
     }

     /**
      * Send this stimulus to both iterators and return normally only if both produce the same
      * response.
      */
     abstract void executeAndCompare(ListIterator<E> reference, T target);

     @Override
     public String toString() {
       return toString;
     }
   }

   Stimulus<E, Iterator<E>> hasNext =
       new Stimulus<E, Iterator<E>>("hasNext") {
         @Override
         void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
           assertEquals(reference.hasNext(), target.hasNext());
         }
       };
   Stimulus<E, Iterator<E>> next =
       new Stimulus<E, Iterator<E>>("next") {
         @Override
         void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
           internalExecuteAndCompare(reference, target, NEXT_METHOD);
         }
       };
   Stimulus<E, Iterator<E>> remove =
       new Stimulus<E, Iterator<E>>("remove") {
         @Override
         void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
           internalExecuteAndCompare(reference, target, REMOVE_METHOD);
         }
       };

   @SuppressWarnings("unchecked")
   List<Stimulus<E, Iterator<E>>> iteratorStimuli() {
     return Arrays.asList(hasNext, next, remove);
   }

   Stimulus<E, ListIterator<E>> hasPrevious =
       new Stimulus<E, ListIterator<E>>("hasPrevious") {
         @Override
         void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
           assertEquals(reference.hasPrevious(), target.hasPrevious());
         }
       };
   Stimulus<E, ListIterator<E>> nextIndex =
       new Stimulus<E, ListIterator<E>>("nextIndex") {
         @Override
         void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
           assertEquals(reference.nextIndex(), target.nextIndex());
         }
       };
   Stimulus<E, ListIterator<E>> previousIndex =
       new Stimulus<E, ListIterator<E>>("previousIndex") {
         @Override
         void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
           assertEquals(reference.previousIndex(), target.previousIndex());
         }
       };
   Stimulus<E, ListIterator<E>> previous =
       new Stimulus<E, ListIterator<E>>("previous") {
         @Override
         void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
           internalExecuteAndCompare(reference, target, PREVIOUS_METHOD);
         }
       };
   Stimulus<E, ListIterator<E>> add =
       new Stimulus<E, ListIterator<E>>("add") {
         @Override
         void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
           internalExecuteAndCompare(reference, target, newAddMethod());
         }
       };
   Stimulus<E, ListIterator<E>> set =
       new Stimulus<E, ListIterator<E>>("set") {
         @Override
         void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
           internalExecuteAndCompare(reference, target, newSetMethod());
         }
       };

   @SuppressWarnings("unchecked")
   List<Stimulus<E, ListIterator<E>>> listIteratorStimuli() {
     return Arrays.asList(hasPrevious, nextIndex, previousIndex, previous, add, set);
   }
 }
	/*
	* Copyright (C) 2008 The Guava Authors
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.google.common.collect.testing;

	import static junit.framework.Assert.assertEquals;
	import static junit.framework.Assert.fail;

	import com.google.common.annotations.GwtCompatible;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Iterator;
	import java.util.List;
	import java.util.ListIterator;
	import java.util.NoSuchElementException;
	import java.util.Set;
	import java.util.Stack;
	import junit.framework.AssertionFailedError;

	/**
	* Most of the logic for {@link IteratorTester} and {@link ListIteratorTester}.
	*
	* @param <E> the type of element returned by the iterator
	* @param <I> the type of the iterator ({@link Iterator} or {@link ListIterator})
	* @author Kevin Bourrillion
	* @author Chris Povirk
	*/
	@GwtCompatible
	abstract class AbstractIteratorTester<E, I extends Iterator<E>> {
	private Stimulus<E, ? super I>[] stimuli;
	private final Iterator<E> elementsToInsert;
	private final Set<IteratorFeature> features;
	private final List<E> expectedElements;
	private final int startIndex;
	private final KnownOrder knownOrder;

	/**
	* Meta-exception thrown by {@link AbstractIteratorTester.MultiExceptionListIterator} instead of
	* throwing any particular exception type.
	*/
	private abstract static class PermittedMetaException extends RuntimeException {
	static final PermittedMetaException UOE_OR_ISE =
	new PermittedMetaException("UnsupportedOperationException or IllegalStateException") {
	@Override
	boolean isPermitted(RuntimeException exception) {
	return exception instanceof UnsupportedOperationException
	\|\| exception instanceof IllegalStateException;
	}
	};
	static final PermittedMetaException UOE =
	new PermittedMetaException("UnsupportedOperationException") {
	@Override
	boolean isPermitted(RuntimeException exception) {
	return exception instanceof UnsupportedOperationException;
	}
	};
	static final PermittedMetaException ISE =
	new PermittedMetaException("IllegalStateException") {
	@Override
	boolean isPermitted(RuntimeException exception) {
	return exception instanceof IllegalStateException;
	}
	};
	static final PermittedMetaException NSEE =
	new PermittedMetaException("NoSuchElementException") {
	@Override
	boolean isPermitted(RuntimeException exception) {
	return exception instanceof NoSuchElementException;
	}
	};

	private PermittedMetaException(String message) {
	super(message);
	}

	abstract boolean isPermitted(RuntimeException exception);

	void assertPermitted(RuntimeException exception) {
	if (!isPermitted(exception)) {
	String message =
	"Exception "
	+ exception.getClass().getSimpleName()
	+ " was thrown; expected "
	+ getMessage();
	Helpers.fail(exception, message);
	}
	}

	private static final long serialVersionUID = 0;
	}

	private static final class UnknownElementException extends RuntimeException {
	private UnknownElementException(Collection<?> expected, Object actual) {
	super("Returned value '" + actual + "' not found. Remaining elements: " + expected);
	}

	private static final long serialVersionUID = 0;
	}

	/**
	* Quasi-implementation of {@link ListIterator} that works from a list of elements and a set of
	* features to support (from the enclosing {@link AbstractIteratorTester} instance). Instead of
	* throwing exceptions like {@link NoSuchElementException} at the appropriate times, it throws
	* {@link PermittedMetaException} instances, which wrap a set of all exceptions that the iterator
	* could throw during the invocation of that method. This is necessary because, e.g., a call to
	* {@code iterator().remove()} of an unmodifiable list could throw either {@link
	* IllegalStateException} or {@link UnsupportedOperationException}. Note that iterator
	* implementations should always throw one of the exceptions in a {@code PermittedExceptions}
	* instance, since {@code PermittedExceptions} is thrown only when a method call is invalid.
	*
	* <p>This class is accessible but not supported in GWT as it references {@link
	* PermittedMetaException}.
	*/
	protected final class MultiExceptionListIterator implements ListIterator<E> {
	// TODO: track seen elements when order isn't guaranteed
	// TODO: verify contents afterward
	// TODO: something shiny and new instead of Stack
	// TODO: test whether null is supported (create a Feature)
	/**
	* The elements to be returned by future calls to {@code next()}, with the first at the top of
	* the stack.
	*/
	final Stack<E> nextElements = new Stack<E>();
	/**
	* The elements to be returned by future calls to {@code previous()}, with the first at the top
	* of the stack.
	*/
	final Stack<E> previousElements = new Stack<E>();
	/**
	* {@link #nextElements} if {@code next()} was called more recently then {@code previous},
	* {@link #previousElements} if the reverse is true, or -- overriding both of these -- {@code
	* null} if {@code remove()} or {@code add()} has been called more recently than either. We use
	* this to determine which stack to pop from on a call to {@code remove()} (or to pop from and
	* push to on a call to {@code set()}.
	*/
	Stack<E> stackWithLastReturnedElementAtTop = null;

	MultiExceptionListIterator(List<E> expectedElements) {
	Helpers.addAll(nextElements, Helpers.reverse(expectedElements));
	for (int i = 0; i < startIndex; i++) {
	previousElements.push(nextElements.pop());
	}
	}

	@Override
	public void add(E e) {
	if (!features.contains(IteratorFeature.SUPPORTS_ADD)) {
	throw PermittedMetaException.UOE;
	}

	previousElements.push(e);
	stackWithLastReturnedElementAtTop = null;
	}

	@Override
	public boolean hasNext() {
	return !nextElements.isEmpty();
	}

	@Override
	public boolean hasPrevious() {
	return !previousElements.isEmpty();
	}

	@Override
	public E next() {
	return transferElement(nextElements, previousElements);
	}

	@Override
	public int nextIndex() {
	return previousElements.size();
	}

	@Override
	public E previous() {
	return transferElement(previousElements, nextElements);
	}

	@Override
	public int previousIndex() {
	return nextIndex() - 1;
	}

	@Override
	public void remove() {
	throwIfInvalid(IteratorFeature.SUPPORTS_REMOVE);

	stackWithLastReturnedElementAtTop.pop();
	stackWithLastReturnedElementAtTop = null;
	}

	@Override
	public void set(E e) {
	throwIfInvalid(IteratorFeature.SUPPORTS_SET);

	stackWithLastReturnedElementAtTop.pop();
	stackWithLastReturnedElementAtTop.push(e);
	}

	/**
	* Moves the given element from its current position in {@link #nextElements} to the top of the
	* stack so that it is returned by the next call to {@link Iterator#next()}. If the element is
	* not in {@link #nextElements}, this method throws an {@link UnknownElementException}.
	*
	* <p>This method is used when testing iterators without a known ordering. We poll the target
	* iterator's next element and pass it to the reference iterator through this method so it can
	* return the same element. This enables the assertion to pass and the reference iterator to
	* properly update its state.
	*/
	void promoteToNext(E e) {
	if (nextElements.remove(e)) {
	nextElements.push(e);
	} else {
	throw new UnknownElementException(nextElements, e);
	}
	}

	private E transferElement(Stack<E> source, Stack<E> destination) {
	if (source.isEmpty()) {
	throw PermittedMetaException.NSEE;
	}

	destination.push(source.pop());
	stackWithLastReturnedElementAtTop = destination;
	return destination.peek();
	}

	private void throwIfInvalid(IteratorFeature methodFeature) {
	if (!features.contains(methodFeature)) {
	if (stackWithLastReturnedElementAtTop == null) {
	throw PermittedMetaException.UOE_OR_ISE;
	} else {
	throw PermittedMetaException.UOE;
	}
	} else if (stackWithLastReturnedElementAtTop == null) {
	throw PermittedMetaException.ISE;
	}
	}

	private List<E> getElements() {
	List<E> elements = new ArrayList<E>();
	Helpers.addAll(elements, previousElements);
	Helpers.addAll(elements, Helpers.reverse(nextElements));
	return elements;
	}
	}

	public enum KnownOrder {
	KNOWN_ORDER,
	UNKNOWN_ORDER
	}

	@SuppressWarnings("unchecked") // creating array of generic class Stimulus
	AbstractIteratorTester(
	int steps,
	Iterable<E> elementsToInsertIterable,
	Iterable<? extends IteratorFeature> features,
	Iterable<E> expectedElements,
	KnownOrder knownOrder,
	int startIndex) {
	// periodically we should manually try (steps * 3 / 2) here; all tests but
	// one should still pass (testVerifyGetsCalled()).
	stimuli = new Stimulus[steps];
	if (!elementsToInsertIterable.iterator().hasNext()) {
	throw new IllegalArgumentException();
	}
	elementsToInsert = Helpers.cycle(elementsToInsertIterable);
	this.features = Helpers.copyToSet(features);
	this.expectedElements = Helpers.copyToList(expectedElements);
	this.knownOrder = knownOrder;
	this.startIndex = startIndex;
	}

	/**
	* I'd like to make this a parameter to the constructor, but I can't because the stimulus
	* instances refer to {@code this}.
	*/
	protected abstract Iterable<? extends Stimulus<E, ? super I>> getStimulusValues();

	/**
	* Returns a new target iterator each time it's called. This is the iterator you are trying to
	* test. This must return an Iterator that returns the expected elements passed to the constructor
	* in the given order. Warning: it is not enough to simply pull multiple iterators from the same
	* source Iterable, unless that Iterator is unmodifiable.
	*/
	protected abstract I newTargetIterator();

	/**
	* Override this to verify anything after running a list of Stimuli.
	*
	* <p>For example, verify that calls to remove() actually removed the correct elements.
	*
	* @param elements the expected elements passed to the constructor, as mutated by {@code
	* remove()}, {@code set()}, and {@code add()} calls
	*/
	protected void verify(List<E> elements) {}

	/** Executes the test. */
	public final void test() {
	try {
	recurse(0);
	} catch (RuntimeException e) {
	throw new RuntimeException(Arrays.toString(stimuli), e);
	}
	}

	public void testForEachRemaining() {
	for (int i = 0; i < expectedElements.size() - 1; i++) {
	List<E> targetElements = new ArrayList<E>();
	Iterator<E> iterator = newTargetIterator();
	for (int j = 0; j < i; j++) {
	targetElements.add(iterator.next());
	}
	iterator.forEachRemaining(targetElements::add);
	if (knownOrder == KnownOrder.KNOWN_ORDER) {
	assertEquals(expectedElements, targetElements);
	} else {
	Helpers.assertEqualIgnoringOrder(expectedElements, targetElements);
	}
	}
	}

	private void recurse(int level) {
	// We're going to reuse the stimuli array 3^steps times by overwriting it
	// in a recursive loop. Sneaky.
	if (level == stimuli.length) {
	// We've filled the array.
	compareResultsForThisListOfStimuli();
	} else {
	// Keep recursing to fill the array.
	for (Stimulus<E, ? super I> stimulus : getStimulusValues()) {
	stimuli[level] = stimulus;
	recurse(level + 1);
	}
	}
	}

	private void compareResultsForThisListOfStimuli() {
	int removes = Collections.frequency(Arrays.asList(stimuli), remove);
	if ((!features.contains(IteratorFeature.SUPPORTS_REMOVE) && removes > 1)
	\|\| (stimuli.length >= 5 && removes > 2)) {
	// removes are the most expensive thing to test, since they often throw exceptions with stack
	// traces, so we test them a bit less aggressively
	return;
	}

	MultiExceptionListIterator reference = new MultiExceptionListIterator(expectedElements);
	I target = newTargetIterator();
	for (int i = 0; i < stimuli.length; i++) {
	try {
	stimuli[i].executeAndCompare(reference, target);
	verify(reference.getElements());
	} catch (AssertionFailedError cause) {
	Helpers.fail(cause, "failed with stimuli " + subListCopy(stimuli, i + 1));
	}
	}
	}

	private static List<Object> subListCopy(Object[] source, int size) {
	final Object[] copy = new Object[size];
	System.arraycopy(source, 0, copy, 0, size);
	return Arrays.asList(copy);
	}

	private interface IteratorOperation {
	Object execute(Iterator<?> iterator);
	}

	/**
	* Apply this method to both iterators and return normally only if both produce the same response.
	*
	* @see Stimulus#executeAndCompare(ListIterator, Iterator)
	*/
	private <T extends Iterator<E>> void internalExecuteAndCompare(
	T reference, T target, IteratorOperation method) {
	Object referenceReturnValue = null;
	PermittedMetaException referenceException = null;
	Object targetReturnValue = null;
	RuntimeException targetException = null;

	try {
	targetReturnValue = method.execute(target);
	} catch (RuntimeException e) {
	targetException = e;
	}

	try {
	if (method == NEXT_METHOD
	&& targetException == null
	&& knownOrder == KnownOrder.UNKNOWN_ORDER) {
	/*
	* We already know the iterator is an Iterator<E>, and now we know that
	* we called next(), so the returned element must be of type E.
	*/
	@SuppressWarnings("unchecked")
	E targetReturnValueFromNext = (E) targetReturnValue;
	/*
	* We have an Iterator<E> and want to cast it to
	* MultiExceptionListIterator. Because we're inside an
	* AbstractIteratorTester<E>, that's implicitly a cast to
	* AbstractIteratorTester<E>.MultiExceptionListIterator. The runtime
	* won't be able to verify the AbstractIteratorTester<E> part, so it's
	* an unchecked cast. We know, however, that the only possible value for
	* the type parameter is <E>, since otherwise the
	* MultiExceptionListIterator wouldn't be an Iterator<E>. The cast is
	* safe, even though javac can't tell.
	*
	* Sun bug 6665356 is an additional complication. Until OpenJDK 7, javac
	* doesn't recognize this kind of cast as unchecked cast. Neither does
	* Eclipse 3.4. Right now, this suppression is mostly unnecessary.
	*/
	MultiExceptionListIterator multiExceptionListIterator =
	(MultiExceptionListIterator) reference;
	multiExceptionListIterator.promoteToNext(targetReturnValueFromNext);
	}

	referenceReturnValue = method.execute(reference);
	} catch (PermittedMetaException e) {
	referenceException = e;
	} catch (UnknownElementException e) {
	Helpers.fail(e, e.getMessage());
	}

	if (referenceException == null) {
	if (targetException != null) {
	Helpers.fail(targetException, "Target threw exception when reference did not");
	}

	/*
	* Reference iterator returned a value, so we should expect the
	* same value from the target
	*/
	assertEquals(referenceReturnValue, targetReturnValue);

	return;
	}

	if (targetException == null) {
	fail("Target failed to throw " + referenceException);
	}

	/*
	* Reference iterator threw an exception, so we should expect an acceptable
	* exception from the target.
	*/
	referenceException.assertPermitted(targetException);
	}

	private static final IteratorOperation REMOVE_METHOD =
	new IteratorOperation() {
	@Override
	public Object execute(Iterator<?> iterator) {
	iterator.remove();
	return null;
	}
	};

	private static final IteratorOperation NEXT_METHOD =
	new IteratorOperation() {
	@Override
	public Object execute(Iterator<?> iterator) {
	return iterator.next();
	}
	};

	private static final IteratorOperation PREVIOUS_METHOD =
	new IteratorOperation() {
	@Override
	public Object execute(Iterator<?> iterator) {
	return ((ListIterator<?>) iterator).previous();
	}
	};

	private final IteratorOperation newAddMethod() {
	final Object toInsert = elementsToInsert.next();
	return new IteratorOperation() {
	@Override
	public Object execute(Iterator<?> iterator) {
	@SuppressWarnings("unchecked")
	ListIterator<Object> rawIterator = (ListIterator<Object>) iterator;
	rawIterator.add(toInsert);
	return null;
	}
	};
	}

	private final IteratorOperation newSetMethod() {
	final E toInsert = elementsToInsert.next();
	return new IteratorOperation() {
	@Override
	public Object execute(Iterator<?> iterator) {
	@SuppressWarnings("unchecked")
	ListIterator<E> li = (ListIterator<E>) iterator;
	li.set(toInsert);
	return null;
	}
	};
	}

	abstract static class Stimulus<E, T extends Iterator<E>> {
	private final String toString;

	protected Stimulus(String toString) {
	this.toString = toString;
	}

	/**
	* Send this stimulus to both iterators and return normally only if both produce the same
	* response.
	*/
	abstract void executeAndCompare(ListIterator<E> reference, T target);

	@Override
	public String toString() {
	return toString;
	}
	}

	Stimulus<E, Iterator<E>> hasNext =
	new Stimulus<E, Iterator<E>>("hasNext") {
	@Override
	void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
	assertEquals(reference.hasNext(), target.hasNext());
	}
	};
	Stimulus<E, Iterator<E>> next =
	new Stimulus<E, Iterator<E>>("next") {
	@Override
	void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
	internalExecuteAndCompare(reference, target, NEXT_METHOD);
	}
	};
	Stimulus<E, Iterator<E>> remove =
	new Stimulus<E, Iterator<E>>("remove") {
	@Override
	void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
	internalExecuteAndCompare(reference, target, REMOVE_METHOD);
	}
	};

	@SuppressWarnings("unchecked")
	List<Stimulus<E, Iterator<E>>> iteratorStimuli() {
	return Arrays.asList(hasNext, next, remove);
	}

	Stimulus<E, ListIterator<E>> hasPrevious =
	new Stimulus<E, ListIterator<E>>("hasPrevious") {
	@Override
	void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
	assertEquals(reference.hasPrevious(), target.hasPrevious());
	}
	};
	Stimulus<E, ListIterator<E>> nextIndex =
	new Stimulus<E, ListIterator<E>>("nextIndex") {
	@Override
	void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
	assertEquals(reference.nextIndex(), target.nextIndex());
	}
	};
	Stimulus<E, ListIterator<E>> previousIndex =
	new Stimulus<E, ListIterator<E>>("previousIndex") {
	@Override
	void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
	assertEquals(reference.previousIndex(), target.previousIndex());
	}
	};
	Stimulus<E, ListIterator<E>> previous =
	new Stimulus<E, ListIterator<E>>("previous") {
	@Override
	void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
	internalExecuteAndCompare(reference, target, PREVIOUS_METHOD);
	}
	};
	Stimulus<E, ListIterator<E>> add =
	new Stimulus<E, ListIterator<E>>("add") {
	@Override
	void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
	internalExecuteAndCompare(reference, target, newAddMethod());
	}
	};
	Stimulus<E, ListIterator<E>> set =
	new Stimulus<E, ListIterator<E>>("set") {
	@Override
	void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
	internalExecuteAndCompare(reference, target, newSetMethod());
	}
	};

	@SuppressWarnings("unchecked")
	List<Stimulus<E, ListIterator<E>>> listIteratorStimuli() {
	return Arrays.asList(hasPrevious, nextIndex, previousIndex, previous, add, set);
	}
	}