TCSS143 Fundamentals of Object-Oriented Programming-Theory and Application Programming Assignment 8 The purpose of this programming project is to demonstrate the functionality of Recursion while reviewing such things as the use of Sets (here only a single Set will be implemented), Map, String manipulation, file I/O using the Scanner class for the input file and PrintStream for the output file. REQUIREMENTS Though there will be several instances where iteration would solve the problem, Absolutely NO loops should be found in any of your code! It is a requirement of this assignment that all repeated processes will be performed through recursion. You will submit a single file Programming8.java (NO Zipped File) through the Programming Assignment 8 Submission link on Canvas. This file will be your solution to this assignment. Too, you can use the file I posted on Canvas or create your own test input file in8.txt BUT, you will NOT include this in8.txt in the upload to Canvas. I will use my own for testing. Not only will you be graded on program correctness (Program executes correctly, proper use of methods, classes, inheritance, etc.) but also, good programming documentation techniques as we have learned during this course. 1. Programming8.java All methods used to solve this problem will be contained in a single file that includes main. Of course, these methods will be declared as static. At very least, you are to write 4 separate recursive methods to solve this problem. Their intent is as follows: getWordsString: Recursively read all the words contained in the input file and return a String containing only the words found in the file that contain a given char (The words within this String will be separated by a space). Multiple return statements will be allowed here. hasCharacter: Recursively scan the characters within a received word to see if it contains a given char and return true if it does, false otherwise. getWordSet: Recursively scan the words in a received String where each word is separated by a space and placing each word into a Set (TreeSet) which is returned to the calling program once all the words have been scanned. Multiple return statements will be allowed here. getWordLengthMap: Recursively scan the set created by getWordSet and generate a Map> that Maps the length of a word to a Set of words of that length, i.e. a length of a given word will use this length as a key and add the given word to a Set to which the key maps. This solution implies the use of a non-recursive overloaded helper method of the same name called by main, that simply receives the Set created by getWordSet and in it, instantiates a Map of Integer to a Set of String which should then call the recursive version of getWordLengthMap passing it the Map it creates and an Iterator on the Set which it receives. Other details of each of these methods follows the discussion on main below. main: This program is to read all the words contained in the input file, one at a time recursively until no words remain. To do this main will call a recursive method named getWordsString (discussed shortly) which is passed a Scanner to a File object and a single character. getWordsString will read all the words in the file and return a String containing all words from the input file that contain a single given character, perhaps the character a. getWordString will use the recursive method hasCharacter to determine if the current word needs to be added to the String. Keep in mind, this string must have a single space inserted between each word. In order to remove redundant words, the String returned from getWordsString will be sent to another recursive method getWordSet which will pick out each word in the String and add them to a TreeSet (this will remove all duplicates and, as a TreeSet, will align the words in sorted order). The TreeSet will be returned to main for final output. Details on getWordSet are listed below. Before outputting the results, main will pass the TreeSet of words to the non-recursive helper method getWordLengthMap which in turn, returns a call to the recursive version of this method of the same name to produce a Map (instantiated as a TreeMap) of word lengths to a set of words of that same length. main will output to out8.txt: The size of the TreeSet The letter that was to be found in included words The TreeSet A blank line The size of the TreeMap The TreeMap The output should be sent to out8.txt and include the size of the Set, the character used to choose words (store this in a char variable), the Set, line of space, the size of the Map, and finally, the Map (see sample output on page 4). This program MUST read a file named in8.txt and generate an output file named out8.txt. The in8.txt file must be created by you based on formatting described shortly. in8.txt and out8.txt are NOT to be included during the submission process. public static String getWordsString(final Scanner theFile, final char theC) The method getWordsString is passed the open input file through a Scanner and a single char (your choice) and returns a String of words (each separated by a space) found in the file that contain the char argument. This method will recursively read each word contained in the input file. As each word is read, you will check to determine if it contains the given character through a call to the method hasCharacter discussed below This means you can only use length, indexOf, substring, and charAt. You are not allowed to use any other existing String methods or other pre-written methods to determine if the char is in the String. You have to write this process. If the current word contains the given char, then this word should be concatenated onto a String along with a space to separate each word. This will be tied in with the return statement that includes the recursive call. When all words in the file have been processed, getWordsString will return this String of words that contain the given character. Multiple return statements will be allowed here. public static Boolean hasCharacter(final String theS, final char theC) The hasCharacter method will recursively check the first character of the continuously smaller substring for the given character until the length of the substring reduces to 0, at which point no match was found and the method should return false. However, if the length is > 0 and a match is found, hasCharacter should return true. This means there are 2 base cases here. For all other cases, the length is > 0 AND the character is not found, you should return the result of the recursive call. You can use the charAt method here. Also, though the character being used for testing is lower case, dont forget to check for the uppercase equivalent. toUpperCase or any other pre-written methods are NOT allowed. You have to make this conversion yourself (ASCII a is 32 greater than A, b is 32 greater than B, and so on). However, do not change the case of any character in the original word. Continued public static Set getWordSet(final String theS) This method will be called by main following the call to getWordsString. It receives the String created by getWordsString and returns a Set (using a TreeSet) of the words contained in the String theS. The process should be done recursively with each call passing a substring of removing one word (each removed word is added to the set). You are allowed to use the String methods: indexOf, and substring And the Set methods: add and addAll Any other method calls appearing in this method must be methods written by you. Multiple return statements will be allowed here. public static Map> getWordLengthMap(Set theSet) Non-recursive helper method called by main that instantiates a TreeMap of Integer to a TreeSet of String and then returns the result of calling the overloaded recursive method of the same name (see below) passing it this new empty TreeMap and an Iterator on the received Set (theSet). public static Map> getWordLengthMap( Map> theWordLengths, Iterator theWordSetItr) { (Note: due to the excessive length of declaring Maps in the method header and a concern for loosing 3 points for lines exceeding 72 characters, the parameter list begins on the second line). Adds to the received Map by recursively scanning the Set created by getWordSet using the received Iterator. The Map uses a Set of keys that are the lengths of the words that are accessed by the Iterator. These keys, in turn, will Map to a TreeSet of words of the same length, i.e. a length of a given word will use this length as a key and add the given word to a Set to which the key maps (all words in a given set have the same length). in8.txt The input file in8.txt will contain a series of words. This can be a poem, a set of instructions, an email message, etc., as long as its a text file. See the sample run at the end of this assignment for the in8.txt file I provided. out8.txt All output (the above mentioned) should be sent to the output file out8.txt. See sample run for example. As a suggestion, complete this project in steps: Write main to open, read, and write your I/O files (just echo input to output). Write and call from main, the getWordsString method and output the resulting String. At this stage, have getWordsString call a simple version of hasCharacter that checks for the given character any way you see fit and returns the expected true of false result. Run this for testing and any corrections that need to be made. Re-write the code inside hasCharacter to follow the specifications above in the description. Remember, no loops or outside helper methods. You can only use length, charAt, and substring. Run this for testing and any corrections that need to be made. Write the getWordSet method, test and correct as needed. Write the recursive getWordLengthMap (and the helper non-recursive method that main calls), test and correct as needed. Also, just prior to your final output of the Set to the file, you might want to execute a single remove of an empty string (2 double quotes with nothing in between) operation on the Set (an empty String will lose points). Remember, absolutely no loops! If you feel the need, please implement any other methods you feel would be useful. Sample I/O may appear as follows: Suppose in8.txt contains (first track of Pink Floyds debut album (circa 1967) and also UmmaGumma (circa 1969)): Astronomy Domine (Barrett) 8:31 Lime and limpid green, a second scene A fight between the blue you once knew. Floating down, the sound resounds Around the icy waters underground. Jupiter and Saturn, Oberon, Miranda and Titania. Neptune, Titan, Stars can frighten. Blinding signs flap, Flicker, flicker, flicker blam. Pow, pow. Stairway scare Dan dare who's there? Lime and limpid green, the sounds surronds The icy waters under Lime and limpid green, the sounds surronds The icy waters underground. Then the output of words containing an a should be: Set size = 20 Set of words containing the letter a: [(Barrett), A, Around, Astronomy, Dan, Floating, Miranda, Saturn,, Stairway, Stars, Titan,, Titania., a, and, blam., can, dare, flap,, scare, waters] Map size = 8 Map of word lengths containing the letter a: {1=[A, a], 3=[Dan, and, can], 4=[dare], 5=[Stars, blam., flap,, scare], 6=[Around, Titan,, waters], 7=[Miranda, Saturn,], 8=[Floating, Stairway, Titania.], 9=[(Barrett), Astronomy]} In this example you might note the occasional extra commas, periods, and parenthesis (,.()). This is because the input included these extra characters and are considered part of the word by the next( ) method since there was no space separating these characters from the word. This type of word in your output will be fine. No need to zip anything (and please do not). Just submit your single Programming8.java file. 10 extra credit points can be earned if you clean the words (strip the non-alphabetic characters from the ends of each word as they are initially read from the input). Of course, as the rule of this assignment, no loops will be allowed and this method will have to execute completely recursively. If you choose to earn the extra credit and based on the same input as above, your output should appear as follows: Set size = 20 Set of words containing the letter a: [A, Around, Astronomy, Barrett, Dan, Floating, Miranda, Saturn, Stairway, Stars, Titan, Titania, a, and, blam, can, dare, flap, scare, waters] Map size = 8 Map of word lengths containing the letter a: {1=[A, a], 3=[Dan, and, can], 4=[blam, dare, flap], 5=[Stars, Titan, scare], 6=[Around, Saturn, waters], 7=[Barrett, Miranda, Titania], 8=[Floating, Stairway], 9=[Astronomy]} The next and final page includes an outlined overview of this assignment ---> Addendum to the initial Programming Assignment 8 document This document is to be In Addition To the original Programming Assignment 8 and is intended to describe each method in a clearer, outline approach. All requirements in Programming Assignment 8 remain intact and take precedence over all else (should not be ignored). Also, you should refer to the initial document for specifics (dont forget, No Loops Allowed and you are only allowed to use the String methods: indexOf, substring, length, and charAt. No other methods but your own can be used or applied to the String(s)): main (String[] theArgs): Opens files for input and output: in8.txt and out8.txt respectively. Calls getWordsString and passes the input file scanner & the single character a or any other lowercase character: getWordsString returns a String made of all words (separated by space)in the input file that contain the letter. Passes the String returned from getWordsString to getWordSet which returns a TreeSet containing all the words in the String. Removes the empty String from the TreeSet (if it exists) Passes the TreeSet to getWordLengthMap (which in turn, passes a new TreeMap and an Iterator to the TreeSet to a recursive overloaded method of the same name) to create a Map of word lengths to Sets of words of that length. Outputs the TreeSet and the TreeMap to the output file: out8.txt. public static String getWordsString(final Scanner theFile, final char theC) Recursively reads all words in theFile while concatenating into a String, only words that contain the letter in theC. Calls hasCharacter (passing the current word and char theC) to determine if the word should be concatenated into the String (if so, the word, a space, and the return String from a recursive call to getWordsString is returned. Otherwise, only the return value of a recursive call to getWordsString is returned. (Base Case) An empty String is returned when no words remain in theFile. Needs a local String variable for each word read. public static boolean hasCharacter(final String theS, final char theC) Recursively (reduces the String theS by 1) scans the given String checking in each call for a match with char theC. (Each of these recursive calls are returned to the previous call. This is the general or recursive case) (Base Case)Returns true if char theC is found (need to check both lower and upper case in the String) (Base Case)Returns false if the String length is < 1. (Upper case chars are the int value of 32 less than their lower case equivalent) public static Set getWordSet(final String theS) Receives the String of words each of which is terminated with a space (last word will likely be followed by a space). (General or Recursive Case) Adds a word from the String to a local Set and Recursively calls itself with a reduction of the String by 1 word. This call will return a set whos All elements are to be Added to the local Set. The local set is then returned. (Base Case) Only 1 word in the String which is added to the local set and the local Set is returned. public static Map> getWordLengthMap(Set theSet) Non-recursive method called by the client (main) Instantiates a TreeMap of Integer to Set of Strings returns the result of calling the recursive version of the same name (see below) by passing the TreeMap and an Iterator on theSet. public static Map> getWordLengthMap( Map> theWordLengths, Iterator theWordSetItr) { Recursive helper method called by the non-recursive version of getWordLengthMap (see above) (General or Recursive Case) Gets the next word from theWordSetItr and adds it to theWordLengths Map value Set of String base on its length as the key. If there is no key of this words length, then a new TreeSet of String needs to be instantiated and the word is added to this Set. This new Set, in turn, is added to the Map as the value with the length of the word as a key. Finally, a recursive call to getWordLengthMap is returned (this call passes the theWordLengths Map and the Iterator theWordSetItr). (Base Case) return theWordLengths Map when there are no more words to iterate over.