//////////////////  2010/11/26 Friday
//hwk12qsort.c --- sample program to SORT studat.txt
//========== Originally by tsaiwn@csie.nctu.edu.tw
//====== Modified by student_ID student_Name  _______________ 
const char *hahaha = " \n"
  " 五都選舉在明天, 藍綠搶票爭撒錢;  \n"
  " 管他誰輸誰當選, 太陽依舊在天邊。 \n"
  " 既然現在課已選, 就該習題多多練;  \n"
  " 程式一點也不難, 不該偷懶又擺\爛。 \n"  // 那個ㄅㄞˇ 有問題
  " .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?!\n";
///   上面的"擺\" 反斜線不可以去掉, 不然翻譯有錯!! 
/// /// 因為 擺\爛 的 "擺\" 之內碼是0xc2 0x5c; 0x5c 是反斜線 !!
//////   阿字串中的 \ 是逃脫字符! 例如 \n 是 NewLine, \t 是跳格
////// 所以 "\\" 就變成一個反斜線!  What if 內碼第一Byte是 \ ?
//////  如果註解 // 後面的最後一個字是 擺 阿那會怎樣呢???
/// 
/// 注意, 這範例只做照學號排序(sorting), 照題目規定應該..
///  請看習題說明, 關於 全部同學的平均 和 標準差.. 
///   在資料看完一遍後就可算出來! 不必先算平均喔!
/// .. 算這些統計資料的做法以前範例已經給過, 再不懂舉手問 :-)
// 站在巨人的肩膀上:  
//   這版本是偷用 C 程式庫中的 qsort( ) 做排序
//    注意使用 qsort( ) 須先照規定寫好 call back function
// ..  阿就是compare function 參數要照規定接受兩個 const void* 
// *** 想要不同順序, 只要寫不同的 compare function 傳給qsort
// *** 注意， qsort 只知道資料是連續一堆 bytes,
// *** 每當它想比較, 就會把兩項資料在記憶體的起點傳給比較函數
// *** 所以比較函數的參數是  (const void*, const void*)
///*** 你的比較函數必須自己轉換成你知道的型別(type) 
///*** 因為你 call qsort( ), 然後 qsort( ) 回頭 call 你寫的
///*** .. call 你寫的 比較函數, 所以稱為 call back function! 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
char* fileName = "studat.txt";  // Data File
long test( );  // 會傳回有幾個 records
/// /// 雖然定義 struct 有很多寫法, 建議用這種寫法:
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)
///
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( );  // 這列以上不准改!
   // 打開檔案讀資料到記憶體, 也可寫成 function 在此 call 它 !
   // 一邊讀, 一邊算出每個人的學期總成績; 或讀完再算也可以!
   // ..注意, 還要算出全部同學的平均 和 標準差
   stus = (Student_t*) malloc(sizeof(Student_t)*n); // n 筆
   readALL( stus, n, fileName,&sum, &sumSquare);  //into stus[ ] 
   average = sum / n;    // 以下變異數公式以前給過, 忘了就上網查
   variance = (sumSquare - sum*sum/n) / n;
   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;
   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( ) 印出部份資料+名次
   // Extra credit: 要有名次, 同分者比期末考, 再同比期中考, ..
 ///
   sort2Print(stus, n); // 在裡面做照學號由小到大sort, 要測時間

   printf("=== 其實這些分數根本不是常態分佈, 是 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(  
/// /// /// ================ ============== ==============
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<=5; ++i)
      printStudent(x[i], 1, rankFLAG);
   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, 
/// 要讓 qsort 做 Descending 排序, 若同分, 則照原 record no遞增
/// ..這樣就等同於 stable(穩定)的 sort; (注意qsort不是 stable !)
int myComp(const void*pa, const void*pb) { // for sort( ) 總成績 
   Student_t * sa = (Student_t*) pa; // cast 轉型
   Student_t * sb = (Student_t*) pb;
   if(sa->total < sb->total) return 1;
   if(sa->total > sb->total) return -1;
  /// 總成績相同, 比期末考 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 qsort( )
   qsort((void*)x,
           right-left + 1, sizeof(Student_t), myComp);

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

} // sort(
 
