#include
#include
#include
#include
#include
#include "trendtracker.h"
using namespace std;
inline void _test(const char* expression, const char* file, int line)
{
ce
"test("
expression
") failed in file "
file;
ce
", line "
line
"."
endl;
abort();
}
#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))
int main()
{
Setup
vecto
string> R;
string s, line;
Test constructor, size(), popularity(), tweeted()
Trendtracker T1("small.txt");
test(T1.size() == 4);
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 0);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 0);
test(T1.popularity("#C++") == 0);
T1.tweeted("#programming");
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 0);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 1);
test(T1.popularity("#C++") == 0);
T1.tweeted("#programming");
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 0);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 2);
test(T1.popularity("#C++") == 0);
T1.tweeted("#programming");
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 0);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);
T1.tweeted("#cs4all");
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);
T1.tweeted("#algorithms");
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 1);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);
T1.tweeted("#cs4all");
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 2);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);
T1.tweeted("#datastructures");
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 2);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);
Trendtracker T2("small.txt");
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");
test(T2.popularity("#algorithms") == 2);
test(T2.popularity("#cs4all") == 3);
test(T2.popularity("#programming") == 5);
test(T2.popularity("#C++") == 4);
Enforce no usage of global variables
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 2);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);
Test top_trend(), top_three_trends()
Trendtracker T3("small.txt");
T3.top_three_trends(R);
test(R.size() == 3);
T3.tweeted("#programming");
test(T3.top_trend() == "#programming");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#programming");
T3.tweeted("#C++");
T3.tweeted("#C++");
test(T3.top_trend() == "#C++");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#C++");
test(R[1] == "#programming");
T3.tweeted("#algorithms");
T3.tweeted("#algorithms");
T3.tweeted("#algorithms");
test(T3.top_trend() == "#algorithms");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#algorithms");
test(R[1] == "#C++");
test(R[2] == "#programming");
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] == "#algorithms");
test(R[2] == "#C++");
At this point:
cs4all: 4
algorithms: 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] == "#algorithms");
At this point:
programming: 5
cs4all: 4
algorithms: 3
C++: 2
T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
T3.tweeted("#algorithms");
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] == "#algorithms");
At this point:
cs4all: 6
programming: 5
algorithms: 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("hashtags.txt");
test(T4.size() == 300000);
ifstream f;
f.open("tweeted.txt");
assert(f.is_open());
If this fails, you're missing tweeted.txt
while (getline(f, line))
T4.tweeted(line);
f.close();
test(T4.popularity("#programming") == 10);
test(T4.popularity("#computer") == 9);
test(T4.popularity("#is") == 8);
test(T4.popularity("#very") == 7);
test(T4.popularity("#fun") == 6);
test(T4.popularity("#but") == 5);
test(T4.popularity("#sometimes") == 5);
test(T4.popularity("#can") == 5);
test(T4.popularity("#be") == 5);
test(T4.popularity("#challenging") == 5);
test(T4.top_trend() == "#programming");
T4.top_three_trends(R);
test(R[0] == "#programming");
test(R[1] == "#computer");
test(R[2] == "#is");
Test a Trendtracker with a single hashtag
Trendtracker T5("tiny.txt");
test(T5.size() == 1);
test(T5.popularity("#solo") == 0);
test(T5.popularity("#duo") == -1);
T5.tweeted("#solo");
test(T5.popularity("#solo") == 1);
test(T5.popularity("#duo") == -1);
test(T5.top_trend() == "#solo");
T5.top_three_trends(R);
test(R.size() == 1);
test(R[0] == "#solo");
cout
"Assignment complete."
endl;
}
#C++
#algorithms
#cs4all
#programming
CSCI 3333 Homework TT2: Fast Trendtracke
1 Introduction
In the previous homework, you implemented a Trendtracker data structure that tracks information about
a set of hashtags. Unfortunately, the efficiency of data structure’s operations (tweeted, popularity,
top three trends, etc.) probably wasn’t great. For tracking a few thousand hashtags, the efficiency was
good enough, but Twitter has hundreds of millions of users1 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).
#ads
2
vecto
int> S
vecto
Entry> E
4 1 5
#gig
2
#hot
1
#dog
0
#cat
4
#fad
6
#big
8
#egg
9
string hashtag
int pop
Figure 1: Representing hashtags and their popularities using an efficient vector-based data structure.
2 Instructions
The following files have been given to you:
1. A C++ header file (trendtracker.h) declaring the Trendtracker class.
2. A C++ source file (main.cpp) containing a main function with tests.
3. A text file ( tiny.txt) containing 1 hashtag.
4. A text file (small.txt) containing 4 hashtags.
5. A text file (hashtags.txt) containing XXXXXXXXXXhashtags.3
6. A text file (tweeted.txt) containing XXXXXXXXXXhashtags.4
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. Submit the
source file trendtracker.cpp.
3 Submission and Grading
Submit the aforementioned source file(s) via Blackboard as attached file(s). In the case of multiple submis-
sions, the last submission before the deadline is graded.
For grading, each submission is compiled with the provided files and run. Submissions that do not run
to completion (i.e. fail to print “Assignment complete.”) receive no credit. Submissions that take an
unreasonable amount of time (e.g. more than a minute or so) to run and do not meet the asymptotic
efficiency requirements receive no credit. All other submissions receive full credit.
See the course late work policy for information about receiving partial credit for late submissions.
1https:
techcrunch.com/2017/06/27/facebook-2-billion-users
2http:
iswc2010.semanticweb.org/pdf/352.pdf
3Source: http:
norvig.com/ngrams/count_1w.txt.
4Source: http:
norvig.com/ngrams/count_1w.txt.
1
https:
faculty.utrgv.edu
obert.schwelle
CS3333/hwTT2/trendtracker.h
https:
faculty.utrgv.edu
obert.schwelle
CS3333/hwTT2/main.cpp
https:
faculty.utrgv.edu
obert.schwelle
CS3333/hwTT2/tiny.txt
https:
faculty.utrgv.edu
obert.schwelle
CS3333/hwTT2/small.txt
https:
faculty.utrgv.edu
obert.schwelle
CS3333/hwTT2/hashtags.txt
https:
faculty.utrgv.edu
obert.schwelle
CS3333/hwTT2/tweeted.txt
https:
techcrunch.com/2017/06/27/facebook-2-billion-users
http:
iswc2010.semanticweb.org/pdf/352.pdf
http:
norvig.com/ngrams/count_1w.txt
http:
norvig.com/ngrams/count_1w.txt
Introduction
Instructions
Submission and Grading