TRENDTRACKER.H #include <vector> #include <string> using namespace std; class Tr
ID: 3743867 • Letter: T
Question
TRENDTRACKER.H
#include <vector>
#include <string>
using namespace std;
class Trendtracker
{
// For the mandatory running times below:
// n is the number of hashtags in the Trendtracker.
public:
// Creates a new Trendtracker tracking no hashtags.
//
// Must run in O(1) time.
Trendtracker();
// Inserts a hashtag (tweeted 0 times) into the Trendtracker.
// If the hashtag already is in Trendtracker, does nothing.
//
// Must run in O(n) time.
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(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(n) time.
int popularity(string name);
// Returns a most-tweeted hashtag.
// If the Trendtracker has no hashtags, returns "".
//
// Must run in O(n) time.
string top_trend();
// Fills the provided vector with the 3 most-tweeted hashtags,
// in order from most-tweeted to least-tweeted.
//
// If there are fewer than 3 hashtags, then the vector is filled
// with all hashtags (in most-tweeted to least-tweeted order).
//
// Must run in O(n) time.
void top_three_trends(vector<string> &T);
private:
// A simple class representing a hashtag and
// the number of times it has been tweeted.
class Entry
{
public:
string hashtag;
int pop;
};
// Entries containing each hashtag and its popularity.
vector<Entry> E;
};
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
MAIN.CPP
#include <cassert>
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <string>
#include "trendtracker.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__))
int main()
{
// Setup
vector<string> 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.top_three_trends(R);
test(R.size() == 0);
T3.insert("#programming");
test(T3.top_trend() == "#programming");
T3.top_three_trends(R);
test(R.size() == 1);
test(R[0] == "#programming");
T3.tweeted("#programming");
test(T3.top_trend() == "#programming");
T3.top_three_trends(R);
test(R.size() == 1);
test(R[0] == "#programming");
// At this point:
// programming: 1
T3.insert("#C++");
T3.tweeted("#C++");
T3.tweeted("#C++");
test(T3.top_trend() == "#C++");
T3.top_three_trends(R);
test(R.size() == 2);
test(R[0] == "#C++");
test(R[1] == "#programming");
// At this point:
// C++: 2
// programming: 1
T3.insert("#3333");
T3.tweeted("#3333");
T3.tweeted("#3333");
T3.tweeted("#3333");
test(T3.top_trend() == "#3333");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#3333");
test(R[1] == "#C++");
test(R[2] == "#programming");
// At this point:
// 3333: 3
// C++: 2
// programming: 1
T3.insert("#cs4all");
T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
test(T3.top_trend() == "#cs4all");
T3.top_three_trends(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.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#programming");
test(R[1] == "#cs4all");
test(R[2] == "#3333");
// 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.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#cs4all");
test(R[1] == "#programming");
test(R[2] == "#3333");
// 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.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#C++");
test(R[1] == "#cs4all");
test(R[2] == "#programming");
Trendtracker T4;
ifstream f;
f.open("common.txt");
assert(f.is_open()); // If this fails, you're missing common.txt
while (getline(f, line))
T4.insert(line);
f.close();
test(T4.size() == 3597);
f.open("common.txt");
while (getline(f, line))
T4.tweeted(line);
f.close();
for (int i = 0; i < 1000; ++i)
{
test(T4.popularity("#finishing") == 6);
test(T4.popularity("#completely") == 5);
test(T4.popularity("#is") == 4);
test(T4.popularity("#sometimes") == 3);
test(T4.popularity("#quieting") == 2);
test(T4.top_trend() == "#finishing");
T4.top_three_trends(R);
test(R[0] == "#finishing");
test(R[1] == "#completely");
test(R[2] == "#is");
}
cout << "Assignment complete." << endl;
}
I need help implementing the last function top_three_trends(vector<string> &T), such that my program prints "Assignment Complete."
// Fills the provided vector with the 3 most-tweeted hashtags,
// in order from most-tweeted to least-tweeted.
//
// If there are fewer than 3 hashtags, then the vector is filled
// with all hashtags (in most-tweeted to least-tweeted order).
//
// Must run in O(n) time.
void top_three_trends(vector<string> &T);
Explanation / Answer
ANS:
Trendtracker.cpp:
// Define a class
#include "trendtracker.h"
// Define a new empty Collection of Hashtags.
Trendtracker::Trendtracker()
{
}
// Define a method to inserting
void Trendtracker::insert(string str)
{
// use looping
for(vector<Entry>::iterator Itr = E.begin(); Itr != E.end(); Itr++)
{
// check
if(Itr->hashtag == str)
return;
}
// create an object
Entry en;
// assinging string
een.hashtag = str;
en.pop = 0;
E.push_back(en);
}
// Define a method to get size
int Trendtracker::size()
{
return E.size();
}
// Define a method to tweeted
void Trendtracker::tweeted(string str)
{
// use loop
for(vector<Entry>::iterator Itr = E.begin(); Itr != E.end(); Itr++)
{
// check
if(Itr->hashtag == str)
{
Itr->pop++;
return;
}
}
}
// Define a method for popularity in tweeted
int Trendtracker::popularity(string nam)
{
// use looping
for(vector<Entry>::iterator Itr = E.begin(); Itr != E.end(); Itr++)
{
if(Itr->hashtag == nam)
return Itr->pop;
}
// return value
return -1;
}
// Define a method to get top trend
string Trendtracker::Trends()
{
// Declare and initialize variables
int MAXpopular = 0;
string str;
for(vector<Entry>::iterator itr = E.begin(); itr != E.end(); itr++)
{
if(itr->pop >=MAXpopular)
{
// assign the value
str = itr->hashtag;
MAXpopular = itr->pop;
}
}
// returns
return str;
}
// Define a method for trending
void Trendtracker::trending(int x, vector<string> &Vec)
{
vector<Entry> tp;
T.clear();
for(int i = 0; i < E.size(); i++)
{
bool store = false;
for(vector<Entry>::iterator itr = tp.begin(); itr != tp.end(); itr++)
{
if(E[i].pop > itr->pop)
{
tp.insert(itr, E[i]);
store = true;
if(tp.size() > x)
tp.pop_back();
break;
}
}
if(!store)
tp.push_back(E[i]);
}
for(int i = 0; i < tp.size(); i++)
Vec.push_back(tp[i].hashtag);
}
THANK YOU
OR
CODE:
Given below is the trendtracker.cpp file. While testing, I found that main.cpp needs common.txt which is not provided by you in the question. So all tests passed upto line 320 in main where it looks for the common.txt. Please place that file and test the program.
Hope it was helpful.
trendtracker.cpp
#include "trendtracker.h"
// Creates a new empty collection of hashtags.
Trendtracker::Trendtracker()
{
}
// Inserts a hashtag (tweeted 0 times) into the Trendtracker.
// If the hashtag already is in Trendtracker, does nothing.
//
// Must run in O(n) time.
void Trendtracker::insert(string ht)
{
for(vector<Entry>::iterator it = E.begin(); it != E.end(); it++)
{
if(it->hashtag == ht) //existing one
return;
}
Entry e1;
e1.hashtag = ht;
e1.pop = 0;
E.push_back(e1);
}
// Return the number of hashtags in the Trendtracker.
//
// Must run in O(1) time.
int Trendtracker::size()
{
return E.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(n) time.
void Trendtracker::tweeted(string ht)
{
for(vector<Entry>::iterator it = E.begin(); it != E.end(); it++)
{
if(it->hashtag == ht) //exists
{
it->pop++;
return;
}
}
}
// Returns the number of times a hashtag has been tweeted.
// If the hashtag does not exist in Trendtracker, returns -1.
//
// Must run in O(n) time.
int Trendtracker::popularity(string name)
{
for(vector<Entry>::iterator it = E.begin(); it != E.end(); it++)
{
if(it->hashtag == name) //exists
return it->pop;
}
//does not exist
return -1;
}
// Returns a most-tweeted hashtag.
// If the Trendtracker has no hashtags, returns "".
//
// Must run in O(n) time.
string Trendtracker::top_trend()
{
int maxPop = 0;
string ht;
for(vector<Entry>::iterator it = E.begin(); it != E.end(); it++)
{
if(it->pop >= maxPop)
{
ht = it->hashtag;
maxPop = it->pop;
}
}
return ht;
}
// 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(nk) time.
void Trendtracker::trending(int k, vector<string> &T)
{
vector<Entry> temp;
T.clear();
//keep k elements in descending order of popularity in temp. then copy over the hash tags to T
for(int i = 0; i < E.size(); i++)
{
bool inserted = false;
for(vector<Entry>::iterator it = temp.begin(); it != temp.end(); it++)
{
if(E[i].pop > it->pop)
{
temp.insert(it, E[i]);
inserted = true;
if(temp.size() > k)
temp.pop_back();
break;
}
}
if(!inserted)
temp.push_back(E[i]);
}
for(int i = 0; i < temp.size(); i++)
T.push_back(temp[i].hashtag);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.