The following files have been given to you: 1. A C++ header file (autocompleter.h) declaring the Autocompleter class.1 2. A text file (words 50000.txt) containing 50000 common English words.2 3. A C++ source file (main.cpp) containing a main function with tests.

Download the files at http://andrewwinslow.com/2380/hwAC2/. 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.

The success of your autocomplete feature for PearOS has left users wanting a new and improved version. Specifically, many users have complained that loading the autocomplete feature takes too long: adding all of the words to the autocomplete suggestion list is very slow.

As a fix, your code must support fast loading of a suggestion list (given as an array of words instead of individual words one-at-a-time). And of course, users expect to receive suggestions with the same speed as the previous version.

The add(string* X, int len) method cannot be implemented by repeatedly calling add(string x) (tim- ing tests will fail). Instead, implement the method in three steps:

1. Add the elements of X to A (the array in the Autocompleter). 2. Sort A. 3. Remove duplicates in A (i.e., all but one occurrence of each string).

All three steps must run quickly ((n log n) time or faster).

For the third step, observe that if A is sorted, all occurrences of each string in A occur consecutively. Loop through A and copy only the first occurrence of each string into a second temporary array B with length capacity. Then replace A with B and update count.

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

//autocompleter.h

#ifndef AUTOCOMPLETER_H #define AUTOCOMPLETER_H #include using namespace std; class Autocompleter { public: // Same as hwAC1 Autocompleter(); void add(string x); // Adds the strings in X to the list of potential suggestions in the Autocompleter. // If any of the words are already in the Autocompleter, // does nothing with those words. // // Calling add() will not be fast enough (you need to sort instead) void add(string* X, int len); // Same as hwAC1 int completion_count(string x); // Same as hwAC1 int size(); // Same as hwAC1 void completions(string x, string* suggestions); private: // Same as hwAC1 int index_of(string x, string* A, int len); // Should be a O(n*log(n)) sort (merge sort or quick sort) void sort(string* A, int len); // Same as hwAC1 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 string* words = new string[50000]; ifstream f; f.open("words_50000.txt", ios::in); assert(f.is_open()); // If this fails, you're missing words_50000.txt string line; int i = 0; while (getline(f, line)) { words[i] = line; ++i; } f.close(); assert(i == 50000); // If this fails, words_50000.txt is wrong dictionary.add(words, 25000); delete[] words; // Start results loop 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; string A1[6] = {"camel", "cat", "giraffe", "goose", "gorilla", "alpaca"}; animals.add(A1, 6); test(animals.size() == 6); cout << "10% earned." << endl; string A2[5] = {"goat", "crocodile", "crow", "albatross", "armadillo"}; animals.add(A2, 5); test(animals.size() == 11); cout << "15% earned." << endl; string A3[2] = {"aardvark", "gorilla"}; // Gorilla is already in the Autocompleter animals.add(A3, 2); test(animals.size() == 12); cout << "20% earned." << endl; animals.add("gorilla"); // Gorilla is already in the Autocompleter test(animals.size() == 12); cout << "25% earned." << endl; animals.add("zebra"); test(animals.size() == 13); cout << "30% 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 << "35% earned." << endl; test(animals.completion_count("") == 13); cout << "40% earned." << endl; test(animals.completion_count("an") == 0); test(animals.completion_count("q") == 0); test(animals.completion_count("goat-billed carp") == 0); cout << "45% earned." << endl; 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] == ""); 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] == ""); animals.completions("goat-billed carp", results); test(results[0] == ""); test(results[1] == ""); test(results[2] == ""); test(results[3] == ""); test(results[4] == ""); cout << "50% earned." << endl; // Create an autocompleter of the 10000 most common // American English words and test for correctness. Autocompleter dictionary; // Fill autocompleter with words string* words = new string[50000]; ifstream f; f.open("words_50000.txt", ios::in); assert(f.is_open()); // If this fails, you're missing words_50000.txt string line; int i = 0; while (getline(f, line)) { words[i] = line; ++i; } f.close(); assert(i == 50000); // If this fails, words_50000.txt is wrong clock_t start = clock(); dictionary.add(&(words[0]), 25000); dictionary.add(&(words[25000]), 25000); clock_t end = clock(); float duration = static_cast(end - start) / CLOCKS_PER_SEC; delete[] words; test(dictionary.size() == 42895); // There are some duplicates test(duration < 2.0); cout << "60% earned." << endl; start = clock(); for (int i = 0; i < 100000; ++i) { dictionary.completion_count(random_string(5)); dictionary.completions(random_string(5), results); } end = clock(); duration = static_cast(end - start) / CLOCKS_PER_SEC; test(duration < 4.0); cout << "70% earned." << endl; test(dictionary.completion_count("bir") == 11); test(dictionary.completion_count("hap") == 14); test(dictionary.completion_count("program") == 3); test(dictionary.completion_count("foo") == 27); cout << "85% earned." << endl; dictionary.completions("bir", results); test(results[0] == "birch"); test(results[1] == "birches"); test(results[2] == "bird"); test(results[3] == "bird's"); test(results[4] == "birds"); dictionary.completions("hap", results); test(results[0] == "hap"); test(results[1] == "haphazard"); test(results[2] == "hapless"); test(results[3] == "haply"); test(results[4] == "happen"); dictionary.completions("program", results); test(results[0] == "program"); test(results[1] == "programme"); test(results[2] == "programs"); test(results[3] == ""); test(results[4] == ""); dictionary.completions("foo", results); test(results[0] == "food"); test(results[1] == "foods"); test(results[2] == "foodstuffs"); test(results[3] == "fool"); test(results[4] == "fool's"); cout << "100% earned." << endl; } 

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

//words_50000.txt

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

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

//autocompleter.cpp

// EDIT HERE

#include

#include

#include

#include"autocompleter.h"

// Creates a new, empty autocompleter

Autocompleter::Autocompleter()

{

count=0;

capacity=10000;

A=new string[100];

}

int binary_search_method(string x)

{

int l=0,h=Autocompleter::count-1;

int mid;

while(l

{

mid=(l+h)/2;

if(x.compare(Autocompleter::A[mid])==0)

return mid;

if(x.compare(Autocompleter::A[mid])<0)

h=mid-1;

else

l=mid+1;

}

return -1;

}

// Adds x to the list of potential suggestions in the Autocompleter.

// If the word is already in the Autocompleter, does nothing.

void Autocompleter::add(string x)

{

if (binary_search_method(x)==-1)

{

A[count]=x;

cout<

sort(A,A+count);

count++;

}

}

// Returns the number of strings that are completions of

// the parameter string x.

int Autocompleter::completion_count(string x)

{

int index=index_of(x,A,count);

int count=0;

for(int i=index;A[i].find(x)==0;i++)

count++;

return count;

}

// Identical to labSRCH, but with strings instead of ints

int Autocompleter::index_of(string x, string A[], int len)

{

int l=0,h=count-1;

int mid;

while(l

{

mid=(l+h)/2;

if(x.compare(A[mid])==0)

return mid;

if(x.compare(A[mid])<0)

h=mid-1;

else

l=mid+1;

}

return -1;

}

// Returns the number of strings in the Autocompleter.

int Autocompleter::size()

{

return count;

}

// 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 Autocompleter::completions(string x, string* suggestions)

{

int index=index_of(x,A,count);

int j=0;

for(int i=index;A[i].find(x)==0;i++)

suggestions[j++]=A[i];

while(j<4){

suggestions[j++]="";

}

}