In this iteration of autocomplete, you’ll eliminate the weakness of the previous
ID: 3720791 • Letter: I
Question
In this iteration of autocomplete, you’ll eliminate the weakness of the previous version: a long “load time” due to slow addition of words to the Autocompleter. Instead of add taking theta(n) worst-case time, you should aim for theta(log n) time. All other methods should retain their current speeds. To achieve this, a more advanced data structure is needed: a binary search tree.
The following files have been given to you:
1. A C++ header file (autocompleter.h) declaring the Autocompleter class.
2. A C++ source file (main.cpp) containing a main() function with tests.
3. A text file (words.txt) containing 10000 common words.
Create new C++ source file named autocompleter.cpp that implements the function declared in autocompleter.h so that autocompleter.cpp and the provided files compile into a program that runs with no failed tests.
// BEGIN AUTOCOMPLETER.H
#ifndef AUTOCOMPLETER_H
#define AUTOCOMPLETER_H
#include <string>
using namespace std;
class Autocompleter
{
public:
// Same as hwAC1
Autocompleter();
void insert(string x); // a.k.a. add()
int size();
int completion_count(string x);
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;
};
// Helper method for size()
int size_recurse(Node* root);
// Helper method for completion_count().
// Here's a (recursive) algorithm:
//
// Base case:
// If root is nullptr, then return 0.
//
// Recursive case:
// -Return the sum of the completion counts of the
// left and right subtrees plus:
// 0 if root->s does not start with x.
// 1 if root->s does start with x.
int completion_count_recurse(string x, Node* root);
// Helper method for completions().
// Here's a (recursive) algorithm:
//
// Base case:
// If root is nullptr, return.
// If the last entry of the suggestions array is not "", return.
// (since completions() has already found 5 suggestions).
//
// Recursive case:
// -Recurse on left subtree.
// -If root->s starts with x, add root->s to first empty
// location in suggestions.
// -Recurse on right subtree.
void completions_recurse(string x, string* suggestions, Node* root);
// The data structure should be a binary search tree
Node* root;
};
#endif
//END AUTOCOMPLETER.H
------------------------------------------------
//BEGIN MAIN.CPP
#include <iostream>
#include <fstream>
#include <cassert>
#include <string>
#include "autocompleter.h"
using namespace std;
inline void _test(const char* expression, const char* file, int line)
{
cerr << "test(" << expression << ") failed in file " << file;
cerr << ", line " << line << "." << endl;
abort();
}
#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))
// Used later for testing
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.txt");
assert(f.is_open()); // If this fails, you're missing words.txt
string line;
while (getline(f, line))
dictionary.insert(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 100000 most common words are printed.
//
// interactive_mode();
// Test a small Autocompleter with animal names
Autocompleter animals;
test(animals.size() == 0);
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");
test(animals.size() == 12);
animals.insert("gorilla"); // Already in the Autocompleter
test(animals.size() == 12);
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);
test(animals.completion_count("") == 12);
test(animals.completion_count("an") == 0);
test(animals.completion_count("q") == 0);
test(animals.completion_count("goat-billed carp") == 0);
// Create an autocompleter of common words.
Autocompleter dictionary;
// Fill autocompleter with words
string* words = new string[100000];
ifstream f;
f.open("words.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 < 100000; ++i)
dictionary.insert(words[i]);
delete[] words;
for (int i = 0; i < 10; ++i)
test(dictionary.size() == 100000);
test(dictionary.completion_count("bir") == 55);
test(dictionary.completion_count("hap") == 25);
test(dictionary.completion_count("program") == 25);
test(dictionary.completion_count("foo") == 68);
// 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] == "");
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] == "");
// Test completions() on dictionary Autocompleter already made.
dictionary.completions("bir", results);
test(results[0] == "bir");
test(results[1] == "biracial");
test(results[2] == "birch");
test(results[3] == "birches");
test(results[4] == "birchwood");
dictionary.completions("hap", results);
test(results[0] == "hap");
test(results[1] == "haphazard");
test(results[2] == "haphazardly");
test(results[3] == "hapkido");
test(results[4] == "hapless");
dictionary.completions("program", results);
test(results[0] == "program");
test(results[1] == "programa");
test(results[2] == "programas");
test(results[3] == "programchecker");
test(results[4] == "programe");
dictionary.completions("foo", results);
test(results[0] == "foo");
test(results[1] == "foobar");
test(results[2] == "food");
test(results[3] == "foodborne");
test(results[4] == "foodie");
// Test efficiency of completion_count() and completions()
for (int i = 0; i < 10; ++i)
dictionary.completion_count(random_string(5));
for (int i = 0; i < 10; ++i)
dictionary.completions(random_string(5), results);
cout << "Assignment complete." << endl;
}
//END MAIN.CPP
-----------------------------------------------
NEED TO IMPLEMENT THIS FILE WITHOUT ANY FAILING TESTS, MUST PRINT OUT "ASSIGNMENT COMPLETE"
//BEGIN AUTOCOMPLETER.CPP
//END AUTOCOMPLETER.CPP
Explanation / Answer
autocompleter:
#include <iostream>
#include <set>
using namespace std;
int common_prefix(const string& a, const string& b) {
int i = 0;
while (i < a.size() && i < b.size() && a[i] == b[i])
++i;
return i;
}
int main(int ac, char* av[]) {
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
int n;
cin >> n;
set<string> words;
int total_chars = 0;
for (int k = 0; k < n; ++k) {
string word;
cin >> word;
words.insert(word);
set<string>::iterator it = words.find(word);
int max_pref = 0;
if (it != words.begin()) {
auto prev = it;
--prev;
max_pref = max(max_pref, common_prefix(*prev, word));
}
++it;
if (it != words.end())
max_pref = max(max_pref, common_prefix(*it, word));
if (max_pref != word.size())
++max_pref;
total_chars += max_pref;
}
cout << "Case #" << (i + 1) << ": " << total_chars << endl;
}
return 0;
}
end autocompleter:
#include <iostream>
#include <iomanip>
#include <limits>
#include <cstdlib>
#include <string>
#include <vector>
#include <fstream>
#include "autoCompleteConfig.h"
#include <queue>
bool openGood(std::ifstream&, char* argv);
void readDictionary(std::ifstream&, std::vector<std::string>&, char* argv);
void readInput(std::ifstream&, std::vector<std::string>&, char* argv);
int search(std::vector<std::string>&, std::string);
typedef std::vector<std::string>::iterator vecIter;
int main(int argc, char* argv[])
{
//word and input file, output file and data structures to hold information
std::ifstream wordFile, inFile;
std::ofstream out;
std::queue<std::string> matchingCase;
std::vector<std::string> dictionary, input;
// cmake build version(as specified in cmake header
std::cout << "VERSION " << MAJOR << "." << MINOR << std::endl;
// if the user enters no args
if(argc == 1) {
std::cout << "Usage: ./auto <wordList> <inputFile>" << std::endl;
return 1;
// testing for retarded user
} else if(argc == 2) {
std::cout << "Error, must provide inputFile" << std::endl;
return 1;
}
// open dictionary text file
if(!openGood(wordFile, argv[1])) {
std::cout << "Error, dictionary file could not be opened ";
return 1;
}
// now open input file with the words we need to complete
if(!openGood(inFile, argv[2])) {
std::cout << "Error, input file could not be opened ";
return 1;
}
readDictionary(wordFile, dictionary, argv[1]);
readInput(inFile, input, argv[2]);
//condition: word file MUST be sorted
//--check, ok done
out.open("out.dat");
//for each element in our "find word" vector
for(int i = 0; i < input.size()-1; i++){
std::vector<std::string>::const_iterator pos = std::lower_bound(
dictionary.begin(),
dictionary.end(),
input.at(i));
for( ; pos != dictionary.end(); ++pos) {
if(pos->compare(0,(input.at(i)).size(),input.at(i)) == 0)
{
matchingCase.push(*pos);
}
else break;
}
}
// print contents of queue, counter for format
int counter = 0;
while(!matchingCase.empty()) {
//make sure to display our queue in the order we found them
std::cout << std::setw(15) << matchingCase.front();
out << std::setw(15) << matchingCase.front();
//pop off the front of the queue
matchingCase.pop();
counter++;
//format counter for displaying, 5 per line
if(counter % 5 == 0) {
std::cout << std::endl;
out << std::endl;
}
}
std::cout << std::endl;
out.close();
return 0;
}
// test if file passed to function is valid and can be read
bool openGood(std::ifstream& file, char* argv)
{
file.open(argv);
if (!file.is_open()){
//file cannot be opened, error out
std::cerr << "FILE ERROR...CANNOT BE OPENED" << std::endl;
return false;
}
//file cannot be open
return true;
}
// read data from file into vector, I feel a vector is much more
// optimized for standard data types than say, a linked list. open
// for debate though, a hash table might also be a viable data structure
void readDictionary(std::ifstream& inFile, std::vector<std::string>& vec, char* argv)
{
std::string line;
inFile >> line;
vec.push_back(line);
while(inFile) {
inFile >> line;
vec.push_back(line);
}
}
//same as read dictionary, but for our input file
void readInput(std::ifstream& inFile, std::vector<std::string> &vec, char* argv)
{
std::string line;
inFile >> line;
vec.push_back(line);
while(inFile){
inFile >> line;
vec.push_back(line);
}
}
/* OUTDATED BY STD::LOWER_BOUND
//search function uses a binary search algorithm on a given vector. It is important
//to note that the string MUST be sorted before being passed into binary search
//or you are going to have a very bad time. Currently finds index for first match
//and return int for main loop to start search from that point
int search(std::vector<std::string>& dict, std::string in)
{
//for each element in the input vector
//find all possible word matches and push onto the queue
int first=0, last= dict.size() -1;
while(first <= last)
{
int middle = (first+last)/2;
std::string sub = (dict.at(middle)).substr(0,in.length());
int comp = in.compare(sub);
//if comp returns 0(found word matching case)
if(comp == 0) {
return middle;
}
//if not, take top half
else if (comp > 0)
first = middle + 1;
//else go with the lower half
else
last = middle - 1;
}
//word not found... return failure
return -1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.