//Ifgqueue.h #ifndef LFGQUEUE_H #define LFGQUEUE_H #include \"player.h\" class L
ID: 3794598 • 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_party(Player** players);
int player_count();
int position(Player* p);
private:
Player** players;
int count;
int capacity;
};
#endif
//**************************************************************************************************
//main.cpp
#include <sstream>
#include <cassert>
#include <iostream>
#include "lfgqueue.h"
using namespace std;
int main()
{
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 << "5% 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);
cout << "10% earned." << endl;
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);
cout << "20% earned." << endl;
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_party(group));
cout << "25% earned." << endl;
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_party(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 plaers for a group
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_party(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "50% earned." << endl;
// Test what happens when two full groups of players
// in an undesired 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_party(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_party(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_party(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "65% 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_party(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_party(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_party(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 << "85% earned." << endl;
// Stress test 2: make a queue with 1000001 group.
// 999999xHunter, 1xBard, 1xDefender.
for (int i = 0; i < 999999; ++i)
{
oss.str("");
oss << "AnonHunter_" << i+1;
q.add_player(new Player(oss.str(), Player::Hunter));
}
assert(q.player_count() == 999999);
assert(!q.remove_next_party(group));
q.add_player(new Player("SadBard", Player::Bard));
assert(q.player_count() == 1000000);
assert(!q.remove_next_party(group));
q.add_player(new Player("BusyTank", Player::Defender));
assert(q.player_count() == 1000001);
assert(q.remove_next_party(group));
assert(q.player_count() == 999998);
assert(group[0]->name == "BusyTank");
assert(group[1]->name == "AnonHunter_1");
assert(group[2]->name == "SadBard");
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
//***************************************************************************************************
/*
In many multiplayer online games, there’s a “looking for group” feature for being automatically matched with other players. Such a feature behaves like a queue: players join the queue and removed in complete groups, and players who join the queue first are the first to be grouped.
Implement a looking-for-group queue for a game where players can be one of three roles (Defender, Hunter, and Bard) and each group consists of one Defender, one Hunter, and one Bard.
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 implementation of class LFGQueue in lfgqueue.cpp. Please use it with lfgqueue.h and main.cpp from the question.
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_party(Player** players);
int player_count();
int position(Player* p);
private:
Player** players;
int count;
int capacity;
};
#endif
//**************************************************************************************************
lfgqueue.cpp
#include "lfgqueue.h"
LFGQueue::LFGQueue()
{
capacity = 3;
count = 0;
players = new Player*[capacity];
}
void LFGQueue::add_player(Player* p)
{
if(count == capacity) //expand if already full, double the capacity
{
capacity = 2 * capacity;
Player **temp = new Player* [capacity];
for(int i = 0; i < count; i++)
temp[i] = players[i];
delete []players;
players = temp;
}
players[count++] = p;
}
bool LFGQueue::remove_next_party(Player** group)
{
int indices[3] ={-1, -1, -1}; //index of defender, hunter, bard
bool grouped = false;
if(count < 3) //can not form a group if less than 3 players
return false;
//search and save the index of the 1st player in each role
for(int i = 0; i < count; i++)
{
if( players[i]->role == Player::Defender && indices[0] == -1 )
indices[0] = i;
else if(players[i]->role == Player::Hunter && indices[1] == -1 )
indices[1] = i;
else if(players[i]->role == Player::Bard && indices[2] == -1 )
indices[2] = i;
//already found the required group members, so no need to search further
if(indices[0] != -1 && indices[1] != -1 && indices[2] != -1)
{
//copy the players for the group
group[0] = players[indices[0]];
group[1] = players[indices[1]];
group[2] = players[indices[2]];
grouped = true;
break;
}
}
if(grouped)
{
for(int i = 0 ; i < 3; i++)
{
//starting from the each index, move all elements to left.
//but if previous shift affected the index, then adjust the index
//for ex: if loop1, elements from index 3 to end where shifted,
// in loop2, if we actually need to shift from index 5 to end,
//we need to adjust index 5 as 4 since the previous shift would have
//move the element one position left.
int shift = 0;
int start = indices[i];
for(int k =0; k <i; k++)
if(start > indices[k])
shift--;
start += shift; //adjust the index based on any previous shifts
for(int j = start + 1; j < count; j++)
players[j-1] = players[j];
count--;
}
return true;
}
else
return false;
}
int LFGQueue::player_count()
{
return count;
}
int LFGQueue::position(Player* p)
{
for(int i = 0; i < count; i++)
if(players[i]->name == p->name && players[i]->role == p->role)
return (i+1);
return -1;
}
main.cpp
//main.cpp
#include <sstream>
#include <cassert>
#include <iostream>
#include "lfgqueue.h"
using namespace std;
int main()
{
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 << "5% 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);
cout << "10% earned." << endl;
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);
cout << "20% earned." << endl;
group[0] = group[1] = group[2] = 0;
assert(q.remove_next_party(group));
cout << "25% earned." << endl;
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_party(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 plaers for a group
group[0] = group[1] = group[2] = 0;
assert(!q.remove_next_party(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "50% earned." << endl;
// Test what happens when two full groups of players
// in an undesired 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_party(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_party(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_party(group));
assert(group[0] == 0);
assert(group[1] == 0);
assert(group[2] == 0);
cout << "65% 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_party(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_party(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_party(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 << "85% earned." << endl;
// Stress test 2: make a queue with 1000001 group.
// 999999xHunter, 1xBard, 1xDefender.
for (int i = 0; i < 999999; ++i)
{
oss.str("");
oss << "AnonHunter_" << i+1;
q.add_player(new Player(oss.str(), Player::Hunter));
}
assert(q.player_count() == 999999);
assert(!q.remove_next_party(group));
q.add_player(new Player("SadBard", Player::Bard));
assert(q.player_count() == 1000000);
assert(!q.remove_next_party(group));
q.add_player(new Player("BusyTank", Player::Defender));
assert(q.player_count() == 1000001);
assert(q.remove_next_party(group));
assert(q.player_count() == 999998);
assert(group[0]->name == "BusyTank");
assert(group[1]->name == "AnonHunter_1");
assert(group[2]->name == "SadBard");
cout << "100% earned." << endl;
}
output
5% earned.
10% earned.
20% earned.
25% earned.
35% earned.
40% earned.
50% earned.
65% earned.
85% earned.
100% earned.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.