List & Queue help. I need help implementing the countOff() method in my QueueMain.cpp program.

Here is the problem to solve:

During the Civil War, a group of Confederate officers are in a clandestine meeting when they suddenly discover they are surrounded by an overwhelming Union force. There is absolutely no hope for victory without reinforcements, and Stonewall Jackson's horse, Little Sorrel, is the only horse available that can be used to escape and summon help. The officers agree to a pact to determine which of them is to go for help.

The officers form a queue and they pick a number from a hat. Beginning with the first officer in the queue, they begin to count. As each officer counts off, he moves to the end of the queue. When the count reaches the number that was picked, that officer is removed from the queue, and the count begins again with the next man. Once an officer is removed from the queue, he is no longer counted. The last officer that remains in the queue is the one that rides away on Little Sorrel to summon help.

The process continues in this way until only one officer remains in the queue. The last officer remaining in the queue is the one that goes for help.

In the QueueMain.cpp, the countOff() method displays the name of each officer removed from the queue, in the order in which they are removed, and displays the name of the officer that goes for help.

The countOff() method cannot create a data structure; it MUST use the LinkedQueue data structure named officers, which is passed as an argument. ONLY the countOff() method should be modified. No other modifications to the included files should be made. An assignment without using the LinkedQueue receives 0.

You will use the text file, officers.txt, in the Lab6Files folder to test your program. Your output should not be the same as the example shown above in the description because you use the full set of data from the text file in the folder and test the program with different cutoff numbers.

Your output (including the order of the officers leaving the queue) MUST be the same as of the following:

