JAVA: Removing all occurences from an ArrayList and LLList, Implementing the Bag ADT using a linked list, Palindrome Tester. Ps5.zip

CODE GIVEN: Ps5.zip http://www.cs.bu.edu/courses/cs112/files/ps5/ps5.zip

Begin by downloading the following zip file: ps5.zip

Unzip this archive, and you should find a folder named ps5, and within it the files you will need for Part II. Make sure that you keep all of the files in the same folder.

Important: When you compile the code in this folder, you may see one or more warnings labeled unchecked cast. You can safely ignore them.

Problem 4: Removing all occurrences from a list

20 points; individual-only

If you havent already done so, complete the steps above to prepare for this and the remaining problems in Part II.

Assume that we want list objects to support the following method:

 boolean removeAll(Object item) 

This method takes an item, and it should removes all occurrences of that item from the list. If one or more occurrences of the item are removed, the method should return true. If there were no occurrences of the item to begin with, it should return false.

Create two implementations of this method: one as part of the ArrayList class, and one as part of the LLList class. Both classes can be found in the ps5 folder.

Important: For full credit, both methods should:

run in O(n) time, where n is the number of items in the list

use no more than a constant (O(1)) amount of additional memory.

In addition, you should make sure that your ArrayList version of the method doesnt leave any extraneous references to objects in the items array. For example, lets say that you have 9 items in the ArrayList. If a call to removeAll() removes 3 of them, you should end up with an array in which the first 6 elements hold references to actual items, and all of the remaining elements are null.

To facilitate testing, we have added a constructor to both classes that takes an array of type Objectcontaining the initial contents of the list. Given these constructors, you can test your methods using examples that look like this:

> String[] letters = {"a", "b", "c", "a", "c", "d", "e", "a"}; > ArrayList list1 = new ArrayList(letters); > list1 {a, b, c, a, c, d, e, a} > list1.removeAll("a") true > list1 {b, c, c, d, e} > list1.removeAll("c") true > list1 {b, d, e} > list1.removeAll("x") false > list1 {b, d, e} > LLList list2 = new LLList(letters); > list2 {a, b, c, a, c, d, e, a} > list2.removeAll("a") true > list2 {b, c, c, d, e} > list2.removeAll("x") false 

Problem 5: Implementing the Bag ADT using a linked list

25 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Earlier in the course, we worked with the ArrayBag class. This class can be seen as an implementation of the Bag abstract data type, which we can specify in Java using the following interface:

public interface Bag { boolean add(Object item); boolean remove(Object item); boolean contains(Object item); int numItems(); Object grab(); Object[] toArray(); } 

In the ps5 folder, we have included:

the Bag interface (Bag.java)

a version of the ArrayBag class that includes an implements clause in its header to specify that it implements this interface.

In a file named LLBag.java, write a class called LLBag that implements the Bag interface using a linked list instead of an array. You may use a linked list with or without a dummy head node.

In designing your implementation, you may find it helpful to compare the LLList class, our linked-list implementation of the List ADT, to the ArrayList class, our array-based implementation of that same ADT. In the same way that LLList uses a linked list instead of an array to implement a list, your LLBagclass should use a linked list instead of an array to implement a bag.

Notes:

Make sure that your class explicitly indicates that it implements the Bag interface. To allow your new class to compile, you will need to put it in the ps5 folder with Bag.java.

Like the LLList class, your LLBag class should use a private inner class called Node for the nodes in the linked list.

In addition to the methods in the Bag interface, your LLBag class should also have a toString()method that overrides the default toString() method inherited from the Object class. Consult theArrayBag toString() method to see what the string returned by this method should look like.

One of the benefits of using a linked list is that there is no need to specify a maximum sizethe bag can effectively grow without limit. Therefore, you will not need to provide a constructor that specifies a maximum size, and your add() method can always return true.

Because the order of the items in a bag doesnt matter, you can add items to either end of the linked list; however, make sure that your method adds items in O(1) time.

In general, you should make your methods as efficient as possible. For example, when implementing the remove() method, you should make sure that you dont traverse the list more than once.

Copy over the main() method from the ArrayBag class, and make whatever modifications are necessary to allow it to test your LLBag class.

Important: If you compare the results that you obtain from testing the two classes, you may see that the items are not in the same order in both sets of tests. That is to be expected, and its not a problem because items in a bag do not have a position!

Problem 3: Palindrome tester

20 points; individual-only

(15 points) A palindrome is a string like "radar", "racecar", and "abba" that reads the same in either direction. To enable longer palindromes, we can ignore spaces, punctuation, and the cases of the letters. For example:

"A man, a plan, a canal, Panama!" 

is a palindrome, because if we ignore spaces and punctuation and convert everything to lowercase we get

"amanaplanacanalpanama" 

which is a palindrome.

In the file Palindrome.java that weve included in the ps5 folder, add a static method called isPal() that takes a String object as a parameter and determines if it is a palindrome, returning true if it is and false if it is not.

A string of length 1 and an empty string should both be considered palindromes. Throw an exception for null values.

Although this problem could be solved using recursion or an appropriately constructed loop that manipulates the String object directly, your method must use an instance of one or more of the following collection classes from the ps5 folder:

ArrayStack

LLStack

ArrayQueue

LLQueue

You must not use any other data structure, including arrays or linked lists other than the ones that are inside instances of the above collections. Rather, you should put individual characters from the original string into an instance of one or more of the above collections, and use those collection object(s) to determine if the string is a palindrome.

For full credit, you should:

Write your method so that spaces, punctuation, and the cases of the letters dont prevent a string from being a palindrome. To put it another way, make sure that your method only considers characters in the string that are letters of the alphabet and that it ignores the cases of the letters. See our example above.

Make your method as efficient as possible. In particular:

You should perform only one iteration over the original String object. After that one iteration, any additional manipulations of the characters should be done using the collection object(s) that you have chosen to use.

Because we want to avoid unnecessary scanning, you may not use any of the built-inString methods except charAt() and length().

Hints:

When constructing the collection object(s) that you decide to use, you will need to specify the appropriate data type for the items in the collection. Because char values are primitives, you should use the corresponding wrapper class, which is called Character.

You may also find it helpful to use the Character.toLowerCase() or Character.toUpperCase() method.

Remember that char values are essentially integers, so you can compare them just as you would compare integers.

(5 points) For professional programmers, writing well-formatted units tests is an extremely important part of their work. In the main() method of Palindrome.java, weve given you an example of what such a unit test should look like.

Add five additional unit tests for your isPal() method to the main() method. Your unit tests must follow the same format as our example test. In particular, the output of each of your unit tests should include:

a header that specifies the test number and a description of what is being tested

the actual return value that you get from that test

the expected return value

whether the actual return value matches the expected return value.

Put each test in the context of a try-catch block so that you can handle any exceptions that are thrown. Leave a blank line between tests.

Important: Please note that for this problem, we will be looking at your code in the main() method.