Service Queue ADT in C++ Homework Sample

A popular restaurant has no bookings, but instead issues a numbered ticket on entry, each ticket number is unique. You may bribe the maitre’d in order to advance to the front of the line (no matter the number on your ticket), or can be kicked out (in which case the ticket is returned). Once you are seated the ticket is returned and is able to be used again. There are provided implementations that are slow, you need to provide a version that operates in O(1) time, and O(n) for copy the list. For more C++ programming assignments contact us for details.

Solution:

ServiceQueue.h

#ifndef _SERVICE_QUEUE_H
#define _SERVICE_QUEUE_H
#include <algorithm> // std::reverse
#include <iostream>
#include <vector>
#include <utility>
#include<set>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

class ServiceQueue {

private:
/** Your private data members here!
* (you should have NO PUBLIC data members!
*
* Nested private types also go here.
* For example, if your design needs some kind of
* structure, you would specify it here.
*/
std::set<int> buzzer_bucket; // keeps track of buzzer-IDs
// that can be reused. Operates
// as a stack so buzzer that became
// reusable most recently is on
// top (i.e., at back of vector).

vector<int> line;
vector<int> bribe_line;
int idx_start;
int num_of_kick =0, mx;
public:

/**
* Constructor
* Description: intializes an empty service queue.
*
* RUNTIME REQUIREMENT: O(1)
*
* TODO
*/
ServiceQueue() {
idx_start = 0;
num_of_kick = 0;
mx = 0;
}

/**
* Destructor
* Description: deallocates all memory assciated
* with service queue
*
* RUNTIME REQUIREMENT: O(N_b) where N_b is the number of buzzer
* IDs that have been used during the lifetime of the
* service queue; in general, at any particular instant
* the actual queue length may be less than N_b.
*
* [See discussion of “re-using buzzers” below]
*
* TODO
*/
~ServiceQueue() {

}

/**
* Function: snapshot()
* param: buzzers is an integer vector passed by ref
* Description: populates buzzers vector with a “snapshot”
* of the queue as a sequence of buzzer IDs
*
*
* RUNTIME REQUIREMENT: O(N) (where N is the current queue
* length).
*/
void snapshot(std::vector<int> &buzzers) {
buzzers.clear(); // you don’t know the history of the
// buzzers vector, so we had better
// clear it first.
set<int> tmp;
vector<int> holder;
for(int i = bribe_line.size()-1 ; i>=0 ; i–)
{
if (buzzer_bucket.find(bribe_line[i]) == buzzer_bucket.end() && tmp.find(bribe_line[i]) == tmp.end())
holder.push_back(bribe_line[i]), tmp.insert(bribe_line[i]);
}

for (int i = line.size()-1; i >= idx_start; i–)
{
if( buzzer_bucket.find(line[i]) == buzzer_bucket.end() && tmp.find(line[i]) == tmp.end())
buzzers.push_back(line[i]), tmp.insert(line[i]);
}
reverse(holder.begin(), holder.end());
for (int i : holder)
buzzers.push_back(i);
reverse(buzzers.begin(), buzzers.end());

}

/**
* Function: length()
* Description: returns the current number of
* entries in the queue.
*
* RUNTIME REQUIREMENT: O(1)
*/
int length() {

return line.size() – idx_start-num_of_kick; // placeholder

}

/**
* Function: give_buzzer()
* Return: buzzer-ID (integer) assigned to the new customer.
* Description: This is the “enqueue” operation. For us
* a “buzzer” is represented by an integer (starting
* from zero). The function selects an available buzzer
* and places a new entry at the end of the service queue
* with the selected buzer-ID.
* This buzzer ID is returned.
* The assigned buzzer-ID is a non-negative integer
* with the following properties:
*
* (1) the buzzer (really it’s ID) is not currently
* taken — i.e., not in the queue. (It
* may have been in the queue at some previous
* time — i.e., buzzer can be re-used).
* This makes sense: you can’t give the same
* buzzer to two people!
*
* (2) Reusable Buzzers: A re-usable buzzer is
* a buzzer that _was_ in the queue at some previous
* time, but currently is not.
*
* REQUIREMENT: If there is one or more reusable
* buzzer, you MUST return one of them; furthermore,
* it must be the buzzer that became reusable most
* MOST RECENTLY.
*
* (3) if there are no previously-used / reusable buzzers,
* the SMALLEST possible buzzer-ID is used (retrieved from
* inventory).
* Properties in this situation (where N is the current
* queue length):
*
* – The largest buzzer-ID used so far is N-1
*
* – All buzzer-IDs in {0..N-1} are in the queue
* (in some order).
*
* – The next buzzer-ID (from the basement) is N.
*
* In other words, you can always get more buzzers (from
* the basement or something), but you don’t fetch an
* additional buzzer unless you have to (i.e., no reusable buzzers).
*
* Comments/Reminders:
*
* Rule (3) implies that when we start from an empty queue,
* the first buzzer-ID will be 0 (zero).
*
* Rule (2) does NOT require that the _minimum_ reuseable
* buzzer-ID be used. If there are multiple reuseable buzzers,
* any one of them will do.
*
* Note the following property: if there are no re-useable
* buzzers, the queue contains all buzzers in {0..N-1} where
* N is the current queue length (of course, the buzzer IDs
* may be in any order.)
*
* RUNTIME REQUIREMENT: O(1) ON AVERAGE or “AMORTIZED”
* In other words, if there have been M calls to
* give_buzzer, the total time taken for those
* M calls is O(M).
*
* An individual call may therefore not be O(1) so long
* as when taken as a whole they average constant time.
*
*/
int give_buzzer() {

int b;

if (buzzer_bucket.size() != 0) {
b = *buzzer_bucket.begin();
buzzer_bucket.erase(b);
}
// otherwise, queue must contain exactly buzzers
// 0..the_queue.size()-1
// and therefore, the next smallest buzzer must be
// the_queue.size()
else {
b = mx;
mx ++;
}
line.push_back(b);
return b;
}

/**
* function: seat()
* description: if the queue is non-empty, it removes the first
* entry from (front of queue) and returns the
* buzzer ID.
* Note that the returned buzzer can now be re-used.
*
* If the queue is empty (nobody to seat), -1 is returned to
* indicate this fact.
*
* Returns: buzzer ID of dequeued customer, or -1 if queue is empty.
*
* RUNTIME REQUIREMENT: O(1)
*/
int seat() {
if(line.size()==(unsigned int) (idx_start + num_of_kick))
return -1; // placeholder
while ((unsigned int) idx_start < line.size()&& buzzer_bucket.find(line[idx_start]) != buzzer_bucket.end())
{
idx_start++;
}
if (line.size() == (unsigned int) (idx_start+num_of_kick))
return -1; // placeholder

if (bribe_line.size())
{
while(buzzer_bucket.find( bribe_line.back()) != buzzer_bucket.end())
bribe_line.pop_back();
if(bribe_line.size()){
int ret = bribe_line.back();
bribe_line.pop_back();
buzzer_bucket.insert(ret);
return ret;
}
}
int ret = line[idx_start];
idx_start++;
buzzer_bucket.insert(ret);

return ret;
}

/**
* function: kick_out()
*
* description: Some times buzzer holders cause trouble and
* a bouncer needs to take back their buzzer and
* tell them to get lost.
*
* Specifially:
*
* If the buzzer given by the 2nd parameter is
* in the queue, the buzzer is removed (and the
* buzzer can now be re-used) and 1 (one) is
* returned (indicating success).
*
* Return: If the buzzer isn’t actually currently in the
* queue, the queue is unchanged and false is returned
* (indicating failure). Otherwise, true is returned.
*
* RUNTIME REQUIREMENT: O(1)
*/
bool kick_out(int buzzer) {
if (buzzer_bucket.find(buzzer) != buzzer_bucket.end()) // log(N) time
{
return 0;
}
if(buzzer > mx)
return false; // placeholder
buzzer_bucket.insert(buzzer);
if(mx == buzzer)
mx–;
num_of_kick++;
auto it = find(bribe_line.begin(), bribe_line.end() , buzzer);
if(it != bribe_line.end())
bribe_line.erase(it),num_of_kick–;
return 1;

}

/**
* function: take_bribe()
* description: some people just don’t think the rules of everyday
* life apply to them! They always want to be at
* the front of the line and don’t mind bribing
* a bouncer to get there.
*
* In terms of the function:
*
* – if the given buzzer is in the queue, it is
* moved from its current position to the front
* of the queue. 1 is returned indicating success
* of the operation.
* – if the buzzer is not in the queue, the queue
* is unchanged and 0 is returned (operation failed).
*
* Return: If the buzzer isn’t actually currently in the
* queue, the queue is unchanged and false is returned
* (indicating failure). Otherwise, true is returned.
*
* RUNTIME REQUIREMENT: O(1)
*/
bool take_bribe(int buzzer) {
if (buzzer_bucket.find(buzzer) != buzzer_bucket.end()) // log(N) time
{
return 0;
}
if ((unsigned int) buzzer >= line.size() – idx_start)
return false; // placeholder
bribe_line.push_back(buzzer);

return 1; // placeholder

}

}; // end ServiceQueue class

