Need help making my functions sort quicker. Topics: Vectors and sorting. I was given the header and main files while changes should only be made in the trendtracker.cpp file. Only thing is my sorting algorithm seems to fail.. I wanted to do a binary search but wasn't able to. Perferably use this algorithm and use comments to see what steps I needed to take. The following files are below, thanks! //************************* 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

cerr

abort();

}

#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))

int main()

{

// Setup

vector 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

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

} //************************************ trendtracker.h *****************************//

#ifndef TRENDTRACKER_H

#define TRENDTRACKER_H

#include

#include

#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 Trendtracker containing hashtags

// found in the provided file.

// The file is promised to have the following format:

//

// string1

// string2

// ...

// stringN

//

// where string1

//

// Must run in O(n) time.

Trendtracker(string filename);

// 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 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(1) time.

void top_three_trends(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 of E containing an Entry with hashtag ht.

// If no such hashtag is found, returns -1.

//

// Should run in O(log(n)).

int search(string ht);

// Entries sorted (lexicographically) by hashtag.

vector E;

// Stores indices of the (up to) three most-tweeted

// entries in E.

vector S;

};

#endif

//********************************* trendtracker.cpp ********************************//

#include "trendtracker.h"

#include

using namespace std;

/*************************************************************/

// Creates a Trendtracker containing hashtags

// found in the provided file.

// The file is promised to have the following format:

//

// string1

// string2

// ...

// stringN

//

// where string1

//

// Must run in O(n) time.

Trendtracker::Trendtracker(string filename)

{

}

/*************************************************************/

// 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(log(n)) time.

void Trendtracker::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 Trendtracker::popularity(string name)

{

}

/*************************************************************/

// Returns a most-tweeted hashtag.

// If the Trendtracker has no hashtags, returns "".

//

// Must run in O(1) time.

string Trendtracker::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(1) time.

void Trendtracker::top_three_trends(vector& T)

{

} //********************************* small.txt ********************************//

#C++

#algorithms

#cs4all

#programming //********************************* tiny.txt ********************************//

#solo

//Other text files too large for chegg

homework, you wil implement the same class, but using an efficient two-vector-based data structure (see Figure 1). vector S 4 1 5 string hashtag #ads | # big #cat #dog #egg | #fad | #gig | #hot vector Entry> E int pop Figure 1: Representing hashtags and their popularities using an efficient vector-based data structure homework, you wil implement the same class, but using an efficient two-vector-based data structure (see Figure 1). vector S 4 1 5 string hashtag #ads | # big #cat #dog #egg | #fad | #gig | #hot vector Entry> E int pop Figure 1: Representing hashtags and their popularities using an efficient vector-based data structure