#include<iostream.h>
#include <stdlib.h>
#include <stdio.h>
#define  M  40
int N;
int queue[M];
int Y[M];
int F;
float S[3][2];
struct Pro
{
	int num,time;
};	
/*
int Input(int m,Pro p[M])
{   
	cout<<"請輸入實際頁數：";
	do
	{
		cin>>m;
		if(m>M)cout<<"數目太多，請重試"<<endl;
		else break;
	}while(1);
    cout<<endl<<"請輸入各頁面號"<<endl;
   	for(int i=0;i<m;i++)
	{
		cin>>p[i].num;
		p[i].time=0;
	}
	return m;
}
*/

int readData() 
{ 
  F=0;
  FILE *fp; 
  char fname[20]; 
  int i; 
  cout<<"請輸入頁面流文件名:"; 
  cin>>fname; 
  if((fp=fopen(fname,"r"))==NULL)
  { 
    cout<<"錯誤,文件打不開,請檢查文件名"; 
  } 
  else
  { 
    while(!feof(fp))
	{ 
      fscanf(fp,"%d ",&queue[F]); 
      F++; 
	} 
  } 
  cout<<"讀入的頁面流:"; 
  for(i=0;i<F;i++)
  { 
     cout<<queue[i]<<" "; 
  } 
  cout<<"\n";
  return F;
}

void print(Pro *page1)//打印當前的頁面
{
	Pro *page=new Pro[N];
	page=page1;
	for(int i=0;i<N;i++)cout<<   page[i].num<<"   ";
	cout<<endl;
}


int  Search(int e,Pro *page1  )
{
	Pro *page=new Pro[N];
	page=page1;
	for(int i=0;i<N;i++)if(e==page[i].num)return i;
	return -1;
}

int Max(Pro *page1)
{
	Pro *page=new Pro[N];
	page=page1;
	int e=page[0].time,i=0;
	while(i<N)//找出離現在時間最長的頁面
	{
		if(e<page[i].time)e=page[i].time;
		i++;
	}
    for( i=0;i<N;i++)if(e==page[i].time)return i;
	
	return -1;
}

int Compfu(Pro *page1,int i,int t,Pro p[M])
{
	Pro *page=new Pro[N];
	page=page1;
	
	int count=0;
	for(int j=i;j<M;j++)
	{
		if(page[t].num==p[j].num )break;
		else count++;
	}
	return count;
	
}
void Fifo(Pro p[M],Pro *page)
{    F=0;
	int t=0,i=0;//Y[0]=0;
	float n=0;
	cout<<"FIFO頁面調度算法"<<endl;
    //m=Input(m,p);
    F=readData();
   
	cout<<"頁面置換情況:   "<<endl;
	while(i<F)
	{
		if(Search(queue[i],page)>=0){i++;}//找到相同的頁面
		else 
			{  
			if(t==N){t=0;}
				else 
				{   
			    	n++;
					page[t].num=queue[i];
				    //Y[i]=page[t].num;
					print(page);
					t++;
				}
			}
	}
//	cout<<"淘汰頁面序列:";
//	for(i=0;i<F;i++){
	//	cout<<Y[i];}
	cout<<endl<<"缺頁次數："<<n<<"    缺頁率："<<n/F<<endl;      
	S[0][0]=n;S[0][1]=n/F;		
}

void Lru(Pro p[M],Pro *page)
{  	F=0;
	int t=0, i=0;
	float n=0;
	cout<<"LRU頁面調度算法"<<endl;
//	m=Input(m,p);
    F=readData();
	cout<<"頁面置換情況:   "<<endl; 
	while(i<F)
	{    
	 int k;
	 k=t=Search(queue[i],page);
	 if(t>=0)
	  page[t].time=0;
     else
		{  
		 n++; 
		 t=Max(page);
         page[t].num=queue[i];
		 page[t].time=0;
		}
		if(t==0){page[t+1].time++;page[t+2].time++;}
		if(t==1){page[2].time++;page[0].time++;}
		if(t==2){page[1].time++;page[0].time++;}
        if(k==-1)   print(page);				
		i++;
	}
	cout<<"缺頁次數："<<n<<"    缺頁率："<<n/F<<endl;
	S[1][0]=n;S[1][1]=n/F;
}

void Opt(Pro p[M],Pro *page)
{   F=0;
 	int t=0, i=0;
	float n=0;
   // m=Input(m,p);
	cout<<"OPT頁面調度算法"<<endl;
   F=readData();
   for(i=0;i<F;i++)
   { p[i].num=queue[i];}
	i=0;   
 while(i<F)
 {
  if(Search(queue[i],page)>=0)i++;
  else
	{
	 int temp=0,cn;
	 for(t=0;t<N;t++)
	 {
	  if(temp<Compfu(page,i,t,p))
		{
	     temp=Compfu(page,i,t,p);
		 cn=t;
		}
	 }
	page[cn]=p[i];
	n++;
	print(page);
	i++;
	}
 }
  cout<<"缺頁次數："<<n<<"    缺頁率："<<n/F<<endl; 
  S[2][0]=n;S[2][1]=n/F;
}
void compare()
{  
    cout<<"FIFO頁面置換算法"<<endl;
	cout<<"缺頁次數："<<S[0][0]<<"    缺頁率："<<S[0][1]<<endl;
	cout<<"LRU頁面置換算法"<<endl;
	cout<<"缺頁次數："<<S[1][0]<<"    缺頁率："<<S[1][1]<<endl;
	cout<<"OPT頁面置換算法"<<endl;
	cout<<"缺頁次數："<<S[2][0]<<"    缺頁率："<<S[2][1]<<endl;
}
void Build(void)
{
	cout<<"可用內存頁面數"<<endl;
	cin>>N;	
}
void quit()
{  N=0;
   F=0;
  int i=0;
  int t=0;
   free(S);
   free(queue);
}  
/**/
int main()
{   	//cout<<"可用內存頁面數"<<endl;
	//cin>>N;	

	Pro p[M];
  
	float n=0;
//	m=Input(m,p);
	int c=0;
	Pro *page=new Pro[N];
   cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl; 
   cout<<" ┃　　　 　請求調頁存儲管理的頁面調度　 　　　　  ┃"<<endl; 
   cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; 

	//readData();

	while(1)
	{   
		for(int i=0;i<N;i++)//初試化頁面基本情況
		{
			page[i].num=0;
			page[i].time=2-i;
		} 
		 i=0;
     	cout<<"*********************1:輸入可用頁面數"<<endl;
       cout<<"*********************2:FIFO頁面置換  "<<endl;
		cout<<"*********************3:LRU頁面置換   "<<endl;
		cout<<"*********************4:OPT頁面置換   "<<endl;
		cout<<"*********************5:算法比較      "<<endl;
		cout<<"*********************0:退出程序      "<<endl;
		cout<<endl;
		cout<<"請輸入功能號(0~5):";
		cin>>c;
		switch(c)
		{
		case 1:Build();break;
        case 2:Fifo(p,page); break;
        case 3:Lru(p,page);break;
        case 4:Opt(p,page);break;
		case 5:compare();break;
		case 0:quit();return 0;
		default:cout<<"輸入錯誤,請重新輸入"<<endl;break;
        }
   /* while*/
    }
   return 0;
}