#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
using namespace std;
int maxdis(int *dis,int max)
{
int m=0;
for(int i=0;i<max;i++)
{
if(dis[i]>dis[m]) m=i;
}
return(m);
}
int found(int x,int *l,int j)
{
for(int i=0;i<j;i++)
if(l[i]==x){return(i);}
return(-1);
}
int found1(int x,int *temp,int max)
{
for(int i=0;i<max;i++)
if(temp[i]==x) return(i);
return(-1);
}
int main()
{
cout<<"\n\nEnter the maximum number of frames in the main memory:\t";
int max;
cin>>max;
int *temp=new int[max];
int *dis=new int[max];
int *flag=new int[max];
for(int i=0;i<max;i++) flag[i]=0;
cout<<"\n\nEnter the total number of page requests:\t";
int n,res;
cin>>n;
cout<<"\n\nEnter the entire sequence of page requests:\t";
int *a=new int[n];
for(int i=0;i<n;i++) a[i]=-1;
for(int i=0;i<n;i++) cin>>a[i];
cout<<"\n\nprocess pages are then allocated as follows:\n\n";
int j=0;
for(int i=0;i<max;)
{
cout<<"\n\npage "<<a[j]<<" has been allocated frame "<<i<<" in MM";
if((res=found(a[j],temp,i))!=-1) {cout<<"\n\npage "<<a[j]<<" already exists in frame "<<res<<" in MM";j++;}
else {j++;temp[i++]=a[i];}
}
for(int i=j;i<n;i++)
{
for(int z=0;z<max;z++) flag[z]=0;
if((res=found1(a[i],temp,max))!=-1) {cout<<"\n\npage already exists in frame "<<res<<" in MM";continue;}
cout<<"\n\npage fault has occured";
for(int x=0;x<max;x++)
for(int y=i+1;y<n;y++)
{
if(temp[x]==a[y] && flag[x]==0) {dis[x]=y;flag[x]=1;}
else if(flag[x]!=1) dis[x]=1000000;
}
int pos=maxdis(dis,max);
cout<<"\n\npage "<<a[i]<<" has been allocated frame "<<pos<<" in MM by replacing page "<<temp[pos];
temp[pos]=a[i];
}
delete[] temp;
delete[] dis;
delete[] flag;
delete[] a;
return(0);
}
