OBJECTIVE: TRIE tree (prefix tree) in c++
here are the functions
instructions for how every functions should work(read the whole thing please)
#ifndef BOGGLE_DICTIONARY_H #define BOGGLE_DICTIONARY_H #include using namespace std; const int NUM_CHARS = 26; Eclass DictionaryError{ public: explicit DictionaryError(string msg) { this->msg = msg; } string Msg() { return msgi // returns king of flavor } private: string msg;] }; class Dictionary { public: Dictionary(); ~Dictionary(); // I will not require this Dictionary(const Dictionary& otherDict); explicit Dictionary(string filename); // copy constructor // The keyword explicit is used to tell the compiler // that this is not a conversion constructor. Dictionary& operator=(const Dictionary& otherDict); void LoadDictionaryFile(string filename); void SaveDictionaryFile(string filename); void AddWord(string word); void MakeEmpty(); bool IsWord(string word); bool IsPrefix(string word); int WordCount(); private: class Node { public: // Your node structure here. // You can also use a struct if you like.| }; Node* root; int numWords; // 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, ofstream& outfile); #endif //BOGGLE_DICTIONARY_H To store the words in this assignment, you will be creating dictionary using a data structure called a prefix tree (also known as a Trie). This data structure allows for the quick lookup of whether or not a word is valid. It will also allow you to find all words with a specific prefix. Rather than store each word individually, we instead store the words using a tree: root Node (Level 0) b a z + * Node. is Word false Node (Level 1) a X * Node * is Word true Node (Level 2) a e Z NULL Node * is Word NULL false e Z Node (Level 3) a Node * NULL is Word true NULL The example above shows two how the words "a" and "axe" are represented using a tree. Each node holds 26 pointers to other nodes; each of these nodes corresponds to a specific letter. Each node also holds a single boolean flag. Essentially, each word is represented by a path down the tree. If the path ends with a "false", then the path does not represent a valid word. For example, the root node has a path from the first Node* pointer (i.e. the pointer representing 'a') to another Node . Notice that this first level 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 msg = msg; } string Msg() { return msgi // returns king of flavor } private: string msg;] }; class Dictionary { public: Dictionary(); ~Dictionary(); // I will not require this Dictionary(const Dictionary& otherDict); explicit Dictionary(string filename); // copy constructor // The keyword explicit is used to tell the compiler // that this is not a conversion constructor. Dictionary& operator=(const Dictionary& otherDict); void LoadDictionaryFile(string filename); void SaveDictionaryFile(string filename); void AddWord(string word); void MakeEmpty(); bool IsWord(string word); bool IsPrefix(string word); int WordCount(); private: class Node { public: // Your node structure here. // You can also use a struct if you like.| }; Node* root; int numWords; // 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, ofstream& outfile); #endif //BOGGLE_DICTIONARY_H To store the words in this assignment, you will be creating dictionary using a data structure called a prefix tree (also known as a Trie). This data structure allows for the quick lookup of whether or not a word is valid. It will also allow you to find all words with a specific prefix. Rather than store each word individually, we instead store the words using a tree: root Node (Level 0) b a z + * Node. is Word false Node (Level 1) a X * Node * is Word true Node (Level 2) a e Z NULL Node * is Word NULL false e Z Node (Level 3) a Node * NULL is Word true NULL The example above shows two how the words "a" and "axe" are represented using a tree. Each node holds 26 pointers to other nodes; each of these nodes corresponds to a specific letter. Each node also holds a single boolean flag. Essentially, each word is represented by a path down the tree. If the path ends with a "false", then the path does not represent a valid word. For example, the root node has a path from the first Node* pointer (i.e. the pointer representing 'a') to another Node . Notice that this first level 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
