#include "Stdio.h"
#include "Conio.h"

typedef struct battery
{
   char *data;
   int front,rear;
   int size;
}Battery;

void Initqueue(Battery *Q,int size)
{ /*初始化鏈表隊(duì)列*/

   Q->data=(char *)malloc(sizeof(char)*size);
   if (!Q->data)    printf("Application failed!");
   Q->front=Q->rear=0;
   Q->size=size;
}

void Enqueue(Battery *Q,char elem)
{ /*入隊(duì)操作*/
   if ((Q->rear+1)%(Q->size)==Q->front)  return;
   Q->data[Q->rear]=elem;
   Q->rear=(Q->rear+1)%(Q->size);
}

char Dequeue(Battery *Q)
{ /*出隊(duì)操作*/
   char ret;
   if (Q->front==Q->rear)   return;
   ret=Q->data[Q->front];
   Q->front=(Q->front+1)%(Q->size);
   return ret;
}

char Get(Battery *Q)
{ /*得到隊(duì)頭元素*/
    return Q->data[Q->front];
}

char Index(Battery *Q,int i)
{ /*定位第i個(gè)元素*/
    return Q->data[Q->front+i-1];
}

int Isfull(Battery *Q)
{ /*隊(duì)滿返回1*/
    if ((Q->rear+1)%(Q->size)==Q->front)
        return 1;
}

int Length(Battery *Q)
{ /*返回隊(duì)列長(zhǎng)度*/
    return (Q->rear-Q->front+Q->size)%(Q->size);
}

void Cache(int Page_size/*頁(yè)面大小*/,int Mainmen_size/*主存大小*/,char *string/*輸入的數(shù)據(jù)*/,int num/*需輸入的元素個(gè)數(shù)*/)
{
    int size=Mainmen_size/Page_size;  /*segment是需要分的段數(shù)。如Page_size=200，則0、1屬于一段*/
    Battery *p,*q;
    int i=0,j=0,count1=0,count2=0,count3=0,count=0,n;
    Initqueue(p,size+1);

    for (i=0;i<num;i++)    /*簡(jiǎn)化地址流*/
    {
        switch(Page_size)
        {
            case 100:
               /* if ('0'==string[i])
                    string[i]='0';
                if ('1'==string[i])
                    string[i]='1';
                if ('2'==string[i])
                    string[i]='2';
                if ('3'==string[i])
                    string[i]='3';
                if ('4'==string[i])
                    string[i]='4';
                if ('5'==string[i])
                    string[i]='5';
                if ('6'==string[i])
                    string[i]='6';
                if ('7'==string[i])
                    string[i]='7';
                if ('8'==string[i])
                    string[i]='8';
                if ('9'==string[i])
                    string[i]='9';   這段可有可無(wú)*/
                break;
            case 200:
                if ('0'==string[i] || '1'==string[i])
                    string[i]='0';
                if ('2'==string[i] || '3'==string[i])
                    string[i]='2';
                if ('4'==string[i] || '5'==string[i])
                    string[i]='4';
                if ('6'==string[i] || '7'==string[i])
                    string[i]='6';
                if ('8'==string[i] || '9'==string[i])
                    string[i]='8';
                break;
            case 300:
                if ('0'==string[i] || '1'==string[i] || '2'==string[i])
                    string[i]='0';
                if ('3'==string[i] || '4'==string[i] || '5'==string[i])
                    string[i]='3';
                if ('6'==string[i] || '7'==string[i] || '8'==string[i])
                    string[i]='6';
                if ('9'==string[i])
                    string[i]='9';
                break;
            case 400:
                if ('0'==string[i] || '1'==string[i] || '2'==string[i] || '3'==string[i])
                    string[i]='0';
                if ('4'==string[i] || '5'==string[i] || '6'==string[i] || '7'==string[i])
                    string[i]='4';
                if ('8'==string[i] || '9'==string[i])
                    string[i]='8';
                break;
        }
    }
    if (num<=size)   /*地址流數(shù)小于頁(yè)數(shù)*/
    {
        Enqueue(p,string[0]);
        for (i=1;i<num;i++)   /*邊入隊(duì)邊與隊(duì)列中所有數(shù)比較*/
        {
            for (j=1;j<=i;j++)
                if (string[i]==Index(p,j))
                {
                    count1++;
                    break;
                }
                Enqueue(p,string[i]);
        }
        printf("Target:%d       ",count1);
        printf("Rate:%d%%\n",100*count1/num);
        return;
    }
    else
    {
        Enqueue(p,string[0]);
        for (i=1;i<num;i++)
        {
            if (Isfull(p))   /*隊(duì)列已滿*/
            {
                for (j=1;j<=size;j++)   /*與隊(duì)列中數(shù)比較*/
                {
                    if (Index(p,j)==string[i])  /*命中，但不入隊(duì)*/
                    {
                        count2++;
                        break;
                    }
                    else if (j==size && string[i]!=Index(p,j))  /*最后一個(gè)數(shù)不命中，則出隊(duì)，并把新數(shù)入隊(duì)*/
                    {
                        Dequeue(p);
                        Enqueue(p,string[i]);
                    }
                }

            }
            else       /*隊(duì)列不滿*/
            {
                for (n=1;n<=Length(p);n++)   /*與隊(duì)列所有數(shù)比較*/
                {
                    if (string[i]==Index(p,n))  /*命中，但不入隊(duì)*/
                    {
                        count3++;
                        break;
                    }
                }
                if (string[i]==Index(p,n))    /*確定無(wú)重復(fù)數(shù)入隊(duì)*/
                    continue;
                Enqueue(p,string[i]);
            }
        }
        count=count2+count3;
        printf("Target:%d       ",count);
        printf("Rate:%f%%\n",(float)100*count/num);
    }
}

int main(void)
{
  int pagesize,mainmensize,num=0,i=0;
  char s[50];
  while (getch!='*')
  {
    num=0;i=0;pagesize=0;mainmensize=0;
    gotoxy(5,3);
    printf("Welcome to cache test! Now you can input the Address flow(End with ' '):\n");
    gotoxy(5,5);
    for (i=0;i<50;i++)
    {
        scanf("%c",&s[i]);
        if (s[i]!=' ')
            num++;
        else
            break;
    }
    gotoxy(5,8);
    printf("OK! You can input Pagesize:");
    scanf("%d",&pagesize);
    printf("\n");
    gotoxy(5,10);
    printf("Good! You can input Mainmensize:");
    scanf("%d",&mainmensize);
    printf("\n");
    gotoxy(5,12);
    printf("The result is:\n");
    gotoxy(5,14);
    Cache(pagesize,mainmensize,s,num);
    gotoxy(5,16);
    getch();
    clrscr();
  }
  return 0;
}