#endif

ServiceQueueSlow.h

#ifndef _SERVICE_QUEUE_H
#define _SERVICE_QUEUE_H

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

/**
* Implementation of the ServiceQueue ADT meeting
* behavioral requirements, but not all runtime
* requirements.
*/

class ServiceQueue {

private:
std::vector<int> the_queue; // idx-0 is front of queue

std::vector<int> buzzer_bucket; // keeps track of buzzer-IDs
// that can be reused. Operates
// as a stack so buzzer that became
// reusable most recently is on
// top (i.e., at back of vector).

public:

/**
* Constructor
* Description: intializes an empty service queue.
*
* RUNTIME REQUIREMENT: O(1)
*
* TODO
*/
ServiceQueue() {

// Nothing for us to do here since vector constructors
// will be automatically applied to data members.
}

/**
* Destructor
* Description: deallocates all memory assciated
* with service queue
*
* RUNTIME REQUIREMENT: O(N_b) where N_b is the number of buzzer
* IDs that have been used during the lifetime of the
* service queue; in general, at any particular instant
* the actual queue length may be less than N_b.
*
* [See discussion of “re-using buzzers” below]
*
* TODO
*/
~ServiceQueue() {

// again, nothing for us to do here.
// vector destructors automatically applied to
// data members
}

/**
* Function: snapshot()
* param: buzzers is an integer vector passed by ref
* Description: populates buzzers vector with a “snapshot”
* of the queue as a sequence of buzzer IDs
*
*
* RUNTIME REQUIREMENT: O(N) (where N is the current queue
* length).
*/
void snapshot(std::vector<int> &buzzers) {
buzzers.clear(); // you don’t know the history of the
// buzzers vector, so we had better
// clear it first.

// Note: the vector class over-rides the assignment operator ‘=’
// and does an element-by-element copy from the RHS vector (the_vector)
// in this case) to the LHS vector (buzzers) in this case).

buzzers = the_queue;

}

/**
* Function: length()
* Description: returns the current number of
* entries in the queue.
*
* RUNTIME REQUIREMENT: O(1)
*/
int length() {

return the_queue.size(); // placeholder

}

/**
* Function: give_buzzer()
* Return: buzzer-ID (integer) assigned to the new customer.
* Description: This is the “enqueue” operation. For us
* a “buzzer” is represented by an integer (starting
* from zero). The function selects an available buzzer
* and places a new entry at the end of the service queue
* with the selected buzer-ID.
* This buzzer ID is returned.
* The assigned buzzer-ID is a non-negative integer
* with the following properties:
*
* (1) the buzzer (really it’s ID) is not currently
* taken — i.e., not in the queue. (It
* may have been in the queue at some previous
* time — i.e., buzzer can be re-used).
* This makes sense: you can’t give the same
* buzzer to two people!
*
* (2) Reusable Buzzers: A re-usable buzzer is
* a buzzer that _was_ in the queue at some previous
* time, but currently is not.
*
* REQUIREMENT: If there is one or more reusable
* buzzer, you MUST return one of them; furthermore,
* it must be the buzzer that became reusable most
* MOST RECENTLY.
*
* (3) if there are no previously-used / reusable buzzers,
* the SMALLEST possible buzzer-ID is used (retrieved from
* inventory).
* Properties in this situation (where N is the current
* queue length):
*
* – The largest buzzer-ID used so far is N-1
*
* – All buzzer-IDs in {0..N-1} are in the queue
* (in some order).
*
* – The next buzzer-ID (from the basement) is N.
*
* In other words, you can always get more buzzers (from
* the basement or something), but you don’t fetch an
* additional buzzer unless you have to (i.e., no reusable buzzers).
*
* Comments/Reminders:
*
* Rule (3) implies that when we start from an empty queue,
* the first buzzer-ID will be 0 (zero).
*
* Rule (2) does NOT require that the _minimum_ reuseable
* buzzer-ID be used. If there are multiple reuseable buzzers,
* any one of them will do.
*
* Note the following property: if there are no re-useable
* buzzers, the queue contains all buzzers in {0..N-1} where
* N is the current queue length (of course, the buzzer IDs
* may be in any order.)
*
* RUNTIME REQUIREMENT: O(1) ON AVERAGE or “AMORTIZED”
* In other words, if there have been M calls to
* give_buzzer, the total time taken for those
* M calls is O(M).
*
* An individual call may therefore not be O(1) so long
* as when taken as a whole they average constant time.
*
*/
int give_buzzer() {
int b;

// take top reusable buzzer if possible
if(buzzer_bucket.size() != 0) {
b = buzzer_bucket.back();
buzzer_bucket.pop_back();
}
// otherwise, queue must contain exactly buzzers
// 0..the_queue.size()-1
// and therefore, the next smallest buzzer must be
// the_queue.size()
else {
b = the_queue.size();
}
the_queue.push_back(b);
return b;
}

/**
* function: seat()
* description: if the queue is non-empty, it removes the first
* entry from (front of queue) and returns the
* buzzer ID.
* Note that the returned buzzer can now be re-used.
*
* If the queue is empty (nobody to seat), -1 is returned to
* indicate this fact.
*
* Returns: buzzer ID of dequeued customer, or -1 if queue is empty.
*
* RUNTIME REQUIREMENT: O(1)
*/
int seat() {
int buzzer;

if(the_queue.size()==0)
return -1;
else {
buzzer = the_queue[0];
the_queue.erase(the_queue.begin(), the_queue.begin()+1);
buzzer_bucket.push_back(buzzer);
return buzzer;
}
}

/**
* function: kick_out()
*
* description: Some times buzzer holders cause trouble and
* a bouncer needs to take back their buzzer and
* tell them to get lost.
*
* Specifially:
*
* If the buzzer given by the 2nd parameter is
* in the queue, the buzzer is removed (and the
* buzzer can now be re-used) and 1 (one) is
* returned (indicating success).
*
* Return: If the buzzer isn’t actually currently in the
* queue, the queue is unchanged and false is returned
* (indicating failure). Otherwise, true is returned.
*
* RUNTIME REQUIREMENT: O(1)
*/
bool kick_out(int buzzer) {
std::vector<int>::iterator it;

it = find(the_queue.begin(), the_queue.end(), buzzer);
if(it == the_queue.end())
return false;
else {
the_queue.erase(it);
buzzer_bucket.push_back(buzzer);
return true;
}
}

/**
* function: take_bribe()
* description: some people just don’t think the rules of everyday
* life apply to them! They always want to be at
* the front of the line and don’t mind bribing
* a bouncer to get there.
*
* In terms of the function:
*
* – if the given buzzer is in the queue, it is
* moved from its current position to the front
* of the queue. 1 is returned indicating success
* of the operation.
* – if the buzzer is not in the queue, the queue
* is unchanged and 0 is returned (operation failed).
*
* Return: If the buzzer isn’t actually currently in the
* queue, the queue is unchanged and false is returned
* (indicating failure). Otherwise, true is returned.
*
* RUNTIME REQUIREMENT: O(1)
*/
bool take_bribe(int buzzer) {
std::vector<int>::iterator it;

it = find(the_queue.begin(), the_queue.end(), buzzer);
if(it == the_queue.end())
return false;
else {
the_queue.erase(it);
the_queue.insert(the_queue.begin(), buzzer);
return true;
}
}

}; // end ServiceQueue class