///
/// 再來是 a 比較函數that compares ID, 要讓 qsort 做 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( );

   qsort((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;
   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
   }// 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) {
      printf("%6.2f   ", stu.total);  // 學期成績
      if(rankFlag) {  // 印名次, 須有印學期成績
         printf("%5d", stu.rank);  // note that stu is a struct
      }
   } // finalFlag   
   printf("\n");  // done
} //printStudent(  
/// /// === === === End of the hwk12qsort.c === === === ///
/***********
D:\test> path C:\Dev-Cpp\bin;%path%

D:\test> gcc hwk12qsort.c

D:\test> a.exe

Line-1: 9943760     錢YLs  75  11  84  42

Line-2: 9941564     林PHe   3  80  96  91

kk=6
 something Wrong with data!
id=9941564  name = 林PHe
score= 3 80 96 91
 counting... .. done.
Total 81503 records in file studat.txt
 N= 81503, Average= 62.55, STD標準差= 15.988
Before sort...
 9943760     錢YLs   75   11   84   42   43.50
 9941564     林PHe    3   80   96   91   70.60
 9938531     孫VBd   82   60   84   35   56.80
 9929387     簡ORa   81    5   99    5   29.60
 9918783     林HCs   42    2   83   83   50.50
 9926001     錢SHx   40   47   66   79   60.30
...
Stu ID     name      hwk  mid  quiz fin  學期成績   名次
 9998487     章CDl   64   54   99   59   62.50
 9998488     簡VKc   41   40   52   51   45.80
 9998499     章AJk   14   98   90   77   72.00
 9998501     趙HTq   74   94   67   71   78.10
 9998502     王UTt   73   66   92   38   58.80
...Sorting done in 0.06200 seconds.
After sort...
 9918979     蔡TSs   99   99   96   98   98.30       1
 9927716     魏TEk   94   99   96   99   97.70       2
 9983647     陳NWu   98   95   98   99   97.50       3
 9963171     錢NNt   99   95   94   99   97.30       4
 9993126     孫AHi   99   99   90   97   97.30       5
 9995847     趙OSn   91   99   96   99   97.10       6
...
Stu ID     name      hwk  mid  quiz fin  學期成績   名次
 9931010     陳QVi    8    5   12    2    5.10   81499
 9937701     章BFr   12    5    4    2    5.10   81500
 9946983     吳OVw    1    8    8    2    4.20   81501
 9935478     張AQa   10    1    6    3    4.10   81502
 9973775     張IAk    1    0    4    6    3.00   81503
...Now Sorting according to student ID...
...Sorting done in 0.07800 seconds.

 === Now already sorted in Student_ID at ascending order.
 9917001     林DOs   61   93   13   82   74.20   21276
 9917002     蔡SOk   99   12   83    2   32.50   78011
 9917003     魏SGj   83   12   56   41   42.20   72114
 9917004     蔡UDb    6   10   57   39   25.50   80065
 9917005     林LXa   42   35   55   49   44.00   70390
 9917006     吳KAk   81   66   92   48   64.40   40112
...
Stu ID     name      hwk  mid  quiz fin  學期成績   名次
 9998499     章AJk   14   98   90   77   72.00   25453
 9998500     吳LLi   82   98   88   91   91.00     911
 9998501     趙HTq   74   94   67   71   78.10   14637
 9998502     王UTt   73   66   92   38   58.80   50171
 9998503     林JUg   96   95   90   41   73.10   23345
=== 其實這些分數根本不是常態分佈, 是 Uniform 分布!
 N= 81503, Average= 62.55, STD標準差= 15.988
==> 站在巨人肩膀上: 本程式叫用 C 程式庫的 qsort,
        Sort 81503 筆資料依成績遞減Descending in 0.062 秒.
Hint: 用 rand( )%32767/32767.0 生出 12 個數加總, 然後減去6.0;
        這樣就是 N(0, 1)的常態分配亂數;
        把這亂數乘以你要的標準差, 再加上你希望的平均數;
        .. 這樣, 就會是你希望的常態分佈成績!

 五都選舉在明天, 藍綠搶票爭撒錢;
 管他誰輸誰當選, 太陽依舊在天邊。
 既然現在課已選, 就該習題多多練;
 程式一點也不難, 不該偷懶又擺爛。
 .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?!
 Hit ENTER key...
D:\test>
***************************************************/