#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define maxsize 1024
int Memory[maxsize],flag=0,flag_number=0,count=0;
int spare_memory=maxsize;
struct pcb		//pcb結構體的定義.
{ char name[10];
  int id;
  int state;		//規定0:空白,1:就緒,2:運行,3阻塞.
  int address; 
  int length;
};
typedef struct node   //鏈表的描述.
{ pcb pcb_data;
  struct node *next;
}linklist;               
linklist *null_head=NULL,*ready_head=NULL,*run_head=NULL,*block_head=NULL,*variable=NULL;//空,就緒,運行,阻塞三個隊列的隊頭.
//******************************************************************
linklist *nullpcb_list()                 //空白PCB隊列的建立.
{   
   linklist *head,*s;
	head=NULL;
	int i;
	for(i=9;i>=0;i--)
	{ 
	  s=(linklist *)malloc(sizeof(linklist));
	  s->pcb_data.id=i+1;
	  s->pcb_data.length=-1;
	  s->next=head;
      head=s;
	}
	return head;
}
//********************************************
void Memory_()
{
    for(int i=0;i<=(maxsize-1);i++)
	Memory[i]=0;
}
//********************************************
		void out_put()
		{
		     cout<<"Thanks for using my program !"<<endl
		 	    <<"CopyRight(c) 2004-2018 LIPENG   "<<endl
		 	    <<"This is a program for OS    "<<endl
		 	    <<"Input your command:(please enter 'h' for help)"<<endl
			    <<">";	
		}
		//***************************************************
		void list()
		{
		      cout<<"help: Commmand list:"<<endl
			  <<"C: Creat a process.You must input the name of process."<<endl
			  <<"D: Destroy a process.You must input the name of process."<<endl
			  <<"P: Call a process.You must input the name of process."<<endl
			  <<"E: End the process"<<endl
			  <<"B: Block the process.You must input the name of process."<<endl
			  <<"W: Wakeup the process.You must input the name of process."<<endl
			  <<"T: Time over"<<endl
			  <<"S: Show All the process name."<<endl
			  <<"H: Help."<<endl
		      <<"Enter: Execute a comamd ramdom."<<endl
			  <<"#: Exit the program."<<endl;
		}//*****************************************************************
           
		int not_number(char *number1)//???????????????????????????????????
		{
		   int i=0;
		   int tokenval=0;   
	       while(*(number1+i)!='\0')
 	       {	
			  if((*(number1+i)<'0')||(*(number1+i)>'9'))
			  {
					*(number1+i)='\0';
					flag_number=1;
					tokenval=0;

			  }
			  else
			  {
					tokenval=tokenval*10+*(number1+i)-'0';
				    i++;
			  }
	       }
			return tokenval;
		}
	//*******************************************************
	void memory(int pcbmemory,int sparememory)    ////////////////////////
		{    int w;
			 w=sparememory-pcbmemory;
			 if(w>=0)
			 {
				 cout<<"該進程占據內存  :"<<pcbmemory<<"K"<<endl;
				 cout<<"當前剩余空間    :"<<sparememory<<"K"<<endl;
				 cout<<"創建后內存將剩余:"<<sparememory-pcbmemory<<"K"<<endl;
			 }
			 else
			 {
			    cout<<"您的內存不夠,不能創建該進程!"<<endl;
			    cout<<"該進程占據內存為:"<<pcbmemory<<"K"<<endl;
			    cout<<"當前剩余空間僅為:"<<sparememory<<"K"<<endl;
			 }
		}
//****************************************************************
			linklist *headout(linklist *outhead)	                	//null pcb出隊列函數.
			{   linklist *p;
			    variable=outhead;
				p=outhead->next;
				variable->next=NULL;
				outhead=p;
				return outhead;
			}
			//******************************************************
            
			linklist *else_headout(linklist *outhead,char p_name[10])//非空pcb出隊函數.
			{
				linklist *p,*q;
				int i=0;
				if(outhead->next==NULL)
				{  
					if(strcmp(outhead->pcb_data.name,p_name)==0)
					{
					variable=outhead;
					variable->next=NULL;
					outhead=NULL;
					flag=1;
					return outhead;
					}
					else
					{	cout<<"系統無法找到或操作 '"<<p_name<<"' 進程!"<<endl;
					    flag=0;
					    return outhead;	
					
					}
				}
				else if(strcmp(outhead->pcb_data.name,p_name)==0)
				{   
					q=outhead->next;
					variable=outhead;
					variable->next=NULL;
					outhead=q;
					flag=1;
					return outhead;
				}
				else 
				{		p=outhead;
						while((outhead->next!=NULL)&&(i==0))
						{   
							if(strcmp(outhead->next->pcb_data.name,p_name)==0)
							{   q=outhead->next->next;
								variable=outhead->next;
								variable->next=NULL;
								outhead->next=q;
								flag=1;
								i=1;
							}
							else
							{
								outhead=outhead->next;
							}
						}
						if(i==0)
						{
						  flag=0;
						cout<<"系統無法找到或操作 '"<<p_name<<"' 進程!"<<endl;
						}
						outhead=p;
						return outhead;		
				}

			}
