/*
  Name: Access arm Simulation Scheduler 
  Author: 謝微（掃描算法）、施巧琳（先來先服務算法）、鄭騰龍（最短路徑優先算法）
  Date: 20-01-07 21:32
  Description: This is an Access arm Simulation Scheduler
*/
#include<stdlib.h>
#include<stdio.h>
#include<math.h>


typedef struct
//定義磁道訪問請求序列的結構，其中data為序列數據，flag為數據訪問狀態標記
{
	int data;
	int flag;
}node;

void sort(node *a,int num)
//將序列按從小到大排列
{
    int tmp;
    for (int i = 0; i <num; i++)
    {
       for(int j = 0; j < num - i - 1; j++)
       {
           if(a[j+1].data < a[j].data)
           {
               tmp = a[j+1].data;
               a[j+1].data = a[j].data;
               a[j].data = tmp;
           }
       }
    } 
}

void fcfs(int num,int location,node *serial)
//先來先服務算法
{
	system("cls");
	printf("\n磁臂調度算法之先來先服務算法:\n");
	printf("----------------------------------------------\n");
	printf("\n當前磁道:%d\n",location);
	int i,s,count=0;
	printf("\n----------------------------------------------\n");
	printf("\n磁道請求隊列(磁道數為%d個):\n\n",num);
	for(i=0;i<num;i++)
	{
	s=abs(serial[i].data-location);
	count+=s;
	location=serial[i].data;
	printf("%d-",serial[i].data);
	}
	printf("\n\n----------------------------------------------\n");
	printf("\n磁臂調度訪問序列:\n\n");
	for(i=0;i<num;i++)
		 printf("%d-",serial[i]);
	printf("\n\n----------------------------------------------\n");
    printf("\n移動磁道數:%d\n",count);
    printf("\n----------------------------------------------\n");
}
void scan(int cl,int num,node *a)
//電梯（掃描）算法
{
	system("cls");
	int i,t;
	node *queue=(node *)malloc(num*sizeof(node));
	printf("\n磁臂調度算法之電梯（掃描）算法:\n");
	printf("----------------------------------------------\n");
	printf("\n當前磁道:%d\n",cl);
	printf("\n----------------------------------------------\n");
	printf("\n磁道請求隊列(磁道數為%d個):\n\n",num);
	for(i=0;i<num;i++)
	//復制請求隊列 
 	{
        queue[i].data=a[i].data;
        queue[i].flag=a[i].flag;
	}
	sort(queue,num);
	for(i=0;i<num;i++)
		printf("%d-",queue[i].data);
	printf("\n\n----------------------------------------------\n");
	printf("\n磁道調度序列為：\n\n");
	for (i=0;i<num;i++)//磁頭向右掃描
	{
		if(queue[i].data>cl)
		{ 
			if(queue[i].flag==0) 
		  {
			  printf("%d-",queue[i].data);
			  if(i%10==0) printf("\n");//每十個數為一行輸出
			  queue[i].flag=1;
		  }
		  
		}
	}
	t=abs(cl-queue[num-1].data);
	for(i=num-1;i>=0;i--)//磁頭向左掃描
	{
		int f=0;f++;
		if(queue[i].data<cl)
		{
			if(queue[i].flag==0)
			{
				printf("%d-",queue[i].data);
                
				if(f%10==0) printf("\n");//每十個數為一行輸出
				queue[i].flag=1;
			}
			
		}
	}
	t=t+queue[num-1].data-queue[0].data;//移動的磁道數
	printf("\n\n----------------------------------------------\n");
	printf("\n移動磁道數為：%d\n",t);
	printf("\n----------------------------------------------\n");
}
void sstf(node *a,int num,int location)
//最短路徑優先算法
{
	system("cls");
	int i,j,m,n,tmp,sum=0;
	node *queue=(node *)malloc(num*sizeof(node)+1);
	node *temp=(node *)malloc(num*sizeof(node)+1);
	printf("\n磁臂調度算法之最短路徑優先算法:\n");
	printf("----------------------------------------------\n");
	printf("\n當前磁道:%d\n",location);
	printf("\n----------------------------------------------\n");
	printf("\n磁道請求序列(磁道數為%d個):\n\n",num); 
	for(i=0;i<num;i++)
	//復制請求隊列 
 	{
        queue[i].data=a[i].data;
        queue[i].flag=a[i].flag;
	}
	sort(queue,num);
	for(i=0;i<num;i++)
	{
		printf("%d-",queue[i].data);//打印輸出待訪問的磁道序列
		if((i+1)%15==0)printf("\n");//每15個數據為一行
	}
	printf("\n");
	printf("\n----------------------------------------------\n");
	queue[num].data=location;
	temp[0].data=location;
	sort(queue,num+1);
	printf("\n磁臂調度訪問序列:\n\n");
	for(i=0;i<num;i++)
	{
 	    for(tmp=0;tmp<=num;tmp++)//獲取location在隊列中的位置
		{
			if(queue[tmp].data==location)
			{
				queue[tmp].flag=1;
				j=tmp;
			}
		}
		m=1;n=1;
		while(queue[j-m].flag==1&&m<j)
			m++;			
		while(queue[j+n].flag==1&&n+j<=num)
			n++;
		if(queue[0].flag==1)//極端情況
			location=queue[j+n].data;
		else
			if(queue[num].flag==1)//極端情況
				location=queue[j-m].data;
		else
			if(abs(location-queue[j-m].data)<abs(location-queue[j+n].data))
				location=queue[j-m].data;
		else
			location=queue[j+n].data;
		printf("%d-",location);
		if((i+1)%15==0)printf("\n");//每15個數據為一行
		temp[i+1].data=location;
	}
	for(i=0;i<num;i++)
	{
		sum=sum+abs(temp[i+1].data-temp[i].data);
	}
	printf("\n");
	printf("\n----------------------------------------------\n");
	printf("\n移動的磁道數：%d",sum);
	printf("\n");
	printf("\n----------------------------------------------\n");
}

