In hwAC1, you implemented an Autocompleter using a BST-based data structure. Here, youll improve your implementation, replacing the file-based dictionary construction with one-at-a-time insertion. This allows creating dictionaries in any order, and on-the-fly word additions (like when a user adds their name or address to the dictionary).

Create a new C++ source file named autocompleter.cpp that implements the class declared in autocompleter.h, so that autocompleter.cpp and the provided files compile into a program that runs with no failed tests. Submit the source file "autocompleter.cpp".

(autocompleter.h):

 #ifndef AUTOCOMPLETER_H #define AUTOCOMPLETER_H #include  #include  #include  #include  using namespace std; class Autocompleter { // For the mandatory running times below: // n is the number of strings in the dictionary. // Assume that the length of every string is O(1). public: // Creates a new Autocompleter with an empty dictionary. // // Must run in O(1) time. Autocompleter(); // Adds a string x to the dictionary. // If x is already in the dictionary, does nothing. // // Must run in O(log(n)) time. void insert(string x, int freq); // Returns the number of strings in the dictionary // of possible completions. // // Must run in O(n) time. int size(); // Fills the vector T with the three most-frequent completions of x. // If x has less than three completions, then // T is filled with all completions of x. // The completions appear in T from most to least frequent. // // Must run in O(log(n) + k) time, // where k is the number of completions of x in the dictionary. void completions(string x, vector &T); private: // A helper class that stores a string and a frequency. class Entry { public: string s; int freq; }; // A helper class that implements a binary search tree node. class Node { public: Node() { height = -1; left = right = nullptr; } Node(Entry e) { this->e = e; height = -1; left = right = nullptr; } Entry e; int height; Node* left; Node* right; }; static int height(Node* root) { if (root == nullptr) return -1; return root->height; } // Root of the binary-search-tree-based data structure Node* root; // Optional helper methods (you'll probably want them) void completions_recurse(string x, Node* root, vector &T); int size_recurse(Node* root); void insert_recurse(Entry e, Node* root); void rebalance(Node* root); // Call to rebalance a subtree void right_rotate(Node* root); // Use in rebalance() void left_rotate(Node* root); // Use in rebalance() }; #endif 

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

