//msort.c that contains merge sort  (兩個不同版本)
//   @CopyLeft by tsaiwn@cs.nctu.edu.tw
// 注意: msort( ) 用法與程式庫 qsort( )一樣; useMgSort( ) 則用法不一樣!
#include <string.h>
#include <stdlib.h>
#include  "mystu.h"
// 認真的同學可以研究這兩個 merge sort 是如何把資料排序好!
//////
// 再宣告一次也沒關係: (但要宣告一樣才可!)
void useMgSort(Student*x, int n, int(*comp)(Student*,int,int));
// 注意上面這版本的用法! 還有, 所需的 compare function 的寫法也不同!
// 以下的 msort( ) 與 qsort( )用法完全相同的版本寫在後半部
void msort(void*x, int n,int sz, int(*comp)(const void*, const void*));
//////
// 注意在 mystu.h 裡面除了要先有 struct Student 的定義, 還有..
// 裡面要放這兩個 merge sort 函數的宣告!
// 這樣, 你只要 #include "mystu.h"  就可使用這兩個函數!
// 不然, 你要自己把上面這宣告 copy 到你程式內! (讓Compiler編譯時看的)
// 還有, 這檔案中很多函數, 但我只有開放這 useMgSort( ), 和 msort( )
/// 其他的函數都用 "static" 保護起來, 只在這檔案(file)內有效!
// 注意! 關於資料結構 (struct),
// 注意這例子我故意用 Student 而不是 Student_t 免得你以為依定要有 _t
// 不過, 一般是建議要尾巴有 _t 以方便辨識是 type!
/// 可以用 Student 是因為我在 mytstu.h 內用 typedef 再弄出 Student 來用 !
/// gcc yourMain.c msort.c 
//////
// In fact, we do NOT have to use copy2tmp/copyBack functions.
// Why? Because of using struct, the copy jobs become very simple!
// Thus, you can simply do these jobs directly in the sorting prog.
static void copy2tmp(Student*a, Student*t, int k, int i){
   t[k] = a[i];
}
static void copyBack(Student*a, Student*t, int i){
   a[i] = t[i];
}
static void merge(Student*, Student*,
          int left, int right, int m, int(*)(Student*,int, int));
static void mergeSort(Student*a, Student*tmp,  // sorting array a[ ]
          int left, int right, int(*comp)(Student*,int,int)) {
   int mid;   // sorting from a[left] to a[right]
   if(left >= right) return; // nothing to do :-)
   if(left+1 == right) {  // two elements
       if( comp(a, left, right) <= 0 ) return;  // 順序符合不用做 :-)
   }// 2 elements
   mid = (left+right)/2;
   mergeSort(a, tmp, left, mid, comp);  // left..mid 算左半
   mergeSort(a, tmp, mid+1, right, comp);  // mid+1 .. right
   merge(a, tmp, left, right, mid, comp); // 注意要把比較函數傳過去
} // mergeSort(
void merge(Student *a, Student* tt,
      int left, int right, int mid, int(*comp)(Student*,int,int)) {
   int i, r, to;  // 注意我故意用變數 tt 免得你以為一定要寫 tmp
   i = to = left;
   r = mid+1;
   while((i <= mid) && (r <= right)) { // 左右都還有資料
      if(comp(a, i, r) <= 0) {    // a[i]<a[r] ?
         copy2tmp(a, tt, to, i);  // tt[to]=a[i];
         to++;  i++;   // 這樣寫 <= 0 則相等時是先拿左半的
      }else{
         copy2tmp(a, tt, to, r);   // tt[to]=a[r];
         to++;  r++;
      }
   }// while
   while(i <= mid) {  // 左半還有嗎?
      copy2tmp(a, tt, to, i);  // tt[to]=a[i];
      to++; i++;
   }
   while(r <= right) {  // 右半還有嗎?
      copy2tmp(a, tt, to, r);  // tt[to]=a[r];
      to++; r++;
   }
   //for(i=left; i < to; i++) copyBack(a, tt, i); // a[i] = tt[i]; 
   memcpy(a+left, tt+left, sizeof(Student)* (to-left));
} // merge(
////////////////////////////////////////
/// 告訴我array起點, 有幾個元素; 還有, 這個不可以 static 喔!
void useMgSort(Student*x, int n, int(*comp)(Student*,int,int)) {
   Student*temp = (Student*) malloc(n* sizeof(Student));
   // 以上這句是先去要個足夠空間 (n 個學生)來當臨時用途
   mergeSort(x, temp, 0, n-1, comp);
   free(temp);  // 有借有還, 再借不難 :-)
}// useMgSort(
// 注意因為我們把這個 useMgSort( ) 放獨立的檔案
// 所以要把這 useMgSort( ) 的"樣子" (prototype, 雛形 ) 給使用者!
// 那最方便的方式就是把這函數的"頭"(prototype)抄到 mystu.h 內
// 然後, 本檔案(file)的最前面 #include "mystu.h"
// 使用者(就是會用這sort的主程式啦)也要 #include "mystu.h"
// 阿當然啦, 就把 struct Student 的定義搬到 mystu.h 內
// 還有, mystu.h 要用以下三句保護, 以免不小心被 #include 太多次:
//  #ifndef _MYSTU_H_
//  #define _MYSTU_H_
//  ... 這裡是原先你要寫在 mystu.h 的內容
//  #endif
// 這裡的 _MYSTU_H_ 是慣用法, 把檔案名稱用全大寫並於左右補 _ 識別.
/// 再強調一遍..
// 如果這 sorting program 的原始檔案不想要給別人看, 但要給人用,
// 那就先  gcc -c msort.c   生出  msort.o
// 只要把 msort.o 和 mystu.h 給別人, 則別人就可使用了:-)
// 像這樣:
//  gcc yourMain.c msort.o   這樣就可生出執行檔案
////////////////////////////////////////////////////////////
////////
//////
// void msort( ) --- Another version of merge sort
///
// 再宣告一次也沒關係: (但要宣告一樣才可!)
// 以下這是仿照 C Library 的 qsort( ), 用法跟 qsort( ) 完全相同!
void msort(void*x, int n,int sz, int(*comp)(const void*, const void*));
// 注意在 mystu.h 裡面也要放這 msort( ) 的宣告, 方便使用者使用!
// 不然, 你要自己把上面這宣告 copy 到你程式內! (讓Compiler編譯時看的)
///
static void merge22(void*, void*,int sz,
          int left, int right, int m, int(*)(const void*, const void*));
