/* gensort2.c
   Performs a general sort on data stored as an array. Demonstrates
   calling a function gsort() which calls a comparison function passed as
   a parameter. The gsort() function is called twice to sort a set of
   records firstly by name, then by mark.
   
   This second version is more general in that it will sort any
   data. It does not require the user of gsort() to define
   a data type for swapping or comparison purposes, but results in
   more complex swap and (user defined) comparison functions.
   
   Richard Kay
   4 Jan 2001
*/

#include <stdio.h>
#include <string.h>

struct student {
  char name[30];
  float mark;
};
typedef struct student RECORD;

/* To make gsort truly general we need to pass the record length
   as a parameter to it and swap() functions. swap() has to 
   copy 1 byte (char) at a time up to the record length . This
   is easier with variable record length data as with this we just
   swap fixed size pointers to sort it.
*/


void gsort(void *a, size_t rleng, int rows, int (*comp)(void *x,void *y));
  /* gsort parameters:
     *a: address of array to be sorted
     rleng: record length in bytes 
     rows: number of records in the array
     *comp: address of the user-defined comparison function */

  /* comp parameters:
     *x,*y: addresses of first and second records to compare    */

void swap(void *x,void *y, size_t rleng);
  /* swap parameters:
     *x and *y the addresses of the starts of records to be swapped 
     rleng: record length in bytes */ 

void pause(void); /* pauses program */

RECORD a[]={{"Ashok",92.6},
	    {"Seamus",74.7},
	    {"Jaswinder",56.4},
	    {"George",63.2},
	    {"Suresh",34.2},
	    {"Stuart",11.1},
	    {"Harry",87.4},
	    {"Delroy",55.5}};

/* comp_name() and comp_mark() functions are defined above the
   call of gsort() in main() so that their addresses are known 
   beforehand. */


int comp_name(void *x,void *y){
  /* compares sort position based on name */
  RECORD *a,*b;
  a=(RECORD*)x; /* cast addresses in x and y to type RECORD */
  b=(RECORD*)y;
  /* compares 2 names to see if in order, same or in reverse sort order */
  return strcasecmp(a->name,b->name); 
      /* Linux strcasecmp() is the same as Borland stricmp(),
        to compare strings case insensitively 
        both return -1 , 0 or +1 */
}

int comp_mark(void *x,void *y){
  /* compares sort position based on mark */
  RECORD *a,*b;
  a=(RECORD*)x; /* cast addresses in x and y to type RECORD* */
  b=(RECORD*)y;
  if(a->mark > b->mark)
    return 1;
  else if(a->mark > b->mark)
    return -1;
  else
    return 0;
}


int main(void){
  int n,i;
  n=sizeof(a)/sizeof(RECORD); /* should be 8 */
  printf("there are %d records\n",n);

  /* sort and display by name */
  gsort((void*)a,sizeof(RECORD),n,comp_name);
  printf("data sorted by name\n");
  for(i=0;i<n;i++)
    printf("%30s %f\n",a[i].name,a[i].mark);
  pause();

  /* sort and display by mark */
  gsort((void*)a,sizeof(RECORD),n,comp_mark);
  printf("data sorted by mark\n");
  for(i=0;i<n;i++)
    printf("%30s %f\n",a[i].name,a[i].mark);

  pause();
  return 0;
}


void pause(void){
  printf("press enter to continue\n");
  getchar();
}

void gsort(void *a,size_t rleng,int rows, int (*comp)(void *x,void *y) ){
   /* realistic general sorts functions are more likely to use the
      quicksort recursive algorithm. This one uses bubble
      sort for simplicity.  */
   int i,j=rows;
   for(j=rows;j>0;j--){
     for(i=0;i<j-1;i++){
        /* Using a void array pointer we now have to multiply array indexes 
	 * by the record length in order to get the 2 record addresses */
       if((*comp)(a+i*rleng,a+(i+1)*rleng) > 0 ) 
	 swap(a+i*rleng,a+(i+1)*rleng,rleng);
     }
   }
}

void swap(void *x,void *y,size_t rleng){
  /* swaps rleng bytes at address x with rleng bytes at address y.
   * This depends upon char being 1 byte wide. Unicode users beware!  */
  char temp, *a,*b;
  int i;
  a=(char*)x; /* cast void* pointers to char* pointers */
  b=(char*)y;
  for(i=0;i<rleng;i++){
    temp=*(a+i);
    *(a+i)=*(b+i);
    *(b+i)=temp;
  }  
}