/****A. V. Gerbessiotis 
 ****Permission to use, copy, modify, and distribute this software,
 ****and to incorporate it, in whole or in part, into 
 ****other software,is hereby granted without fee, provided that
 ****  (1) the above copyright notice and this permission 
 ****      notice appear in all copies of the source code, and 
 ****      the above copyright notice appear in clearly visible 
 ****      form on all supporting documentation and distribution 
 ****      media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee, whatsoever, is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects. Use this code at your own personal risk.
 ****/
#include "ssrt.h"
#include "../avgmain.h"
#include "sids.h"

#define N_SORT_ALGS 15


#define MY_DATA char
#define SLENGTH 4   /* STRING LENGTH */
#define SL      4   /* STRING LENGTH THAT IS BEING PRINTED (DEBUGGING) <= slength */

/* CHECK DELETE OR NOT THIS LINE; FOR D-SORTING OR RAND-SORTING */

/*
#define DSORT
*/


#define CHECKOUTPUT  for(k=0;k<n-1;k++) { if (compare((char*)&rptr[SLENGTH*k],(char*)&rptr[SLENGTH*(k+1)])>0) printf("error %d %d \n",k,k+1);}
#define CHECKOUTPUT2  for(k=0;k<n-1;k++) { if (compare((char*)&ptr[SLENGTH*k],(char*)&ptr[SLENGTH*(k+1)])>0) printf("error %d %d \n",k,k+1);}

#define SET_PTR    memcpy(ptr,bptr,(SLENGTH*n*sizeof(MY_DATA)));
#define PRINT_INP printmd(ptr,debug,n,"In :");
#define PRINT_OUTQ printmd(ptr,debug,n,"Out:");
#define PRINT_OUT printmd(rptr,debug,n,"Out:");
#define PRINT_INP2 printmd(ptr,debug,n,"In2:");
#define PRINT_OUT2 printmd(ptr,debug,n,"Ou2:");
#define PRINT_OU2 \
        if ((debug==1) || (debug == -1)) { \
         printmd(0,ptr,PRINT_INT,n,"Ou2:"); \
        }
#define TINIT   perrun=elapsed=(double)0;
#define TSTART  perrun =(double)0; avg_tstart();
#define TEND    avg_tend(); perrun=(avg_treturn()); elapsed +=(perrun);

int compare(const void *x,const void *y)
{
/*
 return (int)(* ((MY_DATA*)x)-*((MY_DATA*)y));
*/
 return (memcmp(x,y,SLENGTH));
}

int initialize(MY_DATA *keys, int n)
{
 register int i,j;
 srandom(21+1001*0);
 for(i=0;i< n;i++){
   for(j=0;j< SLENGTH-4;j++){
/*
    keys[i*SLENGTH+j] = (MY_DATA)(0);  
*/
    keys[i*SLENGTH+j] = (MY_DATA)(random() &  255 );
   }
   for(j=SLENGTH-4;j< SLENGTH;j++){
    keys[i*SLENGTH+j] = (MY_DATA)(random() &  255 );  /* & 127 */
   }
 }
 return(0);
}


void print_cha(char *ptr, int n, char *s, int num)
{
  register int i;
  printf("%3sP[%d]:",s,n);
  for(i=0;i<num;i++) {
    printf("%2d%2d,"
     ,(unsigned int) ptr[i*SLENGTH+0]
 ,(unsigned int)ptr[i*SLENGTH+1] 
    );
  }
  printf("...");
  for(i=n-num;i<n;i++){
   printf("%2d%2d," ,
     (unsigned int) ptr[i*SLENGTH+0]
    ,(unsigned int)ptr[i*SLENGTH+1]
    );
  }
  printf("\n"); fflush(stdout);
}

void  printmd(void *ptr,int opt,int n,char *s) 
{
 if (opt==1)   print_cha((char *)ptr,n,s,ELMNTS);
}



