HELP!! IMPLEMENT A BINARY SEARCH TREE TO ELIMINATE THE WEAKNESS OF SLOW ADDITION
ID: 3720718 • Letter: H
Question
HELP!! IMPLEMENT A BINARY SEARCH TREE TO ELIMINATE THE WEAKNESS OF SLOW ADDITION OF WORDS TO THE AUTOCOMPLETER.
In this assginment, you’ll eliminate the weakness of an autocompleter: a long “load time” due to slow addition of words to the Autocompleter. Instead of add taking ?(n) worst-case time, you should aim for ?(log n) time. All other methods should retain their current speeds. To acheive 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
code:
Autocompleter.h
#ifndef AUTOCOMPLETER_H
#define AUTOCOMPLETER_H
#include <string>
using namespace std;
class Autocompleter
{
public:
Autocompleter();
void add(string x);
int completion_count(string x);
int size();
int binary_search_method(string x);
void completions(string x, string* suggestions);
private:
int index_of(string x, string* A, int len);
string* A;
int count;
int capacity;
};
#endif
Autocompleter.cpp:
#include<iostream>
#include<string>
#include<algorithm>
#include"Autocompleter.h"
Autocompleter::Autocompleter()
{
count=0;
capacity=10000;
A=new string[100];
}
int Autocompleter::binary_search_method(string x)
{
int l=0,h=count-1;
int mid;
while(l<h)
{
mid=(l+h)/2;
if(x.compare(A[mid])==0)
return mid;
if(x.compare(A[mid])<0)
h=mid-1;
else
l=mid+1;
}
return -1;
}
//Method to add
void Autocompleter::add(string x)
{
if (binary_search_method(x)==-1)
{
A[count]=x;
cout<<A[count];
sort(A,A+count);
count++;
}
}
//Method to count the completion
int Autocompleter::completion_count(string x)
{
int index=index_of(x,A,count);
int count=0;
for(int i=index;A[i].find(x)==0;i++)
count++;
return count;
}
//method to define index
int Autocompleter::index_of(string x, string A[], int len)
{
int l=0,h=len-1;
int mid;
size_t found;
while(l<h)
{
mid=(l+h)/2;
if((A[mid].find(x)==0) && (A[mid-1].find(x)!=0))
return mid;
if(A[mid].at(0)>=x.at(0))
h=mid-1;
else
l=mid=1;
}
return -1;
}
//method to return the size
int Autocompleter::size()
{
return count;
}
//method to define completitions
void Autocompleter::completions(string x, string* suggestions)
{
int index=index_of(x,A,count);
int j=0;
for(int i=index;A[i].find(x)==0;i++)
suggestions[j++]=A[i];
while(j<4)
{
suggestions[j++]="";
}
}
Main.cpp:
#include <iostream>
#include <fstream>
#include <cassert>
#include <string>
#include <ctime>
#include "autocompleter.h"
using namespace std;
inline void _test(const char* expression, const char* file, int line)
{
cerr << "test(" << expression << ") failed in file " << file << ", line " << line << "."<< endl;
abort();
}
#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))
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_10000.txt", ios::in);
assert(f.is_open()); // If this fails, you're missing above file
string line;
while (getline(f, line))
dictionary.add(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 10000 most common words are printed.
//
//interactive_mode();
// Test a small Autocompleter with animal names
Autocompleter animals;
test(animals.size() == 0);
cout << "5% earned." << endl;
animals.add("aardvark");
cout<<endl;
animals.add("albatross");
cout<<endl;
animals.add("alpaca");
cout<<endl;
animals.add("armadillo");
cout<<endl;
animals.add("camel");
cout<<endl;
animals.add("cat");
cout<<endl;
animals.add("crocodile");
cout<<endl;
animals.add("crow");
cout<<endl;
animals.add("giraffe");
cout<<endl;
animals.add("goat");
cout<<endl;
animals.add("goose");
cout<<endl;
animals.add("gorilla");
cout<<endl;
test(animals.size() == 12);
cout << "10% earned." << endl;
animals.add("gorilla"); // Already in the Autocompleter
test(animals.size() == 12);
cout << "15% earned." << endl;
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);
cout << "25% earned." << endl;
test(animals.completion_count("") == 12);
cout << "30% earned." << endl;
test(animals.completion_count("an") == 0);
test(animals.completion_count("q") == 0);
test(animals.completion_count("goat-billed carp") == 0);
cout << "35% earned." << endl;
// Create an autocompleter of the 10000 most common
// American English words and test for correctness.
Autocompleter dictionary;
// Fill autocompleter with words
ifstream f;
f.open("words_10000.txt", ios::in);
assert(f.is_open()); // If this fails, you're missing above file
string line;
while (getline(f, line))
dictionary.add(line);
f.close();
test(dictionary.size() == 9990); // There are some duplicates
test(dictionary.completion_count("bir") == 5);
test(dictionary.completion_count("hap") == 6);
test(dictionary.completion_count("program") == 7);
test(dictionary.completion_count("foo") == 8);
cout << "40% earned." << endl;
// 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] == "");
cout << "45% earned." << endl;
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] == "");
cout << "50% earned." << endl;
animals.completions("goat-billed carp", results);
test(results[0] == "");
test(results[1] == "");
test(results[2] == "");
test(results[3] == "");
test(results[4] == "");
cout << "55% earned." << endl;
// Test completions() on dictionary Autocompleter already made.
dictionary.completions("bir", results);
test(results[0] == "bird");
test(results[1] == "birds");
test(results[2] == "birmingham");
test(results[3] == "birth");
test(results[4] == "birthday");
dictionary.completions("hap", results);
test(results[0] == "happen");
test(results[1] == "happened");
test(results[2] == "happening");
test(results[3] == "happens");
test(results[4] == "happiness");
dictionary.completions("program", results);
test(results[0] == "program");
test(results[1] == "programme");
test(results[2] == "programmer");
test(results[3] == "programmers");
test(results[4] == "programmes");
dictionary.completions("foo", results);
test(results[0] == "foo");
test(results[1] == "food");
test(results[2] == "foods");
test(results[3] == "fool");
test(results[4] == "foot");
cout << "85% earned." << endl;
// Test Autocompleter for completing 100000 words
clock_t start = clock();
for (int i = 0; i < 100000; ++i)
dictionary.completions(random_string(5), results);
clock_t end = clock();
float duration = static_cast<float>(end - start) / CLOCKS_PER_SEC;
// If your completions() implementation is using binary-search,
// all other tests pass, and this test is still failing, talk to Andrew.
test(duration < 5.0);
cout << "100% earned." << endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.