#include <ncbi.h>
#include <gishlib.h>

#ifdef LINK_PNTR
#undef LINK_PNTR
#endif
#define LINK_PNTR(item,offset) (*(VoidPtr PNTR)((CharPtr)item + offset))

#define NSTACK_ITEMS	200

/* LinkCount -- return the count of items in a linked list */
size_t LIBCALL
LinkCount(lp, nextoff)
	register VoidPtr	lp;
	register size_t	nextoff;
{
	register size_t	n = 0;

	while (lp != NULL) {
		++n;
		lp = LINK_PNTR(lp, nextoff);
	}
	return n;
}


/* LinkPreviousCreate -- instantiate the 'previous' fields in a linked list */
void LIBCALL
LinkPreviousCreate(lp, nextoff, prevoff)
	VoidPtr	lp; /* linked list, with the "next" items set properly */
	size_t	nextoff;
	size_t	prevoff;
{
	register VoidPtr	lp0; /* item pointer */

	/* Install backward links */
	lp0 = NULL;
	while (lp != NULL) {
		LINK_PNTR(lp, prevoff) = lp0;
		lp0 = lp;
		lp = LINK_PNTR(lp, nextoff);
	}
	return;
}

int LIBCALL
LinkSort(lpp, nextoff, cmpfunc)
	VoidPtr	PNTR lpp; /* the linked list of items to be sorted */
	size_t	nextoff; /* offset of "next" element in structure */
	int		(LIBCALLBACK *cmpfunc)(); /* item comparison function */
{
	VoidPtr	vpstack[NSTACK_ITEMS]; /* short list storage to avoid some malloc-ing */
	VoidPtr	PNTR vpp0;
	size_t	nitems; /* number of items in list */
	register VoidPtr	PNTR vpp, PNTR vpp2;
	register VoidPtr	PNTR vppmax;

	nitems = LinkCount(*lpp, nextoff);
	if (nitems < 2)
		return 0;

	if (nitems <= DIM(vpstack))
		vpp0 = vpstack;
	else {
		vpp0 = (VoidPtr PNTR)mem_malloc(sizeof(VoidPtr) * nitems);
		if (vpp0 == NULL)
			return 1;
	}

	/* Linearize the list */
	vppmax = vpp0 + (nitems-1);
	for (vpp = vpp0, *vpp = *lpp; vpp < vppmax; vpp = vpp2) {
		vpp2 = vpp + 1;
		*vpp2 = LINK_PNTR(*vpp, nextoff);
	}

	HeapSort((VoidPtr)vpp0, nitems, sizeof(VoidPtr), cmpfunc);

	/* Linkize the list */
	for (vpp = vpp0; vpp < vppmax; vpp = vpp2) {
		vpp2 = vpp + 1;
		LINK_PNTR(*vpp, nextoff) = *vpp2;
	}
	LINK_PNTR(*vpp, nextoff) = NULL;

	*lpp = *vpp0;
	if (vpp0 != vpstack)
		Nlm_Free(vpp0);
	return 0;
}

int LIBCALL
LinkSort1(lpp, nextoff, cmpfunc, onearg)
	VoidPtr	PNTR lpp; /* the linked list of items to be sorted */
	size_t	nextoff; /* offset of "next" element in structure */
	int		(LIBCALLBACK *cmpfunc)(); /* item comparison function */
	VoidPtr	onearg;
{
	VoidPtr	vpstack[NSTACK_ITEMS]; /* short list storage to avoid some malloc-ing */
	VoidPtr	PNTR vpp0;
	size_t	nitems; /* number of items in list */
	register VoidPtr	PNTR vpp, PNTR vpp2;
	register VoidPtr	PNTR vppmax;

	nitems = LinkCount(*lpp, nextoff);
	if (nitems < 2)
		return 0;

	if (nitems <= DIM(vpstack))
		vpp0 = vpstack;
	else {
		vpp0 = (VoidPtr PNTR)mem_malloc(sizeof(VoidPtr) * nitems);
		if (vpp0 == NULL)
			return 1;
	}

	/* Linearize the list */
	vppmax = vpp0 + (nitems-1);
	for (vpp = vpp0, *vpp = *lpp; vpp < vppmax; vpp = vpp2) {
		vpp2 = vpp + 1;
		*vpp2 = LINK_PNTR(*vpp, nextoff);
	}

	hsort1((VoidPtr)vpp0, nitems, sizeof(VoidPtr), cmpfunc, onearg);

	/* Linkize the list */
	for (vpp = vpp0; vpp < vppmax; vpp = vpp2) {
		vpp2 = vpp + 1;
		LINK_PNTR(*vpp, nextoff) = *vpp2;
	}
	LINK_PNTR(*vpp, nextoff) = NULL;

	*lpp = *vpp0;
	if (vpp0 != vpstack)
		Nlm_Free(vpp0);
	return 0;
}

