/// hwk13m22.c --- use Merge Sort (合併排序法) to SORT studat.txt
////// merge sort application  2010/12/03 Friday
///   msort( )    @CopyLeft by tsaiwn@csie.nctu.edu.tw
#include "mystu.h"
/// gcc hwk13m22.c msort.c
//////
// 這版本其實跟 hwk12qsort.c 幾乎完全依樣,
/// 唯一差別就是改叫用 msort( ), 就是把叫用 qsort( ) 換成叫用 msort( )
///  叫用 msort( ) 時用法則跟 qsort( ) 完全相同 ! ! !
///  注意:
//////   msort( ) 在另一個檔案 msort.c 內
///  再注意 msort.c 內還有另一個類似但要用到 Student 的 useMgSort( )
/////  請參看宣告檔案 mystu.h
// @CopyLeft by tsaiwn@csie.nctu.edu.tw
const char *hahaha = " \n"
  " 遊戲放兩邊, 功\課擺\中間; \n"
  " 注意我有講, 醜話說在先。 \n"
  " 別心存僥倖, 更不該偷懶;  \n"  
  " 要想不被當, 習題多多練。 \n"  
  " .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?!\n";
///   上面的"功\" 和 "擺\" 反斜線不可以去掉, 不然翻譯有錯!! 
/// /// 因為 擺\中間 的 "擺\" 之內碼是0xc2 0x5c; 0x5c 是反斜線 !!
//////   阿字串中的 \ 是逃脫字符! 例如 \n 是 NewLine, \t 是跳格
////// 所以 "\\" 就變成一個反斜線!  What if 內碼第一Byte是 \ ?
//////  如果註解 // 後面該列的最後一個字是 擺 阿那會怎樣呢???
///      自己是看看就知道了 :-)
///
/// 注意, 這範例已經照規定完成工作, 使用的是  msort( )
////  msort( ) 用法跟 Library function qsort( ) 完全依樣!
///  請看習題說明, 關於 全部同學的平均 和 標準差.. 
///   在資料看完一遍後就可算出來! 不必先算平均喔!
/// .. 算這些統計資料的做法以前範例已經給過, 再不懂舉手問 :-)
// 站在巨人的肩膀上:
//   這版是用自己寫的msort( ), 類似 C 程式庫中的 qsort( ) 做排序
//    注意使用 msort( ) 須先照規定寫好 call back function
// ..  阿就是compare function 參數要照規定接受兩個 const void*
// *** 想要不同順序, 只要寫不同的 compare function 傳給msort
// *** 注意， msort 只知道資料是連續一堆 bytes,
// *** 每當它想比較, 就會把兩項資料在記憶體的起點傳給比較函數
// *** 所以比較函數的參數是  (const void*, const void*)
///*** 你的比較函數必須自己轉換成你知道的型別(type)
///*** 因為你 call msort( ), 然後 msort( ) 回頭 call 你寫的
///*** .. call 你寫的 比較函數, 所以稱為 call back function!
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "mystu.h"
char* fileName = "studat.txt";  // Data File
long test( );  // 會傳回有幾個 records, 該叫 count( )
/// /// 雖然定義 struct 有很多寫法, 建議用以下這種寫法:
/******     // 注意, 已經搬到 mystu.h 內
typedef struct {
   long sid;  int s1, s2, s3, s4; // struct 內各項目順序不重要
   double total;  // 學期總成績= (h*0.2 + m*0.3 + q*0.1+f*0.4); 
              /// 這裡的 s1, s2, s3, s4 就是 h, m, q, f
   long rank, recno;  // rank, original record number
   char name[9];  // student's name
} Student_t;   // 這種命名方式是不錯的習慣 ( _t)
******/
/// 注意我把上面去掉, 因為 "mystu.h" 內已經有定義 Student_t
///
void sort(Student_t*, long left, long right);
     // sort( ) is your sorting program according to the score
     // left 是開始那項的 index, 最後一筆是 right
void sort2Print(Student_t*, long n); // n records
      // sort2Print() is your another sorting program (照學號)
      // 注意我故意把參數用不同的寫法 ! 不是第幾個到第幾個
