/****Copyright (c) 2002-2003  Alexandros V. Gerbessiotis.
 **** All rights reserved.
 ****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	<stdio.h>
#include	<stdlib.h>
#include        <time.h>
#include        <limits.h>
#include	"bsp.h"
#include	"mybsp.h"
#include         <math.h>
#define TEN 40
#define WRITE1   i=initialize(sum,size,testid,(unsigned int)range);
#define WRITE2   t2=bsp_time()
#define WRITE3   rsze=irand_sort_i((void *)sum,size,(int)r1,(int)r2,(char **)&sum3,(size_t)TEN,ITYPESORT,compare)
#define WRITE4   t3=bsp_time()
#define WRITE6   print_seq((void *)sum3,debug,rsze,"Out"); 
#define WRITE6a  print_seq((void *)sum, debug,rsze,"Out"); 
#define WRITE7   
#define WRITE8   (*ITYPESORT)((char *)sum,size,(size_t)TEN,compare)
#define WRITEX(Y)   for(k=0;k<rsze-1;k++) { if (compare((char*)&sum3[TEN*k],(char*)&sum3[TEN*(k+1)])>0) printf("error %s \n",#Y);}
#define WRITEY(Y)   for(k=0;k<rsze-1;k++) { if (compare((char*)&sum[TEN*k],(char*)&sum[TEN*(k+1)])>0) printf("error %s \n",#Y);}


#define MAX_RINT        ((unsigned int)2147483647)
#define LG(X)    (log((double)(X))/log(2.0))


extern int CLog2();
int irand_sort_i(int *, int , int , int , char **, int , 
void (*)(void *, int ,int, int (*)(const void *, const void *)), 
int (*)(const void *, const void *));

void check_if_null(void *x,char *s,char *t)
{
  if (NULL == x) {
     printf("%s::Malloc error (%s)\n",s,t);
     bsp_abort("check_if_null");
  }
}

int	initialize(char *d,int size,int testid,unsigned int range)
{
 register int 	gid,bid;
 register int 	i,j,temp,k,two;
 srandom(21+1001*0); 
 for(i=0;i<TEN*size;i++)
    d[i]= 32+ ((random()) % 64);
 return(0);
}


extern clock_t clock();

void  (*ITYPESORT)(void *,int ,int ,int (*w)(const void *,const void *));
void print_seq(void *sum,int option,int size,char *s);
void print_dbl(double *sum,int size,char *s);
void print_cha(char   *sum,int size,char *s);


int  compare(const void *left,const void *right)
{
/*
 return(*((int *)left) - *((int *)right));
*/
 return(memcmp(left,right,TEN));
}


/**** for any data type that can be compared with ">" (i.e. double,float) */
extern double          pow(double,double);
extern double          log(double);

