#include<stdio.h>
//#include<unistd.h>
//#include<sys/types.h>
#include "process.h"
#include "stdlib.h"
#include "iostream.h"
//模擬實現
void randarray(int a[ ],int k)//生成隨機數
{
    int i,s;
    srand(getpid());
    s=int((float)319.0*(rand()%32767)/32767.0+1.0);
    for(i=0;i<k;i+=4)
	{
        a[i]=s+512;
        a[i+1]=a[i]+513;
        a[i+2]=int((float)a[i]*(rand()%32767)/32767.0+512);
        a[i+3]=a[i+2]+1;
        s=int((float)(rand()%32767)*(318.0-a[i+2])/32767.0+a[i+2]+2.0+512);
    }
}

float FIFO(int a[],int n)//先進先出置換算法
{
  int * array=new int [n];
  int time=0;
  int i,j,flag;
  int *p;
    for(i=0;i<n;i++)
	  array[i]=-1;
  p=&array[0];//FIRST IN


  for(i=0;i<320;i++)
  {   
     flag=-1;
     for(j=0;j<n;j++)
     {
	if(array[j]!=a[i])//未匹配
		{
	    if(*p!=array[j])//內存頁數未滿時
		continue;
		else
		flag=j;
		}
	else
		{
	    time++;
	    flag=-1;
	    break;
		}
     }

     if(flag!=-1)//miss
     {
	array[flag]=a[i];
	p=&array[(flag+1)%n];
     }
  }

 return (float)time/320;
}

float BEST(int a[],int n)//最佳置換算法
{
  int *array=new int[n];
  int time=0;
  int i,j,l,m,k;

  for(i=0;i<n;i++)
	  array[i]=-1;

  for(i=0;i<320;i++)  
  {
     m=-1;
     l=0;
     for(j=0;j<n;j++)
     {
	if(array[j]!=a[i])//未匹配
	{
	   for(k=i+1;k<320;k++)
	   {
		if(array[j]==a[k])
		{  
		   if(l<k)
		   {   
			l=k;      //the farest element
			m=j;      //the index in a[n] 
		   }
		   break;
		}
	   }
	   if(k==320)//到達最后一個數
	   {
		l=320;
		m=j;
	   }	
	}
	else//匹配
	{
	   m=-1;
	   time++;
	   break;
        }
     }

    if(m!=-1)
    array[m]=a[i];
  }
     
  return (float)time/320;
}

float LRU(int a[],int n)//最近最久未使用置換算法
{
  int * array=new int[n];
  int * index=new int [n];//設定上次的訪問時間，每次沒訪問到就加1
  int time=0;
  int i,j,k,m,temp=0;

  for(i=0;i<n;i++)
  {
	  index[i]=-1;
      array[i]=-1;
  }
  for(i=0;i<320;i++)  
  {
     m=0;
     for(j=0;j<n;j++)
     {
        if(a[i]!=array[j])
            continue;
        else//匹配
        {
            time++;
            index[j]=0;
            m=1;
            for(k=0;k<n;k++)
                if(k!=j)
                    index[k]++;
        }
        if(m==1)
            break;
     }

     if(m!=1)   //miss
     {
        for(j=0;j<n;j++)
        {
           index[j]++;
           if(temp<index[j])
           {
                temp=index[j];
                m=j;
           }
        }
        array[m]=a[i];
     }
  }
  return  (float)time/320;
}

int main()
{
  int i,pagenum;
  float rate1,rate2,rate3;
  int a[320];
  randarray(a,320);

  for(i=0;i<320;i++)//轉化為頁面
	a[i]=a[i]/512;

  for(pagenum=3;pagenum<=8;pagenum++)
  {
    rate1=FIFO(a,pagenum);
    rate3=LRU(a,pagenum);
    rate2=BEST(a,pagenum);

    cout<<"The page number is :"<<pagenum<<endl;
    cout<<"rate in FIFO is :"<<rate1<<endl;
    cout<<"rate in LRU  is :"<<rate3<<endl;
	cout<<"rate in BEST is :"<<rate2<<endl<<endl;
  }
exit(0);
}