//////////////////////////////////////////////////////
///////      SHORTEST JOB FIRST ALGORITHM     ///////
////////////////////////////////////////////////////
 
/* Developed BY : Harsh Chandra
   Contact : harshchandra@gmail.com
   Tested & Compiled on Turbo C++ IDE
*/
 
 
 
# include<stdio.h>
# include<conio.h>
# include<alloc.h>
 
struct node
{  int process_no;
   int btime;
   struct node *link;
};
 
void append(struct node **,int,int);
void display(struct node *,int);
void chart(struct node **);
 
void main()
{  clrscr();
   struct node *p;
   p = NULL; /* Empty Linked list */
   int i=1,time;
   char ans = 'y';
   while(ans != 'n')
   {    printf("\nEnter Burst Time For Process No. %d : ",i);
	scanf("%d",&time);
	append(&p,i,time);
	printf("Any More Process (Y/N) ? ");
	ans = getche();
	i++;
   }
   getch();
   clrscr();
   printf("\nThe Order Of Execution Of Process For SJF Algorithm Will be :- ");
   display(p,1);
   getch();
   printf("\nThe Waiting Time Of Process For SJF Algorithm Will be :- ");
   display(p,2);
   getch();
   chart(&p);
   getch();
 
}
 
void append(struct node **q,int i,int time)
{  struct node *r,*temp = *q;
   r = (struct node *)malloc(sizeof(struct node));
   r->process_no = i;
   r->btime = time;
 
   /* If list is empty or new data to be inserted b4 the first node */
   if(*q==NULL || (*q)->btime > time)
   {   *q = r;
      (*q)->link = temp;
   }
   else
   {  /* traverse the entire linked list
      to search the position the new node to be inserted */
      while(temp != NULL)
      {   if(temp->btime <=time &&(temp->link->btime > time || temp->link ==NULL))
	  {   r->link = temp->link;
	      temp->link = r;
	      r->link = NULL;
	  }
	  temp = temp->link;
      }
   }
}
 
void display(struct node *q,int kk)
{   struct node *temp;
    int wtime,avg=0,total = 0,count=0;
    temp = q;
    int i;
    printf("\n");
    printf("\n\t\t%c",218);
    for(i=1;i<33;i++)
    { if(i==17)
      printf("%c",194);
      else
      printf("%c",196);
    }
    printf("%c",191);
    if(kk==1)
    { printf("\n\t\t%c  PROCESS NO.   %c  BURST TIME   %c\n",179,179,179);
    }
    if(kk==2)
    { printf("\n\t\t%c  PROCESS NO.   %c  WAIT  TIME   %c\n",179,179,179);
    }
    printf("\t\t%c",195);
    for(i=1;i<33;i++)
    { if(i==17)
      printf("%c",197);
      else
      printf("%c",196);
    }
    printf("%c",180);
 
    while( temp !=NULL)
    {  count++;
       if(kk==1)
       {    printf("\n\t\t%c      %d.        %c      %3d      %c",179,temp->process_no,179,temp->btime,179);
       }
       if(kk==2)
       {  if(temp ==q)  /* First Process In The Ready Queue */
	  {  wtime = 0;
	     total+= temp->btime;
	     avg+=wtime;
	  }
	  else
	  {  wtime = total;
	     total+= temp->btime;
	     avg +=wtime;
	  }
 
	  printf("\n\t\t%c      %d.        %c      %3d      %c",179,temp->process_no,179,wtime,179);
 
	}
	temp=temp->link;
    }
    printf("\n\t\t%c",192);
    for(i=1;i<33;i++)
    { if(i==17)
      printf("%c",193);
      else
      printf("%c",196);
    }
    printf("%c",217);
    if(kk==2)
    {  printf("\nThe Average Waiting Time (%d %c %d) = %.2f",avg,246,count,float(avg/float(count)));
    }
 
}
 
void chart(struct node **q)
{
    printf("\n");
    printf("\nThe Glant Chart Is As Follows :-\n");
 
    struct node *temp,*temp1,*temp2,*temp3,*temp4;
    temp = *q; temp1 = *q;temp2 = *q;temp3 = *q;temp4=*q;
    int sum = 0;float sfactor;
    while(temp4 !=NULL)
    {  sum+=temp4->btime;
       temp4 = temp4->link;
    }
    if(sum<80)
    {  sfactor = 1.0;
    }
    else
    { sfactor = (sum%80)/float(sum);
    }
 
    int i,k=0;
    printf("%d",k);
    while(temp3 != NULL)
    {   if((sfactor*temp3->btime) == 0)
	{  goto harsh;
	}
	for(i=-1;i<=(sfactor*temp3->btime);i++)
	{   printf(" ");
	}
	k+=temp3->btime;
	printf("%d",k);
	harsh:
	temp3=temp3->link;
    }
    printf("\n");
    while( temp !=NULL)
    {   if(temp == *q)
	{
	    printf("%c%c",218,196);
	    if((sfactor*temp->btime) == 0)
	    {   goto last;
	    }
 
	    for(i=-1;i<=(sfactor*temp->btime);i++)
	    {  printf("%c",196);
	    }
	    if(temp->link != NULL)
	    {  printf("%c",194);
	    }
	    else
	    {  printf("%c",191);
	    }
	}
	else
	{   if((sfactor*temp->btime) == 0)
	    {  goto last;
	    }
	    for(i=-1;i<=(sfactor*temp->btime);i++)
	    {   printf("%c",196);
	    }
	    if(temp->link != NULL)
	    {  printf("%c",194);
	    }
	    else
	    {  printf("%c",191);
	    }
	}
	last:
	temp = temp->link;
 
    }
    printf("\n");
    printf("%c ",179);
 
    while(temp1 != NULL)
    {     if((sfactor*temp1->btime) == 0)
	    {  goto last1;
	    }
	  for(i=0;i<=(sfactor*temp1->btime);i++)
	  {  if(i==int(sfactor*temp1->btime)/2)
	     {  printf("P%d",temp1->process_no);
	     }
	     else
	     printf(" ");
	  }
	  printf("%c",179);
	  last1:
	  temp1 = temp1->link;
 
    }
 
    printf("\n");
    while(temp2 !=NULL)
    {  if(temp2 == *q)
       {    printf("%c%c",192,196);
	    if((sfactor*temp2->btime) == 0)
	    {  goto last2;
	    }
	    for(i=-1;i<=(sfactor*temp2->btime);i++)
	    {  printf("%c",196);
	    }
	    if(temp2->link != NULL)
	    {  printf("%c",193);
	    }
	    else
	    {  printf("%c",217);
	    }
       }
       else
       {   if((sfactor*temp2->btime) == 0)
	    {  goto last2;
	    }
	   for(i=-1;i<=(sfactor*temp2->btime);i++)
	   {  printf("%c",196);
	   }
	   if(temp2->link != NULL)
	    {  printf("%c",193);
	    }
	    else
	    {  printf("%c",217);
	    }
       }
      last2:
      temp2=temp2->link;
 
    }
}