C++ code

The people who run the Motor Vehicle Department (MVD) have a problem. They are concerned that people do not spend enough time waiting in lines to appreciate the privilege of owning and driving an automobile. The current arrangement is as follows:

When people walk in the door, they must wait in a line to sign in.

Once they have signed in, they are told either to stand in line for registration renewal or to wait until they are called for license renewal.

O nce they have completed their desired transaction, they must go and wait in line for the cashier.

When they nally get to the front of the cashiers line, if they expect to pay by check, they are told that all checks must get approved. To do this, it is necessary to go to the check-approvers table and then reenter the cashiers line at the end.

Write an event-driven simulation to help the MVD gather statistics. Each line of input will contain

A desired transaction code ( L for license renewal, R for registration renewal)

A method-of-payment code ( $ for cash, C for check)

A n arrival time (integer)

A name

Write out the speci cs of each event (when, who, what, and so on). Then display these nal statistics:

The total number of license renewals and the average time spent in MVD (arrival until completion of payment) to renew a license

The total number of registration renewals and the average time spent in MVD (arrival until completion of payment) to renew a registration

I ncorporate the following details into your program:

De ne the following events: arrive, sign in, renew license, renew registration, and cope with the cashier (make a payment or nd out about check approval).

In the case of a tie, let the order of events be determined by the list of events just giventhat is, arrivals have the highest priority.

A ssume that the various transactions take the following amounts of time:

Sign in 10 seconds

Renew license 90 seconds

Register automobile 60 seconds

See cashier (payment) 30 seconds

See cashier (check not approved) 10 seconds

As ridiculous as it may seem, the people waiting for license renewal are called in alphabetical order. Note, however, that people are not pushed back once their transactions have started.

For the sake of this simulation, you can assume that checks are approved instantly. Therefore, the rule for arriving at the front of the cashiers line with a check that has not been approved is to go to the back of the cashiers line with a check that has been approved.

*Please use PriorityQueue

SL_PriorityQueue.h

#ifndef _PRIORITY_QUEUE

#define _PRIORITY_QUEUE

#include "PriorityQueueInterface.h"

#include "LinkedSortedList.h"

#include "PrecondViolatedExcep.h"

template

class SL_PriorityQueue : public PriorityQueueInterface