//*****************************************************************
		    linklist *headin(linklist *inhead,linklist *q)		//pcb入隊列函數.
			{   
				linklist *w;
				w=inhead;
				if(inhead==NULL)
				{
					q->next=NULL;
					inhead=q;

					return inhead;
				}
				else
				{
					    for(int i=0;i<=9;i++)
						{  if(inhead->next==NULL)
							{
								i=10;
							}     
							else
							{
							 inhead=inhead->next;
							}
						}
						inhead->next=q;
						q->next=NULL;
						inhead=w;
						return inhead;
				}
			}
//**************************************************************************
			int deal_memory(int *memory,int length_)     //分配內存函數并返回address.
			{  
				int address_,count=0,i=0,j;
				for(int k=0;k<maxsize;k++)
				{
			       while(i<=(maxsize-1))
				   {
					    if(*(memory+i)==0)
						{  address_=i;
						   i=maxsize;
						}	
						else
						{
							i++;
						}
				   }
				   for(j=address_;j<=(address_+length_-1);j++)
				   {	if(*(memory+j)==0)	
						{
							*(memory+j)=1;
							count++;
							if(count==length_)
							{
								k=maxsize;
							}
						}
						else
						{
							i=j;
							j=maxsize;
							k++;	
						}
				   }
				}
				   return address_;
			}
			//***********************************************************
		    void callBackMemory(int address_1,int length_)     //回收內存函數
			{  
				   int j;
				   for(j=address_1;j<=(address_1+length_-1);j++)
				   {
				        Memory[j]=0;  
				   }
			}
//***************************************************************************8
void create()
{   
  if(count<=10)
  {
		char name1[10],input;
		int memory_pcb1;
		char memory_pcb2[10];
		cout<<"please enter the name of pcb:"<<endl;
		cin>>name1;
		strcpy(null_head->pcb_data.name,name1);
		cout<<"請輸入創建該進程所需要的內存(單位:K):"<<endl;
		cin>>memory_pcb2;
        memory_pcb1=not_number(memory_pcb2);
		if(flag_number!=1)
		{
			cout<<"確認是否創建該進程:Y/N?"<<endl;
			cin>>input;
			if(input=='y')
			{
				 null_head->pcb_data.length=memory_pcb1;
	   			 memory(memory_pcb1,spare_memory);
				 null_head=headout(null_head);
				 variable->pcb_data.address=deal_memory(Memory,variable->pcb_data.length);
				 ready_head=headin(ready_head,variable);
				 spare_memory=spare_memory-variable->pcb_data.length;
				 ready_head->pcb_data.state=1;
				 count++;
				 cout<<endl;
				 cout<<"進程 '"<<name1<<"' 已創建成功!"<<endl;
				 cout<<"NAME   :"<<name1<<endl
				  	<<"ID     :"<<variable->pcb_data.id<<endl;
				if(ready_head->pcb_data.state==1)
				 {
	 			 cout<<"STATE  :"<<"READY"<<endl;
				 }
				 cout<<"ADDRESS:"<<variable->pcb_data.address<<endl
					<<"LENGTH :"<<variable->pcb_data.length<<endl;
			}
			else if(input=='n')
			{	  
				  cout<<"您剛才創建的名為 '"<<name1<<"' 的進程已被系統成功刪除!"<<endl;
			}
			else 
			{
				cout<<"該命令非法!"<<endl;
			}
		}
		else
		{
			    cout<<"該數字非法!!!"<<endl;
				flag_number=0;
		}
  }
  else
  {
	cout<<"PCB已無剩余,不可再申請!"<<endl;
  }
}
//*********************************************************************

