//paging simulation

#include<stdio.h>
#include<conio.h>
#include<process.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++;

    }
    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:

      //    goto lru;
       //goto fcfs  ;


       /*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++;
    }
    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;

           }

    //  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++;
    }
    printf("\npagefaults = %d",pagefault);
       break;
       case 4:
    exit(0);
       }
 }
    getch();
    return 0;
}