#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <stdlib.h>

typedef struct Newnode{
        struct Newnode *next;
        int arr, page, wt, group;
        }node;

int time=0;
int totalWaitingTime=0;
node *root, *newRoot=NULL, *queueNode=NULL;
node *insert(node **q,int a, int p, int u, int w){
node *temp;
temp = *q;
if(*q==NULL)
{
    *q=(node*)malloc(sizeof(node));
    temp = *q;
}
else
{
    while((temp->next)!=NULL)
    {
        temp=temp->next;
    }
    temp->next = (node*)malloc(sizeof(node));
    temp=temp->next;
}
temp->arr = a;
temp->page=p;
temp->group=u;
temp->wt=w;
temp->next=NULL;
return *q;
}
/* merge the lists.. */
node *merge(node *head_one, node *head_two) {
node *head_three = (node*)malloc(sizeof(node));

 if(head_one == NULL)
  return head_two;

 if(head_two == NULL)
  return head_one;

 if(head_one->group < head_two->group) {
  head_three = head_one;
  head_three->next = merge(head_one->next, head_two);
 } else {
  head_three = head_two;
  head_three->next = merge(head_one, head_two->next);
 }

 return head_three;
}

node *mergesort(node *head) {
 node *head_one=(node*)malloc(sizeof(node));
 node *head_two=(node*)malloc(sizeof(node));

 if((head == NULL) || (head->next == NULL))
  return head;

 head_one = head;
 head_two = head->next;
 while((head_two != NULL) && (head_two->next != NULL)) {
  head = head->next;
  head_two = head->next->next;
 }
 head_two = head->next;
 head->next = NULL;

return merge(mergesort(head_one), mergesort(head_two));
}

int queue(node *n, int t){
    node *temp=(node*)malloc(sizeof(node));

if(t<n->arr){

n->wt=0;
t=(n->arr)+(n->page);
queueNode=insert(&queueNode,n->arr, n->page, n->group, n->wt);
n=n->next;
while(t>=n->arr){
newRoot=insert(&newRoot,n->arr, n->page, n->group, 0 );
n=n->next;
}
newRoot=mergesort(newRoot);
    while(newRoot!=NULL){

queue(newRoot, t);
temp=newRoot->next;
free(newRoot);
newRoot=temp;}
}
else{
     if(n->page<50){
n->wt=t-n->arr;
t+=n->page;
queueNode=insert(&queueNode,n->arr, n->page, n->group, n->wt);
n=n->next;
while(t>=n->arr){
newRoot=insert(&newRoot,n->arr, n->page, n->group, 0 );
n=n->next;
}
newRoot=mergesort(newRoot);
    while(newRoot!=NULL){
queue(newRoot, t);
temp=newRoot->next;
free(newRoot);
newRoot=temp;}
}
else{
queueNode=insert(&queueNode,n->arr, n->page, n->group, n->wt);
n=n->next;
while(t>=n->arr){
newRoot=insert(&newRoot,n->arr, n->page, n->group, 0 );
n=n->next;
}
newRoot=mergesort(newRoot);
    while(newRoot!=NULL){
queue(newRoot, t);
newRoot=newRoot->next;
}
}
}
}



int printwt(node *n){
    if(n==NULL){
    printf("");}
    else
    while(n==NULL){

totalWaitingTime+=n->wt;
n=n->next;
printwt(n);
}
return totalWaitingTime;
printwt(n);
}
int printw(node *n){if(n==NULL){
    printf("");}
    else
    while(n==NULL){

totalWaitingTime+=n->wt;
printf("Arr=%d Page=%d Group=%d WaitingTime=%d Total Waiting=%d ", n->arr, n->page, n->group, n->wt, totalWaitingTime);
n=n->next;
printwt(n);
}
printwt(n);
}

int main(){
int arrival, pagenumber;
int null =0;
root=NULL;
char user[20]="";
char student[20]="student";
char assistant[20]="assistant";
char secretary[20]="secretary";
char instructor[20]="instructor";
FILE *input;
int usergroup=0;
input=fopen("input.txt","r");

    if(input==NULL){
    printf("The input file couldn't open");
    }
    else{
         while(!feof(input)){
         fscanf(input,"%d %d %s", &arrival, &pagenumber, &user, null );

         if(pagenumber<50){

         if(strcmp(user,student) == 0)
         usergroup=pagenumber;

         else if(strcmp(user,instructor) == 0)
         usergroup=100+pagenumber;

         else if(strcmp(user,assistant) == 0)
         usergroup=200+pagenumber;

         else if(strcmp(user,secretary) == 0)
         usergroup=300+pagenumber;
         }
         else{

         if(strcmp(user,student) == 0)
         usergroup=400+pagenumber;

         else if(strcmp(user,instructor) == 0)
         usergroup=500+pagenumber;

         else if(strcmp(user,assistant) == 0)
         usergroup=600+pagenumber;

         else if(strcmp(user,secretary) == 0)
         usergroup=700+pagenumber;
         }

         root=insert(&root, arrival, pagenumber, usergroup, null );
    }
}

fclose(input);
queue(root, time);
int d=printwt(queueNode);
printf("Total Waiting Time = %d",d);
system("pause");
}