//LfU from R Techinique of Paging

#include<iostream.h>
#include<graphics.h>
#include<stdlib.h>
#include<conio.h>
struct str
{
	int pgno,f,p;
}q[20];

int seq,f,p,gd=DETECT,gm,lru[20],top=0,rear=0,x=200,y=50,pgflt=0,k=0;
void draw(int ,int);
void insert();
void replace(int);
int srclf();
int doesntexist(int);
void mov2stktop(int,int);
void main()
{
	clrscr();
	initgraph(&gd,&gm,"E:\\Turboc\\bgi");
	cout<<"\t\t\t\tLFU\n";
	cout<<"--------------------------------------------------------------\n\n";
	cout<<"Enter the no. of frames\n:";
	cin>>f;
	cout<<"Enter the no. of Pages\n:";
	cin>>p;
	cout<<"Enter the Sequence of Pages:\n";
	for(int i=0;i<p;i++)
		insert();
	cout<<"Total Pagefault = "<<pgflt;
	cout<<"\n\n\n\t\t\t..ANY KEY TO EXIT..";
	getch();
}
int srclf()
{
	int min;
	for(int i=0;i<f-1;i++)
	for(int j=i;j<f;j++)
		if(q[i].freq<q[j].freq)
			min=i;
		else min=j;
	return(min);
}
void insert()
{
	cin>>seq;
	if(doesntexist(seq)==1)
	{
		if((rear)==f)
		{
			replace(seq);
			lru[top-1]=seq;
		}
		else
		{
			q[rear].pgno=seq;
			rear=rear+1;
			lru[top]=seq;top++;
		}
		pgflt++;
	}
	else	mov2stktop(seq,1);
	x=x+30;
	draw(x,y);
}
void replace(int v)
{
	for(int i=0;i<f;i++)
		if(lru[k]==q[i].pgno)
		{
			q[i].pgno=v;
			break;
		}
	mov2stktop(lru[k],0);
}
void mov2stktop(int v,int h)
{
	int temp=0,te;
	for(int i=0;i<f;i++)
	{
		if(lru[i]==v)
		{	temp=i;break;	}
		if(v==q[i].pgno)
			q[i].f++;
	}
	for(i=temp;i<top-1;i++)
		lru[i]=lru[i+1];
	if(h==0)
		lru[top-1]=0;
	if(h==1)
		lru[top-1]=v;
}
int doesntexist(int v)
{
	for(int i=0;i<f;i++)
		if(q[i].pgno==v)
			return(0);
	return(1);
}
void draw(int x,int y)
{
	char str[10];
	for(int j=0;j<f;j++)
	{
		rectangle(x,y+j*30,x+30,y+j*30+30);
		itoa(q[j].pgno,str,10);
		outtextxy((2*(x)+30)/2,(2*(y+j*30)+30)/2,str);
	}
}