//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 #include #include #include #include #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(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(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

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.

*/