/****Copyright (c) 1997-2009 All rights reserved
 ****  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"
#define  Parent(i)   ((i-1)>>1)
#define  Left(i)     ((i<<1)+1)
#define  Right(i)    ((i<<1)+2)


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

  l = Left(i);
  r = Right(i);

  if ((l<n) && (compare(&akeys[l*size],&akeys[i*size])>0))
    t=l;
  else 
    t=i;
  if ((r<n) && (compare(&akeys[r*size], &akeys[t*size])>0))
    t=r;
  if (t!=i) {
    MEMCPY(tmp,&akeys[i*size],size);
    MEMCPY(&akeys[i*size],&akeys[t*size],size);
    MEMCPY(&akeys[t*size],tmp,size);
    Heapify(akeys,n,t,tmp,size,compare);
  }
}

void Build_Heap (char *akeys,int n,int size,int (*compare)(const void *,const void*))
{
  char *tmp;
  register int i;

  tmp=(char*)malloc(size*sizeof(char));
  for(i=n-1;i>=0;i--) {
      Heapify(akeys,n,i,tmp,size,compare);
  }
  free((void*)tmp);
}

void g34heapx(void *akeys,int n,int size,int (*compare) (const void*,const void*))
{
 char	*x,*keys,*SRC,*DES;
 register int i,M;

 keys=(char *)akeys;
 x=(char *) malloc(size*sizeof(char));
 Build_Heap(keys,n,size,compare);
 for (i = n-1;i>=1;--i){
      MEMCPY(x,keys,size);
      MEMCPY(keys,&keys[i*size],size);
      MEMCPY(&keys[i*size],x,size);
      Heapify(keys,i,0,x,size,compare);
  }
  free((void*)x);
}
