#include<iostream>
using namespace std; 

int pop;//進程頁面總數
int pom;//內存分配頁面數
int callnum;//程序訪問串數
int callorder[100];//存儲訪問內存每一步程序和數據的頁號
int mempage[100];//內存中分配的頁面空間，用于存儲駐留在內存的頁號
int counter[100];//計數器，在FIFO算法中用于記錄頁面駐留內存的時間，在LFU算法中用于記錄頁面被訪問次數(在OPT算法中用做存儲內存頁面在將來出現的第一個位置,未出現值為0)
int is_pagelack;//是否缺頁的標志
int pagelacknum;//缺頁數

void display(int i,int ad){
	cout<<callorder[i]<<"              ";
	if(ad==-1){
		for(int i=0;i<pom;i++){
			cout<<mempage[i]<<" ";
	}
	}else{
		for(int j=0;j<ad+1;j++){
			cout<<mempage[j]<<" ";
		}
	}
	for(int k=0;k<16-pom*2;k++){
		cout<<" ";
	}
	if(is_pagelack){
		cout<<"不缺頁";
	}else{
		cout<<"缺頁！";
		pagelacknum++;	
		
	}
	cout<<endl;
}//結果輸出顯示

int max(){
	int maxnum=counter[0];
	int max_ad=0;
	for(int k=1;k<pom;k++){
		if(counter[k]>maxnum){
			maxnum=counter[k];
			max_ad=k;
		}
	}
	return max_ad;
}//計算計數器的最大值

void input(){
	int i;
	cout<<"請輸入進程頁面總數：";
	cin>>pop;
	cout<<"請輸入程序訪問串的步驟數：";
	cin>>callnum;
	cout<<"請輸入程序訪問內存的每一步程序和數據的頁號："<<endl;
	for(i=0;i<callnum;i++){
		int temp;
		cout<<"請輸入程序訪問內存的第"<<i+1<<"步所需的程序和數據的頁號：";
		cin>>temp;
		if(temp>-1 && temp<pop){
			callorder[i]=temp;
		}else{
			cout<<"該頁不存在！請重新輸入"<<endl;
			i--;
		}
	}
	cout<<"請輸入內存分配的頁面數：";
	cin>>pom;
	cout<<"初始化內存空間……"<<endl;
	for(int j=0;j<pom;j++){
		mempage[j]=-1;
	}
}//輸入

void cle(){
	for(int i=0;i<100;i++){
		counter[i]=0;
		
	}
	
}//初始化計數器

void clemem(){
	for(int i=0;i<100;i++){
		
		mempage[i]=-1;
	}
}//初始化內存空間

int find_space(){
	int flag=-1;
	for(int i=0;i<pom;i++){
		if(mempage[i]==-1){
			flag=i;
			break;
		}
	}
	return flag;
}//尋找空閑內存，返回空閑內存地址，如無空閑內存地址返回-1

int is_in_mem(int num){
	int flag=-1;
	for(int i=0;i<pom;i++){
		if(mempage[i]==num){
			flag=i;
		}
	}
	return flag;
}//在內存中尋找是否有該頁面,有返回該頁面地址，無返回-1

void fifo(){
	cle();
	clemem();
	for(int i=0;i<callnum;i++){
		is_pagelack=0;
		int flag=is_in_mem(callorder[i]);
		int ad=find_space();
		if(flag!=-1){
			is_pagelack=1;
			if(ad==-1){
				for(int j=0;j<pom;j++){
					counter[j]++;
				
				}
			}else{
				for(int n=0;n<ad;n++){
					counter[n]++;
					
				}
			}
			
		}else{
			if(ad!=-1){
				mempage[ad]=callorder[i];
				for(int o=0;o<ad+1;o++){
					counter[o]++;
					
				}
			}else{
				int m=max();//找出駐留內存時間最久的頁面，max用于記錄最大的時間值，max_add用于記錄駐留內存時間最久的頁面所占的內存地址
				mempage[m]=callorder[i];
				counter[m]=0;
				for(int l=0;l<pom;l++){
					counter[l]++;
					
				}
			}
		}
		display(i,ad);
	}
}//FIFO算法

void lru(){
	clemem();
	for(int i=0;i<callnum;i++){
		is_pagelack=0;
		int flag=is_in_mem(callorder[i]);
		int ad=find_space();
		if(flag!=-1){
			is_pagelack=1;
			int temp=mempage[flag];
			for(int j=flag;j>0;j--){
					mempage[j]=mempage[j-1];
				}
				mempage[0]=callorder[i];
		}else{
			if(ad!=-1){
				
				for(int k=ad;k>0;k--){
					mempage[k]=mempage[k-1];
				}
				mempage[0]=callorder[i];
			}else{
				for(int l=pom-1;l>0;l--){
					mempage[l]=mempage[l-1];
				}
				mempage[0]=callorder[i];
			}
		}
	
		
		display(i,ad);
	}
}//LRU算法

void opt(){
	cle();
	clemem();
	for(int i=0;i<callnum;i++){
		is_pagelack=0;
		int flag=is_in_mem(callorder[i]);
		int ad=find_space();
		if(flag!=-1){
			is_pagelack=1;
		}else{
			if(ad!=-1){
				mempage[ad]=callorder[i];
			}else{
				if(i!=callnum-1){
					for(int j=0;j<pom;j++){
						for(int k=i+1;k<callnum;k++){
							if(mempage[j]==callorder[k]){
								counter[j]=k;
								
								break;
							}
						}
					}
					int flag_1=0;
					for(int l=0;l<pom;l++){
						if(counter[l]==0){
							flag_1=1;
							mempage[l]=callorder[i];				
							break;
						}
					}
					if(flag_1==0){
						int toreplace=max();
						mempage[toreplace]=callorder[i];
					}
					cle();
				}else{
					mempage[0]=callorder[i];
				}
			}
		}
		display(i,ad);
	}
}//OPT算法

void mainpan(){
	pagelacknum=0;
	int i;
	cout<<"歡迎使用請求頁式管理置換算法分析程序!"<<endl;
	cout<<"1、FIFO算法"<<endl;
	cout<<"2、LRU算法"<<endl;
	cout<<"3、OPT算法"<<endl;
	cout<<"4、退出"<<endl;
	cout<<"請選擇一種算法或退出程序:"<<endl;
	cin>>i;
	cout<<"當前訪問頁面號 "<<"內存頁面存儲狀態";
		if((pom*2)>16){
			for(int j=0;j<pom*2-16;j++){
				cout<<" ";
			}
		}
	cout<<"是否缺頁"<<endl;
	switch(i){
		case 1:{
			fifo(); 
			break;
			   }
		case 2:{
			lru(); 
			break;
			   }
		case 3:{
			opt(); 
			break;
			   }
		case 4: {
			exit; 
			break;
				}
		default: {
			cout<<"輸入錯誤！請重新輸入："<<endl;
			mainpan();
				 }
	}
	cout<<"缺頁數為"<<pagelacknum<<endl;
	cout<<"缺頁率為"<<pagelacknum/float(callnum)<<endl;
	mainpan();
}//程序主界面

void main(){
	input();
	mainpan();
}