please help me fix my autocompleter.cpp that implments the methods as specified from the provided autocompleter.h

THIS IS USING A TRIE DATA STRUCTURE

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//autocompleter.cpp

#include "autocompleter.h"

#include

#include

using namespace std;

// Creates a new Autocompleter with an empty dictionary.

//

// Must run in O(1) time.

Autocompleter::Autocompleter()

{

root = nullptr;

}

// Adds a string x to the dictionary.

// If x is already in the dictionary, does nothing.

//

// Must run in O(1) time.

void Autocompleter::insert(string x, int freq)

{

int i = 0;

string longest;

Node * cur = root;

while (i < x.length())

{

//update length of longest word in node's subtree

if (x.length() > cur->longest.length())

cur->longest = x;

//create node if path not already in Trie

if (cur->children[x[i]] == nullptr)

cur->children[x[i]] = new Node();

//move pointer down proper path

cur = cur->children[x[i]];

i++;

}

//update length of longest word in node's subtree

if (x.length() > cur->longest.length())

cur->longest = x;

//set marked to true to add s to Trie

if (cur->marked == false)

cur->marked = true;

}

// Returns the number of strings in the dictionary.

//

// Must run in O(1) time.

int Autocompleter::size()

{

if (p == nullptr)

{

return 0;

}

else

{

int total = 0;

//count node P if it's marked

if (p->marked)

total++;

//add in words for all subtrees

for (int i = 0; i < 256; i++)

{

total += size(p->children[i]);

}

return total;

}

}

// 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(1) time.

void Autocompleter::completions(string x, vector &T)

{

T.clear();

vector R;

//completions_recurse(x, root, R);

int num1 = 0;

int num2 = 0;

int num3 = 0;

string w1;

string w2;

string w3;

for (int i = 0; i < R.size(); i++)

{

if (R[i].freq >= num1)

{

num3 = num2;

num2 = num1;

num1 = R[i].freq;

w3 = w2;

w2 = w1;

w1 = R[i].s;

}

else if (R[i].freq >= num2)

{

num3 = num2;

num2 = R[i].freq;

w3 = w2;

w2 = R[i].s;

}

else if (R[i].freq >= num3)

{

num3 = R[i].freq;

w3 = R[i].s;

}

}

if (num1 == 0)

{

return;

}

if (num2 == 0)

{

T.push_back(w1);

return;

}

if (num3 == 0)

{

T.push_back(w1);

T.push_back(w2);

return;

}

T.push_back(w1);

T.push_back(w2);

T.push_back(w3);

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//autocompleter.h

#ifndef AUTOCOMPLETER_H

#define AUTOCOMPLETER_H

#include

#include

using namespace std;

class Autocompleter

{

// For the mandatory running times below:

// Assume that the length of every string is O(1).

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(1) time.

void insert(string x, int freq);

// Returns the number of strings in the dictionary.

//

// Must run in O(1) 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(1) time.

void completions(string x, vector &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 trie node.

class Node

{

public:

Node()

{

this->marked = false;

for (int i = 0; i < 256; ++i)

children[i] = nullptr;

}

bool marked;

vector top;

Node* children[256];

};

// Root of the trie-based data structure

Node* root;

// Number of marked nodes in the trie-based data structure

int count;

};

#endif

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//main.cpp

#include

#include

#include

#include

#include

#include

#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_last_of(" ")),

stoi(line.substr(line.find_last_of(" ")+1)));

++i;

}

f.close();

assert(i == 300000); // If this fails, words2.txt is wrong

vector 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 words2.txt as the dictionary.

//

// Enter a string and press Enter - the autocompletions

// results from words.txt are printed.

//

//interactive_mode();

// Setup

vector 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_last_of(" ")),

stoi(line.substr(line.find_last_of(" ")+1)));

}

f.close();

test(words.size() == 300000);

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);

// Test insert() and size()

for (int i = 0; i < 100000; ++i)

{

// 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;

}