C++, Need helping finishing up my code. Feel free to make any changes you think
ID: 3742163 • Letter: C
Question
C++, Need helping finishing up my code. Feel free to make any changes you think are necessary. I was given the main.cpp file and trendtracker.h file. The assignment was to create a trendtracker.cpp file with the trendtracker.h completed functions to have the main.cpp file print to the screen "Assignment Complete." Thanks!
/************************************* 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;
}
/*************************** trendtracker.h **************************************************/
#ifndef TRENDTRACKER_H
#define 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;
};
#endif
/********************************* trendtracker.cpp *************************************/
#include "trendtracker.h"
#include <iostream>
using namespace std;
/*************************************************************/
Trendtracker::Trendtracker()
{
}
/*************************************************************/
// Inserts a hashtag (tweeted 0 times) into the Trendtracker.
// If the hashtag already is in Trendtracker, does nothing.
void Trendtracker::insert(string ht)
{
Entry trend;
int n = E.size();
trend.hashtag = ht;
trend.pop = 0;
for (int i = 0; i < n; i++)
{
if (ht == E[i].hashtag)
{
break;
}
else
{
E.push_back(trend);
}
}
}
/*************************************************************/
// Adds 1 to the total number times a hashtag has been tweeted.
// If the hashtag does not exist in TrendTracker, does nothing.
int Trendtracker::size()
{
int n = E.size();
return n;
}
/*************************************************************/
// Inserts a hashtag (tweeted 0 times) into the Trendtracker.
// If the hashtag already is in Trendtracker, does nothing.
void Trendtracker::tweeted(string ht)
{
Entry trend;
trend.hashtag = ht;
int n = E.size();
for (int i = 0; i < n; i++)
{
if (ht == E[i].hashtag)
{
E[i].pop++;
}
}
}
/*************************************************************/
// Returns the number of times a hashtag has been tweeted.
// If the hashtag does not exist in Trendtracker, returns -1.
int Trendtracker::popularity(string name)
{
int i = 0;
int n = E.size();
bool check = 0;
for (i = 0; i < n; i++)
{
if (name == E[i].hashtag)
{
check = 1;
break;
}
}
if (check == 1)
{
return E[i].pop;
}
else
{
return -1;
}
}
/*************************************************************/
// Returns a most-tweeted hashtag.
// If the Trendtracker has no hashtags, returns "".
string Trendtracker::top_trend()
{
int i = 0;
int n = E.size();
int poped = -1;
string Most_Popular;
//loops through Trendtracker checking for the hashtag with most tweets
for (i = 0; i < n; i++)
{
if (E[i].pop > poped)
{
poped = E[i].pop;
Most_Popular = E[i].hashtag;
}
}
return Most_Popular;
}
/*************************************************************/
// 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).
void Trendtracker::top_three_trends(vector<string> &T)
{
int n = E.size();
int i, j;
Entry key;
vector temp = E;
for (i = 1; i < n; i++)
{
key = temp[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && popularity(temp[j].hashtag) > popularity(key.hashtag))
{
temp[j+1] = temp[j];
j = j-1;
}
temp[j+1] = key;
}
if(n >= 3) {
for (int l = 0; l < 3; l++) {
T.push_back(temp[l]);
}
} else {
for (int l = 0; l < n; l++) {
T.push_back(temp[l]);
}
}
}
Explanation / Answer
Here is the solutiom. I've done some modifications in the functions and made it more efficient. And it works for all the test cases provided. However you've not included a testcase input file for the extended set of testcases ("common.txt"). Do include the file while you're testing. It should work. Tell me if it doesn't.
/************************************* 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;
}
/********************************* trendtracker.cpp *************************************/
#include "trendtracker.h"
#include <iostream>
using namespace std;
/*************************************************************/
Trendtracker::Trendtracker() {
}
/*************************************************************/
// Inserts a hashtag (tweeted 0 times) into the Trendtracker.
// If the hashtag already is in Trendtracker, does nothing.
void Trendtracker::insert(string ht)
{
Entry trend;
int i, n = E.size();
trend.hashtag = ht;
trend.pop = 0;
for (i = 0; i < n; i++) {
if (ht == E[i].hashtag) {
break;
}
}
if(i == n)
E.push_back(trend);
//Push the element only if i is equal to n, that is there was no instance of the hastag to be inserted
}
/*************************************************************/
// Return the number of hashtags in the Trendtracker.
int Trendtracker::size() {
return E.size();
}
/*************************************************************/
// Inserts a hashtag (tweeted 0 times) into the Trendtracker.
// If the hashtag already is in Trendtracker, does nothing.
void Trendtracker::tweeted(string ht) {
int n = E.size();
for (int i = 0; i < n; i++) {
if (ht == E[i].hashtag) {
E[i].pop++;
break;
// Breaks if required match found
}
}
}
/*************************************************************/
// Returns the number of times a hashtag has been tweeted.
// If the hashtag does not exist in Trendtracker, returns -1.
int Trendtracker::popularity(string name)
{
int i = 0;
int n = E.size();
bool check = 0;
for (i = 0; i < n; i++) {
if (name == E[i].hashtag) {
check = 1;
break;
}
}
if (check == 1) {
return E[i].pop;
}
else {
return -1;
}
}
/*************************************************************/
// Returns a most-tweeted hashtag.
// If the Trendtracker has no hashtags, returns "".
string Trendtracker::top_trend()
{
if(size() == 0)
return "";
//return an empty string if empty
int i, n, popular;
//loops through Trendtracker checking for the hashtag with most tweets
for (i = 1, n = E.size(), popular = 0; i < n; i++) {
if (E[i].pop > E[popular].pop)
popular = i;
}
return E[popular].hashtag;
}
/*************************************************************/
// 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).
void Trendtracker::top_three_trends(vector<string>& T)
{
T.clear();
//Clears the vector for further use
if(size() == 0)
return;
//Returns if trends are empty
int n = E.size();
Entry dummy = {"", -1};
E.push_back(dummy);
//Create a dummy entry with a negative value and assume its the largest
//first, second and third point to it
int i, j, first, second, third;
for (i = 0, first = second = third = n; i < n; i++) {
if(E[i].pop > E[first].pop) {
third = second;
second = first;
first = i;
} else if(E[i].pop > E[second].pop) {
third = second;
second = i;
} else if(E[i].pop > E[third].pop) {
third = i;
}
}
T.push_back(E[first].hashtag);
if(second != n && second != first)
T.push_back(E[second].hashtag);
if(third != n && third != second)
T.push_back(E[third].hashtag);
//Check if the pointers still point to the dummy variable
//insert only if it doesn't
E.pop_back();
//Remove the dummy element
}
/*************************** trendtracker.h **************************************************/
#ifndef TRENDTRACKER_H
#define 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;
};
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.