/*
	hsort -- sort a list using an heap sort algorithm

	Performance is guaranteed O(NlogN).  Compared to BSD UNIX(TM) qsort,
	hsort averages about half as fast--which may be acceptable
	for a portable, public domain function, which qsort is not.

	This code was derived from an original work by Dr. Webb Miller
	(Penn State University), but don't blame him for this mess or any errors.

	7/31/90 WRG
*/
#include "ncbi.h"
#include "gishlib.h"

static void	heapify PROTO((Nlm_CharPtr b0, Nlm_CharPtr b, Nlm_CharPtr lim, Nlm_CharPtr last, size_t w, int (_cdecl *compar)(Nlm_VoidPtr, Nlm_VoidPtr) ));

static void	heapify1 PROTO((Nlm_CharPtr b0, Nlm_CharPtr b, Nlm_CharPtr lim, Nlm_CharPtr last, size_t w, int (_cdecl *compar)(Nlm_VoidPtr, Nlm_VoidPtr, Nlm_VoidPtr), Nlm_VoidPtr onearg));


void _cdecl
hsort(basearg, nel, width, compar)
	register VoidPtr	basearg;	/* Base address of array */
	size_t	nel;				/* No. of elements in array */
	size_t	width;				/* Width in bytes of each element in array */
	/* Element comparison routine */
	int	(_cdecl *compar) PROTO((Nlm_VoidPtr, Nlm_VoidPtr));
{
	register size_t	i;
	register char	ch;
	register CharPtr	base = (CharPtr)basearg;
	register CharPtr 	base0 = (CharPtr)basearg, lim, basef;

	if (nel < 2)
		return;

	lim = base0 + ((nel-2)/2)*width;
	basef = base0 + (nel-1)*width;
	for (base = &base0[(nel/2 - 1)*width]; base >= base0; base -= width)
		heapify(base0, base, lim, basef, width, compar);

	for (base = &base0[(nel-1)*width]; base > base0; base -= width) {
		for (i=0; i<width; ++i) {
			ch = base0[i];
			base0[i] = base[i];
			base[i] = ch;
		}
		lim = base0 + ((base-base0)/2 - width);
		if (base > base0+width)
			heapify(base0, base0, lim, base-width, width, compar);
	}
}

static void
heapify(base0, base, lim, last, width, compar)
	register CharPtr	base0, base, lim, last;
	register size_t	width;
	register int	(_cdecl *compar) PROTO((Nlm_VoidPtr,Nlm_VoidPtr));
{
	register size_t	i;
	register char	ch;
	register CharPtr left_son, large_son;

	left_son = base0 + 2*(base-base0) + width;
	while (base <= lim) {
		if (left_son == last)
			large_son = left_son;
		else
			large_son = (*compar)((VoidPtr)left_son, (VoidPtr)(left_son+width)) >= 0 ?
							left_son : left_son+width;
		if ((*compar)((VoidPtr)base, (VoidPtr)large_son) < 0) {
			for (i=0; i<width; ++i) {
				ch = base[i];
				base[i] = large_son[i];
				large_son[i] = ch;
			}
			base = large_son;
			left_son = base0 + 2*(base-base0) + width;
		} else
			break;
	}
}

void _cdecl
hsort1(basearg, nel, width, compar, onearg)
	register VoidPtr	basearg;	/* Base address of array */
	size_t	nel;				/* No. of elements in array */
	size_t	width;				/* Width in bytes of each element in array */
	/* Element comparison routine */
	int	(_cdecl *compar) PROTO((Nlm_VoidPtr, Nlm_VoidPtr, Nlm_VoidPtr));
	Nlm_VoidPtr	onearg;
{
	register size_t	i;
	register char	ch;
	register CharPtr	base = (CharPtr)basearg;
	register CharPtr 	base0 = (CharPtr)basearg, lim, basef;

	if (nel < 2)
		return;

	lim = base0 + ((nel-2)/2)*width;
	basef = base0 + (nel-1)*width;
	for (base = &base0[(nel/2 - 1)*width]; base >= base0; base -= width)
		heapify1(base0, base, lim, basef, width, compar, onearg);

	for (base = &base0[(nel-1)*width]; base > base0; base -= width) {
		for (i=0; i<width; ++i) {
			ch = base0[i];
			base0[i] = base[i];
			base[i] = ch;
		}
		lim = base0 + ((base-base0)/2 - width);
		if (base > base0+width)
			heapify1(base0, base0, lim, base-width, width, compar, onearg);
	}
}

static void
heapify1(base0, base, lim, last, width, compar, onearg)
	register CharPtr	base0, base, lim, last;
	register size_t	width;
	register int	(_cdecl *compar) PROTO((Nlm_VoidPtr,Nlm_VoidPtr,Nlm_VoidPtr));
	Nlm_VoidPtr	onearg;
{
	register size_t	i;
	register char	ch;
	register CharPtr left_son, large_son;

	left_son = base0 + 2*(base-base0) + width;
	while (base <= lim) {
		if (left_son == last)
			large_son = left_son;
		else
			large_son = (*compar)((VoidPtr)left_son, (VoidPtr)(left_son+width), onearg) >= 0 ?
							left_son : left_son+width;
		if ((*compar)((VoidPtr)base, (VoidPtr)large_son, onearg) < 0) {
			for (i=0; i<width; ++i) {
				ch = base[i];
				base[i] = large_son[i];
				large_son[i] = ch;
			}
			base = large_son;
			left_son = base0 + 2*(base-base0) + width;
		} else
			break;
	}
}