#include <stdio.h>
#include <math.h>

#define MAX 20
#define INF 999

int length;//被訪問磁道的個數

void Sort(int * head, int len);//對數氣據由小到大排序
int SSTF(int * head, int value);//最短尋道優先算法
int SCAN(int * head, int value);//掃描算法

int main()
{
	int TrackID[MAX];//磁道序列號
	int Begin;//磁頭位置

	printf("please input the length of secquence of track ID: ");
	scanf("%d", &length);//要尋道的磁道個數

	printf("please input the secquence of track ID:\n");
	for(int i = 0; i < length; i++)
		scanf("%d", &TrackID[i]);

	printf("please input the current of track ID: ");
	scanf("%d", &Begin);

	printf("\n*******Shortest Service Time First algorithm********\n");
	SSTF(TrackID, Begin);

	printf("\n*******************Scan algorithm*******************\n");
	SCAN(TrackID, Begin);
	
	return 0;
}
void Sort(int * head, int len)
{//冒泡排序
	int i, j, temp;

	for(i = 0; i < len; i++)
		for(j = 0; j < len - i - 1; j++)
		{
			if( head[j] > head[j+1] )
			{
				temp = head[j];
				head[j] = head[j+1];
				head[j+1] = temp;
			}
		}
}

int SSTF(int * head, int value)
{
	int Min,CurrentID = value;
	int pointer = 0, sum = 0, i, j;
	int MoveLen[MAX] = {0}, Next[MAX];//記錄碰頭移動的長度和訪問磁道的順序
	bool Finish[MAX];//磁道訪問情況

	for(i = 0; i < length; i++)
		Finish[i] = false;

	for(j = 0; j < length; j++)
	{
		Min = INF;
		for(i = 0; i < length; i++)//在未被訪問的磁道中找出下一個被訪問到的磁道
			if(abs(CurrentID - head[i]) < Min && Finish[i] == false)
			{
				Min = abs(CurrentID - head[i]);
				pointer = i;//記錄被訪問的磁道位置
			}
		
		MoveLen[j] = Min;
		Next[j] = head[pointer];
		Finish[pointer] = true;
		CurrentID = head[pointer];
	}

	printf("Next Accessed Track\tMove Length\n");
	for(i = 0; i < length; i++)//輸出尋道序列和移動長度
		printf("%d\t\t\t%d\n", Next[i], MoveLen[i]);

	for(i = 0; i < length; i++)//輸出最平均尋道長度
		sum += MoveLen[i];
	printf("the average seek track length: %.1f\n",(float)sum/length);
	
	return 1;
}

int SCAN(int * head, int value)
{
	int MoveLen[MAX] = {0}, Next[MAX];//記錄碰頭移動的長度和訪問磁道的順序
	int pointer = 0, CurrentID = value;//記錄開始訪問磁道的位置和碰頭所在磁道
	int sum = 0, i;
	bool flag = false;

	Sort(head, length);//對磁道號進行由小到大的排序

	for(i = 0; i < length; i++)
		if(value <= head[i])
		{//尋找第一個比碰所在磁道大的磁道
			pointer = i;
			flag = true;
			break;
		}
	
	if(flag == false)//所有磁道號比碰頭所在磁道號小
		pointer = length - 1;

	for(i = pointer; i < length; i++)
	{//先由里向外訪問每一個磁道
		Next[i - pointer] = head[i];
		MoveLen[i - pointer] = abs(head[i] - CurrentID);
		CurrentID = head[i];
	}

	for( i = pointer-1; i >= 0; i--)
	{//再由外向里訪問每一個磁道
		Next[length - i - 1] = head[i];
		MoveLen[length - i - 1] = abs(head[i] - CurrentID);
		CurrentID = head[i];
	}
	
	printf("Next Accessed Track\tMove Length\n");
	for(i = 0; i < length; i++)//輸出尋道序列和移動的長度
		printf("%d\t\t\t%d\n", Next[i], MoveLen[i]);

	for(i = 0; i < length; i++)//計算平均尋道長度
		sum += MoveLen[i];
	printf("the average seek track length: %.1f\n",(float)sum/length);

	return 1;
}