main.cpp

#include

#include

#include

#include "lfgqueue.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()

{

// Variables used for testing

Player* group[3];

Player daria("Daria", Player::Defender);

Player daniela("Daniela", Player::Defender);

Player hector("Hector", Player::Hunter);

Player hugo("Hugo", Player::Hunter);

Player berta("Berta", Player::Bard);

Player bernardo("Bernardo", Player::Bard);

// Test size(), add(), front_player(), pop_player()

// on a small example.

LFGQueue q;

test(q.size() == 0);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == 0);

test(q.front_player(Player::Bard) == 0);

q.push_player(&daniela);

test(q.size() == 1);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == 0);

test(q.front_player(Player::Bard) == 0);

q.push_player(&hector);

test(q.size() == 2);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == 0);

q.push_player(&berta);

test(q.size() == 3);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.push_player(&hugo);

test(q.size() == 4);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.push_player(&bernardo);

test(q.size() == 5);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.push_player(&daria);

test(q.size() == 6);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

// Order is now [Daniela, Hector, Berta, Hugo, Bernardo, Daria]

q.pop_player(Player::Defender);

test(q.size() == 5);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.pop_player(Player::Hunter);

test(q.size() == 4);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

q.pop_player(Player::Bard);

test(q.size() == 3);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &bernardo);

q.pop_player(Player::Bard);

test(q.size() == 2);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == 0);

q.pop_player(Player::Defender);

test(q.size() == 1);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == 0);

q.pop_player(Player::Hunter);

test(q.size() == 0);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == 0);

test(q.front_player(Player::Bard) == 0);

// Test previous methods plus front_group(), pop_group() on

// a small example.

q.push_player(&hugo);

test(q.size() == 1);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == 0);

test(!q.front_group(group));

q.push_player(&hector);

test(q.size() == 2);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == 0);

test(!q.front_group(group));

q.push_player(&berta);

test(q.size() == 3);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(!q.front_group(group));

q.push_player(&bernardo);

test(q.size() == 4);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(!q.front_group(group));

q.push_player(&daria);

test(q.size() == 5);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(q.front_group(group));

q.push_player(&daniela);

test(q.size() == 6);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(q.front_group(group));

// Order is now [Hugo, Hector, Berta, Bernardo, Daria, Daniela]

group[0] = group[1] = group[2] = 0;

test(q.front_group(group));

test(group[0] == &daria);

test(group[1] == &hugo);

test(group[2] == &berta);

q.pop_group();

test(q.size() == 3);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &bernardo);

group[0] = group[1] = group[2] = 0;

test(q.front_group(group));

test(group[0] == &daniela);

test(group[1] == &hector);

test(group[2] == &bernardo);

q.pop_group();

test(q.size() == 0);

test(q.front_player(Player::Defender) == 0);

test(q.front_player(Player::Hunter) == 0);

test(q.front_player(Player::Bard) == 0);

// Test a set of 999 players: 333 of each role in the following order:

// 333 defenders, 1 hunter, 1 bard, 1 hunter, 1 bard...

// Create the players

Player** players = new Player*[999];

ostringstream oss;

for (int i = 0; i < 333; ++i)

{

oss.str("");

oss << "Defender " << i+1;

players[i] = new Player(oss.str(), Player::Defender);

}

for (int i = 333; i < 999; i+=2)

{

oss.str("");

oss << "Hunter " << (i-333)/2+1;

players[i] = new Player(oss.str(), Player::Hunter);

}

for (int i = 334; i < 999; i+=2)

{

oss.str("");

oss << "Bard " << (i-334)/2+1;

players[i] = new Player(oss.str(), Player::Bard);

}

// Add them to the queue

for (int i = 0; i < 999; ++i)

q.push_player(players[i]);

test(q.size() == 999);

// Repeatedly check and remove the frontmost players.

// Because of how we scrambled, this has a fixed order.

for (int i = 0; i < 333; ++i)

{

group[0] = group[1] = group[2] = 0;

test(q.front_group(group));

oss.str("");

oss << "Defender " << i+1;

test(group[0]->name() == oss.str());

oss.str("");

oss << "Hunter " << i+1;

test(group[1]->name() == oss.str());

oss.str("");

oss << "Bard " << i+1;

test(group[2]->name() == oss.str());

q.pop_group();

test(q.size() == 999 - 3 * (i+1));

}

test(q.size() == 0);

test(!q.front_group(group));

for (int i = 0; i < 999; ++i)

delete players[i];

delete[] players;

cout << "well done." << endl;

}

player.cpp

#include "player.h"

Player :: Player(string name, Role role)

{

_name = name;

_role = role;

}

string Player :: name()

{

return _name;

}

Player::Role Player :: role()

{

return _role;

}

player.h

#ifndef PLAYER_H

#define PLAYER_H

#include

using namespace std;

class Player