void print(Student_t*, long,int); // 用來印出資料, 但只印出一部份!
//////  第三個參數是個 FLAG, 表示要不要印名次 ?
void readALL(Student_t *y, long, char*file,double*s,double*ss); 
  //  read ALL data from file into y[ ]; s=sum, ss=sum of square
/// 
int main( ) {
   Student_t * stus;   // 等一下用 malloc 要記憶體, 當作 stus[ ]
   long long tStart, tStop;  long i, k, n;
   double tRun;
   double sum, sumSquare, average, variance, std;
   n = test( );  // 這列以上不准改! test( )會傳回 record 數目
   // 打開檔案讀資料到記憶體, 也可寫成 function 在此 call 它 !
   // 一邊讀, 一邊算出每個人的學期總成績; 或讀完再算也可以!
   // ..注意, 還要算出全部同學的平均 和 標準差
   stus = (Student_t*) malloc(sizeof(Student_t)*n); // n 筆
           // Note that malloc( )的單位是 Bytes
           // in C++:  stus = new Student_t[n]; 
   readALL( stus, n, fileName,&sum, &sumSquare);  //into stus[ ] 
          // 記得要用 "&" 把 sum 和 sumSquare 的address傳過去
   average = sum / n;   // 以下變異數公式以前給過, 忘了就上網查
   variance = (sumSquare - sum*sum/n) / n;  // sumSquare是平方和
   std = sqrt(variance);    // 高中就學過"變異數開根號就是標準差"
   printf(" N= %ld, Average= %.2f, STD標準差= %.3f\n",
        n, average, std);
   printf("Before sort...\n");
   print(stus, n, 0); // 叫用 print( ) 印出部份資料, 不印名次
   // todo..  print average, standard deviation
   tStart = clock( );
   sort(stus, 0, n-1); // call your sort 程式, 照總成績由高到低
      // this means to sort stus[0..n-1]; 從 stus[0]..stus[n-1]
   tStop = clock( );
   tRun = 1.0*(tStop - tStart)/CLOCKS_PER_SEC;  // in <stdlib.h>
   printf("...Sorting done in %.5f seconds.\n", tRun);
/// fill in the rank (填入名次)
   for(i=0; i< n; i++) stus[i].rank = i+1;   // 第 0 個是第一名
   printf("After sort...\n");
   print(stus, n, 1); // 叫用 print( ) to print partial data+名次
   // Extra credit: 要有名次, 同分者比期末考, 再同比期中考, ..
 ///
   /// part 2
   sort2Print(stus, n); // 在裡面做照學號由小到大sort, 要測時間

   printf("=== 改用gen333.c生的data是常態分佈, 原先是 Uniform 分布!\n");
   printf(" N= %ld, Average= %.2f, STD 標準差= %.3f\n",
        n, average, std);
   printf("==> 站在巨人肩膀上: 你也可以叫用 C 程式庫的 qsort,\n\t"
     "Sort %ld 筆資料依成績遞減Descending in %.3f 秒.\n",n, tRun);
   printf("Hint: 用 rand( )%%32767/32767.0 生出 12 個數加總, "
      "然後減去6.0;\n\t這樣就是 N(0, 1)的常態分配亂數;\n"
      "\t把這亂數乘以你要的標準差, 再加上你希望的平均數;\n"
      "\t.. 這樣, 就會是你希望的常態分佈成績!\n");
   fprintf(stderr, "%s Hit ENTER key...", hahaha);
   getchar( );
   return 0;
} // main(
/// /// /// ================ ============== ==============
/// print one student, with Final grade? with Rank?
void printStudent(Student_t yy, int prtFinal, int prtRank);
///
void print(Student_t *x, long nStu, int rankFLAG) {  // 我用傳參數
          // 當程式是由多人合作時, 最好儘量少用  Global 變數 !
   int i;
   for(i=0; i < 6; ++i)
      printStudent(x[i], 1, rankFLAG);  // with total score
   printf("...\n");
   printf("Stu ID     name      hwk  mid  quiz fin"
                                 "  學期成績   名次\n");
   for(i=nStu-5; i< nStu; ++i)
      printStudent(x[i], 1, rankFLAG);
}
/// do NOT modify the following code
long test( ) {     // 這函數不准改 !
    long id; char name[9]; int s1, s2, s3, s4, kk;
    static char buf[99];
    FILE* fp;
    fp = fopen(fileName, "rt");   // read, text
    if(fp==0) {  // Fail to open it
       fprintf(stderr, "File %s NOT found!\n", fileName);
       getchar( ); exit(38);  // force to exit with an error
    }
    fgets(buf, sizeof(buf), fp);  // stdin
    if(feof(fp) ) {
        fprintf(stderr, "EOF encounted.\n");
        return;
    }
    //fprintf(stderr, "Line-1: %s\n", buf);
    fgets(buf, sizeof(buf), fp);  // stdin
    //fprintf(stderr, "Line-2: %s\n", buf);
    s1=s2=s3=s4=0;
    kk = sscanf(buf,"%ld %s %d %d %d %d", 
       &id, name, &s1, &s2, &s3,&s4);
   // printf("kk=%d\n", kk);
    //if( kk != 4) printf(" something Wrong with data!\n");
   // printf("id=%ld  name = %s\n", id, name);
   // printf("score= %d %d %d %d\n", s1, s2, s3, s4);
    fprintf(stderr, " counting..."); fflush(stderr);
    kk = 2;  // already read 2 records
    while(! feof(fp) ) {   // 只要檔案還沒結束
       buf[0] = 0;
       fgets(buf, sizeof(buf), fp);
       if( feof(fp) ) {  // EOF 也可能有讀到不完整的 Line
          if(buf[0] == 0) break;  // 沒有讀到啦
       }
       ++kk;  // got one record
    }
    fprintf(stderr, " .. done.\nTotal %d records in file %s\n",
       kk, fileName);   // 印到 stderr (螢幕)
    fflush(stderr);
    fclose(fp); // close the file
    return kk;   // total  kk records in the file
} // test(
///////////////////

