----------------------------------------------- //MAIN.CPP #include <iostream> #
ID: 3755055 • Letter: #
Question
-----------------------------------------------
//MAIN.CPP
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cassert>
#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("words.txt");
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()
{
// Uncomment line below to use your Autocompleter
// interactively with words.txt as the dictionary.
//
// Enter a string and press Enter - the autocompletions
// results from words.txt are printed.
//
//interactive_mode();
// Setup
vector<string> R;
// Test constructor and size()
Autocompleter animals("animals.txt");
test(animals.size() == 13);
Autocompleter words("words.txt");
test(words.size() == 293147);
// 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() == 0);
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() == 0);
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("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("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] == "cat");
test(R[1] == "camel");
test(R[2] == "goat");
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;
}
//END MAIN.CPP
-----------------------------------------------
//AUTOCOMPLETER.H
#ifndef AUTOCOMPLETER_H
#define AUTOCOMPLETER_H
#include <vector>
#include <string>
#include <cassert>
#include <fstream>
using namespace std;
class Autocompleter
{
// For the mandatory running times below:
// n is the number of strings in the dictionary.
// Assume that the length of every string is O(1).
public:
// Creates a dictionary of strings and associated frequencies,
// using the file as a source. The file is promised to have
// the following format:
//
// string1 freq1
// string2 freq2
// ...
// stringN freqN
//
// where string1 < string2 < ... < stringN
//
// Must run in O(n) time.
Autocompleter(string filename);
// Returns the number of strings in the dictionary
// of possible completions.
//
// Must run in O(n) time.
int size();
// Fills the vector T with the three most-frequent completions of x.
// If x has less than three completions,
// then T is filled with all completions of x.
// The completions appear in T from most- to least-frequent.
//
// Must run in O(log(n) + k) time,
// where k is the number of completions of x in the dictionary.
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 BST node.
class Node
{
public:
Node()
{
left = right = nullptr;
}
Node(Entry e)
{
this->e = e;
left = right = nullptr;
}
Entry e;
Node* left;
Node* right;
};
// Root of the binary-search-tree-based data structure
Node* root;
// Optional helper methods (you'll probably want them).
// Returns the root of a BST containing the elements
// of the portion of a sorted vector E from index l to r.
//
// Should run in O(r-l) time.
Node* construct_recurse(vector<Entry> &E, int l, int r);
// Returns the size of the binary tree rooted at root.
//
// Should run in O(n) time.
int size_recurse(Node* root);
// Fills T with the three most-frequent completions of x
// that are either:
// -In the BST rooted at root.
// -Already in T.
//
// Should run in O(log(n) + k), where
// -n is the size of the BST rooted at root.
// -k is the number of Entrys in the BST rooted at root
// whose strings start with x.
void completions_recurse(string x, Node* root, vector<Entry> &T);
};
#endif
//END AUTOCOMPLETER.H
-----------------------------------------------
//AUTOCOMPLETER.CPP
#include "autocompleter.h"
// For the mandatory running times below:
// n is the number of strings in the dictionary.
// Assume that the length of every string is O(1).
// Creates a dictionary of strings and associated frequencies,
// using the file as a source. The file is promised to have
// the following format:
//
// string1 freq1
// string2 freq2
// ...
// stringN freqN
//
// where string1 < string2 < ... < stringN
//
// Must run in O(n) time.
Autocompleter::Autocompleter(string filename)
{
}
// Returns the number of strings in the dictionary
// of possible completions.
//
// Must run in O(n) time.
int Autocompleter::size()
{
return 0;
}
// Fills the vector T with the three most-frequent completions of x.
// If x has less than three completions,
// then T is filled with all completions of x.
// The completions appear in T from most- to least-frequent.
//
// Must run in O(log(n) + k) time,
// where k is the number of completions of x in the dictionary.
void Autocompleter::completions(string x, vector<string> &T)
{
}
// Returns the size of the binary tree rooted at root.
//
// Should run in O(n) time.
int Autocompleter::size_recurse(Node* root)
{
return 0;
}
// Fills T with the three most-frequent completions of x
// that are either:
// -In the BST rooted at root.
// -Already in T.
//
// Should run in O(log(n) + k), where
// -n is the size of the BST rooted at root.
// -k is the number of Entrys in the BST rooted at root
// whose strings start with x.
void Autocompleter::completions_recurse(string x, Node* root, vector<Entry> &T)
{
}
//END AUTOCOMPLETER.CPP
-----------------------------------------------
I need assistance implementing the functions in "AUTOCOMPLETER.CPP" so that my program prints "Assignment Complete."
1 Introduction 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 assigument is to implement autocomplete. Specifically, you wil 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 0 OK, let's chat this at G afte noon after 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 worl is more common (eg· "cluit" has frequency 1032 and quixotic has freqency 15, indicating that "qt is a more common word). The dictionary of words and their frequencies should be stored in a balanced binary search tree (see Figure 2) Noda* root 'crocodil e"-stringes-Entry alpaca 8523 52317 albatross canel" 110050 5531 45921 37393 "armadillo 3937 giraffe "goatfish"gorilla 19319 cat 6293 9795 199 Figure 2: A balanced BST containing the words and their frequencies in the provided file animals.txt. Notice that the set of words that start with a given string are always consecutive in sorted order. Said another way, they're all the words in a specific range (see Figure 3) 2 Instructions The following files have been given to you: 1. A C++header file (autocompleter.h) declaring the Autocompleter class. int treqEntry alpaca 8523 52317 al bat roca 5531 canel 110050 "crog 45921 37393 giraffe T85 goatfish 159 gorilla' 13319 6293 3937 Figure 3: The words starting with "a" (bluc), "cr" (yellow), and "go" (green) 2. A C source file (main.cpp) containing a main function with tests 3. A text file (animals.txt) containing 13 animals names and their frequencies in sorted order. . A text file (words.txt) containing 293147 common English words and their frequencies in sorted order.2Explanation / Answer
Code:-
autocompleter.h
#ifndef AUTOCOMPLETER_H
#define AUTOCOMPLETER_H
#include <vector>
#include <string>
#include <cassert>
#include <fstream>
using namespace std;
class Autocompleter
{
// For the mandatory running times below:
// n is the number of strings in the dictionary.
// Assume that the length of every string is O(1).
public:
// Creates a dictionary of strings and associated frequencies,
// using the file as a source. The file is promised to have
// the following format:
//
// string1 freq1
// string2 freq2
// ...
// stringN freqN
//
// where string1 < string2 < ... < stringN
//
// Must run in O(n) time.
Autocompleter(string filename);
// Returns the number of strings in the dictionary
// of possible completions.
//
// Must run in O(n) time.
int size();
// Fills the vector T with the three most-frequent completions of x.
// If x has less than three completions,
// then T is filled with all completions of x.
// The completions appear in T from most- to least-frequent.
//
// Must run in O(log(n) + k) time,
// where k is the number of completions of x in the dictionary.
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 BST 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; // Used in hwAC2 (not in hwAC1)
Node* left;
Node* right;
};
// Root of the binary-search-tree-based data structure
Node* root;
// Optional helper methods (you'll probably want them).
// Returns the root of a BST containing the elements
// of the portion of a sorted vector E from index l to r.
//
// Should run in O(r-l) time.
Node* construct_recurse(vector<Entry> &E, int l, int r);
// Returns the size of a binary tree rooted at root.
//
// Should run in O(n) time.
int size_recurse(Node* root);
// Fills T with the three most-frequent completions of x
// that are either:
// -In the BST rooted at root.
// -Already in T.
//
// Should run in O(log(n) + k), where
// -n is the size of the BST rooted at root.
// -k is the number of Entrys in the BST rooted at root
// whose strings start with x.
void completions_recurse(string x, Node* root, vector<Entry> &T);
};
#endif
autocompleter.cpp
#include "autocompleter.h"
#include <iostream>
using namespace std;
Autocompleter::Autocompleter(string filename)
{
ifstream files;
files.open(filename);
if(!files.is_open())
{
abort();
}
string inputs;
Entry jose;
vector<Entry> Entries;
while(!files.eof())
{
files>>jose.s;
files>>jose.freq;
if(files.eof())
break;
Entries.push_back(jose);
}
root=construct_recurse(Entries, 0, (int)Entries.size()-1);
}
int Autocompleter::size()
{
int size=0;
size=size_recurse(root);
return size;
}
void Autocompleter::completions(string x, vector<string> & T)
{
}
Autocompleter:: Node* Autocompleter:: construct_recurse(vector <Entry> & E, int l, int r)
{
if(l>r)
return nullptr;
Entry temp;
int m=(l+r)/2;
temp.s=E[m].s;
temp.s=E[m].freq;
Node * cur= new Node(temp);
cur->left=cur->right=nullptr;
root=cur;
root->left=construct_recurse(E,l,m-1);
root->right=construct_recurse(E,m+1,r);
return cur;
}
int Autocompleter:: size_recurse(Node * root)
{
if (root == nullptr)
return 0;
return size_recurse(root->left) + size_recurse(root->right) + 1;
}
main.cpp
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cassert>
#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("words.txt");
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()
{
// Uncomment line below to use your Autocompleter
// interactively with words.txt as the dictionary.
//
// Enter a string and press Enter - the autocompletions
// results from words.txt are printed.
//
//interactive_mode();
// Setup
vector<string> R;
// Test constructor and size()
Autocompleter animals("animals.txt");
cout<<animals.size()<<endl;
test(animals.size() == 13);
Autocompleter words("words.txt");
test(words.size() == 300000);
// 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() == 0);
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() == 0);
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("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("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] == "cat");
test(R[1] == "camel");
test(R[2] == "goat");
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");
animals.txt
aardvark 6293
albatross 5531
alpaca 8523
armadillo 3937
cat 468398
camel 110050
crocodile 16583
crow 45921
giraffe 9785
goat 52317
goatfish 199
goose 37393
gorilla 19319
cout << "Assignment complete." << endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.