/****Copyright (c) 1997-2005 All rights reserved
 ****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"

void g07shake(void *akeys,int n,int size,int (*compare) (const void*,const void*))
{
  register int j,k,l,r;
  char	*tmp,*keys;

  if (n<=1) return;
  keys = (char *) akeys;
  tmp = (char *) malloc(size*sizeof(char));
#ifdef SANITY_CHECK
  check_if_null(tmp,"g07shake","tmp");
#endif
  l=1;r=n-1;k=n-1;
  do {
    for(j=r;j>=l;j--) {
      if (compare(&keys[(j-1)*size],&keys[j*size]) > 0) {
        MEMCPY(tmp,&keys[(j-1)*size],size);
        MEMCPY(&keys[(j-1)*size],&keys[j*size],size);
        MEMCPY(&keys[j*size],tmp,size);
        k=j;
      }
    }
    l=k+1;
    for(j=l;j<=r;j++) {
      if (compare(&keys[(j-1)*size],&keys[j*size]) > 0) {
        MEMCPY(tmp,&keys[(j-1)*size],size);
        MEMCPY(&keys[(j-1)*size],&keys[j*size],size);
        MEMCPY(&keys[j*size],tmp,size);
        k=j;
      }
    }
    r=k-1;
  } while (l <= r);
 free((void*)tmp);
}