/// 以下myComp is a 比較函數 that will compare 總成績 total, 
/// 要讓 msort 做 Descending 排序, 若同分, 則照原 record no遞增
/// ..這樣就等同於 stable(穩定)的 sort; (注意msort不是 stable !)
int myComp(const void*pa, const void*pb) { // for sort( ) 總成績 
   Student_t * sa = (Student_t*) pa;  // cast (轉型)
   Student_t * sb = (Student_t*) pb;  // 其實 cast 電腦沒做任何事
   if(sa->total < sb->total) return 1;
   if(sa->total > sb->total) return -1;
  /// toal 總成績相同, 比期末考 s4, 仍是遞減序 Descending order
   if(sa->s4 < sb->s4) return 1;
   if(sa->s4 > sb->s4) return -1;  
   // 又同分ㄟ, 若要繼續比期中考是在 s2 , 請自己練習 (太簡單 :-)
  /// 成績同, 以下是比原來讀入的序號, 但用遞增序!
   if(sa->recno < sb->recno) return -1; // 這樣是遞增
   if(sa->recno > sb->recno) return 1;  // return sa-sb;
   return 0;
} //myComp(


void sort(Student_t x[ ], long left, long right) { // 我用傳參數!
   // call Library msort( )
   msort((void*)x,
           right-left + 1, sizeof(Student_t), myComp);

   // 注意程式庫 msort( ) 要這 4 項資料作參數:
    // 1.資料起點(address), 2.有幾項, 3.每項多少Bytes, 4.比較函數
     //  再注意: "比較函數" 必須接受 兩個指標 (const void*)

} // sort(

///
/// 再來是 a 比較函數that compares ID, 要讓 msort 做 Ascending 排 
int compID(const void*pa, const void*pb) { // for sort2Print(
   Student_t * a = (Student_t*) pa; // cast 轉型
   Student_t * b = (Student_t*) pb;
   if(a->sid < b->sid) return -1;  //左小右大回傳 -1 : Ascending
   if(a->sid > b->sid) return 1;
   return 0;   // ID 相同 ? 不管它 !
} //compID(

