//Ifgqueue.h #ifndef LFGQUEUE_H #define LFGQUEUE_H #include \"player.h\" class L
ID: 3799863 • Letter: #
Question
//Ifgqueue.h
#ifndef LFGQUEUE_H
#define LFGQUEUE_H
#include "player.h"
class LFGQueue
{
public:
LFGQueue();
void add_player(Player* p);
bool remove_next_group(Player** players);
int player_count();
int position(Player* p);
private:
class Node
{
public:
Player* p;
Node* next;
};
void remove_node(Node* n);
Node* head;
Node* tail;
};
#endif
//***************************************************************************
//main.cpp
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <cassert>
#include <iostream>
#include "lfgqueue.h"
using namespace std;
void permute(Player** players, int len)
{
for (int i = 0; i < len; ++i)
swap(players[i], players[i + rand() % (len-i)]);
}
int main()
{
srand(2017);
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);
LFGQueue q;
cout << "10% earned." << endl;
// Test when queue contains a single complete party
// in the desired order (Defender, Hunter, Bard)
q.add_player(&daniela);
assert(q.position(&daniela) == 1);
assert(q.position(&hector) == -1);
assert(q.position(&berta) == -1);
assert(q.player_count() == 1);
q.add_player(&hector);
assert(q.position(&daniela) == 1);
assert(q.position(&hector) == 2);
assert(q.position(&berta) == -1);
assert(q.player_count() == 2);
q.add_player(&berta);
assert(q.position(&daniela) == 1);
assert(q.position(&hector) == 2);
assert(q.position(&berta) == 3);
assert(q.player_count() == 3);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daniela);
assert(group[0]->name == "Daniela");
assert(group[0]->role == Player::Defender);
assert(group[1] == &hector);
assert(group[1]->name == "Hector");
assert(group[1]->role == Player::Hunter);
assert(group[2] == &berta);
assert(group[2]->name == "Berta");
assert(group[2]->role == Player::Bard);
assert(q.player_count() == 0);
cout << "35% earned." << endl;
// Test when queue contains a single complete party in
// in an undesired order (Bard, Hunter, Defender)
q.add_player(&bernardo);
q.add_player(&hugo);
q.add_player(&daria);
assert(q.player_count() == 3);
assert(q.position(&bernardo) == 1);
assert(q.position(&hugo) == 2);
assert(q.position(&daria) == 3);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daria);
assert(group[0]->name == "Daria");
assert(group[0]->role == Player::Defender);
assert(group[1] == &hugo);
assert(group[1]->name == "Hugo");
assert(group[1]->role == Player::Hunter);
assert(group[2] == &bernardo);
assert(group[2]->name == "Bernardo");
assert(group[2]->role == Player::Bard);
assert(q.player_count() == 0);
cout << "40% earned." << endl;
// Test what happens when not enough group
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "50% earned." << endl;
// Test what happens when two full parties of group,
// not in a kind order (Def, Hunt, Hunt, Bard, Bard, Def)
q.add_player(&daria);
q.add_player(&hector);
q.add_player(&hugo);
q.add_player(&bernardo);
q.add_player(&berta);
q.add_player(&daniela);
assert(q.player_count() == 6);
assert(q.position(&daria) == 1);
assert(q.position(&hector) == 2);
assert(q.position(&hugo) == 3);
assert(q.position(&bernardo) == 4);
assert(q.position(&berta) == 5);
assert(q.position(&daniela) == 6);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daria);
assert(group[1] == &hector);
assert(group[2] == &bernardo);
assert(q.player_count() == 3);
assert(q.position(&hugo) == 1);
assert(q.position(&berta) == 2);
assert(q.position(&daniela) == 3);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daniela);
assert(group[1] == &hugo);
assert(group[2] == &berta);
assert(q.player_count() == 0);
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "60% earned." << endl;
// Stress test 1: make a queue with 3000 group.
// 1000xBard, 1000xDefender, 1000xHunter.
ostringstream oss;
for (int i = 0; i < 1000; ++i)
{
oss.str("");
oss << "Bard_" << i+1;
q.add_player(new Player(oss.str(), Player::Bard));
}
assert(q.player_count() == 1000);
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
for (int i = 0; i < 1000; ++i)
{
oss.str("");
oss << "Hunter_" << i+1;
q.add_player(new Player(oss.str(), Player::Hunter));
}
assert(q.player_count() == 2000);
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
for (int i = 0; i < 1000; ++i)
{
oss.str("");
oss << "Defender_" << i+1;
q.add_player(new Player(oss.str(), Player::Defender));
}
assert(q.player_count() == 3000);
for (int i = 0; i < 1000; ++i)
{
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
oss.str("");
oss << "Defender_" << i+1;
assert(group[0]->name == oss.str());
assert(group[0]->role == Player::Defender);
oss.str("");
oss << "Hunter_" << i+1;
assert(group[1]->name == oss.str());
assert(group[1]->role == Player::Hunter);
oss.str("");
oss << "Bard_" << i+1;
assert(group[2]->name == oss.str());
assert(group[2]->role == Player::Bard);
delete group[0];
delete group[1];
delete group[2];
assert(q.player_count() == 3000 - (i + 1) * 3);
}
cout << "70% earned." << endl;
// Timing test: make a queue with 3000000 group.
// 1000000xDefender, 1000000xHunter, 1000000xBard,
// queued in random order.
LFGQueue qt;
const int timing_player_count = 3000000;
Player** all = new Player*[timing_player_count];
for (int i = 0; i < timing_player_count; i += 3)
{
all[i] = new Player("Defender_???", Player::Defender);
all[i+1] = new Player("Hunter_???", Player::Hunter);
all[i+2] = new Player("Bard_???", Player::Bard);
}
for (int i = 0; i < timing_player_count; i += 30)
permute(&(all[i]), 30);
// Time how long it takes to add all group
clock_t start = clock();
for (int i = 0; i < timing_player_count; ++i)
qt.add_player(all[i]);
float duration = static_cast<float>(clock() - start) / CLOCKS_PER_SEC;
assert(qt.player_count() == timing_player_count);
assert(duration < 2.0);
delete[] all;
cout << "80% earned." << endl;
// Time how long it takes to form 10000 groups
start = clock();
for (int i = 0; i < 10000; ++i)
assert(qt.remove_next_group(group));
duration = static_cast<float>(clock() - start) / CLOCKS_PER_SEC;
assert(qt.player_count() == timing_player_count - 30000);
assert(duration < 0.1);
cout << "95% earned." << endl;
// Remove another groups, testing for correctness
group[0] = group[1] = group[2] = 0;
assert(qt.remove_next_group(group));
assert(qt.player_count() == timing_player_count - 30003);
assert(group[0]->role == Player::Defender);
assert(group[1]->role == Player::Hunter);
assert(group[2]->role == Player::Bard);
cout << "100% earned." << endl;
}
//**********************************************************************************
//player.h
#ifndef PLAYER_H
#define PLAYER_H
#include <string>
using namespace std;
class Player
{
public:
enum Role {Defender, Hunter, Bard};
Player(string name, Role role)
{
this->name = name;
this->role = role;
}
string name;
Role role;
};
#endif
//**********************************************************************
/*
Implement a “looking for group” queue using a linked list, rather than a dynamic array. The result is faster groupmaking, in many cases taking only a fraction of a second where an array-based solution would take several seconds or more.
Create a new C++ source file named lfgqueue.cpp that implements the LFGQueue class declared in lfgqueue.h such that main.cpp and lfgqueue.cpp compile into a program that runs with no failed assertions.
*/
Explanation / Answer
Given below is the Looking for Group implement using single linked list. Please use the lfgqueue.cpp along with the other files from question. lfgqueue.h, player.h and main.cpp are not modified. Please do rate the answer if it helped. Thank you very much.
lfgqueue.h
//Ifgqueue.h
#ifndef LFGQUEUE_H
#define LFGQUEUE_H
#include "player.h"
class LFGQueue
{
public:
LFGQueue();
void add_player(Player* p);
bool remove_next_group(Player** players);
int player_count();
int position(Player* p);
private:
class Node
{
public:
Player* p;
Node* next;
};
void remove_node(Node* n);
Node* head;
Node* tail;
};
#endif
lfgqueue.cpp
#include "lfgqueue.h"
LFGQueue::LFGQueue()
{
head = NULL;
tail = NULL;
}
void LFGQueue::add_player(Player* p)
{
Node *n = new Node;
n->p = p;
n->next = NULL;
if(head == NULL)
head = tail = n;
else
{
tail->next = n;
tail = n;
}
}
bool LFGQueue::remove_next_group(Player** group)
{
Node *gp[3] = { NULL, NULL, NULL};
Node *curr = head;
while(curr != NULL)
{
if(gp[0] == NULL && curr->p->role == Player::Defender)
gp[0] = curr;
else if(gp[1] == NULL && curr->p->role == Player::Hunter)
gp[1] = curr;
else if(gp[2] == NULL && curr->p->role == Player::Bard)
gp[2] = curr;
if(gp[0] != NULL && gp[1] != NULL && gp[2] != NULL)
{
for(int i = 0; i < 3; i++)
{
group[i] = gp[i]->p;
remove_node(gp[i]);
}
return true;
}
curr = curr->next;
}
return false;
}
int LFGQueue::player_count()
{
Node *curr = head;
int count = 0;
while(curr != NULL)
{
count++;
curr = curr->next;
}
return count;
}
int LFGQueue::position(Player* p)
{
Node *curr = head;
int position = 1;
while(curr != NULL)
{
if(curr->p->name == p->name && curr->p->role == p->role)
return position;
position++;
curr = curr->next;
}
return -1;
}
void LFGQueue::remove_node(Node* n)
{
if(n == NULL || head == NULL)
return;
Node *curr = head, *prev = NULL;
while(curr != NULL)
{
if(curr == n)
break;
prev = curr;
curr = curr->next;
}
if(curr != NULL)
{
if(prev == NULL)
head = curr->next;
else
prev->next = curr->next;
if(head == NULL)
tail = NULL;
else if(tail == n)
tail = prev;
delete curr;
}
}
player.h
//**********************************************************************************
//player.h
#ifndef PLAYER_H
#define PLAYER_H
#include <string>
using namespace std;
class Player
{
public:
enum Role {Defender, Hunter, Bard};
Player(string name, Role role)
{
this->name = name;
this->role = role;
}
string name;
Role role;
};
#endif
main.cpp
//***************************************************************************
//main.cpp
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <cassert>
#include <iostream>
#include "lfgqueue.h"
using namespace std;
void permute(Player** players, int len)
{
for (int i = 0; i < len; ++i)
swap(players[i], players[i + rand() % (len-i)]);
}
int main()
{
srand(2017);
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);
LFGQueue q;
cout << "10% earned." << endl;
// Test when queue contains a single complete party
// in the desired order (Defender, Hunter, Bard)
q.add_player(&daniela);
assert(q.position(&daniela) == 1);
assert(q.position(&hector) == -1);
assert(q.position(&berta) == -1);
assert(q.player_count() == 1);
q.add_player(&hector);
assert(q.position(&daniela) == 1);
assert(q.position(&hector) == 2);
assert(q.position(&berta) == -1);
assert(q.player_count() == 2);
q.add_player(&berta);
assert(q.position(&daniela) == 1);
assert(q.position(&hector) == 2);
assert(q.position(&berta) == 3);
assert(q.player_count() == 3);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daniela);
assert(group[0]->name == "Daniela");
assert(group[0]->role == Player::Defender);
assert(group[1] == &hector);
assert(group[1]->name == "Hector");
assert(group[1]->role == Player::Hunter);
assert(group[2] == &berta);
assert(group[2]->name == "Berta");
assert(group[2]->role == Player::Bard);
assert(q.player_count() == 0);
cout << "35% earned." << endl;
// Test when queue contains a single complete party in
// in an undesired order (Bard, Hunter, Defender)
q.add_player(&bernardo);
q.add_player(&hugo);
q.add_player(&daria);
assert(q.player_count() == 3);
assert(q.position(&bernardo) == 1);
assert(q.position(&hugo) == 2);
assert(q.position(&daria) == 3);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daria);
assert(group[0]->name == "Daria");
assert(group[0]->role == Player::Defender);
assert(group[1] == &hugo);
assert(group[1]->name == "Hugo");
assert(group[1]->role == Player::Hunter);
assert(group[2] == &bernardo);
assert(group[2]->name == "Bernardo");
assert(group[2]->role == Player::Bard);
assert(q.player_count() == 0);
cout << "40% earned." << endl;
// Test what happens when not enough group
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "50% earned." << endl;
// Test what happens when two full parties of group,
// not in a kind order (Def, Hunt, Hunt, Bard, Bard, Def)
q.add_player(&daria);
q.add_player(&hector);
q.add_player(&hugo);
q.add_player(&bernardo);
q.add_player(&berta);
q.add_player(&daniela);
assert(q.player_count() == 6);
assert(q.position(&daria) == 1);
assert(q.position(&hector) == 2);
assert(q.position(&hugo) == 3);
assert(q.position(&bernardo) == 4);
assert(q.position(&berta) == 5);
assert(q.position(&daniela) == 6);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daria);
assert(group[1] == &hector);
assert(group[2] == &bernardo);
assert(q.player_count() == 3);
assert(q.position(&hugo) == 1);
assert(q.position(&berta) == 2);
assert(q.position(&daniela) == 3);
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
assert(group[0] == &daniela);
assert(group[1] == &hugo);
assert(group[2] == &berta);
assert(q.player_count() == 0);
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "60% earned." << endl;
// Stress test 1: make a queue with 3000 group.
// 1000xBard, 1000xDefender, 1000xHunter.
ostringstream oss;
for (int i = 0; i < 1000; ++i)
{
oss.str("");
oss << "Bard_" << i+1;
q.add_player(new Player(oss.str(), Player::Bard));
}
assert(q.player_count() == 1000);
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
for (int i = 0; i < 1000; ++i)
{
oss.str("");
oss << "Hunter_" << i+1;
q.add_player(new Player(oss.str(), Player::Hunter));
}
assert(q.player_count() == 2000);
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_group(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
for (int i = 0; i < 1000; ++i)
{
oss.str("");
oss << "Defender_" << i+1;
q.add_player(new Player(oss.str(), Player::Defender));
}
assert(q.player_count() == 3000);
for (int i = 0; i < 1000; ++i)
{
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_group(group));
oss.str("");
oss << "Defender_" << i+1;
assert(group[0]->name == oss.str());
assert(group[0]->role == Player::Defender);
oss.str("");
oss << "Hunter_" << i+1;
assert(group[1]->name == oss.str());
assert(group[1]->role == Player::Hunter);
oss.str("");
oss << "Bard_" << i+1;
assert(group[2]->name == oss.str());
assert(group[2]->role == Player::Bard);
delete group[0];
delete group[1];
delete group[2];
assert(q.player_count() == 3000 - (i + 1) * 3);
}
cout << "70% earned." << endl;
// Timing test: make a queue with 3000000 group.
// 1000000xDefender, 1000000xHunter, 1000000xBard,
// queued in random order.
LFGQueue qt;
const int timing_player_count = 3000000;
Player** all = new Player*[timing_player_count];
for (int i = 0; i < timing_player_count; i += 3)
{
all[i] = new Player("Defender_???", Player::Defender);
all[i+1] = new Player("Hunter_???", Player::Hunter);
all[i+2] = new Player("Bard_???", Player::Bard);
}
for (int i = 0; i < timing_player_count; i += 30)
permute(&(all[i]), 30);
// Time how long it takes to add all group
clock_t start = clock();
for (int i = 0; i < timing_player_count; ++i)
qt.add_player(all[i]);
float duration = static_cast<float>(clock() - start) / CLOCKS_PER_SEC;
assert(qt.player_count() == timing_player_count);
assert(duration < 2.0);
delete[] all;
cout << "80% earned." << endl;
// Time how long it takes to form 10000 groups
start = clock();
for (int i = 0; i < 10000; ++i)
assert(qt.remove_next_group(group));
duration = static_cast<float>(clock() - start) / CLOCKS_PER_SEC;
assert(qt.player_count() == timing_player_count - 30000);
assert(duration < 0.1);
cout << "95% earned." << endl;
// Remove another groups, testing for correctness
group[0] = group[1] = group[2] = 0;
assert(qt.remove_next_group(group));
assert(qt.player_count() == timing_player_count - 30003);
assert(group[0]->role == Player::Defender);
assert(group[1]->role == Player::Hunter);
assert(group[2]->role == Player::Bard);
cout << "100% earned." << endl;
}
output
10% earned.
35% earned.
40% earned.
50% earned.
60% earned.
70% earned.
80% earned.
95% earned.
100% earned.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.