/****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 	<math.h>
#include        <limits.h>
#include 	<string.h>
#include	"bsp.h"
#include	"mybsp.h"
#define   TWO31 ((unsigned int)1<<31)

#undef ALEX
#define ALEX
#define SUN
#undef SUN

void print_int();


int irand_sort_i
  (char  *keys,
   int n,
   int splitters,
   int oversample,
   char **result,
   int nbytes,
   void (*gTYPESORT)(void *, int , int , int (*)(const void*,const void*)),
   int  (*compare)(const void *,const void*)
  )
{
  register int ns;         /* sample size */
  char           *sample;  /* key sample array */
  char           *split;   /* splitter array */
  int		*bucket;   /* local bucket size */
  int		*buck;   /* local bucket size */
  int		*lbucket;  /* auxiliary local */
  int           *destin;
  char 	        *temp_keys;
  char 		*out;
  register int 	index;     /* aux variables in random sampling*/
  register int	compare_res;  /* comparison result */
  register int	i,j;       /* index variables */
  register int 	left,right,middle;/* binary search variables */

  /**** PART 1: Initializations */
  ns= splitters*oversample-1;
  srandom(23+1001*11); 
  sample = (char *) malloc(ns*nbytes);     /* Sample data storage */
  split  = (char *) malloc(splitters*nbytes); /* splitter storage */
  temp_keys =(char *)malloc(n*nbytes);/* key bucket index */
  bucket = (int *) malloc(splitters*sizeof(int)); /* bucket size */
  buck =   (int *) malloc(splitters*sizeof(int)); /* bucket size */
  lbucket = (int *)malloc(splitters*sizeof(int)); /* auxiliary variable */
  destin= (int *)malloc(n*sizeof(int)); /* auxiliary variable */

  /**** PART 5: Sampling*/

   for(i=0;i<ns;i++) {
#ifdef SUN
   index =(int) (n * (random()/((double)INT_MAX)));
#else
   index = (int) (drand48()*(double)n);
   index =(int) (n * (random()/((double)INT_MAX)));
#endif
      memcpy(&sample[i*nbytes],&keys[index*nbytes],nbytes);
   }

/*
   qsort((char *)sample,ns,nbytes,compare);
*/
   (*gTYPESORT)((char *)sample,ns,nbytes,compare);

   for(i=0;i<splitters-1;i++) {
      memcpy(&split[i*nbytes],&sample[(i+1)*oversample*nbytes],nbytes);
      bucket[i]=0;
   }
      bucket[splitters-1]=0;

  for(i=0;i<n;i++) {
     left=0; 
     right=splitters-2; 
     middle=(left+right)>>1;
     while (left <= right) { 
       compare_res = compare(&keys[i*nbytes],&split[middle*nbytes]);
       if (compare_res > 0) {
          left=middle+1;
        } else {
          right =middle-1;
        }
        middle=(left+right)>>1;
     }
     destin[i]=left;
     bucket[left]++;
   }
   out = (char *) malloc(n*nbytes);
   lbucket[0]=0;
   buck[0]=bucket[0]-1;
   for(i=1;i<splitters;i++) {
      lbucket[i] =lbucket[i-1]+bucket[i-1]; 
      buck[i]= buck[i-1]+bucket[i];
   }
   for(i=n-1;i>=0;--i){
     memcpy(&out[(buck[destin[i]])*nbytes],&keys[i*nbytes],nbytes);
     --buck[destin[i]];
   }

   memcpy(keys,out,nbytes*n);
   free((void *)out);

   for(i=0;i<splitters;i++) {
         (*gTYPESORT)(&keys[lbucket[i]*nbytes],bucket[i],nbytes,compare);
   }

   *result = (char *) keys;
free((void *) lbucket);
free((void *) buck);
free((void *) bucket);
free((void *) split);
free((void *) sample);
   return(n);

}