{

public:

// This works like a custom type with just four values.

// Outside of Player methods, reference them like:

// "if (p->role == Player::Defender)", etc.

enum Role {Defender, Hunter, Bard};

// Initializes a player with the given name and role

Player(string name, Role role);

// Returns the name of the player

string name();

// Returns the role of the player

Role role();

private:

string _name;

Role _role;

};

#endif

lfgueue.h

#ifndef LFGQUEUE_H

#define LFGQUEUE_H

#include "player.h"

class LFGQueue

{

public:

// Constructs a new empty queue

LFGQueue();

// Returns the number of players in the queue.

int size();

// Adds a (pointer to a) player to the back of the queue

void push_player(Player* p);

// Returns a pointer to the frontmost player

// with the specified role. If no such player

// exists, returns 0.

Player* front_player(Player::Role r);

// Removes the frontmost player with the

// specified role. If no such player exists

// does nothing.

void pop_player(Player::Role r);

// Returns whether the queue contains a complete group

// (a Defender, a Hunter, and a Bard).

// If the queue contains a complete group, the method

// sets the first three elements of the array parameter

// equal to the addresses of the frontmost:

// 1. Defender (index 0)

// 2. Hunter (index 1)

// 3. Bard (index 2)

bool front_group(Player** group);

// Removes the frontmost Defender, Hunter,

// and Bard from the queue. If some role

// has no player with that role, then

// no players are removed.

void pop_group();

private:

Player** players;

int count;

int capacity;

};

#endif

Above is part 1.

Now below is part 2.

main.cpp

#include

#include

#include

#include

#include "lfgqueue.h"

using namespace std;

using namespace chrono;

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()

{

// Variables used for testing

Player* group[3];

Player daria("Daria", Player::Defender);

Player daniela("Daniela", Player::Defender);

Player hector("Hector", Player::Hunter);

Player hugo("Hugo", Player::Hunter);

Player berta("Berta", Player::Bard);

Player bernardo("Bernardo", Player::Bard);

// Test size(), add(), front_player(), pop_player()

// on a small example.

LFGQueue q;

test(q.size() == 0);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == nullptr);

test(q.front_player(Player::Bard) == nullptr);

q.push_player(&daniela);

test(q.size() == 1);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == nullptr);

test(q.front_player(Player::Bard) == nullptr);

q.push_player(&hector);

test(q.size() == 2);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == nullptr);

q.push_player(&berta);

test(q.size() == 3);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.push_player(&hugo);

test(q.size() == 4);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.push_player(&bernardo);

test(q.size() == 5);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.push_player(&daria);

test(q.size() == 6);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

// Order is now [Daniela, Hector, Berta, Hugo, Bernardo, Daria]

q.pop_player(Player::Defender);

test(q.size() == 5);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &berta);

q.pop_player(Player::Hunter);

test(q.size() == 4);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

q.pop_player(Player::Bard);

test(q.size() == 3);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &bernardo);

q.pop_player(Player::Bard);

test(q.size() == 2);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == nullptr);

q.pop_player(Player::Defender);

test(q.size() == 1);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == nullptr);

q.pop_player(Player::Hunter);

test(q.size() == 0);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == nullptr);

test(q.front_player(Player::Bard) == nullptr);

// Test previous methods plus front_group(), pop_group() on

// a small example.

q.push_player(&hugo);

test(q.size() == 1);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == nullptr);

test(!q.front_group(group));

q.push_player(&hector);

test(q.size() == 2);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == nullptr);

test(!q.front_group(group));

q.push_player(&berta);

test(q.size() == 3);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(!q.front_group(group));

q.push_player(&bernardo);

test(q.size() == 4);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(!q.front_group(group));

q.push_player(&daria);

test(q.size() == 5);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(q.front_group(group));

q.push_player(&daniela);

test(q.size() == 6);

test(q.front_player(Player::Defender) == &daria);

test(q.front_player(Player::Hunter) == &hugo);

test(q.front_player(Player::Bard) == &berta);

test(q.front_group(group));

// Order is now [Hugo, Hector, Berta, Bernardo, Daria, Daniela]

group[0] = group[1] = group[2] = nullptr;

test(q.front_group(group));

test(group[0] == &daria);

test(group[1] == &hugo);

test(group[2] == &berta);

q.pop_group();

test(q.size() == 3);

test(q.front_player(Player::Defender) == &daniela);

test(q.front_player(Player::Hunter) == &hector);

test(q.front_player(Player::Bard) == &bernardo);

group[0] = group[1] = group[2] = nullptr;

test(q.front_group(group));

test(group[0] == &daniela);

test(group[1] == &hector);

test(group[2] == &bernardo);

q.pop_group();

test(q.size() == 0);

test(q.front_player(Player::Defender) == nullptr);

test(q.front_player(Player::Hunter) == nullptr);

test(q.front_player(Player::Bard) == nullptr);

// Test a set of 999 players: 333 of each role in the following order:

// 333 defenders, 1 hunter, 1 bard, 1 hunter, 1 bard...

// Create the players

Player** players = new Player*[999];

ostringstream oss;

for (int i = 0; i < 333; ++i)

