ICSI 45 C Hot Potato Game

Building a Queue

A queue is a special type of object that gets particular uses in computer science. When you use this structure, you can add elements to it (a process called an enqueue), but you can access one specific element: the element you added the least recently (among those still in the queue). You can remove that element (called a dequeue action) or access it (requesting the front).

There are several ways to implement a Queue.

In the first part of this project, you will implement a queue as a linked list. Unlike the linked list you saw in lecture, which stored variables of type int and had arbitrary access, we will implement a queue that stores std::string objects.

You will need to implement the following functions:

• Default constructor: create the queue in an empty state.
• Destructor: be sure to manage your memory properly.
• Copy constructor and assignment operator. These need to be deep copies: do not allow a change to a copy to affect the original, or vice versa.
• enqueue : this function will add the given std::string to the end of the line.
• front : there are two versions of this, depending on whether or not the given QueueOfStrings is able to be modified or not.
  • If the QueueOfStrings is empty, throw a QueueEmptyException from the function -- that is an irregular return. Do not catch the QueueEmptyException inside the function.
• dequeue. Whoever is at the front of the line is removed from the QueueOfStrings. Do not return it -- just remove it. If the line is empty, throw a QueueEmptyException instead of modifying the list. Do not catch the QueueEmptyException inside the function.
  • Please note: there are some variations of the Queue data structure where dequeue returns the front element in addition to returning it. We are treating "tell me what is at the front" and "remove what is at the front" as separate actions for this project.

Restrictions on QueueOfStrings

There are other ways to implement a queue; yours must be a linked list.

Playing Hot Potato

The game hot potato works as follows. A group of participants stand in a line. The first participant has an object, which may or may not be a potato, but is referred to as one anyway. When a round of the game begins, whoever holds the potato passes it to the next participant in line, then moves to the back of the line. This is repeated until some stop signal is given; at that point, whoever is holding the potato is out and exits the game, handing the potato to whoever is next in line. This process repeats until only one person remains. This game passed for quality entertainment in an era before smartphones.

For this portion of the assignment, we will get a list of people who are going to play hot potato, and the order in which they are lined up. The order of the line does not change, except for when a participant exits the game.

You must implement the following function in HotPotato.cpp:

std::string playHotPotato(std::istream &in, const std::vector< unsigned > & numOfPasses);

The first parameter is a file; it contains at least one line, each of which is to be interpreted as the name of a distinct person playing Hot Potato. The first person listed will start with the potato; each person, when having the potato, will pass it to the person listed next in the file. The exception to this is the last person listed, who will pass it to the first person listed. If a person is eliminated, they pass it to the same person they would have passed it to if they were not eliminated, and then they exit the game.

The vector numOfPasses is how many times the potato is passed in each phase; whoever is left holding it after that is eliminated. The first round uses numOfPasses[0], the second uses numOfPasses[1], and so on; after the last element of the vector is used, we return to the beginning.

Let's examine the example in the required test case.

A game of hot potato is being played by Aya, Dara, Idris, Jasmine, Lakshmi, Patrick, Sammy, and Yaphet; they are lined up in that order5. Our vector numOfPasses is {5,3}. In the first round, Aya passes to Dara, who passes to Idris, who passes to Jasmine, who passes to Lakshmi, who passes to Patrick. That last one is the fifth pass, so Patrick, who is holding the potato, is out. Patrick hands the potato to Sammy (this is not a pass of the potato for counting purposes) and sits down.

In the second round, Sammy begins with the potato. Sammy passes to Yaphet, who passes to Aya, who passes to Dara. This was the third pass, and because numOfPasses[1] is 3, Dara is out. Dara hands the potato to Idris and exits the game.

Because numOfPasses had only two elements, the next round goes back to using numOfPasses[0]. I encourage you to write this by hand and trace a few times before sitting down to write code. You will see that Lakshmi wins this game.

I suggest the following approach to solving this problem:

• Add all names from the file into an initially empty QueueOfStrings in the proper order.
• Simulate one round of the game by making a number of operations:
  • Enqueue the name of whoever is at the front.
  • Remove that name from the front of the queue.
  • After the requisite number of operations, remove whoever is left holding the potato from the queue.
• Repeat until only one player remains in the queue; that person is the winner.

Restrictions

You must use your QueueOfStrings in solving this problem; you may not use any standard library container classes, nor may you make your own, with the exception of the QueueOfStrings. You may also use std::vector, but only for purposes of the second parameter -- you may not create your own std::vector for usage elsewhere in this problem;

Starter Codes

QueueOfStrings.hpp

#ifndef __QUEUE_OF_STRINGS_HPP
#define __QUEUE_OF_STRINGS_HPP

#include < string >
#include < stdexcept >

class QueueEmptyException : public std::runtime_error
{
public:
explicit QueueEmptyException(const std::string & err) : std::runtime_error(err) {}
};


class QueueOfStrings
{
private:


public:
QueueOfStrings();

// Note: copy constructors are required.
// Be sure to do a "deep copy" -- if I
// make a copy and modify one, it should not affect the other.
QueueOfStrings(const QueueOfStrings & st);
QueueOfStrings & operator=(const QueueOfStrings & st);
~QueueOfStrings();

size_t size() const noexcept;
bool isEmpty() const noexcept;


void enqueue(const std::string & elem);


// both versions of front(), as well as dequeue(), throw a QueueEmptyException if called when empty.
std::string & front();
const std::string & front() const;


// does not return anything. Just removes.
void dequeue();
};

#endif

QueueOfStrings.cpp

#include "QueueOfStrings.hpp"

QueueOfStrings::QueueOfStrings()
{
}



// Be sure to do a "deep copy" -- if I
// make a copy and modify one, it should not affect the other.
QueueOfStrings::QueueOfStrings(const QueueOfStrings & st)
{

}

QueueOfStrings & QueueOfStrings::operator=(const QueueOfStrings & st)
{
return *this;
}

QueueOfStrings::~QueueOfStrings()
{
}


size_t QueueOfStrings::size() const noexcept
{
return 15; // stub, probably not the right answer.
}


bool QueueOfStrings::isEmpty() const noexcept
{
return false; // stub, probably not the right answer.
}

void QueueOfStrings::enqueue(const std::string & elem)
{

}


std::string & QueueOfStrings::front()
{
throw QueueEmptyException{"Queue is Empty"};
}

const std::string & QueueOfStrings::front() const
{
throw QueueEmptyException{"Queue is Empty"};
}


// does not return anything. Just removes.
void QueueOfStrings::dequeue()
{
}

HotPotato.hpp

#ifndef __45C_HOT_POTATO_GAME
#define __45C_HOT_POTATO_GAME

#include < istream >
#include < vector >



std::string playHotPotato(std::istream &in, const std::vector & numOfPasses);

#endif

HotPotato.cpp

#include "HotPotato.hpp"
#include "QueueOfStrings.hpp"

#include < istream >
#include < vector >

// You may want to #include others that we have talked about


std::string playHotPotato(std::istream &in, const std::vector< unsigned > & numOfPasses)
{
return "";
}