#include<stdio.h>
void FIFO();
void LEASTRECENTLYUSED();
void OPTIMAL();

int main()
{
    int ch;
    do
    {
        printf("\n\n\t1.FIFO\n\t2.LEASTRECENTLYUSED\n\t3.Optimal\n\t4.Exit\n\tEnter Choice : ");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:
            FIFO();
            break;
            case 2:
            LEASTRECENTLYUSED();
            break;
            case 3:
            OPTIMAL();
            break;
        }
    }while(ch!=4);
}
void FIFO()
{
    int frame[3]={-1,-1,-1},refer[20],ctn=0,i,j,number,flag;
    float ratio,hitctn=0.00;
    printf("\n\tEnter length of refererence string : ");
    scanf("%d",&number);
    printf("\n\tEnter refererence String with giving space ....\n\t");
    for(i=0;i<number;i++)
    scanf("%d",&refer[i]);
    //printf("\n\tExecution is started here .....");
    for(i=0;i<number;i++)
    {
        flag=0;
        for(j=0;j<3;j++)
        if(frame[j]==refer[i])
        {
            printf("\n\tPage Hit ");
            hitctn++;
            flag=1;
            break;
        }

        if(flag==0)
        {
            printf("\n\tPage Miss");
            printf("\tBefore :\t");
            for(j=0;j<3;j++)
            printf(" %d",frame[j]);
            frame[ctn]=refer[i];
            ctn++;
            if(ctn>=3)
            ctn=0;
            printf("\tAfter :\t");
            for(j=0;j<3;j++)
            printf(" %d",frame[j]);
        }
    }
ratio=hitctn/number;
printf("\n\n\tHit ratio = %f ",ratio);
}
void LEASTRECENTLYUSED()
{
    int frame[3]={-1,-1,-1},used[3]={-1,-1,-1},ctn=0,refer[20],i,j,flag,number,index,value;
    float ratio,hitctn=0;
    printf("\n\tEnter length of refererence string : ");
    scanf("%d",&number);
    printf("\n\tEnter refererence String with giving space \n\t");
    for(i=0;i<number;i++)
    scanf("%d",&refer[i]);
    //printf("\n\tExecution is started ");
    for(i=0;i<number;i++)
    {
        flag=0;
        for(j=0;j<3;j++)
        if(frame[j]==refer[i])
        {
            printf("\n\tPage Hit ");
            hitctn++;
            flag=1;
            used[j]=ctn;
            break;
        }
        if(flag==0)
        {
            printf("\n\tPage Miss");
            printf("\tBefore :");
            for(j=0;j<3;j++)
            printf(" %d",frame[j]);
            //selection of Fault for replacement
            index=0;
            value=used[0];
            if(ctn!=0) {
            for(j=0;j<3;j++)
            if(value>used[j]&&value!=used[j])
            {
                index=j;
                value=used[j];
            }
        }
        //printf("\tFault is %d ",index);
        frame[index]=refer[i];
        used[index]=ctn;
        printf("\tAfter :");
        for(j=0;j<3;j++)
        printf(" %d",frame[j]);
    }
ctn++;
}
ratio=hitctn/number;
printf("\n\n\tHit ratio = %f ",ratio);
}
void OPTIMAL()
{
    int frame[3]={-1,-1,-1},used[3]={-1,-1,-1},ctn=0,refer[20],i,j,flag,number,value1,value2,value3,index;
    float ratio,hitctn=0;
    printf("\n\tEnter length of refererence string : ");
    scanf("%d",&number);
    printf("\n\tEnter refererence String with giving space \n\t");
    for(i=0;i<number;i++)
    scanf("%d",&refer[i]);
    //printf("\n\tExecution is started here ");
    for(i=0;i<number;i++)
    {
        flag=0;
        for(j=0;j<3;j++)
        if(frame[j]==refer[i])
        {
            flag=1;
            printf("\n\tPage Hit");
            hitctn++;
            break;
        }
    if(flag==0)
    {
    printf("\n\tPage Miss");
    if(ctn<3)
    {
        frame[ctn]=refer[i];
        printf("\tStatus :");
        for(j=0;j<3;j++)
        printf(" %d",frame[j]);
        ctn++;
    }
    else
    {
        printf("\tBefore :");
        for(j=0;j<3;j++)
        printf(" %d",frame[j]);
        //selection of Fault
        value1=frame[0];
        flag=0;
        for(j=i;j<number;j++)
        if(refer[j]==value1)
        {
            value1=j;
            flag=1;
            break;
        }
        if(flag==0)
        value1=number;
        value2=frame[1];
        flag=0;
        for(j=i;j<number;j++)
        if(refer[j]==value2)
        {
            value2=j;
            flag=1;
            break;
        }
        if(flag==0)
        value2=number;
        value3=frame[2];
        flag=0;
        for(j=i;j<number;j++)
        if(refer[j]==value3)
        {
            value3=j;
            flag=1;
            break;
        }
        if(flag==0)
            value3=number;
        if(value1<value2)
        if(value3<value2)
            index=1;
        else
            index=2;
        else
        if(value3<value1)
            index=0;
        else
            index=2;

        frame[index]=refer[i];
        printf("\tAfter :");
        for(j=0;j<3;j++)
            printf(" %d",frame[j]);
        }
    }
}
ratio=hitctn/number;
printf("\n\n\tHit ratio = %f ",ratio);
}