Chapter 12 Programming Homework

This week we will be working with Linked Lists and Iterators. We will have the user add integers to the list. The user will then remove a specific integer from the list by inputting the minimum index, maximum index, and value to be removed.

OBJECTIVES:

Compare iterative (looping) and recursive algorithm solutions

OVERVIEW:

This homework we will work with recursion having a method call on itself. Because we want you to get some experience actually writing recursive methods, we'll introduce this topic by having you reverse the order of the words in an ArrayList. Normally we would have you do this using a simple loop (simple loops are preferred over recursion), simply because it is more efficient in both time and memory. However, I also want to be sure you are comfortable with recursion.

**Please note that this application will be reversing the order of the words in the list and *not* manipulating the order of the letters within the words themselves

Recursion

PART I:

Start a new Java project with the name Recursion

Create a model class named WordManager that defines:

Instance Variables (only):

An ArrayList to hold the words

A 0-parameter constructor that initializes the ArrayList

Write instance methods:public void addWord(String word) method that accepts a String to be added to the ArrayList and adds it

Make sure to check if the String is null or if it is empty and throw the appropriate exception

A toString method that returns a single line containing the original list of words with a space betwen them.

**public String reverseListLoop() - does not accept any parameters and uses an "appropriate looping" structure to go through all the words in the ArrayList to build a Stringvalue that has those words in reverse order.

Because all of the words will be on the same line inside the String, be sure to include a single blank space character between words.

Note that this method will NOT manipulate (i.e. change) the actual ArrayList being stored as an instance variable.

**Note: This is not recursion for this method. Write it using what you already know about loops.

To start learning about unit testing, download the WordManagerTest file that has a main method (we will remove this class later after we have written our Driver). This will create a WordManager object and add words to your list and call the toString() and reverseListLoop() methods to make sure they are giving the correct output.

Please make sure Part I is working before moving on to Part II.

WordManagerTest file

public class WordManagerTest { public static void main(String[] args) { WordManager myWords = new WordManager(); myWords.addWord("one"); myWords.addWord("two"); myWords.addWord("three"); myWords.addWord("four"); myWords.addWord("five"); System.out.print("Expected output ORIGINAL list: "); System.out.println("one two three four five "); System.out.print("Actual: "); System.out.println(myWords); System.out.println(); System.out.print("Expected output REVERSED FOR LOOP list: "); System.out.println("five four three two one "); System.out.print("Actual: "); System.out.println(myWords.reverseListLoop()); /* System.out.println(); System.out.print("Expected output REVERSED RECURSION list: "); System.out.println("five four three two one "); System.out.print("Actual: "); System.out.println(myWords.reverseListRecursion()); System.out.println(); System.out.print("Expected output for ORIGINAL list: "); System.out.println("one two three four five "); System.out.print("Actual: "); System.out.println(myWords); */ } }

PART II:

Write instance methods:

public String reverseListRecursion()

This is a method that accepts no parameters and calls its private, recursive, helper method.

Note: You will be sending a String and an Index as parameters to the private, recursive helper method. Think of an "easy" way to get the String of words using existing code.

To get an index, you might look at indexOf and lastIndexOf from the java String API. Or you may use something else if you wish.

private String reverseListHelper(String list, int index)

This is the recursive method it's the method that will be calling on itself over and over in order to build the String of reversed words. As you consider how to do this, think about things like how you're going to get the 'next word', where that next word will go, and what the order might be. **Please note: You are not using an ArrayList at this point, but the String containing all of the words!

Please be sure that when you write this code that you have:

A base case the case where you know exactly what value gets returned

A general case here you'll make a call back to reverseListHelper which will solve a smaller version of itself (Hint: you'll solve it based on a list with exactly 1 less word in it)

I have had success in the past when I've needed to write recursive methods like this one to simply write a method that tests for, and only does the base case. In our little example, that would be for a list of exactly 1 word. Then I make an attempt at writing code for the general case, but only test it with one more than the base case (in this example, that would be a list with 2 words inside).

Include preconditions and error checking that throws IllegalArgumentExceptions if the list is empty or null. Also, throw an StringIndexOutOfBoundsException if the index is out of range.

Please use the WordManagerTest file to test your existing and new methods before we proceed to Part III.

** You will need to remove the commenting for the last two sections of the file.

PART III:

Create a WordTUI class.

Instance variables (only):

A Scanner object for input from the console

A WordManager object

A 1-parameter constructor that accepts a WordManager object and initializes it. Initialize the Scanner, too.

Write instance methods:public void run()

This is a method that accepts no parameters and will get a user's input and will direct the flow of the applicationsuch that users will be welcomed to the application and then be continually prompted to do one of the following until they choose to quit. (Please see Ch. 11 HW for this. The only thing that changes is the method calls and more options)

1 Add words from a file

2 Display original word list on the console

3 Display loopreversed word list on the console

4 Display recursionreversed word list on the console

5 Quit

private void addWords() -

***This will be the most difficult method to write. It will prompt the user for an input file name. It will then open and read the contents of that file (one word per line) and add them to the collection.

See the words.txt for how the data will be stored in the file (one word per line) and save it to your folder

Prompt the user for a file name and store this in a String variable.

Declare a Scanner object to be used to read the input file and initialize it to null

Open a try/catch statement and inside the try:

Create a new Scanner object that creates a new File, passing the file name the user gave.

Use a while loop to test that the Scanner object has a next word to read

Use the Scanner object to read in a line of the file and then call the addWord method to add that word to your ArrayList

You will have two catch statements for exceptions. Use a println to output a message to the user.

Reading the file (FileNotFoundException):Please enter your choice: 1

Please enter file name: wrds.txt

The input file does not exist. Returning to main menu.

Reading past the end of the file (NoSuchElementException)

Read past the end of the file

Outside the catch statements, call a method to output the words read in from the file (hint: you have already written a method to do this)

PART IV:

Download and save the WordDriver file and add it your project. This will be the Driver to start the program.

Make sure you have commented ALL of your methods with @param, @return as well as method and class descriptions.

Words.txt output

WordDriver file

/**

* This is the driver for the informal test application.

*

* @author Angela Service

* @version 3/6/2014

*

*/

public class WordDriver {

/**

* Entry point for the program. It creates one TimeManager object

* instance that is passed to TimeTUI constructor and calls its

* run method.

*

* @param args not used

*/

public static void main(String[] args) {

WordManager wordList = new WordManager();

WordTUI wordCollection = new WordTUI(wordList);

wordCollection.run();

}

}

o public void greetUsergreets the user with a welcome message JGRASP exec: java edu.westga.c Welcome to the word list reverser public void displayMenu() -that displays the menu to the user 1 Add words from a file 2 Display original word list on console 3 Display loop-reversed word list on console 4Display recursive-reversed list on console 5 Quit o public void quit) Outputs a "goodbye" message to the user Thank you for using the word manager Goodbye! jGRASP: operation complete. private void displayoriginalRords (o Displays on the console the list of words read in from the file all on a single line (simple method call and println statement(s)) 1 Add words from a file 2 Display original word list on console 3 Display loop-reversed word list on console 4Display recursive-reversed list on console 5 Quit