objective: trie (prefix tree) in c++

Here is the header file

here is the .cpp file

here is the instructions

#ifndef BOGGLE_DICTIONARY_H #define BOGGLE_DICTIONARY_H 2 3 4 5 #include #include #include using namespace std; G 7 8 9 10 const int NUM_CHARS - 26; 11 12 13 14 15 1 16 17 19 class Dictionary Error public: explicit DictionaryError(string mse) { this->msg = mg; > string Msg return me; // returns king of flavor } private: string msg; }; 19 20 21 22 23 24 class Dictionary 25 26 27 28 29 30 31 public: Dictionary(); --Dictionary(); // I will not require this Dictionary(const Dictionary& otherDict); explicit Dictionary (strine filename); // copy constructor // The keyword explicit is used to tell the compiler // that this is not a conversion constructor. 32 33 34 Dictionary& operator=(const Dictionary& otherDict); void LoadDictionaryFile(string filename); void SaveDictionaryFile(string Filename); 35 36 37 38 void Addlord(string word); void MakeEmpty(); 39 41 42 43 bool Isword(string word); bool ISPrefix(string word); int WordCount(); private: 48 49 class Node public: // Your node structure here. // You can also use a struct if you like. 50 51 52 ); 53 54 Node* roots int nunilords; 55 56 57 59 59 60 // Any private methods you need/want // You may change these helpers if you want, but you don't need to. void destroyHelper (Node* thisTree); void copyHelper (Node"& thisTree, Node & otherTree); void SaveDictionaryHelper (Node> curr, string currPrefix, of stream& outfile); }; 62 63 #endif //BOGGLE_DICTIONARY_H 1 #include "Dictionary.h" 2 3 // Your code here 4 5 6 7 LOCO // The copy constructor is complete. // However, the operator= must be completed for it to work. Dictionary::Dictionary(const Dictionary &otherDict) { root = new Node; numWords = 0; *this = otherDict; } 10 11 12 13 14 15 node has a "true" flag. This indicates that "a" is a valid word. If we examine the pointer for the second level "x" position, we find that a path exists for "ax" to another node. When we examine this second level node, we find that the pointer for the 'a' position is NULL. This indicates that "aa" is not a valid word or prefix. If we examine the pointer for the 'e' position, we see that another node exists. When we look at this 3rd level node, we find that the flag for this position is true; this make sense since "axe" is a valid word. Notice that the 'a' Node pointer at the third level is NULL; this means that there is no word with a prefix of "axea". Similarly, since the node for 'z at the third level is NULL, this means there is no word with the prefix "axez". HINT: I highly suggest using the following tool to help you get a feel for how the data structure works. https://www.cs.usfca.edu/-galles/visualization/Trie.html Bigger Example: This is an example of the prefix tree with all of the words starting with the letter x from the boggle dictionary. The green nodes indicates that the path to that node is a word. For example, "xebec" is a word. (See the trie_x.pdf in the readme_images folder for a higher resolution image). root 9 n ar b D D h o a Prefix A prefix is a valid path down the tree. A prefix may or may not be a valid word. For the example below, "a" and "ax" are valid prefixes since there are words starting with these letters. However, "aaa" is not a valid prefix. This because the path ends with a NULL Basic_Dictionary.cpp The Basic_Dictionary.cpp can be used for development. It will not be used for grading. I suggest using this program first before running the Dictionary_tests. Note: This program is a CMake Application. It will not show up as a Catch Application DI Dictionary Tests Debug Edit Configurations... ary.cpp V Debug 1 Dictionary Tests * Boggle_Tests Basic_Boggle_Solver Basic_Dictionary root Node b * * a + Z Node. is Word false Node a *** Z * . Node. is Word true Node a e Z NULL Node" NULL . is Word false struct Node Your Node structure should contain an array of pointers. The node can be a struct or class. The size of the array should be NUM_CHARS (ie 26). The struct/class should also contain a boolean flag called isword to indicate if the path to this node represents a word. HINT: You may want to consider having a default constructor for your node. This will decrease the amount of code you will need later. You can create a default constructor for a struct the same way you would for a class. Dictionary() Default Constructor The default constructor should establish a root node and make each position of the branch array null. It should also set the root is Word to false. The total number of words should be 0. Hint: Having a default constructor for your node will reduce the code required for this function and other functions. Dictionary& operator=(const Dictionary& otherDict) This function should copy all of the values from otherdict to this instance of the dictionary. It will serve as a wrapper for copyHelper in a similar way we recursively copied a binary tree in class. The only difference is we have 26 children instead of two. Here is a rough algorithm: operator+(const Dictionary& otherDict): Make this of the instance empty copy over the numbwords from otherDict for each letter call copyHelper with the correct parameters return this instance copyHelper (Node*& thisTree, Node *& otherTree): This code is very similar to a binary tree. The only difference is you need to copy 26 branches instead of 2 branches. Make sure you also copy the Isword parameter over too. WARNING: DO NOT JUST SET THE ROOTS EQUAL! In other words, DO NOT do the following: root = otherDict.root; // DON'T DO THIS!!! This will cause both dictionaries to share the same root! Dictionary(string filename) This constructor should establish a root node similar to the default constructor. After that, it should open the file filename and add all the words in this file to the dictionary. HINT: There may be a function that you already wrote to help you with this. This constructor should have very few lines of code. void LoadDictionaryFile(string filename) This function should open the file filename and add all the words in this file to the dictionary. This function does NOT reset the words in the dictionary. It just adds to the words already in the tree. void SaveDictionaryFile(string filename) The SaveDictionaryFile function should use a recursive function to find every word in the tree and save it to a file. This function mainly serves as a "Wrapper" for the SaveDictionaryHelper function. The following is a rough algorithm: SaveDictionaryFile(filename): Open the file if the file fails to open: throw a DictionaryError with the message filename+"failed to open" Call SaveDictionaryHelper with the appropriate arguments HINT: What should the prefix be at the root? A path down the tree represents a word. If you have a path that ends at the root node, what word does that represent? Think about this when you set your prefix in the first call to SaveDictionaryHelper called in SaveDictionaryFile. SaveDictionaryFile(curr, currPrefix, outFile): Basecase (for you to figure out) if the current node represents a word output the word to the file for each letter: Call SaveDictionaryHelper with the appropriate arguments HINT: How should the prefix change in each call to SaveDictionaryHelper? Be sure to look at how we tracked the path in the maze example. This strategy can also work here. void AddWord(string word) This method adds a word to the tree. This is accomplished by reading the word character by character and creating a path in the tree for the word if it doesn't exist. Below is the pseudocode for this method: currNode - root; for (each character c of the word) { if (the branch for character cis NULL) { set the branch of character c = new Node. set flag of this new Node to false } currNode = the pointer index of character c } Set the flag at the currNode to true Here is some code that will help you loop through each character of a string. // How to loop through each letter of a word string str = "hello"; for (int i = 0; i #include #include using namespace std; G 7 8 9 10 const int NUM_CHARS - 26; 11 12 13 14 15 1 16 17 19 class Dictionary Error public: explicit DictionaryError(string mse) { this->msg = mg; > string Msg return me; // returns king of flavor } private: string msg; }; 19 20 21 22 23 24 class Dictionary 25 26 27 28 29 30 31 public: Dictionary(); --Dictionary(); // I will not require this Dictionary(const Dictionary& otherDict); explicit Dictionary (strine filename); // copy constructor // The keyword explicit is used to tell the compiler // that this is not a conversion constructor. 32 33 34 Dictionary& operator=(const Dictionary& otherDict); void LoadDictionaryFile(string filename); void SaveDictionaryFile(string Filename); 35 36 37 38 void Addlord(string word); void MakeEmpty(); 39 41 42 43 bool Isword(string word); bool ISPrefix(string word); int WordCount(); private: 48 49 class Node public: // Your node structure here. // You can also use a struct if you like. 50 51 52 ); 53 54 Node* roots int nunilords; 55 56 57 59 59 60 // Any private methods you need/want // You may change these helpers if you want, but you don't need to. void destroyHelper (Node* thisTree); void copyHelper (Node"& thisTree, Node & otherTree); void SaveDictionaryHelper (Node> curr, string currPrefix, of stream& outfile); }; 62 63 #endif //BOGGLE_DICTIONARY_H 1 #include "Dictionary.h" 2 3 // Your code here 4 5 6 7 LOCO // The copy constructor is complete. // However, the operator= must be completed for it to work. Dictionary::Dictionary(const Dictionary &otherDict) { root = new Node; numWords = 0; *this = otherDict; } 10 11 12 13 14 15 node has a "true" flag. This indicates that "a" is a valid word. If we examine the pointer for the second level "x" position, we find that a path exists for "ax" to another node. When we examine this second level node, we find that the pointer for the 'a' position is NULL. This indicates that "aa" is not a valid word or prefix. If we examine the pointer for the 'e' position, we see that another node exists. When we look at this 3rd level node, we find that the flag for this position is true; this make sense since "axe" is a valid word. Notice that the 'a' Node pointer at the third level is NULL; this means that there is no word with a prefix of "axea". Similarly, since the node for 'z at the third level is NULL, this means there is no word with the prefix "axez". HINT: I highly suggest using the following tool to help you get a feel for how the data structure works. https://www.cs.usfca.edu/-galles/visualization/Trie.html Bigger Example: This is an example of the prefix tree with all of the words starting with the letter x from the boggle dictionary. The green nodes indicates that the path to that node is a word. For example, "xebec" is a word. (See the trie_x.pdf in the readme_images folder for a higher resolution image). root 9 n ar b D D h o a Prefix A prefix is a valid path down the tree. A prefix may or may not be a valid word. For the example below, "a" and "ax" are valid prefixes since there are words starting with these letters. However, "aaa" is not a valid prefix. This because the path ends with a NULL Basic_Dictionary.cpp The Basic_Dictionary.cpp can be used for development. It will not be used for grading. I suggest using this program first before running the Dictionary_tests. Note: This program is a CMake Application. It will not show up as a Catch Application DI Dictionary Tests Debug Edit Configurations... ary.cpp V Debug 1 Dictionary Tests * Boggle_Tests Basic_Boggle_Solver Basic_Dictionary root Node b * * a + Z Node. is Word false Node a *** Z * . Node. is Word true Node a e Z NULL Node" NULL . is Word false struct Node Your Node structure should contain an array of pointers. The node can be a struct or class. The size of the array should be NUM_CHARS (ie 26). The struct/class should also contain a boolean flag called isword to indicate if the path to this node represents a word. HINT: You may want to consider having a default constructor for your node. This will decrease the amount of code you will need later. You can create a default constructor for a struct the same way you would for a class. Dictionary() Default Constructor The default constructor should establish a root node and make each position of the branch array null. It should also set the root is Word to false. The total number of words should be 0. Hint: Having a default constructor for your node will reduce the code required for this function and other functions. Dictionary& operator=(const Dictionary& otherDict) This function should copy all of the values from otherdict to this instance of the dictionary. It will serve as a wrapper for copyHelper in a similar way we recursively copied a binary tree in class. The only difference is we have 26 children instead of two. Here is a rough algorithm: operator+(const Dictionary& otherDict): Make this of the instance empty copy over the numbwords from otherDict for each letter call copyHelper with the correct parameters return this instance copyHelper (Node*& thisTree, Node *& otherTree): This code is very similar to a binary tree. The only difference is you need to copy 26 branches instead of 2 branches. Make sure you also copy the Isword parameter over too. WARNING: DO NOT JUST SET THE ROOTS EQUAL! In other words, DO NOT do the following: root = otherDict.root; // DON'T DO THIS!!! This will cause both dictionaries to share the same root! Dictionary(string filename) This constructor should establish a root node similar to the default constructor. After that, it should open the file filename and add all the words in this file to the dictionary. HINT: There may be a function that you already wrote to help you with this. This constructor should have very few lines of code. void LoadDictionaryFile(string filename) This function should open the file filename and add all the words in this file to the dictionary. This function does NOT reset the words in the dictionary. It just adds to the words already in the tree. void SaveDictionaryFile(string filename) The SaveDictionaryFile function should use a recursive function to find every word in the tree and save it to a file. This function mainly serves as a "Wrapper" for the SaveDictionaryHelper function. The following is a rough algorithm: SaveDictionaryFile(filename): Open the file if the file fails to open: throw a DictionaryError with the message filename+"failed to open" Call SaveDictionaryHelper with the appropriate arguments HINT: What should the prefix be at the root? A path down the tree represents a word. If you have a path that ends at the root node, what word does that represent? Think about this when you set your prefix in the first call to SaveDictionaryHelper called in SaveDictionaryFile. SaveDictionaryFile(curr, currPrefix, outFile): Basecase (for you to figure out) if the current node represents a word output the word to the file for each letter: Call SaveDictionaryHelper with the appropriate arguments HINT: How should the prefix change in each call to SaveDictionaryHelper? Be sure to look at how we tracked the path in the maze example. This strategy can also work here. void AddWord(string word) This method adds a word to the tree. This is accomplished by reading the word character by character and creating a path in the tree for the word if it doesn't exist. Below is the pseudocode for this method: currNode - root; for (each character c of the word) { if (the branch for character cis NULL) { set the branch of character c = new Node. set flag of this new Node to false } currNode = the pointer index of character c } Set the flag at the currNode to true Here is some code that will help you loop through each character of a string. // How to loop through each letter of a word string str = "hello"; for (int i = 0; i