#endif

ServiceQueueSlow2.h

#ifndef _SERVICE_QUEUE_H
#define _SERVICE_QUEUE_H

#include <iostream>
#include <vector>
#include <utility>

/**
* Implementation of the ServiceQueue ADT meeting
* behavioral requirements, but not all runtime
* requirements.
*/

class ServiceQueue {

private:
std::vector<int> the_queue; // idx-0 is front of queue

std::vector<int> buzzer_bucket; // keeps track of buzzer-IDs
// that can be reused. Operates
// as a stack so buzzer that became
// reusable most recently is on
// top (i.e., at back of vector).

public:

/**
* Constructor
* Description: intializes an empty service queue.
*
* RUNTIME REQUIREMENT: O(1)
*
* TODO
*/
ServiceQueue() {

// Nothing for us to do here since vector constructors
// will be automatically applied to data members.
}

/**
* Destructor
* Description: deallocates all memory assciated
* with service queue
*
* RUNTIME REQUIREMENT: O(N_b) where N_b is the number of buzzer
* IDs that have been used during the lifetime of the
* service queue; in general, at any particular instant
* the actual queue length may be less than N_b.
*
* [See discussion of “re-using buzzers” below]
*
* TODO
*/
~ServiceQueue() {

// again, nothing for us to do here.
// vector destructors automatically applied to
// data members
}

/**
* Function: snapshot()
* param: buzzers is an integer vector passed by ref
* Description: populates buzzers vector with a “snapshot”
* of the queue as a sequence of buzzer IDs
*
*
* RUNTIME REQUIREMENT: O(N) (where N is the current queue
* length).
*/
void snapshot(std::vector<int> &buzzers) {
buzzers.clear(); // you don’t know the history of the
// buzzers vector, so we had better
// clear it first.

// Note: the vector class over-rides the assignment operator ‘=’
// and does an element-by-element copy from the RHS vector (the_vector)
// in this case) to the LHS vector (buzzers) in this case).

buzzers = the_queue;

}

/**
* Function: length()
* Description: returns the current number of
* entries in the queue.
*
* RUNTIME REQUIREMENT: O(1)
*/
int length() {

return the_queue.size(); // placeholder

}

/**
* Function: give_buzzer()
* Return: buzzer-ID (integer) assigned to the new customer.
* Description: This is the “enqueue” operation. For us
* a “buzzer” is represented by an integer (starting
* from zero). The function selects an available buzzer
* and places a new entry at the end of the service queue
* with the selected buzer-ID.
* This buzzer ID is returned.
* The assigned buzzer-ID is a non-negative integer
* with the following properties:
*
* (1) the buzzer (really it’s ID) is not currently
* taken — i.e., not in the queue. (It
* may have been in the queue at some previous
* time — i.e., buzzer can be re-used).
* This makes sense: you can’t give the same
* buzzer to two people!
*
* (2) Reusable Buzzers: A re-usable buzzer is
* a buzzer that _was_ in the queue at some previous
* time, but currently is not.
*
* REQUIREMENT: If there is one or more reusable
* buzzer, you MUST return one of them; furthermore,
* it must be the buzzer that became reusable most
* MOST RECENTLY.
*
* (3) if there are no previously-used / reusable buzzers,
* the SMALLEST possible buzzer-ID is used (retrieved from
* inventory).
* Properties in this situation (where N is the current
* queue length):
*
* – The largest buzzer-ID used so far is N-1
*
* – All buzzer-IDs in {0..N-1} are in the queue
* (in some order).
*
* – The next buzzer-ID (from the basement) is N.
*
* In other words, you can always get more buzzers (from
* the basement or something), but you don’t fetch an
* additional buzzer unless you have to (i.e., no reusable buzzers).
*
* Comments/Reminders:
*
* Rule (3) implies that when we start from an empty queue,
* the first buzzer-ID will be 0 (zero).
*
* Rule (2) does NOT require that the _minimum_ reuseable
* buzzer-ID be used. If there are multiple reuseable buzzers,
* any one of them will do.
*
* Note the following property: if there are no re-useable
* buzzers, the queue contains all buzzers in {0..N-1} where
* N is the current queue length (of course, the buzzer IDs
* may be in any order.)
*
* RUNTIME REQUIREMENT: O(1) ON AVERAGE or “AMORTIZED”
* In other words, if there have been M calls to
* give_buzzer, the total time taken for those
* M calls is O(M).
*
* An individual call may therefore not be O(1) so long
* as when taken as a whole they average constant time.
*
*/
int give_buzzer() {
int b;

// take top reusable buzzer if possible
if(buzzer_bucket.size() != 0) {
b = buzzer_bucket.back();
buzzer_bucket.pop_back();
}
// otherwise, queue must contain exactly buzzers
// 0..the_queue.size()-1
// and therefore, the next smallest buzzer must be
// the_queue.size()
else {
b = the_queue.size();
}
the_queue.push_back(b);
return b;
}

private:
// “slides” elements from index idx+1 to end of vector
// one position to the left (over-writing element at
// position idx).
// final pop_back is to remove duplicate element (or elem
// at position idx in the event that idx==vec.size()-1)
static void slide_left(std::vector<int> &vec, int idx){
int n=vec.size();
for(int i=idx; i<n-1; i++)
vec[i]=vec[i+1];
vec.pop_back();
}

// returns index of first vector entry containing x
// if x does not appear, -1 is returned
static int find(std::vector<int> &vec, int x){

for(unsigned int i=0; i<vec.size(); i++) {
if(vec[i]==x)
return i;
}
return -1;
}

static void push_front(std::vector<int> &vec, int val){

if(vec.size()==0)
vec.push_back(val);
else {
vec.push_back(vec.back()); // make new entry at end
// now slide everything one slot to right
for(int i=vec.size()-1; i>0; i–) {
vec[i]=vec[i-1];
}
// now we can overwrite slot zero with value to push
vec[0] = val;
}
}

public:

/**
* function: seat()
* description: if the queue is non-empty, it removes the first
* entry from (front of queue) and returns the
* buzzer ID.
* Note that the returned buzzer can now be re-used.
*
* If the queue is empty (nobody to seat), -1 is returned to
* indicate this fact.
*
* Returns: buzzer ID of dequeued customer, or -1 if queue is empty.
*
* RUNTIME REQUIREMENT: O(1)
*/
int seat() {
int buzzer;

if(the_queue.size()==0)
return -1;
else {
buzzer = the_queue[0];

slide_left(the_queue, 0);
buzzer_bucket.push_back(buzzer);
return buzzer;
}
}

/**
* function: kick_out()
*
* description: Some times buzzer holders cause trouble and
* a bouncer needs to take back their buzzer and
* tell them to get lost.
*
* Specifially:
*
* If the buzzer given by the 2nd parameter is
* in the queue, the buzzer is removed (and the
* buzzer can now be re-used) and 1 (one) is
* returned (indicating success).
*
* Return: If the buzzer isn’t actually currently in the
* queue, the queue is unchanged and false is returned
* (indicating failure). Otherwise, true is returned.
*
* RUNTIME REQUIREMENT: O(1)
*/
bool kick_out(int buzzer) {
int idx;

idx = find(the_queue, buzzer);
if(idx == -1)
return false;
else {
slide_left(the_queue,idx);
buzzer_bucket.push_back(buzzer);
return true;
}
}

/**
* function: take_bribe()
* description: some people just don’t think the rules of everyday
* life apply to them! They always want to be at
* the front of the line and don’t mind bribing
* a bouncer to get there.
*
* In terms of the function:
*
* – if the given buzzer is in the queue, it is
* moved from its current position to the front
* of the queue. 1 is returned indicating success
* of the operation.
* – if the buzzer is not in the queue, the queue
* is unchanged and 0 is returned (operation failed).
*
* Return: If the buzzer isn’t actually currently in the
* queue, the queue is unchanged and false is returned
* (indicating failure). Otherwise, true is returned.
*
* RUNTIME REQUIREMENT: O(1)
*/
bool take_bribe(int buzzer) {
int idx;

idx = find(the_queue, buzzer);
if(idx == -1)
return false;
else {
slide_left(the_queue,idx);
push_front(the_queue, buzzer);
return true;
}
}

}; // end ServiceQueue class