int main (int argc, char  **argv)
{  
int 		size,runs,testid,rsze,range;
char  		*sum,*sum2,*sum3;
double 		t1,t2,t3,r1,r2,r3;
int 		i,j,k;
int		debug,sortalg;
int splitters;
clock_t		d1,d2;

   size = 100; runs=1; testid=0; range=0; sortalg=0; debug=0;splitters=0;
  if (argc == 1) {
   printf("rsort size splitters runs test oversampling sortalg debug\n");
   printf("size splitters(0) runs(1) test(0) oversample(0) sortalg(0) debug(F)\n");
   } else if (argc == 8) {
     size=atoi(argv[1]); splitters=atoi(argv[2]); runs=atoi(argv[3]);
     testid=atoi(argv[4]); range=atoi(argv[5]);sortalg=atoi(argv[6]);
     debug=atoi(argv[7]);
   }

 sum= (char *) malloc(TEN*size*sizeof(char));

  t1=0.0;
   for(i=0;i<argc;i++)
      printf("%s ",argv[i]);
   printf("\n");fflush(stdout);

  printf("n=%d (%d)\n",size,TEN);fflush(stdout);
  srandom(21+1001*0); 
  r1=r2=r3=0.0;
  r3= (double)size;
  if (splitters==0)
     /* before March 29
     r1= (double) ((((double)pow((double)size,0.5))/(log((double)size))));
     */
     /* Rho =1.0, gamma =1.0 , delta =1.0 delta is exponent of lgn  
        in oversample */
     r1= (double) (2.20*r3)/pow(LG(r3),2.5);
   else 
     r1=(double)splitters;

   if (r1 < 2.0) r1=2.0;

 if (range == 0)
    /* Before March 29
    r2= (double) (size/(r1* (log((double)size)) *(log((double)size) )));
    */
    r2= (double) (1.0*pow(LG(r3),1.0));
 else 
    r2= (double)range;

    printf("splitters = %d oversample = %d ns=%d \n",(int)r1,(int)r2,(int) (r1*r2-1));
/*
*/

   i=initialize(sum,size,testid,(unsigned int)range);
   print_seq((void *)sum,debug,size,"In ");fflush(stdout);

/*** 1: FIRST RUN *************************************************/
 WRITE1; ITYPESORT= (void (*) (void *, int,int,int (*)(const void *,const void*)) ) qsort;
 WRITE2; WRITE3; WRITE4;
 WRITEX("qsort-imp");
 printf("iqs %6.2f:",(t3-t2));
 WRITE6;WRITE7;
 /******* *****/
 if ((testid ==0) || (size < 100000000)){
 WRITE1; WRITE2;WRITE8;WRITE4; rsze=size;
 WRITEY("qsort");
 printf("qs %6.2f:",(t3-t2));
 WRITE6a;
 } else {
    printf("qs %6.2f:",0.00);
 }

/*** 1: SECOND RUN **************************************************/
 WRITE1; ITYPESORT= (void (*) (void *, int,int,int (*)(const void *,const void*)) ) Merge;
 WRITE2;WRITE3;WRITE4;
 WRITEX("merge-imp");
 printf("ims %6.2f:",(t3-t2));
 WRITE6;WRITE7;
 /******* *****/
 WRITE1; WRITE2;WRITE8;WRITE4;rsze=size;
 WRITEY("merge");
 printf("ms %6.2f:",(t3-t2));
 WRITE6a;
 /**********************************/
 WRITE1; ITYPESORT= (void (*) (void *, int,int,int (*)(const void *,const void*)) ) sort_q;
 WRITE2;WRITE3;WRITE4;
 WRITEX("myq-imp");
 printf("imq %6.2f:",(t3-t2));
 WRITE6;WRITE7;

 /******* *****/
 if ((testid ==0) || (size < 10000000)) {
 WRITE1; WRITE2;WRITE8;WRITE4;rsze=size;
 WRITEY("myq");
 printf("mq %6.2f:",(t3-t2));
 WRITE6a;
 } else
 printf("mq %6.2f ",0.0);
/*** 1: THIRD RUN *****************************************/
 WRITE1; ITYPESORT= (void (*) (void *, int,int,int (*)(const void *,const void*)) ) heap;
 WRITE2;WRITE3;WRITE4;
 WRITEX("heap-imp");
 printf("ihs %6.2f:",(t3-t2));
 WRITE6;WRITE7;

 /******* *****/
 WRITE1; WRITE2;WRITE8;WRITE4;rsze=size;
 WRITEY("heap");
 printf("hs %6.2f ",(t3-t2));
 WRITE6a;

 WRITE1; ITYPESORT= (void (*) (void *, int,int,int (*)(const void *,const void*)) ) sort_ins;
 WRITE2;WRITE3;WRITE4;
 WRITEX("soin-imp");
 printf("iis %6.2f\n",(t3-t2));
 WRITE6;WRITE7;

 /******* *****/
if (size< 65536) {
 WRITE1; WRITE2;WRITE8;WRITE4;rsze=size;
 WRITEY("inss");
 printf("is %6.2f ",(t3-t2));
 WRITE6a;
}

 printf("\n");

 /******* *****/


 free((void*)sum);


}

void print_seq(void *sum,int option,int size,char *s)
{
 if (option ==1) print_cha((char *)sum, size,s);
}

void print_cha(char *sum,int size,char *s)
{
 int i,j;
   printf("%3d %s:\n",size,s);
 for(i=0;i<5;i++){
   printf("%3d %3d %3d %3d %3d %3d %3d %3d %3d %3d\n",
         (unsigned int) sum[i*TEN],
         (unsigned int) sum[i*TEN+1],
         (unsigned int) sum[i*TEN+2],
         (unsigned int) sum[i*TEN+3],
         (unsigned int) sum[i*TEN+4],
         (unsigned int) sum[i*TEN+5],
         (unsigned int) sum[i*TEN+6],
         (unsigned int) sum[i*TEN+7],
         (unsigned int) sum[i*TEN+8],
         (unsigned int) sum[i*TEN+9]);
 }
   printf("...\n");
 for(i=size-5;i<size;i++){
   printf("%3d %3d %3d %3d %3d %3d %3d %3d %3d %3d\n",
        (unsigned int) sum[i*TEN],
       (unsigned int) sum[i*TEN+1],
         (unsigned int) sum[i*TEN+2],
         (unsigned int) sum[i*TEN+3],
         (unsigned int) sum[i*TEN+4],
         (unsigned int) sum[i*TEN+5],
         (unsigned int) sum[i*TEN+6],
         (unsigned int) sum[i*TEN+7],
         (unsigned int) sum[i*TEN+8],
         (unsigned int) sum[i*TEN+9]);
 }
 
}

void print_dbl(double *sum,int size,char *s)
{
 printf("%3sP[%d]:%8.1f,%8.1f,%8.1f,",s,size,sum[0],sum[1],sum[2]);
 printf("...,%8.1f,%8.1f,%8.1f\n", sum[size-3],sum[size-2],sum[size-1]);
}