Officers in original queue: Bate, William Brimage, Major General Beauregard, Pierre Gustave Toutant, General Bowen, John Stevens, Major General Bragg, Braxton, General Brown, John Calvin, Major General Buckner, Simon Bolivar, Major General Cheatham, Benjamin Franklin, Major General Cleburne, Patrick Ronayne, Major General Cooper, Samuel, General Early, Jubal Anderson, Lieutenant General Elzey, Arnold, Major General Ewell, Richard Stoddert, Lieutenant General Forney, John Horace, Major General Forrest, Nathan Bedford, Lieutenant General French, Samuel Gibbs, Major General Gardner, Franklin, Major General Gordon, John Brown, Major General Hardee, William Joseph, Lieutenant General Hays, Harry Thompson, Major General Heth, Henry, Major General Hill, Ambrose Powell, Lieutenant General, Corps Commander Hindman, Thomas Carmichael, Major General Hoke, Robert Frederick, Major General Hood, John Bell, General Huger, Benjamin, Major General Jackson, Thomas Jonathan 'Stonewall', Major General Johnson, Bushrod Rust, Major General Johnson, Edward, Major General Johnston, Albert Sidney, General Johnston, Joseph Eggleston, General Jones, Samuel, Major General Kershaw, Joseph Brevard, Major General Lee, Fitzhugh, Major General Lee, George Washington Custis, Major General Lee, Robert Edward, General Lee, William Henry Fitzhugh, Major General Longstreet, James, Lieutenant General Loring, William Wing, Major General Lovell, Mansfield, Major General Magruder, John Bankhead, Major General Mahone, William, Major General Marie, Camille Armand Jules, Major General Marmaduke, John Sappington, Major General Maury, Dabney Herndon, Major General McLaws, Lafayette, Major General Pender, William Dorsey, Major General Pike, Albert, Brigadier General Polk, Leonidas, Major General Price, Sterling, Major General Rodes, Robert Emmett, Major General Rosser, Thomas Lafayette, Major General Smith, Edmund Kirby, General Smith, Martin Luther, Major General Stevenson, Carter Littlepage, Major General Stuart, James Ewell Brown 'JEB', General Taylor, Richard, Lieutenant General Van Dorn, Earl, Major General Walthall, Edward Cary, Major General Wharton, John Austin, Major General Wheeler, Joseph, Major General Wilcox, Cadmus Marcellus, Major General Withers, Jones Mitchell, Major General Count is: 5 The officers leaving the queue are: Brown, John Calvin, Major General Early, Jubal Anderson, Lieutenant General French, Samuel Gibbs, Major General Heth, Henry, Major General Huger, Benjamin, Major General Johnston, Joseph Eggleston, General Lee, Robert Edward, General Magruder, John Bankhead, Major General McLaws, Lafayette, Major General Rodes, Robert Emmett, Major General Stuart, James Ewell Brown 'JEB', General Wheeler, Joseph, Major General Bowen, John Stevens, Major General Cooper, Samuel, General Gardner, Franklin, Major General Hindman, Thomas Carmichael, Major General Johnson, Edward, Major General Lee, George Washington Custis, Major General Mahone, William, Major General Pike, Albert, Brigadier General Smith, Martin Luther, Major General Wharton, John Austin, Major General Bragg, Braxton, General Ewell, Richard Stoddert, Lieutenant General Hays, Harry Thompson, Major General Johnson, Bushrod Rust, Major General Lee, William Henry Fitzhugh, Major General Marmaduke, John Sappington, Major General Rosser, Thomas Lafayette, Major General Walthall, Edward Cary, Major General Buckner, Simon Bolivar, Major General Forrest, Nathan Bedford, Lieutenant General Hood, John Bell, General Lee, Fitzhugh, Major General Maury, Dabney Herndon, Major General Stevenson, Carter Littlepage, Major General Bate, William Brimage, Major General Forney, John Horace, Major General Jackson, Thomas Jonathan 'Stonewall', Major General Loring, William Wing, Major General Price, Sterling, Major General Withers, Jones Mitchell, Major General Gordon, John Brown, Major General Jones, Samuel, Major General Pender, William Dorsey, Major General Wilcox, Cadmus Marcellus, Major General Hardee, William Joseph, Lieutenant General Longstreet, James, Lieutenant General Taylor, Richard, Lieutenant General Elzey, Arnold, Major General Lovell, Mansfield, Major General Beauregard, Pierre Gustave Toutant, General MMMJohnston, Albert Sidney, General Van Dorn, Earl, Major General Kershaw, Joseph Brevard, Major General Cleburne, Patrick Ronayne, Major General Smith, Edmund Kirby, General Polk, Leonidas, Major General Cheatham, Benjamin Franklin, Major General Hoke, Robert Frederick, Major General Marie, Camille Armand Jules, Major General The officer going for help is: Hill, Ambrose Powell, Lieutenant General, Corps Commander Count is: 8 The officers leaving the queue are: Cleburne, Patrick Ronayne, Major General Gardner, Franklin, Major General Hood, John Bell, General Kershaw, Joseph Brevard, Major General Magruder, John Bankhead, Major General Polk, Leonidas, Major General Taylor, Richard, Lieutenant General Beauregard, Pierre Gustave Toutant, General Elzey, Arnold, Major General Heth, Henry, Major General Johnston, Albert Sidney, General Loring, William Wing, Major General Pike, Albert, Brigadier General Van Dorn, Earl, Major General Bragg, Braxton, General Forrest, Nathan Bedford, Lieutenant General Huger, Benjamin, Major General Lee, Robert Edward, General McLaws, Lafayette, Major General Stuart, James Ewell Brown 'JEB', General Brown, John Calvin, Major General Gordon, John Brown, Major General Johnson, Edward, Major General Mahone, William, Major General Smith, Edmund Kirby, General Bate, William Brimage, Major General French, Samuel Gibbs, Major General Johnston, Joseph Eggleston, General Marmaduke, John Sappington, Major General Walthall, Edward Cary, Major General Cooper, Samuel, General Hoke, Robert Frederick, Major General Lovell, Mansfield, Major General Stevenson, Carter Littlepage, Major General Early, Jubal Anderson, Lieutenant General Johnson, Bushrod Rust, Major General Pender, William Dorsey, Major General Withers, Jones Mitchell, Major General Hill, Ambrose Powell, Lieutenant General, Corps Commander Marie, Camille Armand Jules, Major General Wilcox, Cadmus Marcellus, Major General Hindman, Thomas Carmichael, Major General Price, Sterling, Major General Cheatham, Benjamin Franklin, Major General Lee, George Washington Custis, Major General Wheeler, Joseph, Major General Jones, Samuel, Major General Wharton, John Austin, Major General Lee, Fitzhugh, Major General Buckner, Simon Bolivar, Major General Maury, Dabney Herndon, Major General Hays, Harry Thompson, Major General Ewell, Richard Stoddert, Lieutenant General Smith, Martin Luther, Major General Rosser, Thomas Lafayette, Major General Bowen, John Stevens, Major General Hardee, William Joseph, Lieutenant General Longstreet, James, Lieutenant General Lee, William Henry Fitzhugh, Major General Forney, John Horace, Major General Rodes, Robert Emmett, Major General The officer going for help is: Jackson, Thomas Jonathan 'Stonewall', Major General

