Question: Create a trendtracker.cpp file that will make the program work with the given constraints. (trendtracker.h) #ifndef TRENDTRACKER_H #define TRENDTRACKER_H #include #include using namespace std; class

Create a trendtracker.cpp file that will make the program work with the given constraints.

(trendtracker.h)

#ifndef TRENDTRACKER_H

#define TRENDTRACKER_H

#include

using namespace std;

class Trendtracker

{

// For the mandatory running times below:

// n is the number of hashtags in the Trendtracker.

public:

// Creates a new empty collection of hashtags.

Trendtracker();

// Inserts a hashtag (tweeted 0 times) into the Trendtracker.

// If the hashtag already is in Trendtracker, does nothing.

// Must run in O(log(n)) time if the hashtag is already in

// the Trendtracker, and O(n) time otherwise.

void insert(string ht);

// Return the number of hashtags in the Trendtracker.

// Must run in O(1) time.

int size();

// Adds 1 to the total number times a hashtag has been tweeted.

// If the hashtag does not exist in TrendTracker, does nothing.

// Must run in O(log(n)) time.

void tweeted(string ht);

// Returns the number of times a hashtag has been tweeted.

// If the hashtag does not exist in Trendtracker, returns -1.

// Must run in O(log(n)) time.

int popularity(string name);

// Returns a most-tweeted hashtag.

// If the Trendtracker has no hashtags, returns "".

// Must run in O(1) time.

string top_trend();

// Fills the provided vector with the k most-tweeted hashtags,

// in order of most-tweeted-to-least-tweeted.

// If there are fewer than k hashtags, then the vector is filled

// with all hashtags (in most-tweeted-to-least-tweeted order).

// Must run in O(k) time.

void trending(int k, vector &T);

private:

// A simple class representing a hashtag and

// the number of times it has been tweeted.

class Entry

{

public:

string hashtag;

int pop;

};

// Optional helper method.

// Returns the index in S of the hashtag with the given name.

// I.e. the index i such that H[S[i]]->name == name.

// Should run in O(log(n)) time.

int S_index(string ht);

// Optional helper method to return the lowest index in P

// pointing to a hashtag with the specified number of tweets.

// Should run in O(log(n)) time.

int lowest_E_index_with_pop(int pop);

// Stores indices of Entries in E.

// Sorted lexicographically by hashtag (small-to-large).

vector S;

// Entries sorted by number of tweets (large-to-small).

vector E;

};

#endif

(main.cpp)

#include

#include "trendtracker.h"

using namespace std;

using namespace chrono;

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

int main()

{

// Setup

srand(2017);

vector R;

string s, line;

system_clock::time_point start, end;

float dur, adj;

// Test size() and insert().

Trendtracker T1;

test(T1.size() == 0);

test(T1.popularity("#algorithms") == -1);

test(T1.popularity("#cs4all") == -1);

test(T1.popularity("#programming") == -1);

T1.insert("#cs4all");

test(T1.size() == 1);

test(T1.popularity("#algorithms") == -1);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#programming") == -1);

T1.insert("#algorithms");

test(T1.size() == 2);

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#programming") == -1);

T1.insert("#programming");

test(T1.size() == 3);

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#programming") == 0);

T1.insert("#algorithms");

test(T1.size() == 3);

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#programming") == 0);

T1.tweeted("#programming");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#programming") == 1);

T1.tweeted("#programming");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#programming") == 2);

T1.tweeted("#programming");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#programming") == 3);

T1.tweeted("#cs4all");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 1);

test(T1.popularity("#programming") == 3);

T1.tweeted("#algorithms");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 1);

test(T1.popularity("#programming") == 3);

T1.tweeted("#cs4all");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#programming") == 3);

T1.tweeted("#datastructures");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 3);

T1.insert("#datastructures");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == 0);

test(T1.popularity("#programming") == 3);

T1.tweeted("#datastructures");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == 1);

test(T1.popularity("#programming") == 3);

T1.tweeted("#datastructures");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == 2);

test(T1.popularity("#programming") == 3);

T1.tweeted("#datastructures");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == 3);

test(T1.popularity("#programming") == 3);

T1.tweeted("#datastructures");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == 4);

test(T1.popularity("#programming") == 3);

Trendtracker T2;

T2.insert("#3333");

T2.insert("#programming");

T2.insert("#cs4all");

T2.insert("#C++");

T2.insert("#algorithms");

T2.tweeted("#programming");

T2.tweeted("#C++");

