Directed Lab Work

The ArrayBag class is a working implementation of the BagInterface.java $.$ The remove method already

exists but needs to be modifed. The other three methods you will be working on already exist but do not

function yet. Take a look at that code now if you have not done so already.

Equals

Step $1.$ Compile the classes BagExtensionsTest and ArrayBag $.$ Run the main method in

BagExtensionsTest $.$

Checkpoint: If all has gone well, the program will run and the test cases for the four methods will execute.

Don$$t worry about the results of the tests yet. The goal now is to finish the implementation of each of our

methods one at a time.

Step $2.$ In the equals method of ArrayBag $,$ implement your algorithm from the pre$-$lab exercises. Some

kind of iteration will be required in this method.

Checkpoint: Compile and run BagExtensionsTest. The tests for equals should all pass. If not, debug and retest.

Remove

Step $1.$ Look at the results from the test cases from the previous run of BagExtensionsTest. Since this is

an existing method we want to make sure that our extension does not break the correct function of the method.

All but the last two test cases should result in passes. The last two tests are intended to show the new behavior.

Step $2.$ In the remove method of ArrayBag $,$ add the modifications from the pre$-$lab exercises.

Checkpoint: Compile and run BagExtensionsTest. All of the tests in the test remove section should now pass.

If not, debug and retest.

Duplicate All

Step $3.$ In the duplicateAll method of ArrayBag $,$ implement your algorithm from the pre$-$lab

exercises. Iteration is needed.

Checkpoint: Compile and run BagExtensionsTest. All tests up through checkDuplicateAll should pass. If not,

debug and retest.

Remove Duplicates

Step $4.$ In the removeDuplicates method of ArrayBag $,$ implement your algorithm from the pre$-$lab

exercises. This method will require some form of iteration. If you use the technique recommended in the pre$-$

lab, you will use nested iteration.

Final checkpoint: Compile and run BagExtensionsTest. All tests should pass. If not, debug and retest.

Lab Manual for Data Structures and Abstractions with Java $35$

Post$-$Lab Follow$-$Ups

$1.$ Create test cases for the other methods in ArrayBag $.$

$2.$ Implement the duplicateAll method using just methods from the BagInterface along with a

second bag.

$3.$ Use the following idea to implement the body of the outer loop of the removeDuplicates method.

We can scan over each of the remaining items in the bag and $$slide over$$ all the ones that are not

duplicates of item from the outer loop. You will need two indices for this inner loop, one does the scan

and the other marks the location of the slide. If an item is not a duplicate, copy it to the slide position

and increment the slide index. If an item is a duplicate, do nothing. After this is done, we need to

replace any items from after the final slide position with null.

$4.$ Implement the removeDuplicates method using the private method removeEntry $.$

$5.$ Implement the removeDuplicates method using just methods from the BagInterface along with a

second bag.

$6.$ Implement and test a new method

boolean splitInto$($BagInterface first, BagInterface second$)\{$

$...$

$\}$

which will split and add the contents of the bag into two bags that are passed in as arguments. If there

are an odd number of items, put the extra item into the first bag. The method will return a boolean

value. If either bag overflows, return false. Otherwise, return true. Note that while you will directly

access the array of the bag that the method is applied to$,$ you can only use the methods from

BagInterface on the arguments.

$7.$ Implement and test a new method

boolean addAll$($BagInterface toAdd$)\{$

$...$

$\}$

which will add all of the items from the argument into the bag. The method will return a boolean value

indicating an overflow. If adding the items would cause the bag to overflow, do nothing and return

false. Otherwise, add the items and return true. Note that while you will directly access the array of

the bag that the method is applied to$,$ you can only use the methods from BagInterface on the

argument.

$8.$ Implement and test a new method

boolean isSet$()\{$

$...$

$\}$

which will return true if the bag is also a set $($has no duplicates$).$

$9.$ Implement and test a new method

T getMode$()\{$

$...$

$\}$

which will return the item with the greatest frequency. If there isn$$t a single item with the greatest

frequency, return null $.$