Question: Create a new C++ source file named trendtracker.cpp that implements the Trendtracker class, so that trendtracker.cpp and the provided files compile into a program that
Create a new C++ source file named trendtracker.cpp that implements the Trendtracker class, so that trendtracker.cpp and the provided files compile into a program that runs with no failed tests. You cannot add any more functions outside of the methods in the trendtracker.h file.Submit the source file "trendtracker.cpp".
(trendtracker.h):
#ifndef TRENDTRACKER_H #define TRENDTRACKER_H #include#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 E // containing an Entry with the specified pop. // // 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 #include #include #include #include "trendtracker.h" using namespace std; inline void _test(const char* expression, const char* file, int line) { cerr R; string s, line; // 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("#programming"); T2.tweeted("#programming"); T2.tweeted("#programming"); T2.tweeted("#programming"); T2.tweeted("#C++"); T2.tweeted("#C++"); T2.tweeted("#C++"); T2.tweeted("#C++"); T2.tweeted("#cs4all"); T2.tweeted("#cs4all"); T2.tweeted("#cs4all"); T2.tweeted("#algorithms"); 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++"); 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"); T3.tweeted("#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"); T3.tweeted("#cs4all"); T3.tweeted("#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"); T3.tweeted("#programming"); T3.tweeted("#programming"); 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("#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 (shaketags.txt): http://andrewwinslow.com/3333/hwTT2/shaketags.txt
In the previous homework, you implemented a data structure that tracks information about a collection of hashtags, including which are trending. The efficiency of the data structure's operations (tweeted, popularity, trending, etc.) was poor. For tracking a few thousand hashtags, this was good enough, but Twitter has hundreds of mlions of users using millions of distinct hashtags.2 So for this homework you will implement the same class, but using an efficient two-vector-based data structure (see Figure 1). vector
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
Study Help