//Least Frequently Used Page Replacement Techinique
#include<math.h>
#include<iostream.h>
#include<graphics.h>
#include<stdlib.h>
#include<conio.h>
struct str
{
	int pgno,freq,p;
}q[20];

int seq,f,p,gd=DETECT,gm,top=0,count=0,rear=0,x=200,y=50,pgflt=0,k=1;

void draw(int ,int);
int srclf();
void insert();
void replace(int);
int doesntexist(int);
void draw();
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();
	closegraph();
	restorecrtmode();
}
void insert()
{
	cin>>seq;
	if(doesntexist(seq)==1)
	{	if(count==f)
		{
			replace(seq);
		       //	lfu[top-1]=seq;
		}
		else
		{
			q[count].pgno=seq;
			q[count].freq++;
			q[count].p=k;
			k++;
			count++;
		}
		pgflt++;
	}
	x=x+30;
	draw(x,y);
}
void replace(int v)
{
	int mf=srclf(),c=0;
	q[mf].pgno=v;
	q[mf].freq++;
	q[mf].p=k;
	k++;
      /*	for(int t=0;t<f;t++)
	{
		if(q[mf]==q[t])*/
}
int srclf()
{
	int min=0;
	for(int i=0;i<f;i++)
	{
		if((float)(q[i].freq)/(q[i].p)<(float)(q[min].freq)/(q[min].p))
//		if(q[i].freq<=q[min].freq)
			min=i;
	}
	q[min].freq=0;
	return(min);
}
int doesntexist(int v)
{
	for(int i=0;i<f;i++)
		if(q[i].pgno==v)
		{
			q[i].freq++;
			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);
	}
}