static void mergeSort22(void*a, void*t, int sz, // sorting array a[ ]
          int left, int right, int(*comp)(const void*, const void*)) {
   int mid;   // sorting from a[left] to a[right]
   if(left >= right) return; // nothing to do :-)
   if(left+1 == right) {  // two elements
       if( comp(a+left*sz, a+right*sz) <= 0 ) return;  // 順序符合不用做 :-)
   }// 2 elements
   if(left+2 == right) {  // three elements
       if( comp(a+left*sz, a+left*sz+sz) <= 0  && 
          comp(a+right*sz-sz, a+right*sz) <= 0 ) return; // 順序符合不用做 :-)
   }// 3 elements
   mid = (left+right)/2;
   mergeSort22(a, t, sz, left, mid, comp);  // left..mid 算左半
   mergeSort22(a, t, sz, mid+1, right, comp);  // mid+1 .. right
   merge22(a, t, sz, left, right, mid, comp); // 注意要把比較函數傳過去
} // mergeSort22(
void merge22(void *a, void* tt, int sz,
      int left, int right, int mid, int(*comp)(const void*, const void*)) {
   int i, r, to;  // 注意我故意用變數 tt 免得你以為一定要寫 t
   int len;
   i = to = left;
   r = mid+1;
   while((i <= mid) && (r <= right)) { // 左右都還有資料
      if(comp(a+i*sz, a+r*sz) <= 0) {    // a[i]<a[r] ?
         memcpy(tt+to*sz, a+i*sz, sz); // tt[to] = a[i];
         to++;  i++;   // 這樣寫 <= 0 則相等時是先拿左半的
      }else{
         memcpy(tt+to*sz, a+r*sz, sz);  // tt[to] = a[r];
         to++;  r++;
      }
   }// while
   //while(i <= mid) {  // 左半還有嗎?
   //   memcpy(tt+to*sz, a+i*sz, sz);   // tt[to]=a[i];
   //   to++; i++;
   //}
   /// 以下的 if block 與上面 while Loop 做的事是一樣的
   if( i <= mid) {    // 左半還有嗎?
      len =  (mid-i+1);
      memcpy(tt+to*sz, a+i*sz, len*sz); 
      to += len;
      i += len;
   } //if
   if(r <= right) {  // 右半還有嗎?
      len = right - r + 1;
      memcpy(tt+to*sz, a+r*sz, len*sz); 
      to += len;
      r += len;
   }
   /// 以上的 if block 與下面 while Loop 做的事是一樣的
   //while(r <= right) {
   //   memcpy(tt+to*sz, a+r*sz, sz);  // tt[to]=a[r];
   //   to++; r++;
   //}
   //for(i=left; i < to; i++) copyBack(a, tt, i); // a[i] = tt[i]; 
   // Now, ALL data are in tt[ ];  所以就全部 copy 回 a[ ]
   memcpy(a+left*sz, tt+left*sz, sz* (to-left));
} // merge(
////////////////////////////////////////
/// 告訴我array起點, 有幾個元素, 每個元素幾Bytes, compare_function
/// 所以參數與 C Library  的 qsort( ) 完全一樣
/// Note that 這函數不可以 static 喔!
void msort(void*x, int n, int sz, int(*comp)(const void*, const void*)) {
   void*temp = (void*) malloc(n* sz);
   // 以上這句是先去要個足夠空間 (n 個學生)來當臨時用途
   mergeSort22(x, temp, sz, 0, n-1, comp);
   free(temp);  // 有借有還, 再借不難 :-)
}// msort(
///
/// 再強調一遍..
// 如果這 sorting program 的原始檔案不想要給別人看, 但要給人用,
// 那就先  gcc -c msort.c   生出  msort.o
// 只要把 msort.o 和 mystu.h 給別人, 則別人就可使用了:-)
// 像這樣:
//  gcc yourMain.c msort.o   這樣就可生出執行檔案
// ======== 本檔案到此結束  ======