#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define random(x) (rand()%x)

#define LOG     1        //1-show log    2-no show
#define TYPE 10     //page types
#define NUM 20         //page nums
#define SIZE 5        //cache size

struct page{
    int id;//page id
    int time=0;//different meaning in different algorithm
};
struct page pageList[NUM],cache[SIZE];//page needs,page cache

void init(){//random data init
    printf("PageList:\n");
    srand((unsigned)time(NULL));
    for(int i=0;i<NUM;i++)
        printf("%d ",pageList[i].id=random(TYPE));
    printf("\n");
}

void cacheClear(){//clear the cache
    for(int i=0;i<SIZE;i++){
        cache[i].id=-1;
        cache[i].time=0;    
    }
}

int cacheHit(int i){//find cache hit or not
    for(int j=0;j<SIZE;j++)
        if(cache[j].id==pageList[i].id){
            if(LOG) 
                printf(" hit ");
            return j;
        }
    if(LOG) 
        printf("     ");
    return -1;
}

int cacheRoom(){//find cache have free room or not
    for(int i=0;i<SIZE;i++)
        if(cache[i].id==-1)
            return i;
    return -1;
}

void cacheShow(){//show the cache pages
    if(LOG) {
        printf("cache: ");
        for(int i=0;i<SIZE;i++)
            if(cache[i].id==-1){
                printf("N\t");                
            }else
                printf("%d\t",cache[i].id);
        printf("\n");
    } 
}

void cacheTimeAdd(){//add the pages time in cache
    for(int i=0;i<SIZE;i++)
        cache[i].time++;
}

int FIFOfun(){//FIFO replace
    int maxtime=cache[0].time,t=0;
    for(int i=1;i<SIZE;i++)
        if(maxtime<cache[i].time){
            maxtime=cache[i].time;
            t=i;
        }
    return t;
}

double FIFO(){//time in FIFO:live time
    double ret;
    if(LOG) 
        printf("\nFIFO:\n");
    cacheClear();
    int hitsum=0;
    for(int i=0;i<NUM;i++){
        if(LOG) 
            printf("input:%d\t",pageList[i].id);
        int hit=cacheHit(i);
        if(hit==-1){//if not hit
            int room=cacheRoom();
            if(room!=-1)// if have free room
                cache[room]=pageList[i];//use room save page
            else//if have not free room 
                cache[FIFOfun()]=pageList[i];//use FIFO to replace
        }else{//if hit
            hitsum++;    
        }
        cacheShow();
        cacheTimeAdd();
    }
    if(LOG) {
        printf("PageReplacement:%d\n",hitsum);
        printf("PageFault:%d\n",NUM-hitsum);    
    }
    printf("HitRate:%lf\n",ret=(double)hitsum/NUM);
    return ret;
}

double LRU(){//time:from last use to now
    double ret;
    if(LOG)
        printf("\nLRU:\n");
    cacheClear();
    int hitsum=0;
    for(int i=0;i<NUM;i++){
        if(LOG)
            printf("input:%d\t",pageList[i].id);
        int hit=cacheHit(i);
        if(hit==-1){//if not hit
            int room=cacheRoom();
            if(room!=-1)//if have free room
                cache[room]=pageList[i];//use free room to save page
            else//if have not free room
                cache[FIFOfun()]=pageList[i];//use LRU ,because time have different meaning ,function is same as FIFO 
        }else{//if hit 
            hitsum++;
            cache[hit].time=0;//LRU：every hit reflash time 
        }
        cacheShow();
        cacheTimeAdd();
    }
    if(LOG){
        printf("PageReplacement:%d\n",hitsum);
        printf("PageFault:%d\n",NUM-hitsum);    
    }
    printf("HitRate:%lf\n",ret=(double)hitsum/NUM);
    return ret;
}

double NUR(){//time:notuse-0 use-1
    double ret;
    if(LOG)
        printf("\nNUR:\n");
    cacheClear();
    int hitsum=0,clockcur=0;//cur of the cache 
    for(int i=0;i<NUM;i++){
        if(LOG)
            printf("input:%d\t",pageList[i].id);
        int loop=1,ishit=0;
        for(int j=0;j<SIZE;j++){  //first loop to find hit or not
            if(cache[j].id==pageList[i].id){
                clockcur=j;
                cache[clockcur].time=1;
                clockcur=(clockcur+1)%SIZE;
                ishit=1;
                loop=0;// if hit ，there not next loop 
                break;
            }
        }
        while(loop){//next loop to find one to replace
            loop=0;
            if(cache[clockcur].id==-1){ //id==-1,free room,loop end
                cache[clockcur]=pageList[i];
                cache[clockcur].time=1;
            }else if(cache[clockcur].time==0){//time==0,replace,loop end
                cache[clockcur]=pageList[i];
                cache[clockcur].time=1;
            }else{ //time==1,change time to 0,loop continue
                cache[clockcur].time=0;
                loop=1; 
            }
            clockcur=(clockcur+1)%SIZE;
        }
        if(ishit){//show hit
            hitsum++;
            if(LOG)
                printf(" hit ");
        }else{
            if(LOG)
                printf("     ");    
        }
        cacheShow();
    }
    if(LOG){
        printf("PageReplacement:%d\n",hitsum);
        printf("PageFault:%d\n",NUM-hitsum);
    }    
    printf("HitRate:%lf\n",ret=(double)hitsum/NUM);
    return ret;
}

int OPTfun(int i){//OPT replace
    int arr[SIZE];//save cache page next use
    for(int j=0;j<SIZE;j++){
        arr[j]=INT_MAX;
        for(int k=i+1;k<NUM;k++){
            if(cache[j].id==pageList[k].id){
                arr[j]=k;
                break;
            }
        }
    }
    int arrmax=arr[0],t=0;//find the longest next use 
    for(int j=1;j<SIZE;j++){
        if(arr[j]>arrmax){
            arrmax=arr[j];
            t=j;
        }
    }
    return t;
} 

double OPT(){
    double ret;
    if(LOG)
        printf("\nOPT:\n");
    cacheClear();
    int hitsum=0;
    for(int i=0;i<NUM;i++){
        if(LOG)
            printf("input:%d\t",pageList[i].id);
        int hit=cacheHit(i);
        if(hit==-1){//if not hit
            int room=cacheRoom();
            if(room!=-1)//if have free room 
                cache[room]=pageList[i];//use free room to save
            else// not free room 
                cache[OPTfun(i)]=pageList[i];//use OPT replace
        }else{//if hit 
            hitsum++;
        }
        cacheShow();
        cacheTimeAdd();
    }
    if(LOG){
        printf("PageReplacement:%d\n",hitsum);
        printf("PageFault:%d\n",NUM-hitsum);    
    }    
    printf("HitRate:%lf\n",ret=(double)hitsum/NUM);
    return ret;
}

int main(){
    int    alltime=LOG?1:100;
    double arr[4]={0,0,0,0};
    for(int i=0;i<alltime;i++){
        init();
        arr[0]+=FIFO();
        arr[1]+=LRU();
        arr[2]+=NUR();
        arr[3]+=OPT();
    }
    printf("\n");
    printf("FIFO:%lf\n",arr[0]/alltime);
    printf("LRU:%lf\n",arr[1]/alltime);
    printf("NUR:%lf\n",arr[2]/alltime);
    printf("OPT:%lf\n",arr[3]/alltime); 
    return 0;
}