#ifdef MYDEBUG
#include 	<stdio.h>
#include 	<stdlib.h>
#include        <limits.h>
#include 	<string.h>
#endif
#include <math.h>
#include "ssrt.h"
#include "sids.h"
#include "../avgmain.h"
#define   TWO31 ((unsigned int)1<<31)

#define CHARD char
#define INLINE_BSEARCH

double log(double);
#undef  MEMCPY
#define MEMCPY(XX,YY,SS) {DES=(XX);SRC=(YY);M=(SS); do {*DES++=*SRC++;} while (--M); }

#undef Malloc
#define Malloc(x,y)    malloc((x))
#undef Free
#define Free(x,y,z)  free((void*)(x))



























int dsort
  (void  *akeys,
   int n,
   int splitters,
   char *tempres,
   int nbytes,
   void (*GENSORT)(void *, int , int , int (*)(const void*,const void*)),
   int  (*compare)(const void *,const void*),
   int  percent,
   int  alexg
  )
{
  register int  oversample, size,sktotal,ksperbuck;
  register int  i,j,k,l,s,left,right;
  register int  boundary,bl,br,boff;
  register int *bucket, *buck,*lbuck;

  register CHARD *sample;
  register CHARD *split,*sp;
  register CHARD *keys, *kp;

  register int LL,RR,MM,RES;
  register char *SRC,*DES,*PP;
  register int M=0;
  register int           NBUCKETS;
  
  register CHARD *SRC1,*SRC2,*FIRST1,*FIRST2,*LAST1,*LAST2,*TEMP,*TMP;
  register int M1,M2;
  register int index;     /* aux variables in random sampling*/

  keys = (char *) akeys;
  NBUCKETS=splitters+1;

  /**** PART 1: Initializations */
  srandom(21+1001*11);
  oversample=(int) ceil(((percent/100.0)*pow(log((double)n),(1.0+alexg/100.0)))+1.0); 
  sktotal   =oversample*NBUCKETS-1;/* sample size */
  ksperbuck = n/NBUCKETS;
  size= ksperbuck*nbytes;   /* bucket size in bytes */
/*
printf("n= %d split=%d ,oversa = %f bsam=%d ns=%d\n",n,splitters,oversample,
      bsample,ns);
printf("nos=%d snos=%d\n",nos,snos);fflush(stdout);
*/

  if ((splitters <1) || (sktotal > n)){
    MEMCPY(tempres,keys,n*nbytes);
    (*GENSORT)((void *)tempres,n,nbytes,compare);
    return(n);
  }

  sample = (char *) Malloc(sktotal*nbytes,"sample");        /* Sample data storage */
  split  = (char *) Malloc(splitters*nbytes,"split"); /* splitter storage */
  bucket = (int *)  Malloc(NBUCKETS*sizeof(int ),"bucket"); /* bucket size */
  buck   = (int *)  Malloc((NBUCKETS*NBUCKETS)*sizeof(int ),"buck"); /* bucket size */
  lbuck  = (int *)  Malloc((NBUCKETS*NBUCKETS)*sizeof(int ),"lbuck"); /* auxiliary variable */

  /**** PART 2: Sort buckets/subsequnces*/
   for(i=0,j=0;i<splitters;i++,j+=size){
    (*GENSORT)((void *)(keys+j),ksperbuck,nbytes,compare);
   }
   (*GENSORT)((void *)(keys+size*splitters),(n-ksperbuck*splitters),nbytes,compare);

/* Example: Say n= 11 S=ns/splitters =3
   o  o  o  o  o  o  o  o  o  o  o
            ^           ^        ^
   splitter 1           2        3 maximum
   CEIL(...) =4 FLOOR(...) =3 i.e. interspace is
              3             2  respectively
 */

 /**** PART 3: Collect sample */
  for(i=0;i<sktotal;i++) {
   index = random() % n;
   MEMCPY((sample+i*nbytes),(keys+index*nbytes),nbytes);
  }

/*
  TMP=(char *) Malloc(n*nbytes,"TMP");
*/
  TMP=(char *) keys;

 /**** PART 4: Sort sample */
  (*GENSORT)((void *)sample,sktotal,nbytes,compare);

 /**** PART 5: Select splitters */
  for(i=0;i<splitters;i++) {
    MEMCPY((split+i*nbytes),(sample+((i+1)*oversample-1)*nbytes),nbytes);
    bucket[i]=0;
  }

  /*** PART 6: Binary search splitters into keys */
  for(k=0,kp=keys;k<=splitters;k++,kp+=size) {
    l=((k<splitters)?ksperbuck:(n-ksperbuck*splitters));
    sp=split+(splitters-1)*nbytes;
    for(i=splitters-1,bucket[splitters]=l; i>=0;i--,sp-=nbytes) {
#ifdef INLINE_BSEARCH
      LL=0; RR=l-1; MM=RR/2 ;PP=kp;
      while (LL<=RR) {
        RES=  compare((PP+MM*nbytes),sp);
        if (RES < 0) LL=MM+1;
          else       RR=MM-1;
        MM=(LL+RR)/2 ;
      }
      bucket[i]=LL;
#else
/*
      bucket[i] = searchbin( (char *)&split[i*nbytes],&keys[j*nbytes],
                             lsize,compare,nbytes);
*/
      bucket[i] = searchbin( sp,kp,l,compare,nbytes);
#endif
      bucket[i+1] -= bucket[i];
      lbuck[(i+1)*NBUCKETS+k]=buck[(i+1)*NBUCKETS+k]=bucket[i+1];
    } 
    lbuck[k]=buck[k] = bucket[0];
  }

  /* Based on binary search decide size of buckets */
for(i=0;i<NBUCKETS;i++) {
    lbuck[i*NBUCKETS]=0;
  }
  for(i=0;i<NBUCKETS;i++) {
    for(l=1;l<NBUCKETS;l++) {
      lbuck[i*NBUCKETS+l] = lbuck[i*NBUCKETS+l-1] + buck[i*NBUCKETS+l-1];
      bucket[i] += buck[i*NBUCKETS+l];
    }
      bucket[i] += buck[i*NBUCKETS+0];
  }
  for(i=0;i<=splitters;i++) {
    bucket[i] = lbuck[i*NBUCKETS+splitters]+buck[i*NBUCKETS+splitters];
  }
  s=bucket[0];bucket[0]=0;  /* Compute base addresses for each bucket */
  for(i=1;i<=splitters;i++) {
    l=bucket[i];
    bucket[i] = bucket[i-1]+s;
    s=l;
  }
  /* Update lbuck by adding base address (bucket) to the  i-th column */
 for(i=0;i<NBUCKETS;i++) {
   for(l=0;l<NBUCKETS;l++) {
      lbuck[i*NBUCKETS+l] +=  bucket[i];
    }
  }

  /**** PART 7:  Rearrange keys based on splitters */
  for(l=0;l<=splitters;l++) {
    s=((l<splitters)?ksperbuck:(n-ksperbuck*splitters));
    j=s*l;
    for(i=0;i<=splitters;i++) {
      MEMCPY((tempres+lbuck[i*NBUCKETS+l]*nbytes),(keys+j*nbytes),(buck[i*NBUCKETS+l]*nbytes));
      j += buck[i*NBUCKETS+l];
    }
       
  }


  /**** PART 8: Merge sorted sequences */
/*
if (alexg ==1) {
*/
  for(l=0;l<NBUCKETS;l++) {
    for(i=1,k=2;i<NBUCKETS;i=(i<<1),k=(k<<1)) {
      for(left=0,right=i;((left< NBUCKETS)&&(right<NBUCKETS));left+=k,right+=k){    /* BUG1234 */
        /* left     is index of left  sequence to be Merged */
        /* right    is index of right sequence to be Merged */
        boff      = bucket[l]*nbytes;
        boundary  = MIN((right+i),(NBUCKETS));                                /* BUG1234 */
        bl        = lbuck[l*NBUCKETS+left];
        br        = lbuck[l*NBUCKETS+right];
        s         = lbuck[l*NBUCKETS+boundary];
        if (boundary == (NBUCKETS))                                       /* BUG1234*/
          s = ((l<splitters)?(bucket[l+1]):(n));
/*
        merge2((char *)&tempres[offset+lsize*nbytes],
               (char *)&tempres[offset+rsize*nbytes],
               rsize-lsize,
               nsize-rsize,
               nbytes,
               compare
             );
*/ 
         SRC1= tempres+bl*nbytes;
	 SRC2= tempres+br*nbytes;
	 M1=br-bl;
	 M2= s-br;
 FIRST1=SRC1;FIRST2=SRC2;
 LAST1 =SRC1+M1*nbytes;
 LAST2 =SRC2+M2*nbytes;
 TEMP=TMP;

 for (;((FIRST1 != LAST1) && (FIRST2 != LAST2));TEMP+=nbytes)
    if (compare(FIRST2,FIRST1)<0){
      MEMCPY(TEMP,FIRST2,nbytes);
      FIRST2+=nbytes;
    }
    else {
      MEMCPY(TEMP,FIRST1,nbytes);
      FIRST1+=nbytes;
    }
 if ( FIRST1 != LAST1)
   MEMCPY(TEMP,FIRST1,(LAST1-FIRST1));
 if ( FIRST2 != LAST2)
   MEMCPY(TEMP,FIRST2,(LAST2-FIRST2));

  MEMCPY(SRC1,TMP,M1*nbytes);
  MEMCPY(SRC2,&TMP[M1*nbytes],M2*nbytes);
     }
   }
 }
/*
 Free((void *)TMP,n*nbytes,"TMP");
*/


  /**** PART 9: EXIT and FREE SPACE BELOW ***/
  Free((void *) lbuck,NBUCKETS*NBUCKETS*sizeof(int),"lbuck");
  Free((void *) buck,NBUCKETS*NBUCKETS*sizeof(int),"buck");
  Free((void *) bucket,NBUCKETS*sizeof(int),"bucket");
  Free((void *) split,splitters*nbytes,"split");
  Free((void *) sample,sktotal*nbytes,"sample");
 
/*
  MEMCPY(keys,tempres,n*nbytes);
  free((void *) tempres);
*/
return(n);

}

