//STLsort.cpp ---  @copyLeft by tsaiwn@csie.nctu.edu.tw
// modified from readstu2.c
// Now we utilize the sort( ) in STL <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define FILE_NAME "studat.txt"
const char* fileName = "studat.txt";   // 這樣也 OK
#define STL_SID_SORT  2008
#define STL_SCORE_SORT  2009
#define UNSTABLE_SEL 5566
#define BUBBLE_SORT  1895
#define INSERTION_SORT 2630
#define C_QSORT 258
// for debugging, print stack height
double weight[ ]={0, 0.3, 0.1, 0.2, 0.4 };
#define PRT_STK_HT 8
typedef struct {     // 這種寫法比較好 :-)
   long sid;   // long 夠用來當交大學號
   char name[9]; 
   int s1, s2, s3, s4; 
     // mid*0.3, quiz*0.1, hwk*0.2, fin*0.4
   double final;  // 學期成績
   int rank; // 名次
} Student;      // 從此可以過快樂的日子  :-)
// /// /// /// /// 因為只有一點點, 所以沒寫成 "student.h" 檔
Student x[99], stmp; 
int readStudent(Student * stu, FILE* fp);
void printStudent(Student stu, int finalFlag, int rankFlag);
void getData(Student*);
void printALL(Student*,int);
void sort(Student*,int,int, int);  // default use quick sort

void hint( );
void printSortMSG(int whichSort);
/// /// /// 
int countRecords(char* fname) {
   int n=0; FILE* fp = fopen(fname, "rt"); static char buf[999];
   fgets(buf, sizeof(buf), fp);
   while(!feof(fp) ) { ++n; fgets(buf, sizeof(buf), fp); }
   fclose(fp);
   return n;    
}
int nStu;  // 記住總共幾個 records
//Student y[88888];   // array vs. pointer ?
Student * y;  // used as y[ ];  // dynamic allocated
int main( ) {
    long long tStart, tStop; double tRun;  // use clock( ) in <time.h>
    FILE* fp;
    fp = fopen(FILE_NAME, "rt");
    if(fp==0) {printf("%s NOT found! ", FILE_NAME); 
       getchar( ); return 1; }
   //////////////////////////////
    printf("Stu ID     name      hwk  mid  quiz fin  學期成績   名次\n");
    readStudent( &x[0], fp);  // 注意 "&"
    readStudent( &x[1], fp);  // 類似 scanf 要傳 address 過去!
    readStudent( &stmp, fp);  x[2] = stmp;  // 哈哈! 這樣也可!!
    printf("The 2nd student (x[1]) :\n");
    printStudent(x[1], 0, 0);     // 若不能用default參數, 要加 ,0,0
    printf("The 3rd student (x[2]) :\n");
    printStudent(x[2], 1, 1);   // 印學期稱績, 與名次
    fclose(fp);
   ///
    int whichSort; static char stmp[99];
    hint( );
    fprintf(stderr, " Enter the value : ");
    fgets(stmp, sizeof(stmp), stdin);

    whichSort = atol(stmp);  // MAGIC_NUMBER (3388) for Selection sort
   ///
    nStu = countRecords(FILE_NAME);
    y = (Student*)malloc( sizeof(Student) * (nStu+1) ); // C 用法
        // y = new Student[nStu+1];   // C++ 這樣用比較好
    if(y != 0) printf(" got memory OK...\n");
    getData(y);
    fprintf(stderr, "Total %d records.\n", nStu);
    fprintf(stderr, "Before sorting ...\n");
    printALL(y, nStu);
    /// ///
    printSortMSG(whichSort); /// ///
    tStart = clock( );
    sort(y, 0, nStu-1, whichSort);
    tStop = clock( );
    tRun = (tStop - tStart)*1.0/CLOCKS_PER_SEC;
    fprintf(stderr, "\n ... sorting  %d records ", nStu); 
    fprintf(stderr, " done in %.3f seconds.\n", tRun);
    printALL(y, nStu);
    fprintf(stderr, "Hit ENTER key...");
    getchar( );
    return 0;
}
// === === === main end === === ===
void printSortMSG(int whichSort) {
    fprintf(stderr, " .. sorting ...");
    return;
} // printSortMSG( )
void hint() {
    fprintf(stderr, "       %d for C_built-in qsort\n",
                 C_QSORT);
    fprintf(stderr, "       %d for STL sid sort\n",
                 STL_SID_SORT);
    fprintf(stderr, "       %d for STL score sort\n",
                 STL_SCORE_SORT);
} // hint( )

