//
//	bank teller simulation routine
//
//	Described in Chapter 10 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//
// MAR 4/13/00 - adapted for Microsoft
// MAR 4/15/00 - adapted to use stack instead of queue - to see why not!

# include <list>
# include <vector>
# include <stack>
# include <string>
# include <iostream>
using namespace std;

// MAR 4/13/00 - changed randomizer to be straightforward instead of
//   complicated
int randomizer (int max) {
		// rand return random integer
		// convert to unsigned to make positive
		// take remainder to put in range
	unsigned int rval = rand();
	int val = rval % max;
	return val;
}



//
//	class Customer
//		a single customer waiting in the bank teller line


class Customer {
public:
		// constructors
	Customer (int at) : arrivalTime(at), 
			processTime(2 + randomizer(6)) {}
	Customer () : arrivalTime(0), processTime(0) { }
	
		// operations
	// done updates a customer so that they have spent another minute 
	//    at the teller window (a side-effect) and reports whether the 
	//    customer is done 
	//    The side effect makes this function do more than it would seem 
	//    to do on the surface. I wouldn't have done it like that MAR
	
	// MAR 04/14/00 - changed done - so need to process tellers independently
	bool done    () { 
		// processTime--;
		return processTime <= 0; }

	// update customer for the passage of a minute - one minute less remaining 
	// in tellers work for the customer
	void MinutePasses () {
		processTime--;
	}

	// report what time (what minute) the customer arrived
	int  arrival () { return arrivalTime; }

	// below operators needed for any list - which stack can be built on
	operator < (Customer & c)	// allows order by arrival time
		{ return arrivalTime < c.arrivalTime; }
		
	operator == (Customer & c)	// no two customers are alike
		{ return false; }
		
protected:
	unsigned int arrivalTime;  // minute that customer arrived
	unsigned int processTime;  // time remaining for customer's task
								// initially the time to do a task - 
								// randomly assigned for simulation
};

//
//	class Teller
//		a teller servicing customers in a bank teller line

class Teller {
public:
	// create teller - available for work
	Teller() { free = true; }
	
	// does two things - marks down another minute spent with current
	//    customer (side effect - of done() nasty, nasty ) and
	//    checks whether teller is free
	// MAR 04/14/00 - changed done - so need to process tellers independently
	bool isFree()	// see if teller is free to work
	{ 
		if (free) return true;
		if (customer.done())
		  	free = true;
		  return free;
	}

	// minute passes as teller processes a customer
	// update customer for the passage of a minute - one minute less remaining 
	// in tellers work for the customer// update customer for the passage of a minute - one minute less remaining 
	// in tellers work for the customer
	void CustMinutePasses () {
		// only can process a customer if working for one
		if (! free) {
			customer.MinutePasses();
		}
	}

	void addCustomer(Customer & c) // start servicing customer
	{
		customer = c;
		free = false;
	}

protected:
	bool free;          // indicates if teller is available or not
	Customer customer;  // if teller isn't available - this data member keeps 
						// track of which customer teller is serving
};

// show contents of stack - uses copy - thats important so dont change the real stack
void ShowLine (stack < Customer > lineq) {
	while (! lineq.empty() ) {
		cout << lineq.top().arrival() << "| ";
		lineq.pop();
	}
	return;
}

void main() {
	int numberOfTellers = 4;
	int numberOfMinutes = 60;
	double totalWait = 0;
	int maxWait = 0;
	int numberOfCustomers = 0;
	int totalLineLen = 0;
	vector < Teller > teller(numberOfTellers);
	stack < Customer > line;
	char wait;
	
	// main loop - loop until simulation is over - one minute at a time
	for (int time = 0; time < numberOfMinutes; time++) {
		// each minute there is a 90% probability that a customer enters the line
		if (randomizer(10) < 9) {
			// create customer and add them
			Customer newCustomer(time);
			line.push(newCustomer);
			cout << "       Customer arrives at time: " << time << endl;
			}
		// loop through whole set of tellers
		for (int i = 0; i < numberOfTellers; i++) {
			// update teller's customer, and if teller becomes free and there
			// is somebody in line, have teller take a customer
			teller[i].CustMinutePasses();
			if (teller[i].isFree() & ! line.empty()) {
				// get customer off top of line
				Customer topCustomer = line.top();
				// update info to prepare for determining average wait later
				numberOfCustomers++;
				double currWait = (time - topCustomer.arrival());
				// update max wait if appropriate
				if (currWait > maxWait) {
					maxWait = currWait;
				}
				cout << "          Customer who arrived at " << topCustomer.arrival()
					<< " served by teller " << i << " after a wait of "
					<< currWait << " mins" << endl;
				totalWait += currWait; // how long did customer
									// just started wait in line before they got served
				// hand the customer off to the teller and remove them from the line
				teller[i].addCustomer(topCustomer);
				line.pop();
				}
		}  // end loop through tellers
		// prep info for ave line len
		int currLineLen = line.size();
		totalLineLen += currLineLen;
		// show line
		cout << endl << "* " << "time: " << time << " " << " line length: "
			<< currLineLen << "| ";
		ShowLine(line);
		cout << endl;
		// give chance to occasionally see whats up
		if ((time % 5) == 0) {
			cout << endl << "num customers: " << numberOfCustomers << "   " << 
				"total wait so far: " << totalWait << endl;
			cout << "Wait> " << flush;
			cin >> wait;
		}
	} // end loop through minutes
	// report average wait for all customers
	cout << endl << "average wait:" <<   (totalWait / numberOfCustomers) << endl;
	double aveLineLen = (1.0 * totalLineLen) / numberOfMinutes;
	cout << "Average line length: " << aveLineLen << endl;
	cout << endl << "max wait:" <<   maxWait << endl;
}