{

private:

LinkedSortedList* slistPtr; // Pointer to sorted list of

// items in the priority queue

public:

SL_PriorityQueue();

SL_PriorityQueue(const SL_PriorityQueue& pq);

~SL_PriorityQueue();

bool isEmpty() const;

bool add(const ItemType& newEntry);

bool remove();

/** @throw PrecondViolatedExcep if priority queue is empty. */

ItemType peek() const throw(PrecondViolatedExcep);

//cpp

template

SL_PriorityQueue::SL_PriorityQueue()

{

slistPtr = new LinkedSortedList();

} // end default constructor

template

SL_PriorityQueue::SL_PriorityQueue(const SL_PriorityQueue& pq)

{

// First, create our own sorted list

slistPtr = new LinkedSortedList();

// Then add items to it using public methods

LinkedSortedList.h

#ifndef _LINKED_SORTED_LIST

#define _LINKED_SORTED_LIST

#include "SortedListInterface.h"

#include "Node.h"

#include "PrecondViolatedExcep.h"

#include

template

class LinkedSortedList : public SortedListInterface

{

private:

Node* headPtr; // Pointer to first node in the chain

int itemCount; // Current count of list items

// Locates the node that is before the node that should or does

// contain the given entry.

// @param anEntry The entry to find.

// @return Either a pointer to the node before the node that contains

// or should contain the given entry, or nullptr if no prior node exists.

Node* getNodeBefore(const ItemType& anEntry) const;

// Locates the node at a given position within the chain.

Node* getNodeAt(int position) const;

// Returns a pointer to a copy of the chain to which origChainPtr points.

Node* copyChain(const Node* origChainPtr);

public:

LinkedSortedList();

LinkedSortedList(const LinkedSortedList& aList);

virtual ~LinkedSortedList();

void insertSorted(const ItemType& newEntry);

bool removeSorted(const ItemType& anEntry);

int getPosition(const ItemType& newEntry) const;

// The following methods are the same as given in ListInterface:

bool isEmpty() const;

int getLength() const;

bool remove(int position);

void clear();

ItemType getEntry(int position) const throw(PrecondViolatedExcep);

//cpp

template

LinkedSortedList::LinkedSortedList() : headPtr(nullptr), itemCount(0)

{

} // end default constructor

template

LinkedSortedList::LinkedSortedList(const LinkedSortedList& aList)

{

headPtr = copyChain(aList.headPtr);

itemCount = aList.itemCount;

} // end copy constructor

template

Node* LinkedSortedList::copyChain(const Node* origChainPtr)

{

Node* copiedChainPtr = nullptr;

if (origChainPtr != nullptr)

{

// Build new chain from given one

copiedChainPtr = new Node(origChainPtr->getItem());

copiedChainPtr->setNext(copyChain(origChainPtr->getNext()));

} // end if

return copiedChainPtr;

} // end copyChain

template

LinkedSortedList::~LinkedSortedList()

{

clear();

} // end destructor

template

void LinkedSortedList::insertSorted(const ItemType& newEntry)

{

Node* newNodePtr = new Node(newEntry);

Node* prevPtr = getNodeBefore(newEntry);

if (isEmpty() || (prevPtr == nullptr)) // Add at beginning

{

newNodePtr->setNext(headPtr);

headPtr = newNodePtr;

}

else // Add after node before

{

Node* aftPtr = prevPtr->getNext();

newNodePtr->setNext(aftPtr);

prevPtr->setNext(newNodePtr);

} // end if

itemCount++;

} // end insertSorted

template

bool LinkedSortedList::removeSorted(const ItemType& anEntry)

{

bool ableToDelete = false;

if (!isEmpty())

{

Node* nodeToRemovePtr = headPtr;

Node* prevPtr = getNodeBefore(anEntry);

if (prevPtr != nullptr)

nodeToRemovePtr = prevPtr->getNext();

ableToDelete = (nodeToRemovePtr != nullptr) &&

(anEntry == nodeToRemovePtr->getItem());

if (ableToDelete)

{

Node* aftPtr = nodeToRemovePtr->getNext();

if (nodeToRemovePtr == headPtr)

{

// Delete the first node in the chain

headPtr = aftPtr;

}

else

{

// Disconnect indicated node from chain by connecting the

// prior node with the one after

prevPtr->setNext(aftPtr);

} // end if

// Return deleted node to system

nodeToRemovePtr->setNext(nullptr);

delete nodeToRemovePtr;

nodeToRemovePtr = nullptr;

itemCount--; // Decrease count of entries

} // end if

} // end if

return ableToDelete;

} // end removeSorted

template

int LinkedSortedList::getPosition(const ItemType& anEntry) const

{

int position = 1;

Node* curPtr = headPtr;

while ((curPtr != nullptr) && (anEntry > curPtr->getItem()))

{

curPtr = curPtr->getNext();

position++;

} // end while

if ((curPtr == nullptr) || (anEntry != curPtr->getItem()))

position = -position;

return position;

} // end getPosition

//=====================

// List operations:

template

bool LinkedSortedList::remove(int position)

{

bool ableToDelete = (position >= 1) && (position <= itemCount);

if (ableToDelete)

{

Node* curPtr = nullptr;

if (position == 1)

{

// Delete the first node in the chain

curPtr = headPtr; // save pointer to node

headPtr = headPtr->getNext();

}

else

{

// Find node that is before the one to delete

Node* prevPtr = getNodeAt(position - 1);

// Point to node to delete

curPtr = prevPtr->getNext();

// Disconnect indicated node from chain by connecting the

// prior node with the one after

prevPtr->setNext(curPtr->getNext());

} // end if

// Return deleted node to system

curPtr->setNext(nullptr);

delete curPtr;

curPtr = nullptr;

itemCount--; // Decrease count of entries

} // end if

return ableToDelete;

} // end remove

template

void LinkedSortedList::clear()

{

while (!isEmpty())

remove(1);

} // end clear

template

ItemType LinkedSortedList::getEntry(int position) const throw(PrecondViolatedExcep)

{

// Enforce precondition

bool ableToGet = (position >= 1) && (position <= itemCount);

if (ableToGet)

{

Node* nodePtr = getNodeAt(position);

return nodePtr->getItem();

}

else

{

string message = "getEntry() called with an empty list or ";

message = message + "invalid position.";

throw(PrecondViolatedExcep(message));

} // end if

} // end getEntry

template

bool LinkedSortedList::isEmpty() const

{

return itemCount == 0;

} // end isEmpty

template

int LinkedSortedList::getLength() const

{

return itemCount;

} // end getLength

template

Node* LinkedSortedList::getNodeBefore(const ItemType& anEntry) const

{

Node* curPtr = headPtr;

Node* prevPtr = nullptr;

while ((curPtr != nullptr) && (anEntry > curPtr->getItem()))

{

prevPtr = curPtr;

curPtr = curPtr->getNext();

} // end while

return prevPtr;

} // end getNodeBefore

template

Node* LinkedSortedList::getNodeAt(int position) const

{

assert((position >= 1) && (position <= itemCount));

// Count from the beginning of the chain

Node* curPtr = headPtr;

for (int skip = 1; skip < position; skip++)

curPtr = curPtr->getNext();

return curPtr;

} // end getNodeAt

// End of implementation file.

};

#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 = "");

PrecondViolatedExcep::PrecondViolatedExcep(const string& message) : logic_error("Precondition Violated Exception: " + message)

{

} // end constructor

// End of implementation file.

};

#endif

Node.h

#ifndef _NODE

#define _NODE

#include

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;

//cpp

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

};

