Please only attempt if you're fluent in C++, thank you.

INSTRUCTIONS: 1. Download files from http://andrewwinslow.com/2380/hwAC1/ 2. In c++, create a autocompleter.cpp file that will pass all tests from main.cpp file to output 100% 3. Use Binary Search, Sorting Algorithms

The following files have been given to you:

1. A C++ header file (autocompleter.h) declaring the Autocompleter class. 2. A text file (words 10000.txt) containing 10000 common English words.1 3. A C++ source file (main.cpp) containing a main function with tests.

Download the files at http://andrewwinslow.com/2380/hwAC1/. Create a new C++ source file named autocompleter.cpp that implements the class declared in autocompleter.h, so that main.cpp and autocompleter.cpp compile into a program that runs with no failed tests.

You are a software engineer at Pear, a mobile phone company. Youve been asked to implement the auto- complete feature of PearOS. Autocomplete suggests how a partially typed word might be completed into a word from a list, e.g. a dictionary.

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 ((logn), i.e. logarithmic time). However, changing the list via adding words is allowed to be slow ((n), i.e. linear time). A dynamic array of sorted words that uses binary search to find suggestions would work.

The Autocompleter consists of a sorted array A of strings. The method completion count(string x) should return the number of strings in A that start with x.

One way to do this is to loop through A, count the the number of elements of A that start with x (see the find method of the string class. Similarly, completions(string x, string* suggestions) can also be implemented by looping through A and placing the first five elements of A that start with x into suggestions.

A good goal is to first implement these methods in this way, so that 65% earned. is reached (i.e. all tests pass except the the final timing test).

Passing the final test requires using binary search to avoid looping through the entire array. First, implement the private helper method index of(string x, string* A, int len) as in lab (using binary search).

Since A is sorted, the words in A that start with a string x occur consecutively in A, beginning at index where x would be inserted into A while keeping A sorted. This index is the value returned by index of(string x, string* A, int len). So the loops used in completions count(string x) and completions(string x, string* suggestions) can start at the index returned by index of(x, A, len). Also, the loop can stop once a word is reached that does not start with x. Doing so makes these methods fast enough to pass the final timing test.

=============================================================

//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 list of potential suggestions in the Autocompleter. // If the word is already in the Autocompleter, does nothing. void add(string x); // Returns the number of strings that are completions of // the parameter string x. int completion_count(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) // Sets the first five 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) void completions(string x, string* suggestions); private: // Identical to labSRCH, but with strings instead of ints int index_of(string x, string* A, int len); // The data structure should consist of // a dynamic array of sorted strings. string* A; int count; int capacity; }; #endif 

=========================================================

//main.cpp

#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 << ", line " << line << "." << endl; abort(); } #define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__)) string random_string(int length) { string s; for (int i = 0; i < length; ++i) s += 'a' + (rand() % 26); return s; } void interactive_mode() { Autocompleter dictionary; // Fill autocompleter with words ifstream f; f.open("words_10000.txt", ios::in); assert(f.is_open()); // If this fails, you're missing above file string line; while (getline(f, line)) dictionary.add(line); f.close(); string results[5]; while (cin) { string line; getline(cin, line); dictionary.completions(line, results); for (int i = 0; i < 5; ++i) if (results[i] != "") cout << " " << results[i] << endl; } exit(0); } int main() { srand(2017); // Initialize random number generation, e.g. rand() string results[5]; // Used to hold output suggestions in some tests // Uncomment line below to use your Autocompleter interactively. // Enter a string and press Enter - the autocompletions // results from the 10000 most common words are printed. // //interactive_mode(); // Test a small Autocompleter with animal names Autocompleter animals; test(animals.size() == 0); cout << "5% earned." << endl; animals.add("aardvark"); animals.add("albatross"); animals.add("alpaca"); animals.add("armadillo"); animals.add("camel"); animals.add("cat"); animals.add("crocodile"); animals.add("crow"); animals.add("giraffe"); animals.add("goat"); animals.add("goose"); animals.add("gorilla"); test(animals.size() == 12); cout << "10% earned." << endl; animals.add("gorilla"); // Already in the Autocompleter test(animals.size() == 12); cout << "15% earned." << endl; test(animals.completion_count("a") == 4); test(animals.completion_count("al") == 2); test(animals.completion_count("cro") == 2); test(animals.completion_count("gir") == 1); test(animals.completion_count("go") == 3); cout << "25% earned." << endl; test(animals.completion_count("") == 12); cout << "30% earned." << endl; test(animals.completion_count("an") == 0); test(animals.completion_count("q") == 0); test(animals.completion_count("goat-billed carp") == 0); cout << "35% earned." << endl; // Create an autocompleter of the 10000 most common // American English words and test for correctness. Autocompleter dictionary; // Fill autocompleter with words ifstream f; f.open("words_10000.txt", ios::in); assert(f.is_open()); // If this fails, you're missing above file string line; while (getline(f, line)) dictionary.add(line); f.close(); test(dictionary.size() == 9990); // There are some duplicates test(dictionary.completion_count("bir") == 5); test(dictionary.completion_count("hap") == 6); test(dictionary.completion_count("program") == 7); test(dictionary.completion_count("foo") == 8); cout << "40% earned." << endl; // Test completions() on animals Autocompleter already made. animals.completions("a", results); test(results[0] == "aardvark"); test(results[1] == "albatross"); test(results[2] == "alpaca"); test(results[3] == "armadillo"); test(results[4] == ""); animals.completions("al", results); test(results[0] == "albatross"); test(results[1] == "alpaca"); test(results[2] == ""); test(results[3] == ""); test(results[4] == ""); animals.completions("cro", results); test(results[0] == "crocodile"); test(results[1] == "crow"); test(results[2] == ""); test(results[3] == ""); test(results[4] == ""); animals.completions("gir", results); test(results[0] == "giraffe"); test(results[1] == ""); test(results[2] == ""); test(results[3] == ""); test(results[4] == ""); animals.completions("go", results); test(results[0] == "goat"); test(results[1] == "goose"); test(results[2] == "gorilla"); test(results[3] == ""); test(results[4] == ""); cout << "45% earned." << endl; animals.completions("", results); test(results[0] == "aardvark"); test(results[1] == "albatross"); test(results[2] == "alpaca"); test(results[3] == "armadillo"); test(results[4] == "camel"); animals.completions("an", results); test(results[0] == ""); test(results[1] == ""); test(results[2] == ""); test(results[3] == ""); test(results[4] == ""); animals.completions("q", results); test(results[0] == ""); test(results[1] == ""); test(results[2] == ""); test(results[3] == ""); test(results[4] == ""); cout << "50% earned." << endl; animals.completions("goat-billed carp", results); test(results[0] == ""); test(results[1] == ""); test(results[2] == ""); test(results[3] == ""); test(results[4] == ""); cout << "55% earned." << endl; // Test completions() on dictionary Autocompleter already made. dictionary.completions("bir", results); test(results[0] == "bird"); test(results[1] == "birds"); test(results[2] == "birmingham"); test(results[3] == "birth"); test(results[4] == "birthday"); dictionary.completions("hap", results); test(results[0] == "happen"); test(results[1] == "happened"); test(results[2] == "happening"); test(results[3] == "happens"); test(results[4] == "happiness"); dictionary.completions("program", results); test(results[0] == "program"); test(results[1] == "programme"); test(results[2] == "programmer"); test(results[3] == "programmers"); test(results[4] == "programmes"); dictionary.completions("foo", results); test(results[0] == "foo"); test(results[1] == "food"); test(results[2] == "foods"); test(results[3] == "fool"); test(results[4] == "foot"); cout << "85% earned." << endl; // Test Autocompleter for completing 100000 words clock_t start = clock(); for (int i = 0; i < 100000; ++i) dictionary.completions(random_string(5), results); clock_t end = clock(); float duration = static_cast(end - start) / CLOCKS_PER_SEC; // If your completions() implementation is using binary-search, // all other tests pass, and this test is still failing, talk to Andrew. test(duration < 5.0); cout << "100% earned." << endl; } 

==========================================================

//words_10000.txt

//download at : http://andrewwinslow.com/2380/hwAC1/

============================================================

//autocompleter.cpp

/*

EDIT HERE

*/