#include <iostream.h>

#define Bsize 3
#define Psize 20

struct pageInfor
{
 int content;//頁面號
 int timer;//被訪問標記
};

class PRA
{
public:
    PRA(void);
 int findSpace(void);//查找是否有空閑內(nèi)存
 int findExist(int curpage);//查找內(nèi)存中是否有該頁面
 int findReplace(void);//查找應予置換的頁面
 void display(void);//顯示
 void FIFO(void);//FIFO算法
 void LRU(void);//LRU算法
 void Optimal(void);//OPTIMAL算法
 void BlockClear(void);//BLOCK恢復
 pageInfor * block;//物理塊
 pageInfor * page;//頁面號串

private:

};

PRA::PRA(void)
{

int QString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};

    block = new pageInfor[Bsize];
 for(int i=0; i<Bsize; i++)
 {
  block[i].content = -1;
  block[i].timer = 0;
 }

 page = new pageInfor[Psize];
 for(i=0; i<Psize; i++)
 {
  page[i].content = QString[i];
  page[i].timer = 0;
 }
}


int PRA::findSpace(void)
{
 for(int i=0; i<Bsize; i++)
  if(block[i].content == -1)
   return i;//找到空閑內(nèi)存，返回BLOCK中位置
 return -1;
}

int PRA::findExist(int curpage)
{

 for(int i=0; i<Bsize; i++)
  if(block[i].content == page[curpage].content)
   return i;//找到內(nèi)存中有該頁面，返回BLOCK中位置

 return -1;
}

int PRA::findReplace(void)
{
 int pos = 0;

 for(int i=0; i<Bsize; i++)
  if(block[i].timer >= block[pos].timer)
   pos = i;//找到應予置換頁面，返回BLOCK中位置
 return pos;
}

void PRA::display(void)
{


 for(int i=0; i<Bsize; i++)
  if(block[i].content != -1)
   cout<<block[i].content<<" ";
 cout<<endl;
}


void PRA::Optimal(void)
{
 int exist,space,position ;

for(int i=0; i<Psize; i++)
 {   
  exist = findExist(i);
  if(exist != -1)
  { cout<<"不缺頁"<<endl; }
  else
  {  
   space = findSpace();
   if(space != -1)
   {
    block[space] = page[i]; 
    display();
   }
   else
   {
     for(int k=0; k<Bsize; k++)
    for(int j=i; j<Psize; j++)
    {
     if(block[k].content != page[j].content)
     { block[k].timer = 1000; }//將來不會用，設置TIMER為一個很大數(shù)
     else
     {
      block[k].timer = j;
      break;
     }
    }
 position = findReplace();  
    block[position] = page[i];  
    display();
   }
  }
 }
}


void PRA::LRU(void)
{
 int exist,space,position ;

 for(int i=0; i<Psize; i++)
 {
  exist = findExist(i);
  if(exist != -1)
  {
       cout<<"不缺頁"<<endl;
   block[exist].timer = -1;//恢復存在的并剛訪問過的BLOCK中頁面TIMER為-1
  }
  else
  {
   space = findSpace();
   if(space != -1)
   {
    block[space] = page[i];
    display();
   }

 else
   {
    position = findReplace();
    block[position] = page[i];  
    display();
   }
  }
  for(int j=0; j<Bsize; j++)
   block[j].timer++;
 }
}


void PRA::FIFO(void)
{

 int exist,space,position ;

 for(int i=0; i<Psize; i++)
 {
  exist = findExist(i);
  if(exist != -1)
   {cout<<"不缺頁"<<endl;}

  else
  {  
   space = findSpace();
   if(space != -1)
   {
    block[space] = page[i]; 
    display();

 }
   else
   {
    position = findReplace();
    block[position] = page[i];  
    display();
   }
  }
  for(int j=0; j<Bsize; j++)
   block[j].timer++;//BLOCK中所有頁面TIMER++
 }
}

void PRA::BlockClear(void)
{
 for(int i=0; i<Bsize; i++)
 {
  block[i].content = -1;
  block[i].timer = 0;
 }
}


void main(void)
{
 cout<<"|----------頁 面 置 換算法----------|"<<endl;
 cout<<"|---power by zhanjiantao(028054115)---|"<<endl;
 cout<<"|-------------------------------------|"<<endl;

cout<<"頁面號引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"<<endl;
 cout<<"----------------------------------------------------"<<endl;
 cout<<"選擇<1>應用Optimal算法"<<endl;
 cout<<"選擇<2>應用FIFO算法"<<endl;
 cout<<"選擇<3>應用LRU算法"<<endl;
 cout<<"選擇<0>退出"<<endl;
 int select;
 PRA test;

 
 while(select)
 {
  cin>>select;
  switch(select)
  {
   case 0:
    break;
   case 1:
    cout<<"Optimal算法結(jié)果如下:"<<endl;

test.Optimal();
    test.BlockClear();
    cout<<"----------------------"<<endl;
    break;
   case 2:
    cout<<"FIFO算法結(jié)果如下:"<<endl;
    test.FIFO();
    test.BlockClear();
    cout<<"----------------------"<<endl;
    break;
   case 3:
    cout<<"LRU算法結(jié)果如下:"<<endl;
    test.LRU();
    test.BlockClear();
    cout<<"----------------------"<<endl;
    break;
   default:
    cout<<"請輸入正確功能號"<<endl;
    break;
  }
 
 }

}