void sort2Print(Student_t *x, long n) { // 要照學號由小到大 !
   /// 參數..
   // 注意我故意用不同於前面 sort( ) 的寫法喔 ! 此處 n是說有 n 筆
   // Ascending order, 記得要量時間, 除了clock( )還有更準的自己查 
   long long tStart, tStop;  // long long 是 64 bits
   double tRun;
   printf("...Now Sorting according to student ID...");
   tStart = clock( );

   msort((void*)x,
           n, sizeof(Student_t), compID);  // 注意寫法 !

   tStop = clock( );
   tRun = 1.0*(tStop - tStart)/CLOCKS_PER_SEC;
          // 注意上面的 1.0*  不可拿掉! Why?
   printf("\n...Sorting done in %.5f seconds.\n", tRun);
   ///
   printf("\n === Now already sorted in Student_ID"
         " at ascending order.\n");
   print(x, n, 1);  // call print( ) to print some data+rank
} //sort2Print(
///
/// 以下的宣告其實是多餘的 ! 因為馬上就要寫了 :-)
int readStudent(Student_t * gg, FILE* fp); // read One學生資料
// /// /// read One student data
int readStudent(Student_t * stu, FILE* fp) {  // default stdin
   // 這裡的 stu 是一個指標, 指向一個學生
   // 注意 default 參數要 C++ 才有, C 不可使用 default 參數
   static char buf[999];
   int nRead;   // 讀到幾項資料?
   fgets(buf, sizeof(buf), fp);
   nRead = sscanf(buf, "%ld %s %d %d %d %d", &(stu->sid),
      stu->name, &(stu->s1), &(stu->s2), &(stu->s3), &(stu->s4) );

      /// 題目規定這樣:
        // 學期總成績= (h*0.2 + m*0.3 + q*0.1+f*0.4); 
        /// 這裡的 s1, s2, s3, s4 就是 h, m, q, f

   stu[0].total = 0.2*stu->s1 + 0.3*stu[0].s2 + 
                                0.1*stu->s3 + 0.4*stu->s4;
   stu->total = ((int)(100* stu->total +0.50000001))/100.0;
   stu[0].rank = 1; // 大家都是第一名 :-); stu-> 改用 stu[0]. 可 
   stu[0].recno = 0;  // 這樣寫 OK,  (I do not know recno :-)
    // 注意, stu[0] 就是 *stu ; 以前說過任何時候 *p 就是 p[0]
    // 阿所以 stu->gg 就是 stu[0].gg 也就是  (*stu).gg
   return nRead;    // 這是 sscanf 回報給我們的
}// readStudent(
///
void readALL(Student_t x[ ], long n, char*file,
                  double sum[ ], double *sumsum) {
   long i; double tmp;
   FILE* fp = fopen(file, "rt"); // 偷懶, 不防呆
   sum[0] = sumsum[0] = 0.0;    // sum[0] 就是 *sum
   for(i=0; i < n; ++i) {
      readStudent( &x[i], fp);  // 注意 &x[i]
      tmp = x[i].total;  // 該學生的總成績
      sum[0] += tmp;    // 注意 sum[0] 就是 *sum  啦
      sumsum[0] += tmp*tmp;   // 平方和
      x[i].recno = i;  // 注意寫法喔! record no., 0..n-1
           // 多把 recno 也記下, 目的是讓 sort 看起來是 Stable
          // 這是因為 msort( ) 不是 stable sort
         // 所以, 我們從 compare function 下手! (看後面該函數)
   }// for i
   fclose(fp);  // 負責任, 我打開的阿就我自己來關掉它 :)
}// readALL(
///
void printStudent(Student_t stu, int finalFlag, int rankFlag) {
   // 注意 default 參數要 C++ 才有, 所以這程式要當作 C++
   // finalFlag !=0 ==> 印學期成績; rankFlag 要不要印名次
   printf("%8d  ", stu.sid);   printf("%8s  ", stu.name);
   printf("%3d  %3d  %3d  %3d  ", stu.s1, stu.s2, stu.s3, stu.s4);
   if(finalFlag) { // 這樣寫是若不印 total, 那一定不會印名次! Why?
      printf("%6.2f   ", stu.total);  // 學期成績
      if(rankFlag) {  // 印名次, 須有印學期成績
         printf("%5d", stu.rank);  // note that stu is a struct
      }// if rankFlag
   } // finalFlag   
   printf("\n");  // done
}
/// /// === === === End of the hwk12msort.c === === === ///
/***********
D:\test> path C:\Dev-Cpp\bin;%path%

D:\test> gcc gen333.c -o 3388

D:\test> 3388.exe
File studat.txt generated successfully.
Total 81518 student records.
 Hit ENTER key...

D:\test> gcc -c msort.c

D:\test> gcc hwk13m22.c msort.o

D:\test> a.exe
 counting... .. done.
Total 81518 records in file studat.txt
 N= 81518, Average= 74.99, STD標準差= 3.848
Before sort...
 9923821     王XRr   80   69   66   67   70.10
 9940081     張KAa   77   71   76   74   73.90
 9945722     簡JBm   86   78   82   68   76.00
 9927157     簡ULy   68   81   68   78   75.90
 9923899     李DMl   73   92   92   68   78.60
 9940059     魏RNh   73   85   70   71   75.50
...
Stu ID     name      hwk  mid  quiz fin  學期成績   名次
 9998420     章PQj   79   72   78   70   73.20
 9998422     張EHv   75   67   69   65   68.00
 9998424     林UVk   74   69   79   79   75.00
 9998457     魏TSh   77   68   72   87   77.80
 9998512     張XDd   64   81   69   72   72.80
...Sorting done in 0.07800 seconds.
After sort...
 9920646     簡YBd   89   90   82   93   90.20       1
 9965628     趙QFa   94   86   81   93   89.90       2
 9917252     陳PVl   87   84   78   98   89.60       3
 9982463     魏GHj   81   92   87   92   89.30       4
 9937815     陳GHx   97   84   83   91   89.30       5
 9925767     張WFq   92   79   82   97   89.10       6
...
Stu ID     name      hwk  mid  quiz fin  學期成績   名次
 9928496     章MRu   81   69   69    1   44.20   81514
 9964215     吳GSj   60   80   72    0   43.20   81515
 9998345     章FEr   78   65   75    0   42.60   81516
 9964826     陳EUr   74   73   56    0   42.30   81517
 9969093     陳DSo   69   63   70    0   39.70   81518
...Now Sorting according to student ID...
...Sorting done in 0.07800 seconds.

 === Now already sorted in Student_ID at ascending order.
 9917001     林KWl   74   75   75   76   75.20   39059
 9917002     張WVx   73   81   78   75   76.70   27056
 9917003     簡CAw   65   72   83   74   72.50   60329
 9917004     簡OMy   75   66   82   80   75.00   40498
 9917005     王GDm   69   68   63   72   69.30   75852
 9917006     蔡DDe   85   78   70   64   73.00   57275
...
Stu ID     name      hwk  mid  quiz fin  學期成績   名次
 9998514     林HKo   62   73   83   69   70.20   72925
 9998515     陳JXt   78   85   77   92   85.60     202
 9998516     張PCc   67   77   74   71   72.30   61757
 9998517     張ZOj   69   70   87   69   71.10   68836
 9998518     林WNl   79   65   84   76   74.10   48148
=== 改用gen333.c生的data是常態分佈, 原先是 Uniform 分布!
 N= 81518, Average= 74.99, STD 標準差= 3.848
==> 站在巨人肩膀上: 你也可以叫用 C 程式庫的 qsort,
        Sort 81518 筆資料依成績遞減Descending in 0.078 秒.
Hint: 用 rand( )%32767/32767.0 生出 12 個數加總, 然後減去6.0;
        這樣就是 N(0, 1)的常態分配亂數;
        把這亂數乘以你要的標準差, 再加上你希望的平均數;
        .. 這樣, 就會是你希望的常態分佈成績!

 遊戲放兩邊, 功課擺中間;
 注意我有講, 醜話說在先。
 別心存僥倖, 更不該偷懶;
 要想不被當, 習題多多練。
 .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?!
 Hit ENTER key...
D:\test>
***************************************************/