// cipan.cpp : Defines the entry point for the console application.
//

#include <iostream.h>
#define MAX 100
//----------------------------------------------------------------------
void getnext(int F[MAX],int n,int k,int neicun[],int numkuai,int next[])
{                                   //获得下次出现位置距离现在的时间
   int i,j,nostop;
   for(i=0;i<5;i++)
       next[i]=n-k;
   for(i=0;i<numkuai;i++)
    {if(neicun[i]==-1)
     next[i]=n+1;
     else{for(nostop=1,j=k+1;j<n&&nostop;j++)
               if(neicun[i]==F[j])
                  {next[i]=j-k;
                   nostop=0;
                  }
          }
     }
}
//--------------------------------------------------------------------
void best_fun(int F[],int n,int numkuai)
{                                    //最佳置换算法
int i,k,countqueye=0,longmax,insign;
int neicun[5],next[5],nextsign=0;
  for(i=0;i<5;i++)
     {
        neicun[i]=-1;next[i]=n;
     }
for(k=0;k<n;k++)
   {insign=0;
    for(i=0;i<numkuai;i++)
     if(neicun[i]==F[k])
        insign=1;
    if(insign==0)
       {neicun[nextsign]=F[k];countqueye++;}
    getnext(F,n,k,neicun,numkuai,next);
    for(longmax=0,i=1;i<numkuai;i++)
        if(next[longmax]<next[i])
       longmax=i;
    nextsign=longmax;
   }
cout<<"BEST:"<<endl;
cout<<"Zongcishu:"<<n<<" queyecishu:"<<countqueye<<" queyelu:"<<100*(float)countqueye/(float)n<<endl;
}
//--------------------------------------------------------------------------------------------------
void fifo_fun(int F[],int n,int numkuai)
{                                      //先来先服务算法
int i,k,countqueye=0,insign;
int neicun[5]={-1,-1,-1,-1,-1},nextsign=0;
for(k=0;k<n;k++)
   {insign=0;
    for(i=0;i<numkuai;i++)
     if(neicun[i]==F[k])
             insign=1;
    if(insign==0)
      {neicun[nextsign]=F[k];
       countqueye++;
       nextsign=(nextsign+1)%numkuai;
      }
    }
cout<<"FIFO:"<<endl;
cout<<"Zongcishu:"<<n<<" queyecishu:"<<countqueye<<" queyelu:"<<100*(float)countqueye/(float)n<<endl;
}
//--------------------------------------------------------------------------------------------------
void getfront(int F[MAX],int n,int k,int neicun[],int numkuai,int front[],int nextsign)
{                                        //获得上次出现位置距离现在的时间
   int i,j,nostop;
   for(i=0;i<5;i++)
       front[i]=k;
   for(i=0;i<numkuai;i++)
    {if(neicun[i]==-1)
       front[i]=k+1;
     else if(i==nextsign)
            front[i]=0;
         else
         { for(nostop=1,j=k-1;j>-1&&nostop;j--)
               if(neicun[i]==F[j])
               {front[i]=k-j;
                nostop=0;
               }
         }
    }
}
//------------------------------------------------------------------------------------------------
void lru_fun(int F[],int n,int numkuai)
{                                                            //电梯调度算法
int i,k,countqueye=0,longmax,insign;
int neicun[5]={-1,-1,-1,-1,-1},front[5],nextsign=0;
for(i=0;i<5;i++) front[i]=n;
for(k=0;k<n;k++)
   {insign=0;
    for(i=0;i<numkuai;i++)
     if(neicun[i]==F[k])
        insign=1;
    if(insign==0)
       {neicun[nextsign]=F[k];countqueye++;}
    getfront(F,n,k,neicun,numkuai,front,nextsign);
    for(longmax=0,i=1;i<numkuai;i++)
     if(front[longmax]<front[i])
       longmax=i;
    nextsign=longmax;
   }
cout<<"LRU:"<<endl;
cout<<"Zongcishu:"<<n<<" queyecishu:"<<countqueye<<" queyelu:"<<100*(float)countqueye/(float)n<<endl;
}
//----------------------------------------------------------------------------------------------------
int main(int argc, char* argv[])           //主函数 模拟页面置换
{
   int i,n=0,nostop=1,F[MAX];
   cout<<"please inrut xulei(input<0 to end):"<<endl;
   for(i=0;i<MAX&&nostop;i++)
   {
       cin>>F[i];
       if(F[i]<0)
       {
           nostop=0;
           n=i;
       }
   }
   for(i=3;i<=5;i++)
   {
       cout<<"now neicun is:"<<i<<endl;
       best_fun(F,n,i);
       fifo_fun(F,n,i);
       lru_fun(F,n,i);
       cout<<endl;
   }
   return 0;
}