Create a new C++ source file named autocompleter.cpp that implements the class d
ID: 3751941 • Letter: C
Question
Create a new C++ source file named autocompleter.cpp that implements the class declared in autocompleter.h, so that autocompleter.cpp and the provided files compile into a program that runs with no failed tests. All the files are provided below the autocompleter.h explains what each method is suppose to do
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//autocompleter.h
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//main.cpp
//animals.txt
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//words.txt (small sample below full words.txt can be accesed from http://andrewwinslow.com/3333/hwAC1/words.txt
A common feature of smartphone typing is autocomplete: after typing the beginning of a word, the user is presented with a list of possible completed words they intended to type. For instance, after typing "an", the user is presented with "and", "ant", "anagram", "anterior", etc. Your assignment is to implement autocomplete. Specifically, you will implement Autocompleter, a class that maintains a dictionary of words and computes the top-3 most-likely completions of any input word quickly Can chat whenever OK, let's chat this af aft afternoon after q w e r ty uiop Figure 1: Autocomplete suggests "afternoon" and "after" as completions of "aft". The dictionary is given as a file containing a sorted list of dictionary words and their frequencies, where higher frequency means that the word is more common (e.g. "quit" has frequency 1032 and "quixotic" has frequency 15, indicating that "quit" is a more common word). The dictionary of words and their frequenciesExplanation / Answer
AC2.cpp
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#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__))
void interactive_mode()
{
Autocompleter words;
ifstream f;
f.open("words2.txt");
assert(f.is_open()); // If this fails, you're missing words2.txt
string line;
int i = 0;
while (getline(f, line))
{
words.insert(line.substr(0, line.find(" ")),
stoi(line.substr(line.find(" ") + 1)));
++i;
}
f.close();
assert(i == 300000); // If this fails, words2.txt is wrong
vector<string> C;
while (cin)
{
string line;
getline(cin, line);
words.completions(line, C);
for (string s : C)
cout << " " << s << endl;
}
exit(0);
}
int main()
{
// Setup
vector<string> R;
// Test constructor and size()
Autocompleter animals;
test(animals.size() == 0);
animals.insert("aardvark", 629356);
animals.insert("albatross", 553191);
animals.insert("alpaca", 852363);
animals.insert("armadillo", 393754);
animals.insert("crow", 4592109);
animals.insert("crocodile", 1658300);
animals.insert("cat", 46839855);
animals.insert("camel", 11005001);
animals.insert("goat", 5231735);
animals.insert("gorilla", 1931906);
animals.insert("goose", 3739382);
animals.insert("goatfish", 19984);
animals.insert("giraffe", 978584);
test(animals.size() == 13);
Autocompleter words;
test(words.size() == 0);
ifstream f;
f.open("words2.txt");
assert(f.is_open()); // If this fails, you're missing words2.txt
string line;
while (getline(f, line))
{
words.insert(line.substr(0, line.find(" ")),
stoi(line.substr(line.find(" ") + 1)));
}
f.close();
test(words.size() == 300000);
// Test insert() and size()
animals.insert("buffalo", 17808542);
test(animals.size() == 14);
animals.insert("deer", 10007644);
test(animals.size() == 15);
animals.insert("horse", 58453720);
test(animals.size() == 16);
animals.insert("bullfrog", 273571);
test(animals.size() == 17);
animals.insert("deer", 10007644);
test(animals.size() == 17);
animals.insert("bullfrog", 273571);
test(animals.size() == 17);
// Test completions()
animals.completions("a", R);
test(R.size() == 3);
test(R[0] == "alpaca");
test(R[1] == "aardvark");
test(R[2] == "albatross");
animals.completions("b", R);
test(R.size() == 2);
test(R[0] == "buffalo");
test(R[1] == "bullfrog");
animals.completions("c", R);
test(R.size() == 3);
test(R[0] == "cat");
test(R[1] == "camel");
test(R[2] == "crow");
animals.completions("d", R);
test(R.size() == 1);
test(R[0] == "deer");
animals.completions("e", R);
test(R.size() == 0);
animals.completions("f", R);
test(R.size() == 0);
animals.completions("g", R);
test(R.size() == 3);
test(R[0] == "goat");
test(R[1] == "goose");
test(R[2] == "gorilla");
animals.completions("h", R);
test(R.size() == 1);
test(R[0] == "horse");
animals.completions("aa", R);
test(R.size() == 1);
test(R[0] == "aardvark");
animals.completions("al", R);
test(R.size() == 2);
test(R[0] == "alpaca");
test(R[1] == "albatross");
animals.completions("an", R);
test(R.size() == 0);
animals.completions("bo", R);
test(R.size() == 0);
animals.completions("da", R);
test(R.size() == 0);
animals.completions("de", R);
test(R.size() == 1);
test(R[0] == "deer");
animals.completions("go", R);
test(R.size() == 3);
test(R[0] == "goat");
test(R[1] == "goose");
test(R[2] == "gorilla");
animals.completions("cro", R);
test(R.size() == 2);
test(R[0] == "crow");
test(R[1] == "crocodile");
animals.completions("goat", R);
test(R.size() == 2);
test(R[0] == "goat");
test(R[1] == "goatfish");
animals.completions("gir", R);
test(R.size() == 1);
test(R[0] == "giraffe");
animals.completions("croc", R);
test(R.size() == 1);
test(R[0] == "crocodile");
animals.completions("crow", R);
test(R.size() == 1);
test(R[0] == "crow");
animals.completions("", R);
test(R.size() == 3);
test(R[0] == "horse");
test(R[1] == "cat");
test(R[2] == "buffalo");
animals.completions("CAT", R);
test(R.size() == 0);
animals.completions("cAt", R);
test(R.size() == 0);
animals.completions("giraffez", R);
test(R.size() == 0);
animals.completions("robotron", R);
test(R.size() == 0);
animals.completions("Y", R);
test(R.size() == 0);
animals.completions("YOLO", R);
test(R.size() == 0);
animals.completions("!error", R);
test(R.size() == 0);
words.completions("a", R);
test(R.size() == 3);
test(R[0] == "and");
test(R[1] == "a");
test(R[2] == "are");
words.completions("b", R);
test(R.size() == 3);
test(R[0] == "by");
test(R[1] == "be");
test(R[2] == "but");
words.completions("c", R);
test(R.size() == 3);
test(R[0] == "can");
test(R[1] == "contact");
test(R[2] == "click");
words.completions("!", R);
test(R.size() == 0);
words.completions("ba", R);
test(R.size() == 3);
test(R[0] == "back");
test(R[1] == "based");
test(R[2] == "baby");
words.completions("be", R);
test(R.size() == 3);
test(R[0] == "be");
test(R[1] == "been");
test(R[2] == "best");
words.completions("th", R);
test(R.size() == 3);
test(R[0] == "the");
test(R[1] == "that");
test(R[2] == "this");
words.completions("aft", R);
test(R.size() == 3);
test(R[0] == "after");
test(R[1] == "afternoon");
test(R[2] == "afterwards");
words.completions("cat", R);
test(R.size() == 3);
test(R[0] == "categories");
test(R[1] == "category");
test(R[2] == "catalog");
words.completions("syz", R);
test(R.size() == 3);
test(R[0] == "syzygy");
test(R[1] == "syzygium");
test(R[2] == "syzhthsh");
words.completions("sy$", R);
test(R.size() == 0);
words.completions("bird", R);
test(R.size() == 3);
test(R[0] == "bird");
test(R[1] == "birds");
test(R[2] == "birding");
words.completions("hola", R);
test(R.size() == 3);
test(R[0] == "hola");
test(R[1] == "holabird");
test(R[2] == "holanda");
words.completions("word", R);
test(R.size() == 3);
test(R[0] == "word");
test(R[1] == "words");
test(R[2] == "wordpress");
words.completions("birdz", R);
test(R.size() == 0);
words.completions("yello", R);
test(R.size() == 3);
test(R[0] == "yellow");
test(R[1] == "yellowstone");
test(R[2] == "yellowpages");
cout << "Assignment complete." << endl;
system("Pause");
}
autocompleter.cpp
#include "autocompleter.h"
Autocompleter::Autocompleter()
{
}
void Autocompleter::insert(string x, int freq)
{
Entry cpy;
cpy.s = x; cpy.freq = freq;
if (root == nullptr)
{
root = new Node(cpy);
root->height = height(root) + 1;
return;
}
insert_recurse(cpy, root);
}
int Autocompleter::size()
{
return size_recurse(root);
}
void Autocompleter::completions(string x, vector<string> &T)
{
T.clear();
vector<Entry> R;
completions_recurse(x, root, R);
int max1 = 0, max2 = 0, max3 = 0;
string word1, word2, word3;
for (int i = 0; i < R.size(); i++)
{
if (R[i].freq >= max1)
{
max3 = max2; max2 = max1; max1 = R[i].freq;
word3 = word2; word2 = word1; word1 = R[i].s;
}
else if (R[i].freq >= max2)
{
max3 = max2; max2 = R[i].freq;
word3 = word2; word2 = R[i].s;
}
else if (R[i].freq >= max3)
{
max3 = R[i].freq;
word3 = R[i].s;
}
}
if (max1 == 0) { return; }
if (max2 == 0) { T.push_back(word1); return; }
if (max3 == 0) { T.push_back(word1); T.push_back(word2); return; }
T.push_back(word1); T.push_back(word2); T.push_back(word3); return;
}
int Autocompleter::size_recurse(Node* root)
{
if (root == NULL)
return 0;
else
return(size_recurse(root->left) + 1 + size_recurse(root->right));
}
void Autocompleter::completions_recurse(string x, Node* root, vector<Entry> &T)
{
if (root == nullptr)
{
return;
}
if (!strncmp(root->e.s.c_str(), x.c_str(), x.size()))
{
completions_recurse(x, root->left, T);
T.push_back(root->e);
completions_recurse(x, root->right, T);
}
else if (root->e.s < x)
{
completions_recurse(x, root->right, T);
}
else if (root->e.s > x)
{
completions_recurse(x, root->left, T);
}
}
void Autocompleter::insert_recurse(Entry e, Node* cur)
{
if (cur->e.s == e.s)
return;
else if (cur->e.s < e.s)
{
if (cur->right != nullptr)
{
insert_recurse(e, cur->right);
}
else
{
cur->right = new Node(e);
}
}
else
{
if (cur->left != nullptr)
{
insert_recurse(e, cur->left);
}
else
{
cur->left = new Node(e);
}
}
if (height(cur->left) > height(cur->right))
{
cur->height = 1 + height(cur->left);
}
else
{
cur->height = 1 + height(cur->right);
}
rebalance(cur);
}
void Autocompleter::rebalance(Node* root)
{
if (height(root->left) - height(root->right) == 2)
{
if (height(root->left->right) > height(root->left->left))
{
left_rotate(root->left);
right_rotate(root);
}
else
{
right_rotate(root);
}
}
if (height(root->right) - height(root->left) == 2)
{
if (height(root->right->left) > height(root->right->right))
{
right_rotate(root->right);
left_rotate(root);
}
else
{
left_rotate(root);
}
}
}
void Autocompleter::right_rotate(Node* root)
{
Node* lc = root->left;
root->left = lc->left;
lc->left = lc->right;
lc->right = root->right;
root->right = lc;
swap(root->e, lc->e);
if (root->left != nullptr) {
if (height(root->left->left) > height(root->left))
root->left->height = height(root->left->left) + 1;
if (height(root->left->right)>height(root->left))
root->left->height = height(root->left->right) + 1;
}
if (root != nullptr) {
if (height(root->left) > height(root))
root->height = height(root->left) + 1;
if (height(root->right)>height(root))
root->height = height(root->right) + 1;
}
}
void Autocompleter::left_rotate(Node* root)
{
Node* rc = root->right;
root->right = rc->right;
rc->right = rc->left;
rc->left = root->left;
root->left = rc;
swap(root->e, rc->e);
if (root->right != nullptr) {
if (height(root->right->left) > height(root->right))
root->right->height = height(root->right->left) + 1;
if (height(root->right->right)>height(root->right))
root->right->height = height(root->right->right) + 1;
}
if (root != nullptr) {
if (height(root->left) > height(root))
root->height = height(root->left) + 1;
if (height(root->right)>height(root))
root->height = height(root->right) + 1;
}
}
autocompleter.h
#ifndef AUTOCOMPLETER_H
#define AUTOCOMPLETER_H
#include <vector>
#include <string>
#include <fstream>
#include <cassert>
using namespace std;
class Autocompleter
{
public:
// Creates a new Autocompleter with an empty dictionary.
//
// Must run in O(1) time.
Autocompleter();
// Adds a string x to the dictionary.
// If x is already in the dictionary, does nothing.
//
// Must run in O(log(n)) time.
void insert(string x, int freq);
// Returns the number of strings in the dictionary
// of possible completions.
//
// Must run in O(n) time.
int size();
void completions(string x, vector<string> &T);
private:
// A helper class that stores a string and a frequency.
class Entry
{
public:
string s;
int freq;
};
// A helper class that implements a binary search tree node.
class Node
{
public:
Node()
{
height = -1;
left = right = nullptr;
}
Node(Entry e)
{
this->e = e;
height = -1;
left = right = nullptr;
}
Entry e;
int height;
Node* left;
Node* right;
};
// A convenience method for getting the height of a subtree.
// Useful for rebalance().
static int height(Node* root)
{
if (root == nullptr)
return -1;
return root->height;
}
// Root of the binary-search-tree-based data structure
Node* root;
// Optional helper methods (you'll probably want them)
// Returns the size of the binary tree rooted at root.
//
// Should run in O(n) time.
int size_recurse(Node* root);
void completions_recurse(string x, Node* root, vector<Entry> &T);
// Inserts an Entry into an AVL tree rooted at root.
//
// Should run in O(log(n)) time.
void insert_recurse(Entry e, Node* root);
// Should run in O(1) time.
void rebalance(Node* root);
// Perform left and right rotations around the root
// of an AVL tree (helpful for implementing rebalance).
//
// Should run in O(1) time.
void right_rotate(Node* root);
void left_rotate(Node* root);
};
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.