int main(int argc,char *argv[]) {
  int i,k,n,rn,runs,testid,range,debug,splitters,alexg,percent;
  MY_DATA *ptr,*bptr,*rptr;
  double elapsed,perrun,t1,t2;
  int oversample;

 void (*gfunc[N_SORT_ALGS])() = { 	
   qsort,     g50gnu,      g33heapx,    g63fbc  ,    g68non1,   
   g68wbh ,   g33heapx,    g35heapx,    g61wbh,      g62dbh,   
   g63fbc,    g65non1  ,   g68non1,     g68non2,     g68wbh
/*
   qsort,     g50gnu,      g30mrgit,    g39mrgit,    g65non2,   
   g66non1,   g33heapx,    g35heapx,    g61wbh,      g62dbh,   
   g63fbc,    g65non1  ,   g68non1,     g68non2,     g68wbh
*/
      };
 char *labels[N_SORT_ALGS]   = { 	
   "qs: qsort",    "gq: g50gnu",   "hp:g33heapx",  "fq: g63fbx",  "iq:g68", 
   "wq: g68wbh",  "g33heapx", "g35heapx",  "g61wbh",    "g62dbh",   
   "g63fbc",   "g65non1",  "g68non1",   "g68non2",   "g68wbh"
/*
   "qsort",    "g50gnu",   "g30mrgit",  "g39mrgit",  "g65non2", 
   "g66non1",  "g33heapx", "g35heapx",  "g61wbh",    "g62dbh",   
   "g63fbc",   "g65non1",  "g68non1",   "g68non2",   "g68wbh"
*/
      };

  int doalg[N_SORT_ALGS] = {
    1, 1, 1, 1, 1,    1, 0, 0, 0, 0,   
    0, 0, 0, 0, 0 };
/*
    1, 1, 1, 1, 0,    0, 1, 1, 0, 0,   
    1, 0, 1, 0, 1 };
*/
/*
    1, 1, 1, 1, 0,    0, 0, 0, 0, 0,   
    0, 0, 0, 0, 0 };
*/
/*
    1, 1, 1, 1, 1,    1, 1, 1, 1, 1,   
    1, 1, 1, 1, 1 };
*/


 void (*GTYPESORT)(void *,int,int,int (*) (const void *,const void *));


  n=1000;runs=1;testid=0;range=2;

  if (( argc < 7 ) || (argc > 7)) {
    printf("Usage: %s numofkeys numofsplitters runs alexg percent(=100) debug\n",argv[0]);
    return(1);
  } 
  else {
    n = atoi(argv[1]);
    splitters=atoi(argv[2]);
    runs=atoi(argv[3]);
    alexg=atoi(argv[4]);
    percent=atoi(argv[5]);
    debug=atoi(argv[6]);
    if (percent==0) percent=100;
   }

   printf("%s : n= %d split = %d runs = %d alexg= %d percent = %d debug = %d SL=%d\n", 
          argv[0], n,splitters, runs,alexg,percent,debug,SLENGTH);
#ifdef OLD
   oversample = (int)ceil(((percent/100.0)*(double)log(log((double)n)))+1.0);
   printf("Estimated oversample  = %d \n",oversample);
  if (splitters <  256 )
        oversample =  oversample *4;
    else {
       if ( (splitters > 256) && (splitters <  750 ))
           oversample =  oversample * 1.5;
       else
           oversample =  MAX(oversample/4,1);
    }
#endif
#ifdef DSORT
   oversample=(percent/100.0)*alexg;
#else
   oversample=(int) ceil(((percent/100.0)*pow(log((double)n),(1.0+alexg/100.0)))+1.0);
#endif

#ifdef DSORT
   printf("splitters=%d oversample=%d SamplePerB=%d, SampleTotal=%d n=%d KeysPerB=%d\n",
splitters,oversample,(splitters+1)*oversample,(splitters+1)*(splitters+1)*oversample,n,n/(splitters+1)); fflush(stdout);
   printf("%d %d\n",THRES16,TMERGE); fflush(stdout);
#else
   printf("splitters=%d oversample=%d SamplePerB=%d, SampleTotal=%d n=%d KeysPerB=%d\n",
splitters,oversample,(splitters+1)*oversample-1,(splitters+1)*oversample-1,n,n/(splitters+1)); fflush(stdout);
   printf("%d %d\n",THRES16,TMERGE); fflush(stdout);
#endif

   t1=t2=0.0 ;
   ptr = (MY_DATA *) Malloc(SLENGTH*n*sizeof(MY_DATA),"ptr");
   bptr= (MY_DATA* ) Malloc(SLENGTH*n*sizeof(MY_DATA),"bptr");
   rptr= (MY_DATA* ) Malloc(SLENGTH*n*sizeof(MY_DATA),"rptr");
   memset(ptr,0,SLENGTH*n*sizeof(MY_DATA));
   memset(bptr,0,SLENGTH*n*sizeof(MY_DATA));
   memset(rptr,0,SLENGTH*n*sizeof(MY_DATA));

   i=initialize(bptr,n);

   SET_PTR;
   PRINT_INP;
   GTYPESORT=gfunc[0];
   GTYPESORT(ptr,n,SLENGTH,compare);
   PRINT_OUTQ;


   for(i=0;(i<N_SORT_ALGS);i++) {
    if (doalg[i]==1) {
      GTYPESORT=gfunc[i];
      SET_PTR ; PRINT_INP;  TINIT;
        TSTART;
        rn=dsort((void *)ptr,n,splitters,rptr,(size_t)SLENGTH,GTYPESORT, compare,percent,alexg) ;
        TEND; 
        CHECKOUTPUT;
        printf("Improved=(%3d,%3d,%8d)=%10s T= %8.3f ",
               splitters,THRES16,n,labels[i],perrun);fflush(stdout); t1=perrun;
      PRINT_OUT;
      elapsed=(double)0;
 
      if (alexg >= 1) {
       SET_PTR; PRINT_INP2 ; TINIT;
       TSTART;
       GTYPESORT((void *)ptr,n,(size_t)SLENGTH,compare);
       TEND;
       CHECKOUTPUT2;
       printf("Original=(%3d,%3d,%8d)=%10s T= %6.3f",
               splitters,THRES16,n,labels[i],perrun);fflush(stdout); t2=perrun ;
       PRINT_OUT2;
      }
      if (t1 < t2) printf("<");
           else    printf(">") ;
      printf("\n");
    }
   }
 Free((void *) ptr,SLENGTH*n*sizeof(MY_DATA),"ptr");
 Free((void *)bptr,SLENGTH*n*sizeof(MY_DATA),"bptr");
 Free((void *)rptr,SLENGTH*n*sizeof(MY_DATA),"rptr");
 return(1);
}