int LIBCALL
DblLinkSort(lpp, nextoff, prevoff, cmpfunc)
	VoidPtr	PNTR lpp; /* the linked list of items to be sorted */
	size_t	nextoff; /* offset of "next" element in structure */
	size_t	prevoff; /* offset of "previous" element in structure (or -1) */
	int		(LIBCALLBACK *cmpfunc)(); /* item comparison function */
{
	int		rc;

	rc = LinkSort(lpp, nextoff, cmpfunc);
	if (rc != 0)
		return rc;

	LinkPreviousCreate(*lpp, nextoff, prevoff);

	return 0;
}

int LIBCALL
LinkApply(lp, nextoff, func)
	VoidPtr	lp;
	size_t	nextoff;
	int		(LIBCALLBACK *func)();
{
	while (lp != NULL) {
		if (func(lp))
			return 1;
		lp = LINK_PNTR(lp, nextoff);
	}
	return 0;
}

int LIBCALL
LinkApplyData(lp, nextoff, func, data)
	VoidPtr	lp;
	size_t	nextoff;
	int		(LIBCALLBACK *func)();
	VoidPtr	data;
{
	while (lp != NULL) {
		if (func(lp, data))
			return 1;
		lp = LINK_PNTR(lp, nextoff);
	}
	return 0;
}


#if 0
int LIBCALL
LinkSortInPlace(lp, nextoff, size, cmpfunc)
	VoidPtr	lp; /* the linked list of items to be sorted */
	size_t	nextoff; /* offset of "next" element in structure */
	size_t	size; /* full size of the structure */
	int		(*cmpfunc)(); /* item comparison function */
{
	VoidPtr	vpstack[400]; /* short list storage to avoid some malloc-ing */
	char	istack[128];
	VoidPtr	itemp;
	VoidPtr	PNTR vpp0, PNTR wpp0;
	size_t	nitems; /* number of items in list */
	register VoidPtr	PNTR vpp, PNTR vpp2;
	register VoidPtr	PNTR vppmax;
	register VoidPtr	PNTR wpp, PNTR wpp2;
	register VoidPtr	PNTR wppmax;
	int	retcode = 1;

	nitems = LinkCount(lp, nextoff);
	if (nitems < 2)
		return 0;

	if (nitems <= DIM(vpstack)/2)
		vpp0 = vpstack, wpp0 = vpp0 + nitems;
	else {
		vpp0 = (VoidPtr PNTR)mem_malloc(sizeof(*vpp0) * 2 * nitems);
		if (vpp0 == NULL)
			return retcode;
		wpp0 = vpp0 + nitems;
	}

	if (size < sizeof(istack)) {
		itemp = mem_malloc(size);
		if (itemp == NULL)
			goto Exit;
	}

	/* Linearize the list */
	vppmax = vpp0 + (nitems-1);
	wppmax = wpp0 + (nitems-1);
	for (vpp = vpp0, *vpp = lp, wpp = wpp0; vpp < vppmax; vpp = vpp2) {
		*wpp = *vpp;
		vpp2 = vpp + 1;
		*vpp2 = LINK_PNTR(*vpp, nextoff);
	}

	HeapSort((VoidPtr)vpp0, nitems, sizeof(VoidPtr), cmpfunc);

	for (vpp = vpp0, wpp = wpp0; vpp < vppmax; vpp = vpp2)
		LINK_PNTR(*vpp, nextoff) = NULL;

	for (vpp = vpp0, wpp = wpp0; vpp < vppmax; vpp = vpp2) {
		if (*vpp != *wpp) {
			memcpy(itemp, *wpp, size);
			memcpy(*wpp, *vpp, size);
			memcpy(*vpp, itemp, size);
			LINK_PNTR(*vpp, nextoff) = *wpp;
			LINK_PNTR(*wpp, nextoff) = *vpp;
		}
	}


	/* Linkize the list */
	for (vpp = vpp0; vpp < vppmax; vpp = vpp2) {
		vpp2 = vpp + 1;
		LINK_PNTR(*vpp, nextoff) = *vpp2;
	}
	LINK_PNTR(*vpp, nextoff) = NULL;

	retcode = 0;

Exit:
	if (vpp0 != vpstack)
		Nlm_Free(vpp0);
	return retcode;
}
#endif