INSTRUCTIONS:

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. Submit the source file autocompleter.cpp.

//This weeks topics are sorting algorithms and binary search.

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 and removing words from the list must be permitted. To keep up with your users typing, your code must give suggestions extremely fast (logarithmic time). However, changing the list via adding and removing words is allowed to be slow (linear time). A dynamic array of sorted words that uses binary search to find suggestions would work.

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

//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; // Testing stuff; just ignore it :) 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__)) // End of testing stuff 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"); cout << "45% earned." << endl; 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 << "65% 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

//dowload file(s) at http://andrewwinslow.com/2380/hwAC1/

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

//autocompleter.cpp

/*

EDIT HERE

*/