T2.tweeted("#cs4all");

T2.tweeted("#algorithms");

T2.tweeted("#3333");

test(T2.popularity("#programming") == 5);

test(T2.popularity("#cs4all") == 3);

test(T2.popularity("#algorithms") == 2);

test(T2.popularity("#C++") == 4);

test(T2.popularity("#3333") == 1);

T2.insert("#3333");

T2.insert("#programming");

T2.insert("#cs4all");

T2.insert("#C++");

T2.insert("#algorithms");

test(T2.popularity("#programming") == 5);

test(T2.popularity("#cs4all") == 3);

test(T2.popularity("#algorithms") == 2);

test(T2.popularity("#C++") == 4);

test(T2.popularity("#3333") == 1);

// Enforce no usage of global variables

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == 4);

test(T1.popularity("#programming") == 3);

Trendtracker T3;

test(T3.top_trend() == "");

T3.trending(1, R);

test(R.size() == 0);

T3.trending(2, R);

test(R.size() == 0);

T3.trending(3, R);

test(R.size() == 0);

T3.insert("#programming");

test(T3.top_trend() == "#programming");

T3.trending(1, R);

test(R.size() == 1);

test(R[0] == "#programming");

T3.trending(2, R);

test(R.size() == 1);

test(R[0] == "#programming");

T3.trending(3, R);

test(R.size() == 1);

test(R[0] == "#programming");

T3.tweeted("#programming");

test(T3.top_trend() == "#programming");

T3.trending(1, R);

test(R.size() == 1);

test(R[0] == "#programming");

T3.trending(2, R);

test(R.size() == 1);

test(R[0] == "#programming");

T3.trending(3, R);

test(R.size() == 1);

test(R[0] == "#programming");

T3.insert("#C++");

T3.tweeted("#C++");

test(T3.top_trend() == "#C++");

T3.trending(1, R);

test(R.size() == 1);

test(R[0] == "#C++");

T3.trending(2, R);

test(R.size() == 2);

test(R[0] == "#C++");

test(R[1] == "#programming");

T3.trending(3, R);

test(R.size() == 2);

test(R[0] == "#C++");

test(R[1] == "#programming");

T3.insert("#3333");

T3.tweeted("#3333");

test(T3.top_trend() == "#3333");

T3.trending(1, R);

test(R.size() == 1);

test(R[0] == "#3333");

T3.trending(2, R);

test(R.size() == 2);

test(R[0] == "#3333");

test(R[1] == "#C++");

T3.trending(3, R);

test(R.size() == 3);

test(R[0] == "#3333");

test(R[1] == "#C++");

test(R[2] == "#programming");

T3.insert("#cs4all");

T3.tweeted("#cs4all");

test(T3.top_trend() == "#cs4all");

T3.trending(1, R);

test(R.size() == 1);

test(R[0] == "#cs4all");

T3.trending(2, R);

test(R.size() == 2);

test(R[0] == "#cs4all");

test(R[1] == "#3333");

T3.trending(3, R);

test(R.size() == 3);

test(R[0] == "#cs4all");

test(R[1] == "#3333");

test(R[2] == "#C++");

// At this point:

// cs4all: 4

// 3333: 3

// C++: 2

// programming: 1

T3.tweeted("#programming");

test(T3.top_trend() == "#programming");

T3.trending(5, R);

test(R.size() == 4);

test(R[0] == "#programming");

test(R[1] == "#cs4all");

test(R[2] == "#3333");

test(R[3] == "#C++");

// At this point:

// programming: 5

// cs4all: 4

// 3333: 3

// C++: 2

T3.tweeted("#cs4all");

T3.tweeted("#3333");

test(T3.top_trend() == "#cs4all");

T3.trending(5, R);

test(R.size() == 4);

test(R[0] == "#cs4all");

test(R[1] == "#programming");

test(R[2] == "#3333");

test(R[3] == "#C++");

// At this point:

// cs4all: 6

// programming: 5

// 3333: 4

// C++: 2

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

T3.tweeted("#C++");

test(T3.top_trend() == "#C++");

T3.trending(5, R);

test(R.size() == 4);

test(R[0] == "#C++");

test(R[1] == "#cs4all");

test(R[2] == "#programming");

test(R[3] == "#3333");

// Efficiency tests

// Gather some data about running time to calibrate these:

start = system_clock::now();

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

if (system_clock::now().time_since_epoch().count() == 0)

cout << "";

end = system_clock::now();