#endif

Driver.cpp

#include <stdio.h>
#include <stdlib.h>

/* FILE: Driver.cpp
* desc: simple menu-based interactive program which lets user exercise
* the ServiceQueue class functions, inspect the queue, etc.
*/

// The #ifdef directives below enables compilation using different
// implementations of the ServiceQueue class.
//
// Default compilation uses the ServiceQueue.h implementation:
//
// g++ -std=c++11 Driver.cpp -o Driver
//
// Compilation which sets the _SLOW preprocessor variable uses the
// ServiceQueueSlow.h implementation:
//
// g++ -std=c++11 -D_SLOW Driver.cpp -o DriverSlow
//
// Compilation which sets the _SLOW2 preprocessor variable uses the
// ServiceQueueSlow2.h implementation:
//
// g++ -std=c++11 -D_SLOW2 Driver.cpp -o DriverSlow2

#ifdef _SLOW
#include “ServiceQueueSlow.h”
std::string SourceFile = “ServiceQueueSlow.h”;
#define __IMPL_INCL
#endif

#ifdef _SLOW2
#ifndef __IMPL_INCL
#include “ServiceQueueSlow2.h”
std::string SourceFile = “ServiceQueueSlow2.h”;
#define __IMPL_INCL
#endif
#endif

#ifndef __IMPL_INCL
#include “ServiceQueue.h”
std::string SourceFile = “ServiceQueue.h”;
#define __IMPL_INCL
#endif

