P10 Dictionary that uses a Binary Search Tree (BST).

CS300: PROGRAMMING II
Pair Programming is NOT allowed for this assignment. 
This Assignment involves developing a Dictionary that uses a Binary Search Tree (BST). This BST will be implemented represented with linked nodes, and will support operations including: inserting new word-meaning pairs into the dictionary, looking up the meaning of a particular word, and retrieving a list of all words in the dictionary. OBJECTIVES AND GRADING CRITERIA The main goals of this assignment include: implementing common BST operations, and making use of this BST in an application. You will also get practice implementing recursive methods to perform these common BST operations. 25 points 5 zyBooks Tests: automated grading test results are visible upon submission, and allow multiple opportunities to correct the organization and functionality of your code. Your highest scoring submission prior to the deadline will be recorded. 25 points 5 Hidden Tests: automated grading tests are run after the assignment’s deadline. They check for similar functionality and organizational correctness as the zyBooks Tests. But you will NOT be able to resubmit corrections for extra points, and should therefore consider and test your own code even more thoroughly. GETTING STARTED P10 DICTIONARY LECTURE NOTES 0. Create a new Java8 project in Eclipse. You can name this project whatever you like, but Dictionary is a descriptive choice. THE DICTIONARY 1. Add a new class called Dictionary to your project. This class will make use of the DefinitionNode class described in the next step. We are introducing this class first, to help you understand the context in which the DefinitionNode’s helper methods will be used. This class must contain the private fields and publicly accessible methods shown in the following: You may add additional private methods to help organize your implementation of these functions, but may not add additional fields or public methods. However most of the functionality for these methods will come from the DefinitionNode’s recursive helper methods specified below. THE DEFINITION NODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 private DefinitionNode root; // the root definition in the BST /** * Inserts a new word along with its meaning into the dictionary. * @param word The word to be inserted * @param meaning The meaning of the word being inserted * @throws IllegalArgumentException when the word is already in this dictionary */ public void insert(String word, String meaning) throws IllegalArgumentException {     // implement using the DefinitionNode's insertHelper() method } /** * Searches for the definition of a word, and then return that word's meaning. * @param word The word that is being searched for * @return The meaning of the word, or null if the word cannot be found. */ public String lookup(String word) {     // implement using the DefinitionNode's lookupHelper() method } /** * Computes the number of words that are currently in this dictionary. * @return That number of words */ public int getWordCount() {     // implement using the DefinitionNode's getWordCountHelper() method } /** * Computes a list of all of the words that are currently in this dictionary. * @return That list of all the words */ public ArrayList getAllWords() {     // implement using the DefinitionNode's getAllWordsHelper() method } 2. Create a new class called DefinitionNode. Objects of this type will be used to represent the definitions (i.e. word and meaning pairs) in your dictionary. This class must contain the private fields and publicly accessible constructor/methods shown in the following: You may add additional private methods to help organize your implementation of these functions, but may not add additional fields or public methods. After implementing these methods, you should revisit you Dictionary class. Make use of these recursive helper methods to implement the methods within your Dictionary class. THE DRIVER APPLICATION 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 private final String word;      // the word this definition defines private final String meaning;   // the meaning of that word     private DefinitionNode leftChild;   // nodes preceding this one alphabetically private DefinitionNode rightChild;  // nodes following this one alphabetically /** * Constructs a DefinitionNode with the specified word and meaning. * @param word The word associated with this definition * @param meaning The meaning of that word * @throws IllegalArgumentException when the word or meaning are either *         references to an empty string or null references. */ public DefinitionNode(String word, String meaning) { } /** * This helper method inserts a new node into the tree or subtree that is * rooted at this node.  If it cannot directly add the new node as a child * of this node, then it must recursively call this method on its appropriate * child, to eventually complete this insertion. * @param newNode The new node that is being inserted into the tree * @throws IllegalArgumentException when the word inside newNode is already in *         the tree.  Multiple definitions for the same word are not allowed. */ public void insertHelper(DefinitionNode newNode) throws IllegalArgumentException { } /** * This helper method retrieves the meaning of a particular word from the * tree or subtree rooted at this node.  Like the insertHelper method above, * this method should also be defined recursively. * @param word The word associated with the meaning being looked up * @return The meaning of that word, or null if the word is not found */ public String lookupHelper(String word) { return null; } /** * This recursive helper method retrieves the number of words in the tree * or subtree rooted at this node. * @return The number of definitions in this tree or subtree */ public int getWordCountHelper() { return 0; } /** * This recursive helper method retrieves a list containing all of the * words in the tree or subtree rooted at this node. * @return The list of all words in this words tree or subtree */ public ArrayList getAllWordsHelper() { return null; } 3. Your last job for this assignment is to develop a driver application to make use of your Dictionary. Create a new class called Main to a new file called Main.java, and implement this driver within the main() method of that new class. This driver should continuously prompt the user to enter one command at a time, and process each of them until the user enters a ‘Q’ command to quit the program. For each of the command, you basically just need to call the corresponding method on a single Dictionary object. The commands (which should be case insensitive) are as follows: Command Corresponding Method Description I insert(word, meaning) “I” inserts a definition in the dictionary. It prints “WARNING: failed to insert duplicate word: .” for duplicate entry L lookup(word) “L” searches the definition of the word in the dictionary. It prints “No definition found for the word ” when a word doesn’t exist in the dictionary or “There are no definitions in this empty dictionary.” when the dictionary is empty. A getAllWords() “A” gets all the words in the dictionary in sorted order, and then prints those words on a single line separated by spaces. Prints “Dictionary is empty.” when the dictionary has no words. C getWordCount() “C” gets the count of words in the dictionary. Q – “Q” quits the program Some clarifications about the commands: Your program should support commands in both lowercase and uppercase. You may assume that for each command option entered, the number and format of arguments followed are always valid. E.g., an ‘I’ (insert) command option won’t be followed by less than two arguments, and all the arguments can always be interpreted as strings separated by a single space. For the ‘I’ (insert) command option, the first argument will be the word and the second argument will begin after the first argument and will continue till the end of the input line. When the user enters a command option not listed above, you should show user the warning message “WARNING: Unrecognized command.”, and then re-prompt the user to enter another command. Whenever you show the user a warning message, you should not perform the corresponding operation on the dictionary, nor should you exit the program. Instead, you should reprompt the user, and continue the program until the user enters a ‘q’. 4. Here is an interactive log that demonstrates using the complete application (the user’s input is displayed in a orange and the output is in black): ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: i eccentric unconventional and slightly strange ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: i accustom be used to ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: i boring not interesting ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary 5. Congratulations on finishing this CS300 assignment! After verifying that your work is correct, and written clearly in a style that is consistent with the course style guide, you should submit your Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: L boring boring - not interesting ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: i flight the action or process of flying through the air ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: a accustom, boring, eccentric, flight ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: c 4 ==================Dictionary ================= Enter 'I' to Insert a definition in the dictionary Enter 'L' to Lookup a definition in the dictionary Enter 'A' to print All the words in the dictionary Enter 'C' to print the Count of all words in the dictionary Enter 'Q' to quit the program =========================================== Please enter your command: q work through zybooks. The most recent of your highest scoring submissions prior to the deadline of 17:00 on Thursday, November 30th will be used as part of your score for this assignment. Additional grading tests will then be run against your highest scoring submission to determine the rest of your assignment grade.