// /// /// ==========================================================
int readStudent(Student * stu, FILE* fp) {  // default stdin
   // 注意 default 參數要 C++ 才有, 所以這程式要當作 C++
   static char buf[99];
   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) );
   stu->final = weight[1]*stu->s1 +weight[2]*stu->s2 +
      weight[3]*stu->s3 + weight[4]*stu->s4;
   stu->final = ((int)(100* stu->final +0.500001))/100.0;
   stu->rank = 1; // 大家都是第一名 :-)
   return nRead;
}
void printStudent(Student 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.final);  // 學期成績
      if(rankFlag) {  // 印名次, 須有印學期成績
         printf("%5d", stu.rank);  // note that stu is a struct
      }
   } // finalFlag   
   printf("\n");  // done
}
/// /// /// /// /// /// /// /// =====================================
void getData(Student * y) {
   int i;  // nStu is a global
   static char buf[999];
   FILE* fp = fopen(FILE_NAME, "rt");
   if(fp==0) {
      fprintf(stderr, " File %s NOT found...", FILE_NAME);
      getchar( );
      exit(38);
   } //=============
   for(i=0; i< nStu; ++i) readStudent(&y[i], fp);
   fclose(fp);
}
// /// /// /// /// /// /// /// /// /// /// /// /// ///
void printALL(Student*x, int n) {
   int i;
   for(i=0; i<=5; ++i)
      printStudent(x[i], 1, 0);
   printf("...\n");
   for(i=nStu-5; i< nStu; ++i)
      printStudent(x[i], 1, 1);
}
/// /// ///===========================================================
/// /// ///===========================================================
// compare function for C Library function qsort( )
long kkMYC = 0;
int myCompare(const void*a, const void*b) {
   Student *p1 = (Student*)a;
   Student *p2 = (Student*)b;
   if(kkMYC++ < 8) fprintf(stderr, " myCompare.. ");
   return (p1->sid - p2->sid);   // for 由小排到大
      // return (*p1).sid - (*p2).sid;   // for 由小排到大
      // return -(p1->sid - p2->sid);  // 若要相反順序
      // return (p2->sid - p1->sid);  // 若要相反順序
      // return (*p2).sid - (*p1).sid;  // 若要相反順序
}
/////////////
// ///
long kkLess = 0;
bool operator<(const Student& a, const Student& b) {
    if(kkLess++ < 8) fprintf(stderr, " LESS.. ");
    return a.sid < b.sid;  // for 由小排到大
}  /*** used by sort(ary, ary+n);  ***/
// ///
long kkCOMP = 0;
bool comp(const Student& a, const Student& b) {
   if(kkCOMP++ < 8) fprintf(stderr, " COMP.. ");
   if(a.final == b.final) {
      return (a.sid < b.sid);   // for id由小排到大
   }
   return (b.final < a.final);   // for fin 由大排到小
}
///
void stlSidSort(Student*x, int n) {
    sort(x, x+n); //  sort in STL will use operator<
    //sort(x, x+n, comp);    // use comp( ) function
}
/// provide a compare function for "sort" in STL
void stlScoreSort(Student*x, int n) {
    sort(x, x+n, comp);    // use comp( ) function
}
/// /// //
/////////////////////////
void sort(Student* x, int left, int right, int kk) {
   if(kk== STL_SID_SORT) stlSidSort(x, right-left + 1);
   else if(kk== STL_SCORE_SORT) stlScoreSort(x, right-left + 1);
   else if(kk== C_QSORT) qsort((void*)x,  
            right-left + 1, sizeof(Student), myCompare);
                        // 或寫這樣 (int(*)())myCompare
}
/// /// /// === === ===  End of the program  === === === /// /// ///