A08

Due Date: Thursday, March 19
File(s) to be submitted: LinkedBag.java
Sample Output: SampleOutput.html
Starter Files:

• Bag.java
• LinkedBag.java
• TestIterator.java

Linked Iterator with Remove

Summary

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

Ensure that the Iterator returned by LinkedBag'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().
• 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 LinkedBag.java. If you make changes anywhere else your code will not work with the automated testing system.

This assignment is essentially the same as A07, except

• It's with LinkedBag instead of ArrayBag.
• The ConcurrentModificationException code is required.

Details

Activity 1

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

Revise LinkedBag by implementing the iterator method. Use a private class for the iterator.

Also implement the next and hasNext methods in your private iterator class. Write 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:

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

It's fine if the words come out in a different order.

Activity 2

Add the remove method to your iterator.

Activate the testActivity2 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 2 === The bag is: [50, 42, 30, 20, 10] 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 bag is now: [50, 30, 20, 10] The next item should be 30. Good! There should be two items remaining: 20 10 The bag is now: [50, 30, 20, 10]

It's fine if the numbers are returned in a different order. What's important is that the number removed is the number returned by the second call to next.

Activity 3

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.

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

=== Activity 3 === The bag is [30.3, 20.2, 10.1] Testing remove before next Good! correct exception thrown The bag should be unchanged: [30.3, 20.2, 10.1] Testing remove after remove The bag should be missing its 30.3: [20.2, 10.1] Good! correct exception thrown The bag is now: [20.2, 10.1] There should be two items remaining: 20.2 10.1 The Bag should now be empty: []

It is OK if the deleted number is different, so long as it's the same set of numbers (the "missing" number plus those remaining in the bag), and the bag ends up empty.

Activity 4

In this activity you will implement the removeAll and retainAll methods in LinkedBag using your private class.

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

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

In this activity the actual words matter, but the order of those words doesn't.

Activity 5

In this activity you are going to make sure that next and remove throw ConcurrentModificationExceptions when they notice a change to the LinkedBag 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 LinkedBag.

First, add an instance variable to LinkedBag 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 LinkedBag where numInBag gets changed. Those are the places where the number of updates needs to be incremented.

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

Every time the private class's remove method actually removes an element from the LinkedBag, it needs to increment its expected number of updates. (The LinkedBag will notice that it removed an item and increment its expected count of updates. If the private class 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 LinkedBag) and the expected number of updates (as recorded in the private class) 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 testActivity5 call in TestIterator and check the output. In addition to what you saw before, you should see new output for Activity 5:

=== Activity 5 === Here is the bag: [5, 4, 3, 2, 1] Removing an item using it1 That seems to have worked The bag is now: [4, 3, 2, 1] 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 The bag is now: [4, 3, 2, 1] Advancing (again) using it1 That seemed to work -- got 3

Once again, the particular order doesn't matter, but the pattern of results does.