Array Iterator

Summary

Create an Iterator for the ArrayBag class. The iterator must be in a private and non-static class named BagIterator. It must implement all Iterator methods, including the remove() method.

Ensure that the Iterator returned by ArrayBag's iterator method is an object of type BagIterator. Make sure it throws all the proper exceptions:

• NoSuchElementException if next() is called when there is no next element.
• IllegalStateException if remove() is called twice in a row.
• IllegalStateException if remove() is called before next().
• ConcurrentModificationException if the Bag has had any elements added or removed (unless they've been removed by this Iterator).

Other than activating method calls in TestIterator, all changes are to be made in ArrayBag. If you make changes anywhere else your code will not work with the automated testing system.

Details

It'd be best if you were to complete this assignment in parts.

Part 1

Download the class ArrayBag along with the interface Bag and the testing program TestIterator.

Revise ArrayBag by implementing the iterator method.

The implementation requires you to make a private class named BagIterator that implements Iterator<T> inside the ArrayBag class.

Do not make the private class static. By making it an "instance class" it can refer to elements of the ArrayBag that created it. In particular, it can talk about numInBag and contents without needing to specify which ArrayBag they're part of. They automatically refer to the fields of the correct ArrayBag.

Also, because it is an instance class, it has access to the type parameter T, so you don't need to re-introduce that parameter.

A BagIterator is an object that lets a client iterate thru the elements of this Bag. The BagIterator class has the following methods:

• next(), which returns the next item from this Bag that hasn't already been returned by next().
• hasNext(), which checks whether there are any items in the Bag that haven't already been returned by the next() method.
• remove(), which removes the last item returned by next().

A BagIterator is used like any other Iterator:

Iterator it = wordBag.iterator(); while (it.hasNext()) { String word = it.next(); System.out.println("There is a \"" + word + "\" in the bag"); }

Do the basic implementation of the hasNext() and next() methods. Don't worry yet about throwing exceptions.

Run the program TestIterator program to ensure that your iterator loop works. If you've done everything correctly, you should see something like this:

=== Parts 1 & 2 === Here is the bag: [This, is, the, bag] There is a "This" in the bag There is a "is" in the bag There is a "the" in the bag There is a "bag" in the bag There is nothing more in the bag OK, now there is a "extended" in the bag This is no null in the bag, so this line should NOT get printed! You may be ready for Part 2

It is possible that the items in the Bag will be reported in a different order. For example:

=== Parts 1 & 2 === Here is the bag: [This, is, the, bag] There is a "bag" in the bag There is a "the" in the bag There is a "is" in the bag There is a "This" in the bag There is nothing more in the bag Didn't notice the extra thing in the bag This is no null in the bag, so this line should NOT get printed! You may be ready for Part 2

It doesn't matter what order the words appear. All that's important is that all and only the words in the Bag appear, with no extra duplicates.

Those of you who understand about ADTs may be saying "Hey! The two iterators have different behaviour. Shouldn't the behaviour be the same for both?"

That is a very good point.

Nevertheless, it's fine right now because later we're going to make it so that neither of those messages get printed.

Part 2

Revise the next method so that it throws a NoSuchElementException if all of there are no more items to return.

Once you have completed the implementation, your output should look like this:

=== Parts 1 & 2 === Here is the bag: [This, is, the, bag] There is a "This" in the bag There is a "is" in the bag There is a "the" in the bag There is a "bag" in the bag There is nothing more in the bag OK, now there is a "extended" in the bag Good! You noticed the end.

Or possibly like this:

=== Parts 1 & 2 === Here is the bag: [This, is, the, bag] There is a "bag" in the bag There is a "the" in the bag There is a "is" in the bag There is a "This" in the bag There is nothing more in the bag Didn't notice the extra thing in the bag. Good! You noticed the end.

Part 3

Add the remove method to the BagIterator. This method uses ArrayBag's removeItemAt method to remove the element returned by the previous call to next().

Note that the removeItemAt method rearranges the elements of the array. It's important that items not removed by the iterator still get seen by the iterator. For example, if the ArrayBag's contents array is [10, 20, 30, 42, 50, null] and the previous call to next returned the 20, then remove() will update the contents array to [10, 50, 30, 42, null, null]. If the 50 hasn't already been seen, then the next call to next() needs to return the 50.

Of course, if the 50 has already been seen, then next() should not return it. It's also important that items not get seen mutiple times.

Activate the testPart3 method call in TestIterator and run the program again to ensure that you get this behaviour. In addition to the output shown for parts 1 and 2, you should now see:

=== Part 3 === The bag is: [10, 20, 30, 42, 50] The first call to next returns 10 The second call to next returns 20 I will try to remove that. Good. That seems to have worked. The next item should be 50. Good! There should be two items remaining: 30 42 The bag is now: [10, 50, 30, 42]

Or this:

=== Part 3 === The bag is: [10, 20, 30, 42, 50] The first call to next returns 50 The second call to next returns 42 I will try to remove that. Good. That seems to have worked. The next item should be 30. Good! There should be two items remaining: 20 10 The bag is now: [10, 20, 30, 50]

Part 4

In this part you will make sure that remove throws an IllegalStateException whenever it's called at a bad time. It's only OK to call remove when next has been called since the previous (if any) call to remove.

Add a boolean property to your BagIterator to track whether it's OK to call remove:

• When the Iterator is first created, it's not OK to call remove.
• When next gets called successfully (that is, without throwing an exception), it becomes OK again to call remove.
• When remove get called successfully (again, without throwing an exception), it becomes not OK to call it again.

Activate the call to testPart4 in TestIterator and run it. You should see the following additional output:

=== Part 4 === The bag is [10.1, 20.2, 30.3] Testing remove before next Good! correct exception thrown Testing remove after remove Good! correct exception thrown There should be two items remaining: 30.3 20.2 The bag should now be empty: []

It is possible the two numbers remaining are 20.2 and 10.1 instead of 30.3 and 20.2.

Part 5

In this part you will implement the removeAll and retainAll methods in ArrayBag using a BagIterator. Having access to a BagIterator allows you to simply iterate thru your bag and use the iterator's remove method to delete items as appropriate.

When you're done, activate the call to testPart5. In addition to what you saw above, you should now see:

=== Part 5 === Here is the bag: [to, boldly, go, where, no, one, has, gone, before] Removing words 'go' 'no' 'so' 'to' and 'zo' Bag is now: [before, boldly, gone, where, has, one] Retaining words 'before' 'boldly' 'go' 'sleep' Bag is now: [before, boldly]

It's fine if the Bag's elements are in a different order. For example:

Bag is now: [has, boldly, gone, where, before, one]

Part 6

In this part you are going to make sure that hasNext, next and remove throw ConcurrentModificationExceptions when they notice a change to the ArrayBag that this Iterator didn't make.

The way to do this is to keep track of how many additions and removals get made to the ArrayBag.

First, add an instance variable to ArrayBag for the number of updates made. It should start at zero, and get bumped up by one every time an addition or removal is made.

Find the places in ArrayBag where numItems gets changed. Those are the places where the number of updates needs to be incremented.

Second, the BagIterator needs to make a note of how many updates the ArrayBag had when it (the BagIterator) was created. Create an instance variable for that. This is how many updates the iterator expects to see.

Every time the BagIterator's remove method actually removes an element from the ArrayBag, it needs to increment its expected number of updates. (The ArrayBag will notice the call to removeItemAt and increment its count of updates. If BagIterator doesn't also increment, the expected and actual numbers will come apart even tho' the update was made by this iterator.)

Lastly, before the public iterator methods do anything else, they need to check whether the actual number of updates (as recorded in the ArrayBag) and the expected number of updates (as recorded in the BagIterator) are equal. If they are not equal, then the method needs to throw a ConcurrentModificationException.

Since both methods need to do the same check and respond in the same way, it's best to create a private method to do the check and throw the exception as appropriate.

Activate the testPart6 call in TestIterator and check the output. There should be a change in the output for Parts 1 & 2:

=== Parts 1 & 2 === Here is the bag: [This, is, the, bag] There is a "This" in the bag There is a "is" in the bag There is a "the" in the bag There is a "bag" in the bag There is nothing more in the bag Good! You noticed that change! Good! You noticed that change!

as well as the new output for Part 6:

=== Part 6 === Here is the bag: [1, 2, 3, 4, 5] Removing an item using it1 That seems to have worked Advancing using it1 That seemed to work -- got 5 Advancing using it2 Good! Noticed the external change Removing using it2 Good! Noticed the external change Advancing (again) using it1 That seemed to work -- got 2

Again, it's possible the words come out in a different order, and that you get different numbers in part 6. For example:

=== Parts 1 & 2 === Here is the bag: [This, is, the, bag] There is a "bag" in the bag There is a "the" in the bag There is a "is" in the bag There is a "This" in the bag There is nothing more in the bag Good! You noticed that change! Good! You noticed that change!

...and...

=== Part 6 === Here is the bag: [1, 2, 3, 4, 5] Removing an item using it1 That seems to have worked Advancing using it1 That seemed to work -- got 4 Advancing using it2 Good! Noticed the external change Removing using it2 Good! Noticed the external change Advancing (again) using it1 That seemed to work -- got 3

For those of you who noticed the difference outputs in parts 1 and 2, you should now notice that the two versions have replaced their distinct messages (OK, now there is a "extended" in the bag and Didn't notice the extra thing in the bag) with the common message Good! You noticed that change!

The testing program was adding a word to the bag and then asking the iterator if it could see it. One version could, the other could not. But the correct response for the iterator is to cry out "Hey! Someone's been messing with my Collection!"