using System;
using System.IO;


namespace zuoye
{
	[Serializable]
	public class Job
	{
		public string Name;
		public DateTime EnterTime;
		public TimeSpan EstimatedRunningTime;
		public DateTime CompleteTime;
		public bool Scheduled = false;
		public Job(string jobName, DateTime enterTime, TimeSpan ert)
		{
			this.Name = jobName;
			this.EnterTime = enterTime;
			this.EstimatedRunningTime = ert;
		}

		public Job() { }

		public override string ToString()
		{
			return EnterTime.ToString();
		}

	}

	/// <summary>
	/// 調度程序的基類, 抽象類
	/// </summary>
	[Serializable]
	public abstract class JobScheduler
	{
		public Job[] Jobs;

		/// <summary>
		/// 對一個作業集合進行調度, 計算其平均周轉時間, 平均加權調度時間以及每個作業的完成時刻
		/// </summary>
		/// <param name="jobs"></param>
		public abstract void Schedule();

		/// <summary>
		/// 平均周轉時間
		/// </summary>
		public TimeSpan AverageWorkingTime;

		/// <summary>
		/// 平均加權周轉時間
		/// </summary>
		public double AverageWeightedWorkingTime;

		/// <summary>
		/// 獲得沒有調度的作業中最早進入調度程序的作業
		/// </summary>
		/// <param name="jobs"></param>
		/// <returns></returns>
		protected Job GetFirstComeJob()
		{
			Job min = null;
			for (int i = 0; i < this.Jobs.Length; i++)
			{
				if (!this.Jobs[i].Scheduled)
				{
					if (min == null)
					{
						min = this.Jobs[i];
					}
					else if (this.Jobs[i].EnterTime < min.EnterTime)
					{
						min = this.Jobs[i];
					}
				}
			}
			return min;
		}

		protected void CalculateTime()
		{
			TimeSpan workingTime = TimeSpan.Zero;
			double weightedWorkingTime = 0;
			for (int i = 0; i < this.Jobs.Length; i++)
			{
				TimeSpan w = Jobs[i].CompleteTime - Jobs[i].EnterTime;
				workingTime += w;
				weightedWorkingTime += w.TotalMilliseconds / Jobs[i].EstimatedRunningTime.TotalMilliseconds;
			}
			this.AverageWorkingTime = TimeSpan.FromMilliseconds(workingTime.TotalMilliseconds / Jobs.Length);
			this.AverageWeightedWorkingTime = weightedWorkingTime / Jobs.Length;
		}
	}

	/// <summary>
	/// First Coming First Service 調度程序
	/// </summary>
	[Serializable]
	public class FCFSScheduler : JobScheduler
	{
		public FCFSScheduler(Job[] jobs)
		{
			this.Jobs = jobs;
		}

		public override void Schedule()
		{
			DateTime current = GetFirstComeJob().EnterTime;
			Job j = null;
			while ((j = GetFirstComeJob()) != null)
			{
				j.Scheduled = true;
				if (j.EnterTime < current) // current 時刻前已經在等待, 作業立刻開始運行
				{
					current += j.EstimatedRunningTime;
				} 
				else // 作業在 current 時刻后才開始運行
				{
					current = j.EnterTime + j.EstimatedRunningTime;
				}
				j.CompleteTime = current;
			}
			CalculateTime();
		}
	}

	/// <summary>
	/// Shortest Job First 調度程序
	/// </summary>
	[Serializable]
	public class SJFScheduler : JobScheduler
	{
		public SJFScheduler(Job[] jobs)
		{
			this.Jobs = jobs;
		}

		public override void Schedule()
		{
			Job first = GetFirstComeJob();
			DateTime current = first.EnterTime + first.EstimatedRunningTime;
			first.CompleteTime = current;
			first.Scheduled = true;
			Job j = null;
			while ((j = GetShortestEnteredJob(current)) != null)
			{
				j.Scheduled = true;
				if (j.EnterTime < current)
				{
					current += j.EstimatedRunningTime;
				}
				else
				{
					current = j.EnterTime + j.EstimatedRunningTime;
				}
				j.CompleteTime = current;
			}
			CalculateTime();
		}

		/// <summary>
		/// 得到最短運行時間而且在now時刻以及進入調度程序的未被調度的作業
		/// </summary>
		/// <param name="now"></param>
		/// <returns></returns>
		public Job GetShortestEnteredJob(DateTime now)
		{
			Job r = null;
			for (int i = 0; i < Jobs.Length; i++)
			{
				Job j = Jobs[i];
				if (!j.Scheduled && j.EnterTime <= now)
				{
					if (r == null)
					{
						r = j;
					}
					else if (j.EstimatedRunningTime < r.EstimatedRunningTime)
					{
						r = j;
					}
				}
			}
			if (r == null) // now 時刻沒有等待中的作業, 則返回下一個最先進入等待隊列的作業
			{
				r = GetFirstComeJob();
			}
			return r;
		}
	}

	/// <summary>
	/// 主程序
	/// </summary>
	public class Program
	{
		[STAThread]
		static void Main(string[] args)
		{
			Job[] jobs = new Job[4];
			jobs[0] = new Job("1", GetTime(8, 0), TimeSpan.FromMinutes(120));
			jobs[1] = new Job("2", GetTime(8, 50), TimeSpan.FromMinutes(50));
			jobs[2] = new Job("3", GetTime(9, 0), TimeSpan.FromMinutes(10));
			jobs[3] = new Job("4", GetTime(9, 50), TimeSpan.FromMinutes(20));

			SJFScheduler s = new SJFScheduler(jobs);
			s.Schedule();
			
			for (int i = 0; i < s.Jobs.Length; i++)
			{
				Console.WriteLine("作業"+s.Jobs[i].Name + "進入時間: " + s.Jobs[i].EnterTime);
			}
			Console.WriteLine("\n");
			Console.WriteLine("SJF作業調度:");
			for (int i = 0; i < s.Jobs.Length; i++)
			{
				Console.WriteLine("作業"+s.Jobs[i].Name + "完成時間: " + s.Jobs[i].CompleteTime);
			}
			Console.WriteLine("SJF平均周轉時間:"+s.AverageWorkingTime.TotalMinutes);
			Console.WriteLine("SJF帶權平均周轉時間:"+s.AverageWeightedWorkingTime);

			for (int i = 0; i < jobs.Length; i++)
				jobs[i].Scheduled = false;
			FCFSScheduler f = new FCFSScheduler(jobs);
			f.Schedule();
			Console.WriteLine("\n");
			Console.WriteLine("FCFS作業調度:");
			for (int i = 0; i < f.Jobs.Length; i++)
			{
				Console.WriteLine("作業"+f.Jobs[i].Name + "完成時間: " + f.Jobs[i].CompleteTime);
			}
			Console.WriteLine("FCFS平均周轉時間:"+f.AverageWorkingTime.TotalMinutes);
			Console.WriteLine("FCFS帶權平均周轉時間:"+f.AverageWeightedWorkingTime);
		}
		static DateTime GetTime(int hour, int minute)
		{
			return new DateTime(2007, 5, 16, hour, minute, 0);
		}
	}
}