void display(ServiceQueue &q) {
std::vector<int> snap;

q.snapshot(snap);

std::cout << ” [ “;
for(int b : snap) {
std::cout << b << ” “;
}
std::cout << “] ” << std::endl;
}

/**
* takes a full line of user input and
* parses it.
*
* Executes specified command and prints appropriate
* message if syntactially correct.
* otherwise prints an error message.
*
* Returns 1 only to indicate the the quite command ‘q’ was
* entered.
* Otherwise, 0 is returned.
*/
int execute_cmd(ServiceQueue &q, char *buf) {
int tok;
char cmd;
int buzzer;
char junk[128];

// tok stores number of tokens parsed
// Note that all commands have either one or two ‘tokens’:
// example: b 8
// ‘b’ is the first token and ‘8’ is the 2nd
// junk array is used to detect if an extraneous 3rd argument
// has been entered (parse error).
tok = sscanf(buf, ” %c %i %s”, &cmd, &buzzer, junk);

if(tok==0) return 0;
if(tok > 2){
printf(” bad command. try again\n”);
return 0;
}

switch (cmd) {
case ‘q’:
if(tok != 1){
printf(” bad command. try again\n”);
return 0;
}
else{
printf(” goodbye…\n”);
return 1;
}
case ‘d’ :
if(tok != 1)
printf(” bad command. try again\n”);
else
display(q);
return 0;
case ‘l’:
if(tok != 1)
printf(” bad command. try again\n”);
else
printf(” len: %i\n”, q.length());
return 0;
case ‘g’:
if(tok != 1)
printf(” bad command. try again\n”);
else
printf(” buzzer: %i\n”, q.give_buzzer());
return 0;
case ‘s’:
if(tok != 1)
printf(” bad command. try again\n”);
else{
buzzer = q.seat();
if(buzzer != -1)
printf(” seating buzzer: %i\n”, buzzer);
else
printf(” sorry, queue is empty\n”);
}
return 0;
case ‘k’:
if(tok != 2)
printf(” bad command. try again\n”);
else {
if(q.kick_out(buzzer))
printf(” %i is outta here!\n”, buzzer);
else
printf(” could not remove tkt %i!\n”, buzzer);
}
return 0;
case ‘b’:
if(tok != 2)
printf(” bad command. try again\n”);
else {
if(q.take_bribe( buzzer))
printf(” VIP coming through!\n”);
else
printf(” Get in line, then bribe me!\n”);

}
return 0;
default:
printf(” bad command. try again\n”);
return 0;
}
}

int main() {
ServiceQueue q;
char buf[128];
int done = 0;

printf(“\nWelcome to the simple service-queue interactive program\n”);
printf(“\n (SOURCE FILE USED FOR ServiceQueue CLASS: %s)\n\n”, SourceFile.c_str());
printf(” An empty service queue has been created for you\n”);
printf(” Commands:\n”);
printf(” d : display queue\n”);
printf(” l : report length of queue\n”);
printf(” g : give out a buzzer\n”);
printf(” s : serve the first buzzer in line\n”);
printf(” k <buzzer> : kick specified buzzer out!\n”);
printf(” b <buzzer> : take a bribe to move specified buzzer to front!\n”);
printf(” q : quit\n”);
printf(“———————————–\n\n”);

while(!done) {
printf(“cmd > “);
if(fgets(buf, 127, stdin) != NULL) {
if(execute_cmd(q, buf))
done = 1;
}
}
return 0;
}