#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

// --------------------------------------------------

template <class T>
class Node {
friend ostream &operator<<(ostream&, const *(Node<T>));
public:
	T data;
	Node* next;
	Node(T d, Node<T>* n);
};

// --------------------------------------------------

template <class T>
Node<T>::Node(T d, Node<T>* n)
{
	data = d;
	next = n;
}

// --------------------------------------------------
// --------------------------------------------------

template <class T>
class Queue {
friend ostream &operator<<(ostream&, const Queue<T>&);
public:
	void Enqueue(T d);
	T Dequeue(void);
	bool IsEmpty(void);
	bool IsFull(void);
	~Queue();
	Queue();
private:
	Node<T>* head;
	Node<T>* tail;
};

// --------------------------------------------------

template <class T>
void Queue<T>::Enqueue(T d)
{
	Node<T>* temp;
	temp = new Node<T>(d, NULL);

	if (tail == NULL)
	{
		head = temp;
		tail = temp;
	}
	else
	{
		tail->next = temp;
		tail = temp;
	}
}

// --------------------------------------------------

template <class T>
T Queue<T>::Dequeue(void)
{
	T rv;
	Node<T>* temp;

	temp = head;
	rv = head->data;

	if (head == tail)
		tail = NULL;

	head = head->next;

	delete temp;

	return rv;
}

// --------------------------------------------------

template <class T>
bool Queue<T>::IsEmpty(void)
{
	return (head == NULL);
}

// --------------------------------------------------

template <class T>
bool Queue<T>::IsFull(void)
{
	return false;
}

// --------------------------------------------------

template <class T>
Queue<T>::~Queue()
{
	while(!IsEmpty())
	{
		Dequeue();
	}
}

// --------------------------------------------------

template <class T>
Queue<T>::Queue()
{
	head = NULL;
	tail = NULL;
}

// --------------------------------------------------
// --------------------------------------------------

class Job {
friend ostream &operator<<(ostream&, const Job&);
public:
	int Run(int interval);
	int time_required;
	int id;
	Job(int tr=0);
	~Job();
private:
	static int id_count;
};

// --------------------------------------------------

int Job::id_count = 0;

// --------------------------------------------------

Job::Job(int tr)
{
	time_required = tr;
	id = id_count;

	id_count++;

	cout << "Job " << id << " created" << endl; 
}

// --------------------------------------------------

Job::~Job()
{
	cout << "Job " << id << " completed" << endl;
}

// --------------------------------------------------

int Job::Run(int interval)
{
	if (interval > time_required)
	{
		cout << "Job " << id << " runs for " << time_required << endl;
		time_required = 0;
		interval -= time_required;
		return interval;
	}
	
	cout << "Job " << id << " runs for " << interval << endl;
	time_required -= interval;
	return interval;
}

// --------------------------------------------------
// --------------------------------------------------

template <class T>
ostream &operator<<(ostream& output, const Node<T> *n)
{
	if (n != NULL) 
		output << "[" << n->data << "]-> ";
	else
		output << "||";
	return output;
}

// --------------------------------------------------

template <class T>
ostream &operator<<(ostream& output, const Queue<T> &q)
{
	Node<T>* t;
	t = q.head;
	while (t != NULL) {
		output << t;
		t = t->next;
	}
	output << "||" << endl;
	return output;
}

// --------------------------------------------------

ostream &operator<<(ostream& output, const Job *j)
{
//	output << "id: " << j->id << " needs: " << j->time_required;
	output << j->id;

	return output;
}

// --------------------------------------------------

void Sim(Queue<Job*> &q, int JOB_NEED_MAX, int JOB_ENTER_MAX, int JOB_MAX)
{
	int time = 0;
	int job_count = 0;
	Job* new_job = NULL;
	Job* current_job = NULL;
	int time_required;
	int wait_time;
	int enter_time;

	while (true)
	{
		wait_time = rand() % JOB_ENTER_MAX + 1;
		enter_time = time + wait_time;

		while (time < enter_time)
		{
			cout << "Q = " << q;

			if (current_job == NULL)
			{
				if (!q.IsEmpty())
				{
					current_job = q.Dequeue();
				}
			}

			if (current_job == NULL)
			{
				time += wait_time;
				cout << "Nothing happens for " << wait_time << endl;
			}
			else
			{
				if ((job_count == JOB_MAX) || (current_job->time_required <= wait_time))
				{
					current_job->Run(current_job->time_required);
					time += current_job->time_required;

					if (current_job->time_required == 0)
					{
						delete current_job;
						current_job = NULL;
					}
				}
				else
				{
					current_job->Run(wait_time);
					time += wait_time;
				}

			}
		}

		if (job_count < JOB_MAX)
		{
			time_required = rand() % JOB_NEED_MAX + 1;
			new_job = new Job(time_required);
			q.Enqueue(new_job);

			job_count++;
		}

		if ((job_count == JOB_MAX) && q.IsEmpty() && (current_job == NULL))
			break;
	}
}

// --------------------------------------------------

void main (void)
{
	int JOB_MAX;
	int JOB_NEED_MAX;
	int JOB_ENTER_MAX;

	Queue<Job*> q;

	srand((unsigned)time(NULL));

	cout << "How many jobs to run? ";
	cin >> JOB_MAX;

	cout << "What is the max interval between generating a new job? ";
	cin >> JOB_ENTER_MAX;

	cout << "What is the max time needed by any one job? ";
	cin >> JOB_NEED_MAX;

	cout << endl;

	cout << "BEGINNING SIMULATION" << endl;
	cout << "====================" << endl;

	cout << endl;

	Sim(q, JOB_NEED_MAX, JOB_ENTER_MAX, JOB_MAX);

	cout << endl;

	cout << "====================" << endl;
	cout << "SIMULATION COMPLETED" << endl;

	cout << endl;

	system("pause");
}