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. All the files are provided below the autocompleter.h explains what each method is suppose to do

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//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; left = right = nullptr; } Entry e; 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 the 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 629356 albatross 553191 alpaca 852363 armadillo 393754 cat 46839855 camel 11005001 crocodile 1658300 crow 4592109 giraffe 978584 goat 5231735 goatfish 19984 goose 3739382 gorilla 1931906
 
 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
//words.txt (small sample below full words.txt can be accesed from http://andrewwinslow.com/3333/hwAC1/words.txt
 
a 908117 aa 3052 aaa 1024 aaaa 159 aaaah 5 aaaai 3 aaaargh 1 aaab 2 aaabooksearch 2 aaac 3 aaace 6 aaacn 16 aaae 5 aaah 14 aaahh 2 aaahhh 2 aaai 25 aaal 2 aaalac 1 aaand 2 aaap 1 aaargh 4 aaas 41 aaasc 2 aaat 1 aab 33 aaba 4 aabb 9 aabbccdd 5 aabc 3 aaberg 1 aabt 2 aac 250 aaca 6 aacap 2 aacc 23 aacd 1 aace 11 aach 1 aachen 75 aaci 1 aacn 7 aacp 4 aacplus 2 aacr 6 aacraid 3 aacrao 2 aacs 12 aacsb 13 aact 2 aacte 1 aacute 8 aad 38 aada 1 aadac 2 aadc 4 aadd 3 aade 3 aadl 2 aads 2 aadt 6 aadult 2 aadvantage 18 aae 17 aaea 3 aaec 3 aaem 2 aaene 4 aaeon 8 aaep 1 aaf 31 aafa 2 aafc 10 aafco 2 aafes 8 aafp 17 aag 47 aagaard 4 aagard 1 aage 5 aah 33 aaha 2 aahe 3 aahh 2 aahhh 1 aahperd 2 aahs 2 aahsa 3 aahz 4 aai 28 aaia 2 aaid 7 aais 2 aaj 41 aaja 4 aajtk 3 aak 8 aakash 2 aaker 3 aakers 2 aakp 1 aal 31 aala 1 aaland 1 aalas 1 aalbc 1 aalborg 40 aalen 3 aalesund 2 aalib 10 aaliyah 333 aall 17 aallpaper 2 aalpd 3 aals 4 aalsmeer 2 aalst 9 aalto 14 aaltonen 2 aam 25 aama 8 aaman 1 aamas 3 aamc 11 aamco 10 aamer 3 aames 8 aamft 2 aami 10 aamir 14 aamodt 3 aamr 2 aams 2 aamt 2 aamu 2 aamva 2 aan 152 aana 4 aanbevolen 2 aanbieding 3 aanbiedingen 10 aanbod 4 aand 10 aangeboden 2 aankondigingen 2 aanmaken 1 aanmelden 8 aanndd 11 aanr 1 aans 6 aantal 21 aanvraag 1 aanvragen 3 aanwezig 4 aao 22 aaohn 2 aaoms 1 aaos 6 aap 105 aapa 6 aapc 3 aapd 4 aapeli 5 aapg 12 aapi 4 aapl 22 aapm 7 aapne 1 aapno 2 aapp 2 aaps 18 aapt 11 aaq 2 aar 62 aaraa 6 aarau 5 aarc 7 aardal 1 aarde 3 aardema 2 aardman 5 aards 2 aardvark 62 aardvarks 3 aardwolf 2 aare 7 aarez 2 aargau 5 aargh 7 aargon 1 aarhus 59 aarm 1 aarne 1 aarnet 4 aarnio 5 aaro 2 aaron 1169 aaronic 2 aaronovitch 3 aarons 23 aaronsburg 2 aaronson 9 aaronsw 8 aaronswatches 3 aarp 150 aars 4 aarschot 2 aart 7 aarti 6 aarts 3 aas 131 aasa 7 aasb 20 aasc 2 aasd 4 aase 3 aasen 1 aashiq 1 aashish 1 aashto 33 aasia 2 aasis 1 aasl 4 aasld 1 aasp 4 aast 1 aastra 9 aastrom 1 aasu 4
  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 Can chat whenever OK, let's chat this af aft afternoon after q w e r ty uiop Figure 1: Autocomplete suggests "afternoon" and "after" as completions of "aft". 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