0. Introduction.

For this laboratory assignment, you must implement an iterator for the Java class ArrayQueue that was discussed in the lectures. The class ArrayQueue implements a fixed length queue using a circular array.

1. Theory.

Suppose that we want to visit the elements stored in a sequence, like a stack or a queue. Also suppose that we are not allowed to modify the sequence to visit its elements. Then we can visit a sequences elements by using an iterator. An iterator is class whose instances can visit the elements of a sequence. Each iterator typically has a method called hasNext that tests if there are more elements to be visited. It also has a method called next that returns the next element to be visited and advances to the following element. An iterator that visits the elements of a linked stack was discussed in the lectures. We can simplify an iterators design by assuming that the sequence will not change while we visit its elements. For example, if we use an iterator to visit the elements of a stack, then we assume that the stack will not be pushed or popped. Similarly, if we use an iterator to visit the elements of a queue, then we assume that the queue will not be enqueued or dequeued. If a sequence changes while an iterator visits its elements, then the actions of the iterator become undefinedwhich means they dont have to work correctly if that happens.

2. Implementation.

You must add the following members to the class ArrayQueue, whose Java source code is available on Moodle. These members implement an iterator for ArrayQueue. You are not allowed to modify ArrayQueue except to add these additional members.

public class Iterator

This class must be nested inside ArrayQueue. An instance of this class may be used to visit the current elements of an instance of ArrayQueue. It must have one or more private variables that let it know which elements of ArrayQueue are to be visited next. You must decide what those private variables are.

private Iterator(...)

This is Iterators constructor. Of course it must be inside Iterator. It must set Iterators private variables to the values of its parameters. You must decide what these parameters are.

public boolean hasNext()

This method must be inside Iterator. It must return true if there are more elements of ArrayQueue that remain to be visited. It must return falseotherwise. This method must use Iterators private variables only. Hint: use ideas from ArrayQueues method isEmpty.

public Base next()

This method must be inside Iterator. It must return the next Base element to be visited from ArrayQueue. If no more elements remain to be visited, then it must throw an IllegalStateException. This method must use Iterators private variables only. Hint: use ideas from ArrayQueues method dequeue.

public Iterator iterator()

This method must be inside ArrayQueue. It must call Iterators constructor to make a new instance of Iterator. It must then return the new instance.

Be careful to put these members in the right places. For example, Iterator must be nested inside ArrayQueue, and next must be inside Iterator, etc. If the members are in the wrong places, then the iterator will not work. This gives us a slightly different kind of iterator from the one discussed in the lecture, and also different from the ones provided by Java. It does not have a removemethod, and it is not accessed using an interface. The file tests.java on Moodle contains Java code that performs a series of tests. The tests call methods from the ArrayQueue class and your Iterator class. Some of them print what those methods return. Each test is also followed by a comment that tells how many points it is worth, and optionally what must be printed if it works correctly.

3. Deliverables.

Run the tests, then turn in the Java source code for the modified ArrayQueue class with your Iterator class in it. Your lab TA will tell you how and where to turn it in. If your lab is on Monday, March 26, 2018, then your work must be turned in by 11:55 PM on Monday, April 2, 2018. If your lab is on Tuesday, March 27, 2018, then your work must be turned in by 11:55 PM on Tuesday, April 3, 2018. If your lab is on Wednesday, March 28, 2018, then your work must be turned in by 11:55 PM on Wednesday, April 4, 2018. To avoid late penalties, do not confuse these dates!

// ARRAY QUEUE. A fixed length queue represented as a circular array. class ArrayQueue { private int front; // Index of front object in OBJECTS. private int rear; // Index of rear object in OBJECTS. private Base[] objects; // The OBJECTs in the queue. // Constuctor. Make a new empty queue that can hold SIZE - 1 elements. public ArrayQueue(int size) { if (size <= 1) { throw new IllegalArgumentException("Illegal size."); } else { front = 0; rear = 0; objects = (Base []) new Object[size]; } } // DEQUEUE. Remove an object from the queue. public Base dequeue() { if (front == rear) { throw new IllegalStateException("Queue is empty."); } else { front = (front + 1) % objects.length; Base temp = objects[front]; objects[front] = null; return temp; } } // ENQUEUE. Add a new OBJECT to the queue. public void enqueue(Base object) { int nextRear = (rear + 1) % objects.length; if (front == nextRear) { throw new IllegalStateException("Queue is full."); } else { rear = nextRear; objects[rear] = object; } } // IS EMPTY. Test if the queue is empty. public boolean isEmpty() { return front == rear; } // IS FULL. Test if the queue is full. public boolean isFull() { return front == (rear + 1) % objects.length; } }

// QUETERATOR. Test ARRAY QUEUE's ITERATOR class. It's worth 20 points. Unlike // the example in the lecture, this code does NOT use the built-in ITERATOR // interface from the Java library. There are always many different ways to // do things when you write programs. class Queterator { // MAIN. Start execution here. public static void main(String [] args) { // Make an ARRAY QUEUE and enqueue some STRINGs. ArrayQueue queue = new ArrayQueue(4); queue.enqueue("A"); queue.enqueue("B"); queue.enqueue("C"); // Make a FIRST ITERATOR for QUEUE and use it to visit QUEUE's elements. ArrayQueue.Iterator first = queue.iterator(); while (first.hasNext()) { System.out.println(first.next()); // A B C one per line 5 points } // The iterator hasn't changed QUEUE. System.out.println(queue.isEmpty()); // false 1 point System.out.println(queue.dequeue()); // A 1 point System.out.println(queue.dequeue()); // B 1 point System.out.println(queue.dequeue()); // C 1 point System.out.println(queue.isEmpty()); // true 1 point // Let's enqueue more things to QUEUE. queue.enqueue("X"); queue.enqueue("Y"); queue.enqueue("Z"); // Now make a SECOND ITERATOR for QUEUE. The FIRST one does not work any more, // because QUEUE has changed. Use SECOND to visit QUEUE's new elements. ArrayQueue.Iterator second = queue.iterator(); while (second.hasNext()) { System.out.println(second.next()); // X Y Z one per line 5 points } // The new iterator hasn't changed QUEUE either. System.out.println(queue.isEmpty()); // false 1 point System.out.println(queue.dequeue()); // X 1 point System.out.println(queue.dequeue()); // Y 1 point System.out.println(queue.dequeue()); // Z 1 point System.out.println(queue.isEmpty()); // true 1 point } }