adj = duration(end - start).count();

Trendtracker T4;

// Test insert() performance

ifstream f;

f.open("shaketags.txt");

assert(f.is_open()); // If this fails, you're missing shaketags.txt (should fail here)

start = system_clock::now();

while (getline(f, line))

T4.insert(line);

end = system_clock::now();

f.close();

test(T4.size() == 13831);

dur = duration(end - start).count();

test(dur < 1113 * adj);

// Test tweeted() performance

f.open("shaketags.txt");

start = system_clock::now();

while (getline(f, line))

T4.tweeted(line);

end = system_clock::now();

f.close();

dur = duration(end - start).count();

test(dur < 322 * adj);

test(T4.popularity("#hath") == 769);

test(T4.popularity("#doth") == 317);

test(T4.popularity("#whence") == 33);

test(T4.popularity("#hark") == 63);

// Test popularity() performance

f.open("shaketags.txt");

start = system_clock::now();

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

{

getline(f, line);

test(T4.popularity(line) > 0);

}

end = system_clock::now();

f.close();

dur = duration(end - start).count();

test(dur < 72 * adj);

// Test top_trend() performance.

start = system_clock::now();

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

test(T4.top_trend() == "#the");

end = system_clock::now();

dur = duration(end - start).count();

test(dur < 1 * adj);

// Test trending() performance.

start = system_clock::now();

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

T4.trending(10, R);

end = system_clock::now();

dur = duration(end - start).count();

test(dur < 16 * adj);

test(R[0] == "#the");

test(R[5] == "#a");

test(R[9] == "#in");

start = system_clock::now();

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

T4.trending(100000, R);

end = system_clock::now();

dur = duration(end - start).count();

test(dur < 25 * adj);

test(R[28] == "#thou");

test(R[34] == "#are");

test(R[39] == "#good");

cout << "Assignment complete." << endl;

}

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

//trendtracker.h #ifndef TRENDTRACKER_H #define TRENDTRACKER_H #include #include using namespace std; class Trendtracker { public: Trendtracker(); void insert(string ht); int size(); void...

//trendtracker.cpp // Fills the provided vector with the k most-tweeted hashtags, // in order from most-tweeted to least-tweeted. // // If there are fewer than k hashtags, then the vector is filled...

intLinkedList.h #ifndef H_intLinkedList #define H_intLinkedList #include "unorderedLinkedList.h" using namespace std; class intLinkedList: public unorderedLinkedList { public: // part a void...

For C++, please assist. Also, can you include a screenshot of code working and label the codes so I can easily understand? I am unsure what I am doing wrong when doing it with the test file included...

Hello, can I get some help with my code? I don't know why it does not work. This is my code: linkedList.h #ifndef LINKEDLIST_H #define LINKEDLIST_H #include #include using namespace std; //Definition...

c++ Note: I have included the codes I used previously. Please assist with labeling each code please. Codes used below bankAccount .cpp #include "bankAccount.h" //bankAccount::bankAccount() //{ //}...

USE C++ Polymorphism and Exceptions For this lab we will continue working with the shapes developed for Lab 6. (4 pts) Implementing Polymorphism Use the classes from Lab 6 (Shape, Rectangle, Circle,...

C++ linked list So after hours of tryng and tryng cant find what is wrong with my remove function, whenever I remove a node and try to print back the list the program crashes by telling me :...

Suppose the supply of housing construction is infinitely elastic at a price of $150 per square foot. Currently 1 million square feet are built per month. If the price elasticity of demand for housing...

Find the ABCD parameters for the circuit in figure.

AS 2 1 1 0 provides guidance regarding the auditor s responsibilities to understand management s application of accounting principles and related disclosures. Read through AS 2 1 1 0 ( you can find...

Now assume the date is October 2 5 , 2 0 2 0 . Assume further that a 1 0 % , 1 5 - year bond was issued on July 1 , 2 0 2 0 , pays interest semiannually ( on January 1 and July 1 ) , and sells for $...

(Appendices) International Studies Using the Internet, compare the value of the dollar to the value of worldwide currencies. Find the value of the Japanese yen, British pound, Chinese yuan, Euro,...

(Appendices) Economics Select a country with an economic system that is considered communist or socialist. Conduct online research about quality of life, life expectancy rates, tax rates, income and...

(Appendices) Explain how the Federal Reserve Bank affects the money supply in the United States. How do the Feds actions, including setting reserve requirements and controlling discount rates, speed...