/****Copyright (c) 1997-2009 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 g35s(void *akeys,int n,int size,int (*compare)(const void*,const void*),int l,int r)
{
  register int i,j,M;
  char	*tmp,*keys,*SRC,*DES;

  if ((n<=1) ||(size<=0)) return;
  keys=(char *)akeys;
  tmp=(char *)malloc(size*sizeof(char));
#ifdef SANITY_CHECK
 check_if_null(tmp,"g35heaptmp","tmp");
#endif
  i=l;j=2*i;
  MEMCPY(tmp,&keys[(i-1)*size],size);

  while(j<=r){
    if (j<r){
      if (compare(&keys[(j-1)*size],&keys[(j)*size])<0) {
	j++;
       }
    }
    if (compare(tmp,&keys[(j-1)*size])>=0) break;

     MEMCPY(&keys[(i-1)*size],&keys[(j-1)*size],size);
     i=j;j=2*i;
   }
   MEMCPY(&keys[(i-1)*size],tmp,size);
  free((void*)tmp);
}
	

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

  keys=(char*)akeys;
  l=n/2+1;r=n;
  tmp=(char *)malloc(size*sizeof(char));

  while(l>1) {
    l--;
    g35s(keys,n,size,compare,l,r);
  }
  while (r > 1) {
    MEMCPY(tmp,keys,size);
    MEMCPY(keys,&keys[(r-1)*size],size);
    MEMCPY(&keys[(r-1)*size],tmp,size);
    r--;
    g35s(keys,n,size,compare,l,r);
  }

/*
	for(l=0;l<n/2;l++)
	{
		MEMCPY(tmp,&keys[l*size],size);
		MEMCPY(&keys[l*size],&keys[(n-l-1)*size],size);
		MEMCPY(&keys[(n-l-1)*size],tmp,size);
	}
*/
 free((void*)tmp);
}