QueueInterface.h

#ifndef _QUEUE_INTERFACE #define _QUEUE_INTERFACE

template class QueueInterface

{ public: /** Sees whether this queue is empty. @return True if the queue is empty, or false if not. */ virtual bool isEmpty() const = 0; /** Adds a new entry to the back of this queue. @post If the operation was successful, newEntry is at the back of the queue. @param newEntry The object to be added as a new entry. @return True if the addition is successful or false if not. */ virtual bool enqueue(const ItemType& newEntry) = 0; /** Removes the front of this queue. @post If the operation was successful, the front of the queue has been removed. @return True if the removal is successful or false if not. */ virtual bool dequeue() = 0; /** Returns the front of this queue. @pre The queue is not empty. @post The front of the queue has been returned, and the queue is unchanged. @return The front of the queue. */ virtual ItemType peekFront() const = 0; }; // end QueueInterface #endif

Node.h

#ifndef _NODE #define _NODE

template class Node { private: ItemType item; // A data item Node* next; // Pointer to next node public: Node(); Node(const ItemType& anItem); Node(const ItemType& anItem, Node* nextNodePtr); void setItem(const ItemType& anItem); void setNext(Node* nextNodePtr); ItemType getItem() const ; Node* getNext() const ; }; // end Node

#include "Node.cpp" #endif

LinkedQueue.h

#ifndef _LINKED_QUEUE

#define _LINKED_QUEUE

#include "QueueInterface.h"

#include "Node.h"

#include "PrecondViolatedExcep.h"

template

class LinkedQueue : public QueueInterface

{

private:

// The queue is implemented as a chain of linked nodes that has

// two external pointers, a head pointer for front of the queue and

// a tail pointer for the back of the queue.

Node* backPtr;

Node* frontPtr;

public:

LinkedQueue();

LinkedQueue (const LinkedQueue& aQueue);

~LinkedQueue();

bool isEmpty() const;

bool enqueue(const ItemType& newEntry);

bool dequeue();

/** @throw PrecondViolatedExcep if the queue is empty */

ItemType peekFront() const throw(PrecondViolatedExcep);

}; // end LinkedQueue

#include "LinkedQueue.cpp"

#endif

PrecondViolatedExcep.h

#ifndef _PRECOND_VIOLATED_EXCEP #define _PRECOND_VIOLATED_EXCEP

#include #include

using namespace std;

class PrecondViolatedExcep : public logic_error { public: PrecondViolatedExcep(const string& message = ""); }; // end PrecondViolatedExcep #endif

Node.cpp

#include "Node.h" #include

template Node::Node() : next(nullptr) { } // end default constructor

template Node::Node(const ItemType& anItem) : item(anItem), next(nullptr) { } // end constructor

template Node::Node(const ItemType& anItem, Node* nextNodePtr) : item(anItem), next(nextNodePtr) { } // end constructor

template void Node::setItem(const ItemType& anItem) { item = anItem; } // end setItem

template void Node::setNext(Node* nextNodePtr) { next = nextNodePtr; } // end setNext

template ItemType Node::getItem() const { return item; } // end getItem

template Node* Node::getNext() const { return next; } // end getNext

LinkedQueue.cpp

#include "LinkedQueue.h"

#include

template

LinkedQueue::LinkedQueue()

{

backPtr = nullptr;

frontPtr = nullptr;

} // end default constructor

template

LinkedQueue::LinkedQueue(const LinkedQueue& aQueue)

{ // Implementation left as an exercise (Exercise 1).

Node* origChainPtr = aQueue.frontPtr; // Points to nodes in original chain

if (origChainPtr == nullptr)

{

frontPtr = nullptr; // Original queue is empty

backPtr = nullptr;

}

else

{

// Copy first node

frontPtr = new Node();

frontPtr->setItem(origChainPtr->getItem());

// Advance original-chain pointer

origChainPtr = origChainPtr->getNext();

// Copy remaining nodes

Node* newChainPtr = frontPtr; // Points to last node in new chain

while (origChainPtr != nullptr)

{

// Get next item from original chain

ItemType nextItem = origChainPtr->getItem();

// Create a new node containing the next item

Node* newNodePtr = new Node(nextItem);

// Link new node to end of new chain

newChainPtr->setNext(newNodePtr);

// Advance pointers

newChainPtr = newChainPtr->getNext();

origChainPtr = origChainPtr->getNext();

} // end while

newChainPtr->setNext(nullptr); // Flag end of chain

backPtr = newChainPtr;

} // end if

} // end copy constructor

template

LinkedQueue::~LinkedQueue()

{

while (!isEmpty())

dequeue();

assert ( (backPtr == nullptr) && (frontPtr == nullptr) );

} // end destructor

template

bool LinkedQueue::isEmpty() const

{

return backPtr == nullptr;

} // end isEmpty

template

bool LinkedQueue::enqueue(const ItemType& newEntry)

{

Node* newNodePtr = new Node(newEntry);

// Insert the new node

if (isEmpty())

frontPtr = newNodePtr; // Insertion into empty queue

else

backPtr->setNext(newNodePtr); // Insertion into nonempty queue

backPtr = newNodePtr; // New node is at back

return true;

} // end enqueue

template

bool LinkedQueue::dequeue()

{

bool result = false;

if (!isEmpty())

{

// Queue is not empty; delete front

Node* nodeToDeletePtr = frontPtr;

if (frontPtr == backPtr)

{ // Special case: one node in queue

frontPtr = nullptr;

backPtr = nullptr;

}

else

frontPtr = frontPtr->getNext();

// Return deleted node to system

nodeToDeletePtr->setNext(nullptr);

delete nodeToDeletePtr;

nodeToDeletePtr = nullptr;

result = true;

} // end if

return result;

} // end dequeue

template

ItemType LinkedQueue::peekFront() const throw(PrecondViolatedExcep)

{

if (isEmpty())

throw PrecondViolatedExcep("getFront() called with empty queue.");

// Queue is not empty; return front

return frontPtr->getItem();

} // end peekFront

// End of implementation file.

PrecondViolatedExcep.cpp

#include "PrecondViolatedExcep.h"

PrecondViolatedExcep::PrecondViolatedExcep(const string& message): logic_error("Precondition Violated Exception: " + message) { } // end constructor

// End of implementation file.

QueueMain.cpp

#include

#include

#include

#include

#include

#include

#include "LinkedQueue.h"

using namespace std;

/**

* Name of input file containing officer names

*/

const char INPUT_FILE[] = "officers.txt";

/**

* Inputs data from a text file and places each officer's name into the

* queue passed as a parameter.

* @param officers - dynamic queue of Confederate officers in the Civil War

*/

void loadQueue(LinkedQueue &officers);

/**

* Displays a list of officers removed from the queue and also displays

* the name of the officer going for help. Retrieves officers from the

* officers queue, one at a time, counting as each is retrieved. If the

* count is not equal to hatNumber, the officer is put back into the

* queue. When the count reaches hatNumber, that officer is removed from

* the queue permanently (i.e., not put back into the queue), and the

* officer's name is output to the screen. The last officer remaining in

* the queue is the one shown as going for help.

* @param officers - dynamic queue of Confederate officers in the Civil War

* @param hatNumber - the number drawn from the hat, used to count off

*/

void countOff (LinkedQueue officers, int hatNumber);

int main (void)

{

ifstream inFile(INPUT_FILE); // declare and open the input file

int count; // number used for counting off

LinkedQueue officers; // queue containing officer names

string officerName; // name of officer in front of queue

string firstName; // name of first officer in original queue

loadQueue(officers);

// Display list of officers in original queue

cout << "Officers in original queue: " << endl;

firstName = officers.peekFront();

cout << firstName << endl;

officers.dequeue();

officers.enqueue(firstName);

officerName = officers.peekFront();

while (firstName != officerName)

{

cout << officerName << endl;

officers.dequeue();

officers.enqueue(officerName);

officerName = officers.peekFront();

}

// Test countOff() method using various numbers drawn from the hat

count = 5;

cout << endl << endl<< "Count is: " << count << endl;

countOff (officers, count);

count = 8;

cout << endl << endl << "Count is: " << count << endl;

countOff (officers, count);

return EXIT_SUCCESS;

}

void loadQueue(LinkedQueue &officers)

{

ifstream inFile(INPUT_FILE); // declare and open the input file

string officerName; // name of officer input from file

if (!inFile)

cout << "Error opening file for input: " << INPUT_FILE << endl;

else

{

getline (inFile, officerName);

while (!inFile.eof())

{

officers.enqueue(officerName);

getline (inFile, officerName);

}

inFile.close();

}

}

void countOff (LinkedQueue officers, int count)

{

// This method must be implemented

}

officers

Bate, William Brimage, Major General Beauregard, Pierre Gustave Toutant, General Bowen, John Stevens, Major General Bragg, Braxton, General Brown, John Calvin, Major General Buckner, Simon Bolivar, Major General Cheatham, Benjamin Franklin, Major General Cleburne, Patrick Ronayne, Major General Cooper, Samuel, General Early, Jubal Anderson, Lieutenant General Elzey, Arnold, Major General Ewell, Richard Stoddert, Lieutenant General Forney, John Horace, Major General Forrest, Nathan Bedford, Lieutenant General French, Samuel Gibbs, Major General Gardner, Franklin, Major General Gordon, John Brown, Major General Hardee, William Joseph, Lieutenant General Hays, Harry Thompson, Major General Heth, Henry, Major General Hill, Ambrose Powell, Lieutenant General, Corps Commander Hindman, Thomas Carmichael, Major General Hoke, Robert Frederick, Major General Hood, John Bell, General Huger, Benjamin, Major General Jackson, Thomas Jonathan 'Stonewall', Major General Johnson, Bushrod Rust, Major General Johnson, Edward, Major General Johnston, Albert Sidney, General Johnston, Joseph Eggleston, General Jones, Samuel, Major General Kershaw, Joseph Brevard, Major General Lee, Fitzhugh, Major General Lee, George Washington Custis, Major General Lee, Robert Edward, General Lee, William Henry Fitzhugh, Major General Longstreet, James, Lieutenant General Loring, William Wing, Major General Lovell, Mansfield, Major General Magruder, John Bankhead, Major General Mahone, William, Major General Marie, Camille Armand Jules, Major General Marmaduke, John Sappington, Major General Maury, Dabney Herndon, Major General McLaws, Lafayette, Major General Pender, William Dorsey, Major General Pike, Albert, Brigadier General Polk, Leonidas, Major General Price, Sterling, Major General Rodes, Robert Emmett, Major General Rosser, Thomas Lafayette, Major General Smith, Edmund Kirby, General Smith, Martin Luther, Major General Stevenson, Carter Littlepage, Major General Stuart, James Ewell Brown 'JEB', General Taylor, Richard, Lieutenant General Van Dorn, Earl, Major General Walthall, Edward Cary, Major General Wharton, John Austin, Major General Wheeler, Joseph, Major General Wilcox, Cadmus Marcellus, Major General Withers, Jones Mitchell, Major General