/* algo11-2.c 通過置換－選擇排序產生不等長的初始歸并段文件 */
 #include"c1.h"
 typedef int InfoType; /* 定義其它數據項的類型 */
 #include"c10-1.h" /* 定義KeyType、RedType及SqList */
 #define MAXKEY INT_MAX
 #define RUNEND_SYMBOL INT_MAX
 #define w 6 /* 內存工作區可容納的記錄個數 */
 #define M 10 /* 設輸出M個數據換行 */
 #define N 24 /* 設大文件有N個數據 */

 typedef int LoserTree[w]; /* 敗者樹是完全二叉樹且不含葉子，可采用順序存儲結構 */
 typedef struct
 {
   RedType rec; /* 記錄 */
   KeyType key; /* 從記錄中抽取的關鍵字 */
   int rnum; /* 所屬歸并段的段號 */
 }RedNode,WorkArea[w]; /* 內存工作區，容量為w */

 void Select_MiniMax(LoserTree ls,WorkArea wa,int q) /* 算法11.6 */
 { /* 從wa[q]起到敗者樹的根比較選擇MINIMAX記錄，并由q指示它所在的歸并段 */
   int p,s,t;
   for(t=(w+q)/2,p=ls[t];t>0;t=t/2,p=ls[t])
     if(wa[p].rnum<wa[q].rnum||wa[p].rnum==wa[q].rnum&&wa[p].key<wa[q].key)
     {
       s=q;
       q=ls[t]; /* q指示新的勝利者 */
       ls[t]=s;
     }
   ls[0]=q;
 }

 void Construct_Loser(LoserTree ls,WorkArea wa,FILE *fi)
 { /* 輸入w個記錄到內存工作區wa,建得敗者樹ls,選出關鍵字最小的記錄并由s指示 */
   /* 其在wa中的位置。算法11.7 */
   int i;
   for(i=0;i<w;++i)
     wa[i].rnum=wa[i].key=ls[i]=0; /* 工作區初始化 */
   for(i=w-1;i>=0;--i)
   {
     fread(&wa[i].rec,sizeof(RedType),1,fi); /* 輸入一個記錄 */
     wa[i].key=wa[i].rec.key; /* 提取關鍵字 */
     wa[i].rnum=1; /* 其段號為＂1＂ */
     Select_MiniMax(ls,wa,i); /* 調整敗者 */
   }
 }

 void get_run(LoserTree ls,WorkArea wa,int rc,int *rmax,FILE *fi,FILE *fo)
 { /* 求得一個初始歸并段，fi為輸入文件指針，fo為輸出文件指針。算法11.5 */
   int q;
   KeyType minimax;
   while(wa[ls[0]].rnum==rc) /* 選得的MINIMAX記錄屬當前段時 */
   {
     q=ls[0]; /* q指示MINIMAX記錄在wa中的位置 */
     minimax=wa[q].key;
     fwrite(&wa[q].rec,sizeof(RedType),1,fo); /* 將剛選得的MINIMAX記錄寫入輸出文件 */
     fread(&wa[q].rec,sizeof(RedType),1,fi); /* 從輸入文件讀入下一記錄(改) */
     if(feof(fi))
     { /* 輸入文件結束，虛設記錄（屬＂rmax+1＂段） */
       wa[q].rnum=*rmax+1;
       wa[q].key=MAXKEY;
     }
     else
     { /* 輸入文件非空時 */
       wa[q].key=wa[q].rec.key; /* 提取關鍵字 */
       if(wa[q].key<minimax)
       { /* 新讀入的記錄屬下一段 */
         *rmax=rc+1;
	 wa[q].rnum=*rmax;
       }
       else /* 新讀入的記錄屬當前段 */
	 wa[q].rnum=rc;
     }
     Select_MiniMax(ls,wa,q); /* 選擇新的MINIMAX記錄 */
   }
 }

 void Replace_Selection(LoserTree ls,WorkArea wa,FILE *fi,FILE *fo)
 { /* 在敗者樹ls和內存工作區wa上用置換－選擇排序求初始歸并段，fi為輸入文件 */
   /* (只讀文件)指針,fo為輸出文件(只寫文件)指針,兩個文件均已打開。算法11.4 */
   int rc,rmax;
   RedType j;
   j.key=RUNEND_SYMBOL;
   Construct_Loser(ls,wa,fi); /* 初建敗者樹 */
   rc=rmax=1; /* rc指示當前生成的初始歸并段的段號，rmax指示wa中關鍵字所屬初始歸并段的最大段號 */
   while(rc<=rmax) /* ＂rc=rmax+1＂標志輸入文件的置換－選擇排序已完成 */
   {
     get_run(ls,wa,rc,&rmax,fi,fo); /* 求得一個初始歸并段 */
     j.otherinfo=rc;
     fwrite(&j,sizeof(RedType),1,fo); /* 將段結束標志寫入輸出文件 */
     rc=wa[ls[0]].rnum; /* 設置下一段的段號 */
   }
 }

 void print(RedType t)
 {
   printf("(%d,%d)",t.key,t.otherinfo);
 }

 void main()
 {
   RedType b,a[N]={{51,1},{49,2},{39,3},{46,4},{38,5},{29,6},{14,7},{61,8},{15,9},{30,10},{1,11},{48,12},{52,13},{3,14},{63,15},{27,16},{4,17},{13,18},{89,19},{24,20},{46,21},{58,22},{33,23},{76,24}};
   FILE *fi,*fo;
   LoserTree ls;
   WorkArea wa;
   int i,k,j=RUNEND_SYMBOL;
   char s[3],fname[4];
   fo=fopen("ori","wb"); /* 以寫的方式打開大文件ori */
   fwrite(a,sizeof(RedType),N,fo); /* 將數組a寫入大文件ori */
   fclose(fo);
   fi=fopen("ori","rb"); /* 以讀的方式重新打開大文件ori */
   printf("大文件的記錄為:\n");
   for(i=1;i<=N;i++)
   {
     fread(&b,sizeof(RedType),1,fi); /* 依次將大文件ori的數據讀入b */
     print(b); /* 輸出b的內容 */
     if(i%M==0)
       printf("\n");
   }
   printf("\n");
   rewind(fi); /* 使fi的指針重新返回大文件ori的起始位置，以便重新讀入內存，產生有序的子文件 */
   fo=fopen("out","wb"); /* 以寫的方式打開初始歸并段文件out */
   Replace_Selection(ls,wa,fi,fo); /* 用置換－選擇排序求初始歸并段 */
   fclose(fo);
   fclose(fi);
   fi=fopen("out","rb"); /* 以讀的方式重新打開初始歸并段文件out */
   printf("初始歸并段文件的記錄為:\n");
   i=1;
   do
   {
     k=fread(&b,sizeof(RedType),1,fi); /* 依次將大文件out的數據讀入b */
     if(k==1)
     {
       print(b); /* 輸出b的內容 */
       if(i++%M==0)
         printf("\n");
     }
   }while(k==1);
   printf("\n");
   rewind(fi); /* 使fi的指針重新返回大文件ori的起始位置，以便重新讀入內存，產生有序的子文件 */
   k=0;
   while(!feof(fi)) /* 按段輸出初始歸并段文件out */
   {
     itoa(k,s,10); /* 依次生成文件名f0,f1,… */
     strcpy(fname,"f");
     strcat(fname,s);
     fo=fopen(fname,"wb"); /* 依次以寫的方式打開文件f0,f1,… */
     do
     {
       i=fread(&b,sizeof(RedType),1,fi);
       if(i==1) /* fread()調用成功 */
       {
	 fwrite(&b,sizeof(RedType),1,fo); /* 將b寫入文件f0,f1,… */
         if(b.key==j) /* 1個歸并段結束 */
         {
           k++;
           fclose(fo);
           break;
         }
       }
     }while(i==1);
   };
   fclose(fi);
   printf("共產生%d個初始歸并段文件\n",k);
 }