(main.cpp)

 #include  #include  #include  #include  #include "autocompleter.h" using namespace std; inline void _test(const char* expression, const char* file, int line) { cerr << "test(" << expression << ") failed in file " << file; cerr << ", line " << line << "." << endl; abort(); } #define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__)) void interactive_mode() { Autocompleter words; ifstream f; f.open("words2.txt"); assert(f.is_open()); // If this fails, you're missing words2.txt string line; int i = 0; while (getline(f, line)) { words.insert(line.substr(0, line.find(" ")), stoi(line.substr(line.find(" ")+1))); ++i; } f.close(); assert(i == 300000); // If this fails, words2.txt is wrong vector C; while (cin) { string line; getline(cin, line); words.completions(line, C); for (string s : C) cout << " " << s << endl; } exit(0); } int main() { // Uncomment line below to use your Autocompleter // interactively with words2.txt as the dictionary. // // Enter a string and press Enter - the autocompletions // results from words.txt are printed. // //interactive_mode(); // Setup vector R; // Test constructor and size() Autocompleter animals; test(animals.size() == 0); animals.insert("aardvark", 629356); animals.insert("albatross", 553191); animals.insert("alpaca", 852363); animals.insert("armadillo", 393754); animals.insert("crow", 4592109); animals.insert("crocodile", 1658300); animals.insert("cat", 46839855); animals.insert("camel", 11005001); animals.insert("goat", 5231735); animals.insert("gorilla", 1931906); animals.insert("goose", 3739382); animals.insert("goatfish", 19984); animals.insert("giraffe", 978584); test(animals.size() == 13); Autocompleter words; test(words.size() == 0); ifstream f; f.open("words2.txt"); assert(f.is_open()); // If this fails, you're missing words2.txt string line; while (getline(f, line)) { words.insert(line.substr(0, line.find(" ")), stoi(line.substr(line.find(" ")+1))); } f.close(); test(words.size() == 300000); // Test insert() and size() animals.insert("buffalo", 17808542); test(animals.size() == 14); animals.insert("deer", 10007644); test(animals.size() == 15); animals.insert("horse", 58453720); test(animals.size() == 16); animals.insert("bullfrog", 273571); test(animals.size() == 17); animals.insert("deer", 10007644); test(animals.size() == 17); animals.insert("bullfrog", 273571); test(animals.size() == 17); // Test completions() animals.completions("a", R); test(R.size() == 3); test(R[0] == "alpaca"); test(R[1] == "aardvark"); test(R[2] == "albatross"); animals.completions("b", R); test(R.size() == 2); test(R[0] == "buffalo"); test(R[1] == "bullfrog"); animals.completions("c", R); test(R.size() == 3); test(R[0] == "cat"); test(R[1] == "camel"); test(R[2] == "crow"); animals.completions("d", R); test(R.size() == 1); test(R[0] == "deer"); animals.completions("e", R); test(R.size() == 0); animals.completions("f", R); test(R.size() == 0); animals.completions("g", R); test(R.size() == 3); test(R[0] == "goat"); test(R[1] == "goose"); test(R[2] == "gorilla"); animals.completions("h", R); test(R.size() == 1); test(R[0] == "horse"); animals.completions("aa", R); test(R.size() == 1); test(R[0] == "aardvark"); animals.completions("al", R); test(R.size() == 2); test(R[0] == "alpaca"); test(R[1] == "albatross"); animals.completions("an", R); test(R.size() == 0); animals.completions("bo", R); test(R.size() == 0); animals.completions("da", R); test(R.size() == 0); animals.completions("de", R); test(R.size() == 1); test(R[0] == "deer"); animals.completions("go", R); test(R.size() == 3); test(R[0] == "goat"); test(R[1] == "goose"); test(R[2] == "gorilla"); animals.completions("cro", R); test(R.size() == 2); test(R[0] == "crow"); test(R[1] == "crocodile"); animals.completions("goat", R); test(R.size() == 2); test(R[0] == "goat"); test(R[1] == "goatfish"); animals.completions("gir", R); test(R.size() == 1); test(R[0] == "giraffe"); animals.completions("croc", R); test(R.size() == 1); test(R[0] == "crocodile"); animals.completions("crow", R); test(R.size() == 1); test(R[0] == "crow"); animals.completions("", R); test(R.size() == 3); test(R[0] == "horse"); test(R[1] == "cat"); test(R[2] == "buffalo"); animals.completions("CAT", R); test(R.size() == 0); animals.completions("cAt", R); test(R.size() == 0); animals.completions("giraffez", R); test(R.size() == 0); animals.completions("robotron", R); test(R.size() == 0); animals.completions("Y", R); test(R.size() == 0); animals.completions("YOLO", R); test(R.size() == 0); animals.completions("!error", R); test(R.size() == 0); words.completions("a", R); test(R.size() == 3); test(R[0] == "and"); test(R[1] == "a"); test(R[2] == "are"); words.completions("b", R); test(R.size() == 3); test(R[0] == "by"); test(R[1] == "be"); test(R[2] == "but"); words.completions("c", R); test(R.size() == 3); test(R[0] == "can"); test(R[1] == "contact"); test(R[2] == "click"); words.completions("!", R); test(R.size() == 0); words.completions("ba", R); test(R.size() == 3); test(R[0] == "back"); test(R[1] == "based"); test(R[2] == "baby"); words.completions("be", R); test(R.size() == 3); test(R[0] == "be"); test(R[1] == "been"); test(R[2] == "best"); words.completions("th", R); test(R.size() == 3); test(R[0] == "the"); test(R[1] == "that"); test(R[2] == "this"); words.completions("aft", R); test(R.size() == 3); test(R[0] == "after"); test(R[1] == "afternoon"); test(R[2] == "afterwards"); words.completions("cat", R); test(R.size() == 3); test(R[0] == "categories"); test(R[1] == "category"); test(R[2] == "catalog"); words.completions("syz", R); test(R.size() == 3); test(R[0] == "syzygy"); test(R[1] == "syzygium"); test(R[2] == "syzhthsh"); words.completions("sy$", R); test(R.size() == 0); words.completions("bird", R); test(R.size() == 3); test(R[0] == "bird"); test(R[1] == "birds"); test(R[2] == "birding"); words.completions("hola", R); test(R.size() == 3); test(R[0] == "hola"); test(R[1] == "holabird"); test(R[2] == "holanda"); words.completions("word", R); test(R.size() == 3); test(R[0] == "word"); test(R[1] == "words"); test(R[2] == "wordpress"); words.completions("birdz", R); test(R.size() == 0); words.completions("yello", R); test(R.size() == 3); test(R[0] == "yellow"); test(R[1] == "yellowstone"); test(R[2] == "yellowpages"); cout << "Assignment complete." << endl; } -------------------------------------------------------------------------------------------------------------------------------- 

(words2.txt): http://andrewwinslow.com/3333/hwAC2/words2.txt