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. Do not change main.cpp or autocompleter.h, just create autocompleter.cpp to pass all tests in main. All instructions are in autocompleter.h. My code keeps failing in main.cpp for size, need help finishing, please use basic syntax to pass run-times given, thank you.

The following files have been given to you:

1. A C++ header file (autocompleter.h) declaring the Autocompleter class.

2. A C++ source file (main.cpp) containing a main function with tests.

3. A text file (words2.txt) containing 293147 common English words and their frequencies.

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

main.cpp

#include  #include  #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 == 293147); // 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() == 293147); // 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); // 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; }

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

autocmpleter.h

#ifndef AUTOCOMPLETER_H #define AUTOCOMPLETER_H #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 = 0; left = right = nullptr; } Node(Entry e) { this->e = e; height = 0; left = right = nullptr; } Entry e; int height; Node* left; Node* right; }; // A convenience method for getting the height of a subtree. // Useful for rebalance(). 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) // Returns the size of the binary tree rooted at root. // // Should run in O(n) time. int size_recurse(Node* root); // Fills C with the completions of x in the BST rooted at root. // // Should run in O(log(n) + k), where // -n is the size of the BST rooted at root. // -k is the number of Entrys in the BST rooted at root // whose strings start with x. void completions_recurse(string x, Node* root, vector &C); // Inserts an Entry into an AVL tree rooted at root. // // Should run in O(log(n)) time. void insert_recurse(Entry e, Node* root); // Rebalances the AVL tree rooted at root. // Helpful for insert(). // Should be called on every node visited during // the search in reverse search order. // // Should run in O(1) time. void rebalance(Node* root); // Perform left and right rotations around the root // of an AVL tree (helpful for implementing rebalance). // // Should run in O(1) time. void right_rotate(Node* root); void left_rotate(Node* root); }; #endif

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

words2.txt

copy/paste to address bar to save.

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

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\