Instances of Iterator allow the elements to be iterated only in the forward direction with the method next, but not rewinding the sequence to an earlier position to repeat the elements of the sequence that we already saw the Yirst time around. Since this ability would sometimes be useful in many algorithms that operate on sequences, we shall write a general purpose decorator for Iterator instances that allows a position in any existing sequence to be marked, so that the decorated sequence can afterwards be rewound back to that position.

The mass test method of the JUnit test class RewindIteratorTest uses the simple sequence of natural numbers 0, 1, 2, ... as the underlying sequence, and then performs "mark" and "rewind" operations at pseudo-randomly chosen positions of the sequence. The three public test methods generate the Yirst thousand, Yirst million and Yirst hundred million elements of this sequence. If you edit the test method for the Yirst thousand elements to be verbose, the Yirst eight lines of output (shown below as generated with the instructor's private model solution) help you trace what is supposed to happen, with M and R denoting marking and rewinding, and numbers denoting the element that pops out of the decorated sequence at that moment.

0 1 2	M R 3 4	5 6 M 7 R 7 8 9 10 11 12 13 14 15 16 M 17 R 17
18	19	20	M 21	22 23 24 25 26 27 M 28 M R	29	R 28 29 30 31 R 21 22 23 24
25	26	27	M 28	M 29 30 31 R 29 R 28 29 30	31	32 33 M R 34 35 36 37 38 39
40	41	42	43	44	45	46	47	48	49	50 51 M	52	53	54 55 56 57 58 R 52
53	54	55	56	57	58	59	60	61	62	63 64 M	65	66	M 67 68 69 M 70 M R 71 72

R 70 M R 71 72 73 74 75 76 R 67 68 R 65 66 67 68 69 70 71 72 73 74 75

76 77 78 79 M 80 81 82 83 84 85 86 87 R 80 81 82 83 M 84 85 86 87

R 84 85 86 87 88 89 90 M 91 92 93 94 95 96 97 98 99 100 101 M 102 103

The reader might want to trace the effect of the mark and rewind operations by hand for the Yirst two or three lines. Since the original underlying sequence produces each natural number exactly once and in order, the repeated appearances of each number are due to the rewinding operations.

Create a new class with the following signature in your labs project:

public class RewindIterator implements Iterator

Being a decorator, this class should have a private Yield

private Iterator it;

that refers to the underlying iterator object being decorated, initialized in the constructor

public RewindIterator(Iterator it) { this.it = it; }

Since the underlying iterator does not remember the elements it has produced, your decorator has to store these elements into some kind of list from which they can be extracted for their repeat appearances. The simplest way to do this is to use two such lists, perhaps named

private LinkedList buffer = new LinkedList(); private LinkedList emitted = new LinkedList();

so that emitted contains the elements that have been given out by this decorator with its next method, and buffer contains the elements that have been rewound and are waiting to be given out again. For the iterator functionality, this class must have the methods

@Override public boolean hasNext() @Override public E next()

The decorated iterator has a next element if either its buffer is nonempty or if its underlying iterator has a next element. The next element produced by this decorator is then the Yirst element of the buffer, and in the case that the buffer is empty, the next element of the underlying iterator. If any marks are active at the moment (that is, they have been marked but not yet rewound), the element is pushed into the emitted list.

public void mark()

public void rewind() throws IllegalStateException

These two new methods implement the functionality of marking the current position in the sequence, and later rewinding the sequence back to that position to repeat its elements. It is your task in this lab to implement these methods so that they behave correctly in all possible situations. Note that multiple positions can be marked at the same time, and the same position can be marked multiple times. The method rewind always rewinds the sequence to the most recent marked position, or if there are no active marks at the moment, reports this to the caller by throwing an IllegalStateException. It might be a good idea to use a third instance Yield

private LinkedList markPositions = new LinkedList();

that contains all the positions in the emitted list that have been marked at the current time. (If this list is empty, the emitted elements do not need to be stored in emitted to waste memory, since

such elements will never be needed again.)

TEST CODE: import org.junit.Test; import java.util.Iterator; import java.util.Random; import java.util.zip.CRC32; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class RewindIteratorTest { @Test public void testFirst1000() { // Change false to true to see what your iterator generates. massTest(1000, 876040768L); } @Test public void testFirstMillion() { massTest(1_000_000, 1839975941L); } @Test public void testFirstHundredMillion() { massTest(100_000_000, 2819947101L); } private void massTest(int n, long expected) { CRC32 check = new CRC32(); Random rng = new Random(4444); Iterator ints = new Iterator<>() { int v = 0; public boolean hasNext() { return true; } public Integer next() { return v++; } }; RewindIterator rwi = new RewindIterator<>(ints); int marks = 0, count = 0, prev = -1; for(int i = 0; i < n; i++) { int v = rwi.next(); if(prev != -1) { // If no rewind took place last round, elements must increase by one. assertEquals(prev + 1, v); } prev = v; count++; check.update(v); if(rng.nextInt(100 + i) < 20 || (marks == 0 && count > 10 + i / 10)) { rwi.mark(); marks++; count = 0; } if(marks > 0 && rng.nextInt(100 + i) < 30) { rwi.rewind(); marks--; prev = -1; } } assertEquals(expected, check.getValue()); while(marks-- > 0) { rwi.rewind(); } try { rwi.rewind(); } catch(IllegalStateException e) { return; } // If this line is reached, your rewind method does not fail as specified. fail(); } }