#endif

SortedListInterface.h

#ifndef _SORTED_LIST_INTERFACE #define SORTED_LIST_INTERFACE

template class SortedListInterface { public: /** Inserts an entry into this sorted list in its proper order so that the list remains sorted. @pre None. @post newEntry is in the list, and the list is sorted. @param newEntry The entry to insert into the sorted list. */ virtual void insertSorted(const ItemType& newEntry) = 0; /** Removes the first or only occurrence of the given entry from this sorted list. @pre None. @post If the removal is successful, the first occurrence of the given entry is no longer in the sorted list, and the returned value is true. Otherwise, the sorted list is unchanged and the returned value is false. @param anEntry The entry to remove. @return True if removal is successful, or false if not. */ virtual bool removeSorted(const ItemType& anEntry) = 0; /** Gets the position of the first or only occurrence of the given entry in this sorted list. In case the entry is not in the list, determines where it should be if it were added to the list. @pre None. @post The position where the given entry is or belongs is returned. The sorted list is unchanged. @param anEntry The entry to locate. @return Either the position of the given entry, if it occurs in the sorted list, or the position where the entry would occur, but as a negative integer. */ virtual int getPosition(const ItemType& anEntry) const = 0; // The following methods are the same as those given in ListInterface // in Listing 8-1 of Chapter 8 and are completely specified there. /** Sees whether this list is empty. */ virtual bool isEmpty() const = 0; /** Gets the current number of entries in this list. */ virtual int getLength() const = 0; /** Removes the entry at a given position from this list. */ virtual bool remove(int position) = 0; /** Removes all entries from this list. */ virtual void clear() = 0; /** Gets the entry at the given position in this list. */ virtual ItemType getEntry(int position) const = 0; }; // end SortedListInterface #endif

PriorityQueueInterface.h

#ifndef _PRIORITY_QUEUE_INTERFACE #define _PRIORITY_QUEUE_INTERFACE

template class PriorityQueueInterface

{ public: /** Sees whether this priority queue is empty. @return True if the priority queue is empty, or false if not. */ virtual bool isEmpty() const = 0; /** Adds a new entry to this priority queue. @post If the operation was successful, newEntry is in the priority 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 add(const ItemType& newEntry) = 0; /** Removes from this priority queue the entry having the highest priority. @post If the operation was successful, the highest priority entry has been removed. @return True if the removal is successful or false if not. */ virtual bool remove() = 0; /** Returns the highest-priority entry in this priority queue. @pre The priority queue is not empty. @post The highest-priority entry has been returned, and the priority queue is unchanged. @return The highest-priority entry. */ virtual ItemType peek() const = 0; }; // end PriorityQueueInterface #endif