Create a new C++ source file named autocompleter.cpp that implements the class d
ID: 3756704 • 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.
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//autocompleter.h
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//main.cpp
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//animals.txt
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//words.txt (full text file can be accesed at http://andrewwinslow.com/3333/hwAC1/words.txt)
Explanation / Answer
1) We need to 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.
2) Here's the code for autocompleter.h
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()
{
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
3) Here's the code for Main.cpp
CODE:
//main.cpp
#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
4) And the provided text files are:
//animals.txt
aardvark 629356
albatross 553191
alpaca 852363
armadillo 393754
cat 46839855
camel 11005001
crocodile 1658300
crow 4592109
giraffe 978584
goat 5231735
goatfish 19984
goose 3739382
gorilla 1931906
//words.txt (full text file can be accesed at http://andrewwinslow.com/3333/hwAC1/words.txt)
a 908117
aa 3052
aaa 1024
aaaa 159
aaaah 5
aaaai 3
aaaargh 1
aaab 2
aaabooksearch 2
aaac 3
aaace 6
aaacn 16
aaae 5
aaah 14
aaahh 2
aaahhh 2
aaai 25
aaal 2
aaalac 1
aaand 2
aaap 1
aaargh 4
aaas 41
aaasc 2
aaat 1
aab 33
aaba 4
aabb 9
aabbccdd 5
aabc 3
aaberg 1
aabt 2
aac 250
aaca 6
aacap 2
aacc 23
aacd 1
aace 11
aach 1
aachen 75
aaci 1
aacn 7
aacp 4
aacplus 2
aacr 6
aacraid 3
aacrao 2
aacs 12
aacsb 13
aact 2
aacte 1
aacute 8
aad 38
aada 1
aadac 2
aadc 4
aadd 3
aade 3
aadl 2
aads 2
aadt 6
aadult 2
aadvantage 18
aae 17
aaea 3
aaec 3
aaem 2
aaene 4
aaeon 8
aaep 1
aaf 31
aafa 2
aafc 10
aafco 2
aafes 8
aafp 17
aag 47
aagaard 4
aagard 1
aage 5
aah 33
aaha 2
aahe 3
aahh 2
aahhh 1
aahperd 2
aahs 2
aahsa 3
aahz 4
aai 28
aaia 2
aaid 7
aais 2
aaj 41
aaja 4
aajtk 3
aak 8
aakash 2
aaker 3
aakers 2
aakp 1
aal 31
aala 1
aaland 1
aalas 1
aalbc 1
aalborg 40
aalen 3
aalesund 2
aalib 10
aaliyah 333
aall 17
aallpaper 2
aalpd 3
aals 4
aalsmeer 2
aalst 9
aalto 14
aaltonen 2
aam 25
aama 8
aaman 1
aamas 3
aamc 11
aamco 10
aamer 3
aames 8
aamft 2
aami 10
aamir 14
aamodt 3
aamr 2
aams 2
aamt 2
aamu 2
aamva 2
aan 152
aana 4
aanbevolen 2
aanbieding 3
aanbiedingen 10
aanbod 4
aand 10
aangeboden 2
aankondigingen 2
aanmaken 1
aanmelden 8
aanndd 11
aanr 1
aans 6
aantal 21
aanvraag 1
aanvragen 3
aanwezig 4
aao 22
aaohn 2
aaoms 1
aaos 6
aap 105
aapa 6
aapc 3
aapd 4
aapeli 5
aapg 12
aapi 4
aapl 22
aapm 7
aapne 1
aapno 2
aapp 2
aaps 18
aapt 11
aaq 2
aar 62
aaraa 6
aarau 5
aarc 7
aardal 1
aarde 3
aardema 2
aardman 5
aards 2
aardvark 62
aardvarks 3
aardwolf 2
aare 7
aarez 2
aargau 5
aargh 7
aargon 1
aarhus 59
aarm 1
aarne 1
aarnet 4
aarnio 5
aaro 2
aaron 1169
aaronic 2
aaronovitch 3
aarons 23
aaronsburg 2
aaronson 9
aaronsw 8
aaronswatches 3
aarp 150
aars 4
aarschot 2
aart 7
aarti 6
aarts 3
aas 131
aasa 7
aasb 20
aasc 2
aasd 4
aase 3
aasen 1
aashiq 1
aashish 1
aashto 33
aasia 2
aasis 1
aasl 4
aasld 1
aasp 4
aast 1
aastra 9
aastrom 1
aasu 4
aat 64
aata 4
aatc 1
aatcc 2
aatf 2
aatg 1
aatomik 1
aaton 1
aatsr 1
aatt 3
aau 39
aaup 15
aaus 2
aauw 11
aav 14
aavan 2
aave 1
aavers 2
aavid 1
aavso 23
aaw 6
aax 5
aaxx 3
aay 2
aaya 2
aayla 2
aaz 2
aazak 2
ab 2421
aba 272
abaa 5
abab 3
ababa 51
abac 8
abaca 7
abacavir 10
abacha 9
aback 27
abaco 22
abacos 2
abacre 3
abacus 101
abacuslaw 20
abad 19
abadan 3
abaddon 7
abadi 10
abadia 1
abadie 2
abadon 3
abaft 1
abag 5
abagail 1
abagnale 3
abair 3
abaixo 4
abajo 11
abakan 1
abakus 6
abalone 51
abalos 1
abalou 13
abamectin 1
aban 5
abana 2
abandon 274
abandoned 637
abandoning 77
abandonment 129
abandonments 1
abandons 32
abandonware 22
5) Now we need to Create a new C++ source file named autocompleter.cpp that implements the class declared in autocompleter.h
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
int main()
{
std::vector<std::string> dict;
std::vector<std::string>::iterator it;
std::ifstream inf;
std::string temp, word, sentence;
bool done = false;
char input;
inf.open("dict.txt");
while(!inf.eof())
{
inf >> word;
dict.push_back(word);
}
temp = "";
word = "";
sentence = "";
std::cout << "Press 1 to accept autocomplete word " <<
"Press 2 to accept current word " << std::endl;
while(!done)
{
std::cin >> input;
if(input == '1')
{
sentence += temp + ' ';
word = "";
std::cout << sentence << std::endl;
}
else if(input == '2')
{
sentence += word + ' ';
word = "";
std::cout << sentence << std::endl;
}
else if(input != '0')
{
word += input;
for(it = dict.begin(); it != dict.end(); ++it)
{
if(word == (*it).substr(0, word.length()))
{
std::cout << (*it) << std::endl;
temp = (*it);
break;
}
}
}
else
done = true;
}
std::cout << sentence << std::endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.