void call()
{
	char name_call[10];
	if(ready_head==NULL)
	{
		cout<<"系統中無READY進程!"<<endl;
	}
	else if(run_head!=NULL)
	{
		cout<<"系統中存在正在運行的進程,該進程無法運行,請等待..."<<endl;
	}
    else
	{   
		cout<<"Please enter the name you want to call:"<<endl;
	    cin>>name_call;
		ready_head=else_headout(ready_head,name_call);
		if(flag==1)
		{
		variable->pcb_data.state=2;
		run_head=headin(run_head,variable);
		cout<<"進程 '"<<run_head->pcb_data.name<<"' 開始運行!"<<endl;
		flag=0;
		}
		else
		{
		cout<<"系統中無 '"<<name_call<<"' 進程!"<<endl;
		}
	}
}
//***************************************************************************
void destroy()
{	char name_destroy[10];
	if(run_head==NULL)
	{
		cout<<"系統中無READY進程!"<<endl;
	}
	else
	{   
		cout<<"Please enter the name you want to destroy:"<<endl;
	    cin>>name_destroy;
		run_head=else_headout(run_head,name_destroy);
		if(flag==1)
		{
		null_head=headin(null_head,variable);
		callBackMemory(variable->pcb_data.address,variable->pcb_data.length);
		variable->pcb_data.state=0;
        spare_memory=spare_memory+variable->pcb_data.length; 
		cout<<"進程 '"<<variable->pcb_data.name<<"' 已被系統刪除!"<<endl
			<<"PCB '"<<variable->pcb_data.name<<"' 原占用系統內存 "<<variable->pcb_data.length<<" K已釋放!"<<endl;
		flag=0;
		count--;
		}
		cout<<"系統剩余空間: "<<spare_memory<<" K"<<endl;
	}  
}
//*********************************************************************************
void end()
{
	char name_end[10];
	if(run_head==NULL)
	{
		cout<<"系統中無RUN進程!"<<endl;
	}
	else
	{   
		cout<<"Please enter the name you want to block:"<<endl;
	    cin>>name_end;
		run_head=else_headout(run_head,name_end);
		if(flag==1)
		{
		ready_head=headin(ready_head,variable);
		variable->pcb_data.state=1;
		cout<<"進程 '"<<variable->pcb_data.name<<"' 已進入就緒狀態!"<<endl;
		flag=0;
		}
	}
}
//***********************************************************************************
void block()
{	
	char name_block[10];
	if(run_head==NULL)
	{
		cout<<"系統中無RUN進程!"<<endl;
	}
	else
	{   
		cout<<"Please enter the name you want to block:"<<endl;
	    cin>>name_block;
		run_head=else_headout(run_head,name_block);
		if(flag==1)
		{
		block_head=headin(block_head,variable);
		variable->pcb_data.state=3;
		cout<<"進程 '"<<variable->pcb_data.name<<"' 已進入阻塞狀態!"<<endl;
		flag=0;
		}
	}
}
//**************************************************************************************
void wakeup()
{
	char name_wakeup[10];
	if(block_head==NULL)
	{
		cout<<"系統中無阻塞進程!"<<endl;
	}
	else
	{   
		cout<<"Please enter the name you want to wakeup"<<endl;
	    cin>>name_wakeup;
		block_head=else_headout(block_head,name_wakeup);
		if(flag==1)
		{
		ready_head=headin(ready_head,variable);
		variable->pcb_data.state=1;
		cout<<"進程 '"<<variable->pcb_data.name<<"' 已進入就緒狀態!"<<endl;
		flag=0;
		}
	}
}
//******************************************************************************
void time()
{
	cout<<"time over"<<endl;
}
//******************************************************************************
void show()
{	linklist *run,*ready,*block,*null_;
	cout<<"  READY      :  ";
	ready=ready_head;
	while(ready_head!=NULL)
	{
	cout<<ready_head->pcb_data.name<<"  -->  ";
	ready_head=ready_head->next;
	}
	ready_head=ready;
	cout<<"NULL"<<endl;
	cout<<"  RUN        :  ";
	run=run_head;
	while(run_head!=NULL)
	{
	cout<<run_head->pcb_data.name<<"  -->  ";
	run_head=run_head->next;
	}
	run_head=run;
	cout<<"NULL"<<endl;
	cout<<"  BLOCK      :  ";
	block=block_head;
	while(block_head!=NULL)
	{
	cout<<block_head->pcb_data.name<<"  -->  ";
	block_head=block_head->next;
	}
	block_head=block;
	cout<<"NULL"<<endl;
	int i=0;
	null_=null_head;
	while(null_head!=NULL)
	{
        i++;
	    null_head=null_head->next;
	}
	null_head=null_;
	cout<<"  空白PCB個數:   "<<i<<" 個."<<endl;
	cout<<"  進程共占用內存 "<<maxsize-spare_memory<<" K,剩余空間: "<<spare_memory<<" K"<<endl;
}
//********************************************************************************
void enter()
{
	cout<<"The system is executing a command random..."<<endl;
}
void exit()
{
    char c;
	cout<<"Will you exit this system?Y/N..."<<endl;
	cin>>c;
	if(c=='y')
	{
		exit(0);
	}
}
void main()
{    
	 Memory_();
	 null_head=nullpcb_list();
	 out_put();
  	 char in_put;
  	 cin>>in_put;
   	 while(in_put)
  	 {
  	     switch(in_put)
  	     {
     	   case('h'):	list();
				break; 
		   case('c'):   create();
				break;
		   case('d'):   destroy();
			    break;
	   	   case('p'):   call();
				break;
	   	   case('e'):   end();
				break;
	   	   case('b'):   block();
				break;
	  	   case('w'):   wakeup();
				break;
	 	   case('t'):   time();
				break;
		   case('s'):   show();
				break;
		   case('\n'):  enter();
				break;
		   case('#'):   exit();
				break;
		   default:     cout<<"The word you enter is wrong~!"<<endl;
				break;
	     }
	     cin>>in_put;
       }
}