/*
 程序說明：
 裝入作業：采用最先適應算法。輸入要裝入的作業的大小，程序查找合適位置插入；若空間不足，給出"內存不足"的提示；若總的剩余空間足夠，但分配不連續，則提示整理內存；若作業總數已達最大值，在插入時給出提示，要求撤除不需要的作業。
 撤除作業：需要輸入要撤除的作業的起始地址，程序找到目標表目后，將其狀態置空，并檢查其相鄰表目，若為空，則合并之；若輸入的首地址沒有在表中找到，則提示錯誤；空閑表目不能再次被撤除；起始地址為零的表目為操作系統，不能被撤除。
 整理內存：將所有的已分配表目向低地址端移動，將其連成一片，所有空閑表目將被合并到表尾的"空表目"。
 print() 函數：用于輸出空閑分區表。

 部分變量說明：
 wlon 作業長度 ；whadr   起始地址 ；
 maxl 數組長度 ；nowlong 當前作業的總長度 ；
 i、j 、k 循環控制變量
 狀態表示：  1:已分配   0:空閑   -1:空表目
 */
///////////////////////////////////////////////////////////
#include<iostream.h>
#include<iomanip.h>

struct works //表目結構
{
	int hadr;		//起始地址
	int lon;		//長度
	int state;		//狀態
};
// 函數定義 //
bool load_works(works [],int &,int &);
bool remove_works(works [],int &,int &);
void print(works [],int,int);
void tidy_memory(works [],int &);
// *****   ***** //
const int MAX=2000;	//最大總長度（內存容量）
const int MAXWORKS=20;	//最多支持20個作業
void main()
{
	works w[MAXWORKS];	//最多支持20個作業
	int choice,maxl,nowlong;
	// ***裝入操作系統*** //
	cout<<"裝入操作系統.................."<<endl;
	w[0].hadr=0; 
	w[0].lon=1; 
	w[0].state=1;
	// *****   ***** //
	maxl=0;		//數組長度標志
	nowlong=1;	//當前總長度
	print(w,maxl,nowlong);	//輸出空閑分區表
	
	while(true)	//開始循環
	{
		cout<<" 1.裝入作業；2.撤除作業；3.整理內存；0.退出程序"<<endl;
		cout<<"CHOICE # > ";
		cin>>choice;
		if(choice==0)break;	//退出程序
		if(choice==1)		//裝入作業
		{
			if(maxl==MAXWORKS-1) //作業數已達最大值
			{
				cout<<"\n警告!作業數已達最大值,請撤除多余的作業以釋放空間!\n"<<endl;
				continue;
			}
			if(load_works(w,maxl,nowlong))
				print(w,maxl,nowlong);	//輸出空閑分區表
		}
		else
		if(choice==2)		//撤除作業
		{
			if(remove_works(w,maxl,nowlong))
				print(w,maxl,nowlong);	//輸出空閑分區表
		}
		else
		if(choice==3)		//整理內存
		{
			tidy_memory(w,maxl);
			print(w,maxl,nowlong);	//輸出空閑分區表
		}
		else continue;
	}//while(true)
}//main()
////////////////////////////////////////////////////////////
//裝入作業
bool load_works(works w[],int & maxl,int & nowlong)
{
	int wlon,i,j;
	cout<<"作業長度 > ";
	cin>>wlon;			//作業長度

	if(wlon>MAX-nowlong)
	{
		cout<<"\t***>>>>> 警告! 內存不足! <<<<<***"<<endl;
		return false;
	}

	for(i=0;i<=maxl;i++)
	{
		if(w[i].state==1)continue;//表目非空
		if(w[i].lon<wlon)continue;//表目長度太小

		if(w[i].lon==wlon)	//表長等于作業長度
		{
			w[i].state=1;	//修改表目狀態
			nowlong=nowlong+wlon;//修改當前內存容量
			return true;
		}

		for(j=maxl;j>i;j--)			//表長大于作業長度
			w[j+1]=w[j];			//w[i]以后表目后移一格
		//拆分w[i]并裝入作業
		w[i+1].hadr=w[i].hadr+wlon;	//修改w[i+1]首地址
		w[i+1].lon=w[i].lon-wlon;	//修改w[i+1]長度
		w[i+1].state=0;				//修改w[i+1]狀態
		w[i].lon=wlon;	//修改w[i]長度
		w[i].state=1;	//修改w[i]狀態
		maxl++;			//數組長度加1
		nowlong=nowlong+wlon;//修改當前內存容量
		return true;
	}//for(i=0;i<=maxl;i++)

	//原空閑表目不能滿足要求或無空閑表目
	if(i>maxl)
	{
		if((MAX-(w[i-1].hadr+w[i-1].lon))<wlon)//表尾空閑長度不足
		{
			cout<<"\t***>>>>> 提示...內存需要整理... <<<<<***"<<endl;
			return false;
		}
		//新建表目
		w[i].hadr=w[i-1].hadr+w[i-1].lon;//起始地址
		w[i].lon=wlon;	//長度
		w[i].state=1;	//狀態
		maxl++;			//數組長度標志加1
		nowlong=nowlong+wlon;//修改當前內存容量
	}
	return true;
}
///////////////////////////////////////////////////////////
//撤除作業
bool remove_works(works w[],int & maxl,int & nowlong)
{
	int whadr,i,j;
	cout<<"要撤除的作業的起始地址 & > ";
	cin>>whadr;
	if(whadr==0)
	{
		cout<<"\t***>>>>> 警告!操作系統不能被撤除! <<<<<***"<<endl;
		return false;
	}
	for(i=0;i<=maxl;i++)//查找目標表目
	{
		if(w[i].hadr==whadr)	//w[i]為符合的表目
		{
			if(w[i].state==0)
			{
				cout<<"\t***>>>>> 提示...表目已經為空... <<<<<***"<<endl;
				return false;
			}
			w[i].state=0;		//狀態置空
			nowlong=nowlong-w[i].lon;//修改當前內存容量

			if(w[i+1].state==0)	//如果w[i+1]為空，合并w[i]、w[i+1]
			{
				w[i].lon=w[i].lon+w[i+1].lon;
				for(j=i+1;j<maxl;j++)//w[i]以后表目前移一格
				{
					w[j].hadr=w[j+1].hadr;
					w[j].lon=w[j+1].lon;
					w[j].state=w[j+1].state;
				}
				maxl--;		//數組長度標志減1
			}//if(w[i+1].state==0)

			if(w[i-1].state==0)	//如果w[i-1]為空，合并w[i]、w[i-1]
			{
				w[i-1].lon=w[i-1].lon+w[i].lon;
				for(j=i;j<maxl;j++)//w[i-1]以后表目前移一格
				{
					w[j].hadr=w[j+1].hadr;
					w[j].lon=w[j+1].lon;
					w[j].state=w[j+1].state;
				}
				maxl--;		//數組長度標志減1
			}//if(w[i-1].state==0)
			return true;
		}//if(w[i].hadr==whadr)
	}//for(i=0;i<=maxl;i++)
	if(i>maxl)
	{
		cout<<"\t***>>>>> 警告!地址輸入錯誤! <<<<<***"<<endl;
		return false;
	}
	return true;
}
///////////////////////////////////////////////////////////
//輸出空閑分區表
void print(works w[],int maxl,int nowlong)	
{
	int k;
	cout<<setw(10)<<"起始地址"<<setw(10)<<"長度"<<setw(10)<<"狀態"<<endl;
	for(k=0;k<=maxl;k++)
		cout<<setw(10)<<w[k].hadr<<setw(10)<<w[k].lon<<setw(10)<<w[k].state<<endl;

	if((w[k-1].hadr+w[k-1].lon)<MAX)//輸出空表目
	cout<<setw(10)<<w[k-1].hadr+w[k-1].lon
		<<setw(10)<<MAX-(w[k-1].hadr+w[k-1].lon)
		<<setw(10)<<"-1"<<endl;

	cout<<"當前作業總長度："<<nowlong<<"\n當前空閑總長度："<<MAX-nowlong
		<<"\n當前內存使用率："<<(double(nowlong)/MAX)*100<<" %"<<endl;
}
///////////////////////////////////////////////////////////
//整理內存
void tidy_memory(works w[],int & maxl)
{
	int i,j;
	for(i=0;i<=maxl;i++)
	if(w[i].state==0)
	{
		for(j=i;j<maxl;j++)
		{
			w[j].hadr=w[j-1].hadr+w[j-1].lon;
			w[j].lon=w[j+1].lon;
			w[j].state=w[j+1].state;
		}
		maxl--;	//數組長度標志減1
	}
	cout<<" \t***... 內存整理完成 ...***"<<endl;
}