#include<stdio.h>
#define  M  40
int N;

struct Pro
{
	int num,time;
};

int Input(int m,Pro p[M])
{   
	printf("Please input the actual page amount:");//輸入實際頁面數
	do
	{
		scanf("%d",&m);
		if(m>M)
                   printf("the amount is too large，please enter again.\n");//數目太大，請重試
		else break;
	}while(1);
    printf("please input the numbers of pages\n");//輸入各頁面號
   	
       for(int i=0;i<m;i++)
	{
		scanf("%d",&p[i].num);
		p[i].time=0;
	}
	return m;
}

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


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;
	
}

int main()
{
    
	printf("usable pages in memory:");//可用內存頁面數
	scanf("%d",&N);	
	Pro p[M];
	Pro *page=new Pro[N];
	char c;
	int m=0,t=0,i;
	float n=0;
	m=Input(m,p);	
	
	do{
		
		for(i=0;i<N;i++)//初試化頁面基本情況
		{
			page[i].num=0;
			page[i].time=2-i;
		}
		
        i=0;		
printf("f:FIFO arithmetic\n");
printf("l:LRU arithmetic\n"); 
printf("o:OPT arithmetic\n"); 
printf("press other keys to exit\n");
	scanf("%c",&c);
		scanf("%c",&c);

		if(c=='f')//FIFO頁面置換
		{
			n=0;
			printf("circs:   \n");//頁面置換情況
			while(i<m)
			{
				if(Search(p[i].num,page)>=0)
                                        i++;                //找到相同的頁面
				else 
				{  
					if(t==N)t=0;
					else 
					{
						n++;
						page[t].num=p[i].num;
						print(page);
						t++;
					}
				}
			}
			printf("times of lacking of pages：%f rate of lacking of pages：%f\n",n,n/m);      //缺頁次數與缺頁率
			
		}

		if(c=='l')//LRU頁面置換
		{    n=0;
		printf("circs:   \n");//頁面置換情況 
		while(i<m)
		{    
			int k;
			k=t=Search(p[i].num,page);
			if(t>=0)
				
				page[t].time=0;
			
			
			else
			{  
				n++; 
				t=Max(page);
				
				page[t].num=p[i].num;
				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++;
		}
		printf("times of lacking of pages：%f rate of lacking of pages：%f\n",n,n/m);//缺頁次數與缺頁率 
		}

		if(c=='o')//OPT頁面置換
		{
			n=0;
			while(i<m)
			{
				if(Search(p[i].num,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++;
				}
			}
			printf("times of lacking of pages：%f rate of lacking of pages：%f\n",n,n/m);//缺頁次數與缺頁率 
		}
		
	}while(c=='f'||c=='l'||c=='o');
	
	
	return 0;
}