main(int argc,char *argv[])
{
  FILE *fp;
  char temp[20];
  int i,num,choice,location;
  if(argc!=2)
  {
	  printf("Usage:haha.exe Datafile\n");
	  return 0;
  }
restart:if((fp=fopen(argv[1],"r"))==NULL)
  {
	  printf("Cannot open this file!");
	  return 0;
  }
  fscanf(fp,"%14s%d",temp,&num);
  fscanf(fp,"%17s%d",temp,&location);
  fscanf(fp,"%s",temp);
  node *serial=(node *)malloc(num*sizeof(node));
  for(i=0;i<num;i++)
	  fscanf(fp,"%d",&(serial[i].data));
  for(i=0;i<num;i++)
  {
	  serial[i].flag=0;
  }
  while(1)
  {
	  //do
	  //{
	  system("cls");
	  printf("This is an Access arm Simulation Scheduler\n微琳龍三人組制作\n");
	  printf("\nUsage of this program:\nChoose options below:\n[1] To see the FCFS Scheduling;\n[2] To see the SCAN Scheduling;\n[3] To see the SSTF Scheduling.\n[4] Refresh this program.\n[5] Quit this program.\n");
	  printf("\n[Choice @ Scheduler] $ ");
	  scanf("%d",&choice);
	  //}while(!isdigit(choice));
	  switch(choice)
	  {
	  case 1:fcfs(num,location,serial);break;
	  case 2:scan(location,num,serial);break;
	  case 3:sstf(serial,num,location);break;
	  case 4:printf("Refreshing program...Done!\n");system("pause");goto restart;
   	  case 5:return 0;
	  default:printf("\nYou entered an invalid choice!\n");
	  }
	  printf("\nAccess arm simulation scheduled completely!\n\n");
	  system("pause");
  }
  fclose(fp);
  return 0;
  }