/****Copyright (c) 1997-2009 All rights reserved
 ****A. V. Gerbessiotis and C. J. Siniolakis
 ****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"

void A51wbh(void *akeys, int   n,int size,int (*compare)(const void*,const void*))
{
 char *split,*tmp,*keys;
 register int l,r,M;
 char *DES,*SRC;

 if (n <= 1) return;
 keys= (char *) akeys;
 tmp = (char *) malloc(size*sizeof(char));
 split=(char *) malloc(size*sizeof(char));
#ifdef SANITY_CHECK
  check_if_null(tmp,"g51wbh","tmp");
  check_if_null(split  ,"g51wbh","split  ");
#endif
 l=0;r=n-1;
#if SPLITTER == MIDDLE_KEY
 memcpy(split,&keys[((l+r)>>1)*size],size);
#elif SPLITTER == FIRST_KEY
 memcpy(split,&keys[l*size],size);
#elif SPLITTER == RANDOM_KEY
 memcpy(split,&keys[(l+GRANDOM((r-l+1)))*size],size);
#endif

 while (l <= r) {
   while (compare(&keys[l*size],split)<0) l++;
   while (compare(split,&keys[r*size])<0) r--;
   if (l <= r) {
     MEMCPY(tmp,&keys[l*size],size);
     MEMCPY(&keys[l*size],&keys[r*size],size);
     MEMCPY(&keys[r*size],tmp,size);
     l++;r--;
   }
 }
  
 if (r>0) {
      if ((r+1)<THRES16) BASES (keys,r+1,size,compare) ;
      else A51wbh(keys,r+1,size,compare) ;
  }
  if (l < n) {
      if ((n-l)<THRES16) BASES (&keys[l*size],n-l,size,compare) ;
      else A51wbh(&keys[l*size],n-l,size,compare) ;
  }
 free((void *)split); free((void *)tmp);
}
           
void g51wbh(void *keys,int n,int size,int (*compare) (const void*,const void *))
{
  if (n <= 1) return ;
#if SPLITTER == RANDOM_KEY
 GSRANDOM();
#endif
  A51wbh(keys,n,size,compare);
}

