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

struct queueNode {
	int data;
	int time;
	struct queueNode* nextPtr;
};

typedef struct queueNode QueueNode;
typedef QueueNode* QueueNodePtr;

void enqueue(QueueNodePtr* headPtr, QueueNodePtr* tailPtr, int value, int inLineTime);
int dequeue(QueueNodePtr* headPtr, QueueNodePtr* tailPtr);
int queueIsEmpty(QueueNodePtr quene);
int randomTime();
int queueLength(QueueNodePtr headPtr);
void printQueue(QueueNodePtr headPtr);
int currentInLineTime(QueueNodePtr headPtr);

int main()
{
	QueueNodePtr waitingLineHead = NULL;
	QueueNodePtr waitingLineTail = NULL;
	int customer = 1;
	int nextArriveTime = 0;
	int dueServiceTime = 0;
	int currentTime = 0;
	int waitingLine = 0;
	int waitingLineMAX = 0;
	int waitingTime = 0;
	int waitingTimeMAX = 0;
	int unableDequeue = 0;

	srand(time(NULL));

	currentTime = randomTime();
	enqueue(&waitingLineHead, &waitingLineTail, customer, currentTime); // first customer arrive

	dueServiceTime = currentTime + randomTime(); // service time due for first customer
	nextArriveTime = currentTime + randomTime(); // second customer arrive

	while (currentTime < 720)
	{

		// is service time for current customer is due
		if (currentTime == dueServiceTime)
		{
			// to find longest waiting time
			if ((waitingTime = currentTime - currentInLineTime(waitingLineHead)) > waitingTimeMAX)
			{
				waitingTimeMAX = waitingTime;
			}

			dequeue(&waitingLineHead, &waitingLineTail); // remove current customer

			printf("OUT : ");
			printQueue(waitingLineHead);

			if (!queueIsEmpty(waitingLineHead))
			{
				dueServiceTime = dueServiceTime + randomTime(); // due time for next customer
			}
			else
			{
				unableDequeue++;
				printf("///// Unable Dequeue /////\n");
				dueServiceTime = nextArriveTime + randomTime();
			}
		}

		if (currentTime == nextArriveTime)
		{
			// to find longest waiting line
			if ((waitingLine = queueLength(waitingLineHead)) > waitingLineMAX)
			{
				waitingLineMAX = waitingLine;
			}

			enqueue(&waitingLineHead, &waitingLineTail, customer, currentTime); // one more customer waiting
			printf("IN  : ");
			printQueue(waitingLineHead);
			customer++;
			nextArriveTime = nextArriveTime + randomTime();
		}
		currentTime++;
	} // end while
	printf("\nHow many times you want to dequeue a customer but can not beacuse queue is already NULL : %d\n", unableDequeue);
	printf("Longest waiting time : %d\n", waitingTimeMAX);
} // end main

// insert a node at queue tail
void enqueue(QueueNodePtr* headPtr, QueueNodePtr* tailPtr, int value, int inLineTime)
{
	QueueNodePtr newPtr; // pointer to new node

	newPtr = malloc(sizeof(QueueNode));

	if (newPtr != NULL) // is space avaliable
	{
		newPtr->time = inLineTime;
		newPtr->data = value;
		newPtr->nextPtr = NULL;

		if (queueIsEmpty(*headPtr)) // if is empty , insert node at head
		{
			*headPtr = newPtr;
		}
		else // insert node at tail
		{
			(*tailPtr)->nextPtr = newPtr;
		}
		*tailPtr = newPtr;
	}
	else
	{
		printf("%d is not inserted. No memory available.\n", value);
	}
} // end function enqueue

// remove node from queue head
int dequeue(QueueNodePtr* headPtr, QueueNodePtr* tailPtr)
{
	int value = 0; // node value
	QueueNodePtr tempPtr; // temporary node pointer

	if (queueIsEmpty(*headPtr))
	{
		*tailPtr = NULL;
	}

	value = (*headPtr)->data;
	tempPtr = *headPtr;
	*headPtr = (*headPtr)->nextPtr;

	free(tempPtr);
	return value;
}

// return 1 if quene is empty
// return 0 if quene is not empty
int queueIsEmpty(QueueNodePtr quene)
{
	return (quene == NULL);
}

int randomTime()
{
	return (rand() % 4 + 1);
}

int queueLength(QueueNodePtr headPtr)
{
	QueueNodePtr currentPtr = NULL;
	int length = 0;

	currentPtr = headPtr;

	while (currentPtr != NULL)
	{
		currentPtr = currentPtr->nextPtr;
		length++;
	}
	return length;
}

void printQueue(QueueNodePtr headPtr)
{
	QueueNodePtr currentPtr = NULL;

	currentPtr = headPtr;

	while (currentPtr != NULL)
	{
		printf("%d--> ", currentPtr->data);
		currentPtr = currentPtr->nextPtr;
	}
	printf("NULL\n");
}

// return in line time of current customer , do not dequeue it
int currentInLineTime(QueueNodePtr headPtr)
{
	return (headPtr->time);
}