#include <stdio.h>
#include <stdlib.h>

int main()
{
    int refstr[50],ch,frame[10],distance[10],present=0,i=0,j=0,k=0,l=0,found=0,flag=0,len=0,val,framesize=0,toberemoved=0,pagefault=0;

    printf("\nenter the referrence string (-1 to terminate):");
//read the referrence string
    while(flag!=1)
    {
        scanf("%d",&refstr[len]);

        if(refstr[len]==-1)
        flag=1;
        len++;

    }//while ends
    len--;
    printf("\nEnter frame size : ");
    scanf("%d",&framesize);

    while(1)
    {
        printf("\n\n\t\tMAIN MENU\n1.OPTIMAL\n2.LRU\n3.FCFS\n4.Exit\n ");
        scanf("%d",&ch);
        switch(ch)
        {

            case 1:

/*optimal starts*/
                pagefault=0;
                for(i=0;i<framesize;i++)
                frame[i]=-1;
//	frame=new int[framesize];
                for(i=0;i<framesize;i++)
                {
                    frame[i]=refstr[i];
                    pagefault++;
                    printf("%d ",frame[i]);
                }
                printf("\n");
                k=0;

//i now starts with framesize,say the frame size is three then now,
//frame already has the first three elements of the referrence string
                while(i<len)
                {
                    found=0;
                    for(j=0;j<framesize;j++)
                    {
                        if(refstr[i]==frame[j])
                        {
                            found=1;
                        }

                    }
                    if(found!=1)
                    {
                        for(j=0;j<framesize;j++)
                        distance[j]=100;
                        int max=0;
                        toberemoved=0;
                        for(j=0;j<framesize;j++)
                        {
                            for(k=i+1;k<len;k++)
                            {
                                if(frame[j]==refstr[k])
                                {
                                    distance[j]=k;
                                    break;
                                }
                            }
                        }
                        for(j=1;j<framesize;j++)
                        {
                            if(distance[j]>distance[max])
                            max=j;
                        }
                        toberemoved=max;
                        frame[toberemoved]=refstr[i];
                        pagefault++;
//	if(k==len)
//	k=0;

                    }

// k++;
                    for(j=0;j<framesize;j++)
                        printf("%d ",frame[j]) ;
                    printf("\n");

                    i++;
                }//while ends
                printf("\npagefaults = %d",pagefault);
/*optimal ends*/


/*lru starts*/
                break;

    case 2:

        for(i=0;i<framesize;i++)
        {
            frame[i]=refstr[i];
            distance[i]=i;
            pagefault++;
            printf("%d ",frame[i]);
        }
        k=0;
        printf("\n");
//i=0;
//i now starts with framesize
        while(i<len)
        {
            found=0;
            for(j=0;j<framesize;j++)
            {
                if(refstr[i]==frame[j])
                {
                    found=1;
                    distance[j]=i;//if the variable is found, then the distance tag should be replaced with the new tag

                }

            }
            if(found!=1)
            {

            int min=0;
            toberemoved=0;
            for(j=1;j<framesize;j++)
            {
                if(distance[j]<distance[min])
                min=j;
            }
            toberemoved=min;
            distance[min]=i;
            frame[toberemoved]=refstr[i];
            pagefault++;
//	if(k==len)
//	k=0;

            }//if ends

// k++;
            for(j=0;j<framesize;j++)
                printf("%d ",frame[j]) ;
            printf("\n");

            i++;
        }
        printf("\npagefaults = %d",pagefault);
/*lru ends*/
        break;
    case 3:

/*fcfs starts*/


// fcfs:

        pagefault=0;
        toberemoved=0;
//	distance=new int[framesize];
        for(i=0;i<framesize;i++)
        {
            frame[i]=refstr[i];
            pagefault++;
            printf("%d ",frame[i]);
        }
        printf("\n");

//	printf("%d %d",i,len);
        while(i<len)
        {
// printf("%d",refstr[i++]);
            found=0;
            for(j=0;j<framesize;j++)
            {
                if(refstr[i]==frame[j])
                found=1;

            }
            if(found!=1)
            {
                frame[toberemoved]=refstr[i];
                toberemoved++;
                if(toberemoved==framesize)
                {
                    toberemoved=0;
                }
                pagefault++;

            }
            for(j=0;j<framesize;j++)
                printf("%d ",frame[j]) ;
            printf("\n");
            i++;
        }//while ends
        printf("\npagefaults = %d",pagefault);
        break;
    case 4:
        exit(0);
    }//switch ends
}
//getch();
return 0;
}//main ends