CSCI 2341 A07

Array Iterator with Remove

Summary

Create an Iterator for the ArrayBag class that implements the remove() method.

Ensure that the Iterator returned by ArrayBag's iterator method 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().
BONUS: 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 TestInterface, all changes are to be made in the file ArrayBag.java. If you make changes anywhere else your code will not work with the automated testing system.

You may have carried out some of the activities in this assignment in earlier labs.

It has occurred to me that my original program TestIterator assumed that you would be doing things the same way I had. But there are multiple correct ways of doing things. I have therefor created another program TestIterator2 which is mostly the same as TestIterator, but allows for one other way of doing things.

If you haven't already started the assignment you should just go with TestIterator2. If you've already started and you're making it work with TestIterator, then you can continue with it.

Details

Activity 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.

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"); }

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

=== Activities 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 Activity 2

Activity 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:

Or possibly like this:

=== Activities 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.

Activity 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 next call to the next() method will need to return the item (if any) that was moved into the current array position. 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] and the next call to next() needs to return the 50.

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

=== Activity 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 52. Good! There should be two items remaining: 30 42 The bag is now: [10, 50, 30, 42]

Or this:

=== Activity 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]

Activity 4

In this activity 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 testActivity4 in TestIterator and run it. You should see the following additional output:

=== Activity 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.

Activity 5

In this activity you will implement the removeAll and retainAll methods in ArrayBag using a BagIterator.

You should already have implemented these methods back in L07. But there you had no access to an Iterator, so you probably had to play around with the loop control variable.

Having access to a BagIterator allows for a cleaner implementation of these two methods: 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 testActivity5. In addition to what you saw above, you should now see:

=== Activity 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]

BONUS Activity 6

This activity is for students who found the above activities not quite challenging enuf. Successful completion of this activity can earn up to ten bonus points.

In this activity you are going to make sure that 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 next and remove 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 testActivity6 call in TestIterator and check the output. There should be a change in the output for Activities 1 & 2:

=== Activities 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 Activity 6:

=== Activity 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

It's possible you get different numbers above. For example:

=== Activity 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

SUBMIT

Check