A common feature of smartphone typing is autocomplete: after typing the beginning of a word, the user is presented with a list of possible completed words they intended to type. For instance, after typing an, the user is presented with and, ant, anagram, anterior, etc. Your assignment is to implement autocomplete. Specifically, you will implement Autocompleter, a class that maintains a dictionary of words and computes the top-3 most-likely completions of any input word quickly.The dictionary is given as a file containing a sorted list of dictionary words and their frequencies, where higher frequency means that the word is more common (e.g. quit has frequency 1032 and quixotic has frequency 15, indicating that quit is a more common word). The dictionary of words and their frequencies should be stored in a balanced binary search tree (see Figure 2).Notice that the set of words that start with a given string are always consecutive in sorted order. Said another way, theyre all the words in a specific range.

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 (animals.txt) containing 13 animals names and their frequencies in sorted order.1 4. A text file (words.txt) containing 300000 common English words and their frequencies in sorted order. 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 dictionary of strings and associated frequencies, // using the file as a source. The file is promised to have // the following format: // // string1 freq1 // string2 freq2 // ... // stringN freqN // // where string1 e = e; height = -1; left = right = nullptr; } Entry e; int height; // Used in hwAC2 (not in hwAC1) Node* left; Node* right; }; // Root of the binary-search-tree-based data structure Node* root; // Optional helper methods (you'll probably want them). // Returns the root of a BST containing the elements // of the portion of a sorted vector E from index l to r. // // Should run in O(r-l) time. Node* construct_recurse(vector &E, int l, int r); // Returns the size of a binary tree rooted at root. // // Should run in O(n) time. int size_recurse(Node* root); // Fills T with the three most-frequent completions of x // that are either: // -In the BST rooted at root. // -Already in T. // // 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 &T); }; #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  
 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
(animals.txt):
 
aardvark 6293 albatross 5531 alpaca 8523 armadillo 3937 cat 468398 camel 110050 crocodile 16583 crow 45921 giraffe 9785 goat 52317 goatfish 199 goose 37393 gorilla 19319
 
 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
(words.txt): found at link: http://andrewwinslow.com/3333/hwAC1/words.txt