{

oss.str("");

oss << "Defender #" << i+1;

players[i] = new Player(oss.str(), Player::Defender);

}

for (int i = 333; i < 999; i+=2)

{

oss.str("");

oss << "Hunter #" << (i-333)/2+1;

players[i] = new Player(oss.str(), Player::Hunter);

}

for (int i = 334; i < 999; i+=2)

{

oss.str("");

oss << "Bard #" << (i-334)/2+1;

players[i] = new Player(oss.str(), Player::Bard);

}

// Add them to the queue

for (int i = 0; i < 999; ++i)

q.push_player(players[i]);

test(q.size() == 999);

// Repeatedly check and remove the frontmost players.

// Because of how we scrambled, this has a fixed order.

for (int i = 0; i < 333; ++i)

{

group[0] = group[1] = group[2] = nullptr;

test(q.front_group(group));

oss.str("");

oss << "Defender #" << i+1;

test(group[0]->name() == oss.str());

oss.str("");

oss << "Hunter #" << i+1;

test(group[1]->name() == oss.str());

oss.str("");

oss << "Bard #" << i+1;

test(group[2]->name() == oss.str());

q.pop_group();

test(q.size() == 999 - 3 * (i+1));

}

test(q.size() == 0);

test(!q.front_group(group));

for (int i = 0; i < 999; ++i)

delete players[i];

delete[] players;

// Test a queue of 1000000 "randomly"-chosen players

// Seed random number generator, so test uses the same

// "random" numbers every time and thus runs same everytime

srand(2017);

// Add 1000000 players

system_clock::time_point start = system_clock::now();

int added[3] = {0, 0, 0};

while (added[0] + added[1] + added[2] < 1000000)

{

// Players are randomly chosen, biased in the following way:

// ~67% Defenders, ~17% Hunters, ~17% Bard

int choice = (rand() % 2) * (rand() % 3);

Player::Role role = static_cast(choice);

string name;

switch (role)

{

case Player::Defender:

name = "Defender #?";

break;

case Player::Hunter:

name = "Hunter #?";

break;

case Player::Bard:

name = "Bard #?";

break;

}

q.push_player(new Player(name, role));

++added[choice];

}

system_clock::time_point end = system_clock::now();

float dur = duration(end - start).count();

test(q.size() == 1000000);

cout << "Added 1000000 players to a queue in ";

cout << dur << " seconds." << endl;

test(dur < 3.0);

// Remove as many complete groups as possible

int complete_groups = added[0];

if (added[1] < complete_groups)

complete_groups = added[1];

if (added[2] < complete_groups)

complete_groups = added[2];

start = system_clock::now();

for (int i = 0; i < complete_groups; ++i)

{

q.pop_group();

test(q.size() == 1000000 - 3 * (i+1));

}

end = system_clock::now();

dur = duration(end - start).count();

test(q.size() == 1000000 - 3 * complete_groups);

cout << "Removed " << complete_groups << " groups of players from ";

cout << "this queue in " << dur << " seconds." << endl;

test(dur < 3.0);

cout << "Assignment complete." << endl;

}

player.h

#ifndef PLAYER_H

#define PLAYER_H

#include

using namespace std;

class Player

{

public:

// This works like a custom type with just four values.

// Outside of Player methods, reference them like:

// "if (p->role == Player::Defender)", etc.

enum Role {Defender=0, Hunter=1, Bard=2};

// Initializes a player with the given name and role

Player(string name, Role role);

// Returns the name of the player

string name();

// Returns the role of the player

Role role();

private:

string _name;

Role _role;

};

#endif

player.cpp

#include "player.h"

Player :: Player(string name, Role role)

{

_name = name;

_role = role;

}

string Player :: name()

{

return _name;

}

Player::Role Player :: role()

{

return _role;

}

lfgqueue.h

#ifndef LFGQUEUE_H

#define LFGQUEUE_H

#include "player.h"

class LFGQueue

{

public:

// All of the methods are the same as the code above in part 1 of lfgqueue.h

LFGQueue();

int size();

void push_player(Player* p);

Player* front_player(Player::Role r);

void pop_player(Player::Role r);

bool front_group(Player** group);

void pop_group();

private:

class Node

{

public:

Player* p;

Node* next;

};

Node* heads[3];

Node* tails[3];

int counts[3];

};

#endif

lfgqueue.cpp

#include "lfgqueue.h"

LFGQueue::LFGQueue()

{

}

int LFGQueue::size()

{

return 1;

}

void LFGQueue::push_player(Player* p)

{

}

Player* LFGQueue::front_player(Player::Role r)

{

return NULL;

}

void LFGQueue::pop_player(Player::Role r)

{

}

bool LFGQueue::front_group(Player** group)

{

return true;

}

void LFGQueue::pop_group()

{

}

main.cpp has changed a little bit

I need help implementing part 2 of lfgqueue.cpp

Part 2 of lfgqueue.h has changed from part 1 and there are new things that need to be implemented in part 2 of lfgqueue.cpp