Good morning, I would like to get help with the implementation of this program in c++. Thank you in advance.

Autocompleter.h :

#ifndef AUTOCOMPLETER_H #define AUTOCOMPLETER_H

#include

using namespace std;

class Autocompleter { public: // Creates a new, empty autocompleter. Autocompleter();

// Adds x to the dictionary which is built as a binary search tree in the Autocompleter. // [create a Node, set the value , etc] // If the word is already in the Autocompleter, does nothing. // // Must run in O(log(n)) time. void insert(string x);

// Returns the number of strings in the Autocompleter. int size();

// Takes a string (named x) and string array of length 5 (named suggestions) // Set the elements of suggestions equal to the first five (in lexicographic order) strings // in the Autocompleter that start with x. // // If there are less than five such strings, the remaining // entries of the suggestions array are set to "" (the empty string) // // Must run in O(log(n)) time. // Hint: Initialize the elements of suggestions equal to empty string ("") and then call the completions_recurse method void completions(string x, string* suggestions);

private: // A helper class that implements // a basic binary search tree node. class Node { public: Node(string s) { this->s = s; left = right = nullptr; }

string s; Node* left; Node* right; };

// The data structure should be a binary search tree Node* root;

// Helper method for size() // you can call this method inside the size method int size_recurse(Node* root);

// Helper method for completions(). // // Suggested base cases: // If root is nullptr, return. // If you found a suggestion but the last entry of the suggestions array is not "", return. // (since completions() has already found 5 suggestions). // // Suggested recursive case: // -If left subtree can contain strings that start with x, // recurse on left subtree. // -If root's string starts with x, // add root->s to first empty location in results. // -If right subtree can contain strings that start with x, // recurse on right subtree. // //Useful function: If I have two string s and x. s.find(x) returns the first index that x exists in the s // For example s = bird; x = bi; s.find(x) returns 0 void completions_recurse(string x, string* suggestions, Node* root);

};

#endif

Source.cpp :

#include #include #include #include #include "autocompleter.h"

using namespace std;

int main() { string results[5]; // Used to hold output suggestions in some tests

// The suggestions that you have to get as a result are in the paranthesis. //So if your program is working, all the words should be similar to the word in paranthesis //If paranthesis is empty, it is because there is no more suggestion. So basically the element in the array is an empty string ("")

// Test a small Autocompleter with animal names Autocompleter animals; animals.insert("aardvark"); animals.insert("albatross"); animals.insert("alpaca"); animals.insert("armadillo"); animals.insert("camel"); animals.insert("cat"); animals.insert("crocodile"); animals.insert("crow"); animals.insert("giraffe"); animals.insert("goat"); animals.insert("goose"); animals.insert("gorilla"); cout

// Test completions() on animals Autocompleter already made. animals.completions("a", results); cout

animals.completions("al", results); cout

animals.completions("cro", results); cout

animals.completions("gir", results); cout

animals.completions("go", results); cout

// no option starting with q in the animal dictionary animals.completions("q", results); cout

// Now Let's move to a larger dictionary // Create an autocompleter of common words. Autocompleter dictionary;

// Fill autocompleter with words string* words = new string[100000]; ifstream f; f.open("words2.txt"); assert(f.is_open()); // If this fails, you're missing words.txt string line; int i = 0; while (getline(f, line)) { words[i] = line; ++i; } f.close(); assert(i == 100000); // If this fails, words.txt is wrong

for (int i = 0; i

cout

// Test completions() on dictionary Autocompleter already made. dictionary.completions("bir", results); cout

dictionary.completions("hap", results); cout

dictionary.completions("foo", results); cout

cout

words2.txt is way too long, so I'm not including that one.

Nowadays most of the cellphones have an Autocomplete. Autocomplete suggests how a partially typed word might be completed into a word from a list, e.g. a dictionary (see Figure 1 Can chat whenever OK, let's chat this aft aft afternoon after Figure 1: Autocomplete suggests "afternoon" and "after" as completions of "aft". Because the data might depend upon the user and what words they use most commonly, adding words to the list must be permitted. To keep up with your users' typing, your code must give suggestions extremely fast (O(logn) time). That's why binary search tree is a good data structure to store the data. In this assignment, you implement the methods in the AutoComplete class. The following files have been given to you AC++ header file (autocompleter.h) declaring the Autocompleter class 2. 1. A C++ source file (source.cpp) containing a main function which test your implementation 3. A test file (words.txt) containing 10000 common words to build your dictionary Create a new C++ source file names autocompleter.cpp that implements the class declared in autocompleter.h. Make sure to copy words.txt in the same folder as other files so that the main function can find it. Submit the source file autocompleter.cpp Nowadays most of the cellphones have an Autocomplete. Autocomplete suggests how a partially typed word might be completed into a word from a list, e.g. a dictionary (see Figure 1 Can chat whenever OK, let's chat this aft aft afternoon after Figure 1: Autocomplete suggests "afternoon" and "after" as completions of "aft". Because the data might depend upon the user and what words they use most commonly, adding words to the list must be permitted. To keep up with your users' typing, your code must give suggestions extremely fast (O(logn) time). That's why binary search tree is a good data structure to store the data. In this assignment, you implement the methods in the AutoComplete class. The following files have been given to you AC++ header file (autocompleter.h) declaring the Autocompleter class 2. 1. A C++ source file (source.cpp) containing a main function which test your implementation 3. A test file (words.txt) containing 10000 common words to build your dictionary Create a new C++ source file names autocompleter.cpp that implements the class declared in autocompleter.h. Make sure to copy words.txt in the same folder as other files so that the main function can find it. Submit the source file autocompleter.cpp