Answered step by step
Verified Expert Solution
Question
1 Approved Answer
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started