C$++$Bank Simulation using Binary Search Tree

Do not use any C$++$ STL libraries like queue. I will give thumbs up for any program sucessfully outputting the required objective. Please complete the Queue.h$,$ BinarySearchTree.h and driver.cpp$.$ Please also output the results through a print function and share a screenshot. Thank you.

Students will implement a bank Service system that simulates customers entering and leaving a bank. This program will read an input file that contains the number of tellers and the arrival time and service time of each customer. As you can see the input file below is not ordered by arrival time. An example input file is as follows:

$//$input$.$txt

numTellers $3$

arrivalTime $78$ serviceTime $124$

arrivalTime $39$ serviceTime $57$

arrivalTime $35$ serviceTime $62$

arrivalTime $79$ serviceTime $32$

arrivalTime $100$ serviceTime $40$

Three tellers are working. The arrival and service times for customers are as follows:

$$ A customer arrives at $78$ and requires service for $124$ units of time.

$$ A customer arrives at $39$ and requires service for $57$ units of time.

$$ A customer arrives at $35$ and requires service for $62$ units of time.

$$ A customer arrives at $79$ and requires service for $32$ units of time.

$$ A customer arrives at $100$ and requires service for $40$ units of time.

Considering these, here$$s the scenario:

$$ Customer $1$ arrives at $35.$ Since no other customers are present, all tellers are available, and the customer is immediately serviced. The customer$$s departure time is calculated as $97(35+62).$

$$ Customer $2$ arrives at time $39$ and can be serviced immediately, scheduled for departure at time $96.$

$$ Customer $3$ arrives at time $78$ and be serviced immediately, scheduled for departure at time $202.$

$$ Customer $4$ arrives at time $79.$ Unfortunately, all tellers are busy. At time $96,$ Customer $2$ leaves, freeing a teller and Customer $4$ can be serviced. Customer $4\text{'}$s departure time is scheduled as $128(96+32).$

$$ At time $97,$ Customer $5$ arrives at time $100,$ freeing a teller, and Customer $5$ can be serviced immediately. Customer $5\text{'}$s departure time is scheduled as$140(100+40).$

$$ The picture below illustrates how tellers serve the customers: $($at the very bottom of the question$)$

The first three customers are promptly served by three tellers without any wait. However, the fourth customer needs to wait for $17(96-79=17)$ before being served by teller $2,$ who finishes serving another customer at time $96.$ Customer $5$ arrives at time $100$ and is immediately served because teller $1$ is available at that moment.

Queue:

$$ Initialize a queue to store information about customers waiting in line, representing each customer arrival that hasn$$t been processed yet.

$$ At program start, read the input file containing customer records. For each arrival, create a node with customer information $($arrivalTime and serviceTime$)$ and insert it into the queue, maintaining the first$-$in$-$first$-$out $($FIFO$)$ order.

In the given instance, the queue displays customers in the order of arrival, with the customer who arrived at $35$ being the first node and the one arriving at $100$ being the last.

The queue displays the following:

$35->39->78->79->100$

$$ The Queue.h is shown below:

$//$Queue$.$h

struct Customer $\{$

int arrivalTime;

int serviceTime;

int waitTime;

int departureTime;

$\}$;

struct qNode $\{$

Customer customer;

qNode$*$ next;

$\}$;

class Queue $\{$

public:

Queue$()$;

bool isEmpty$()$; $//$check if head is NULL

Customer peek$()$; $//$get the first customer from the queue

void enqueue$($Customer$)$;

void dequeue$()$;

Customer peek$()$; $//$ return first customer on the queue

private:

qNode$*$ head;

$\}$;

Next, process customer services using a binary search tree.

Binary Search Tree:

$$ Create a BinarySearchTree that represents customers currently being serviced.

$$ When adding a new customer to the tree, calculate customer$$s departure time by adding the current time and service time. Insert the customer into the tree in ascending order sorted by departure time.

$$ BinarySearchTree.h Implementation:

struct bstNode $\{$

Customer value;

bstNode$*$ left;

bstNode$*$ right;

$\}$;

class BinarySearchTree $\{$

public:

BinarySearchTree$()$;

bool isEmpty$()$ ; $//$check if root is NULL

void Insert$($Customer$,$ int$)$ ; $//$customer and current time

void delete$($Customer$)$;

int smallestDepartTime$()$; $//$find the smallest departure time from the BST

private:

bstNode$*$ root;

void InsertNode$($bstNode$*$&$,$ Customer, int$)$; $//$ current time

void DeleteNode$($bstNode$*$&$,$ Customer$)$;

$\}$;

After inserting the first tree customers to tree, BinarySearchTree is shown below:

$-------------------[35,62,0,97]--------------------$

$-------[35,57,0,96]-----------------[78,124,0,202]------$

Each node represents customer$$s arrivalTime, serviceTime, waitTime, and departureTime.

Main function:

$$ Read input file, creating a customer node for each, and enqueue them into a queue. Continue to enqueue all customers into the queue.

$$ Perform the following procedure until the queue is empty:

$$ Dequeue a customer from the queue.

$$ Remove customers who departed before this current customer$$s arrival from a BST: delete customers with the lowest departure time and increase open tellers.

$$ Set the current time to customer$$s arrival time, which is used for calculating waiting and departure times in the BST$.$

$$ If no tellers are available, wait until one is: update the current time with the lowest departure time, remove the customer with smallest departure time from the BST$,$ and increase open teller by $1.$

$-$Service current customer: insert this customer and current time into BST$,$ then decrease open tellers.

$-$Note: The BST is sorted by customer's departure time, calculated by adding service time to current time.

$-$You may use the following partial code:

int main$()\{$

Queue q;

BinarySearchTree bst;

$//$read input and enqueue cutomers into queue

$//$ service customer throught BST

int openTellers; $//$assign with numTellers from input file.

int currentTime$=0$;

while$(!$q$.$isEmpty$())\{$

$//$get a customer from queue

while$()\{//$delete customers with the lowest departure time and increase open tellers.

$\}$

$//$Set the current time to customer's arrival time, used for calculating waiting and departure times in the bst$.$

$//$If there are no open tellers, wait until there is one

if$($openTellers $==0)\{$

$\}$

$//$Insert this customer and current time into BST and decrease open tellers.

$\}$

$\}$

Grading Rubric:

$1.$ Driver program

$-$Reading data from the file.

$-$Output result.

$2.$Binary Search Tree:

$-$int smallestDepartureTime$()$; $//$find the smallest departure time.

$-$void Insert$($Customer c$,$ int currentTime$)$; $//$Insert a customer into BST

$-$void delete$($Customer$)$; $//$remove the customer with smallest departure time

$3.$Queue Class:

$-$void enqueue$($Customer$)$; $//$add a new customer to the queue

$-$void dequeue$()$; $//$delete the customer from the queue

$-$Customer peek$()$; $//$get the first customer in the queue