/**
*** PQ.C
***  fuer Beschreibung etc. siehe Dr. Dobb's 6'87
***  this has been modified slightly for huffman structures
**/

#include <STDIO.H>
#include "pq.h"

#include "huffman.h"

#define STATIC


#ifndef HUFFMANN
	#define PQ_SWAP(p,ptr1,ptr2) (*p->swap)(ptr1,ptr2)
	#define PQ_CMP(p,ptr1,ptr2)  (*p->cmp)(ptr1,ptr2)
#else


/* 
#define PQ_SWAP(p,ptr1,ptr2) huff_swap((void*)ptr1,(void*)ptr2)

STATIC void _fastcall huff_swap(struct huff_tab **c1,struct huff_tab **c2)
{
	void *tmp;
	tmp = *c1;
	*c1 = *c2;
	*c2 = tmp;
}
*/

#define PQ_SWAP(p,c1,c2)	{							\
	void *tmp;											\
	tmp = *(struct hufftab **)c1;						\
	*(struct hufftab **)c1 = *(struct hufftab **)c2;	\
	*(struct hufftab **)c2 = tmp;						}




#define PQ_CMP(p,ptr1,ptr2) ((int)(((*(struct huff_tab **)ptr2)->count - \
							        (*(struct huff_tab **)ptr1)->count ) ))

//#define PQ_CMP(p,ptr1,ptr2)  huff_cmp((void*)ptr1,(void*)ptr2)
//
//STATIC int _fastcall huff_cmp(struct huff_tab **c1,struct huff_tab **c2);
//STATIC int _fastcall huff_cmp(struct huff_tab **c1,struct huff_tab **c2)
//{
//	return (*c2)->count-(*c1)->count;
//}
#endif


	




/*****************************************************************/

STATIC void reheap_down(register PQ *p)
	{
	int parent;
	int child;
	char *pparent;
	char *pchild;
	char *psibling;
	char *heap;

	heap = p->heap;

	for (parent = 0,  child = 1;  child < p->nitems;  )
		{
		pparent = heap + (parent * p->itemsize);
		pchild = heap + (child * p->itemsize);

		if (child + 1 < p->nitems)
			{
			psibling = pchild + p->itemsize;
			if (PQ_CMP(p,pchild, psibling) < 0)
				{
				pchild = psibling;
				++child;
				}
			}

		if (PQ_CMP(p,pparent, pchild) >= 0)
			break;

		PQ_SWAP(p,pparent, pchild);

		parent = child;
		child = (parent * 2) + 1;
		}
	}

/*****************************************************************/

STATIC void reheap_up(register PQ *p)
	{
	int parent;
	int child;
	char *pparent;
	char *pchild;
	char *heap;

	child = p->nitems - 1;
	heap = p->heap;

	while (child > 0)
		{
		parent = (child - 1) / 2;
		pchild = heap + (child * p->itemsize);
		pparent = heap + (parent * p->itemsize);

		if (PQ_CMP(p,pparent, pchild) >= 0)
			break;

		PQ_SWAP(p,pparent, pchild);
		child = parent;
		}
}

/*****************************************************************/

PQ *pq_create(numele, elesize, cmp, swap, initheap)
int numele;
int elesize;
int (*cmp)();
void (*swap)();
void *initheap;
	{
	register PQ *p;
	void *malloc();
	int heapsize;

	heapsize = numele * elesize;

	if (initheap)
		{
		if ((p = malloc(sizeof(PQ))) == NULL)
			return NULL;

		p->heap = initheap;
		p->bottom = (char *)initheap + ((numele - 1) * elesize);
		p->nitems = numele;
		}
	else 
		{
		if ((p = malloc(sizeof(PQ) + heapsize)) == NULL)
			return NULL;
		p->heap = (char *) (p + 1);
		p->nitems = 0;
		p->bottom = p->heap - elesize;
		}

	p->cmp = cmp;
	p->swap = swap;
	p->itemsize = elesize;
	p->maxitem = numele;
	return p;
	}

/*****************************************************************/

int pq_ins(register PQ *p,void *item)
	{
	int spaceavail = p->maxitem - p->nitems;

	if (spaceavail > 0)
		{
		p->nitems++;
		memcpy(p->bottom += p->itemsize, item, p->itemsize);
		reheap_up(p);
		}
	return spaceavail;
	}

/*****************************************************************/
int pq_del(register PQ *p,void *target)
	{
	int slots_in_use;

	if (slots_in_use = p->nitems)
		{
		memcpy(target, p->heap, p->itemsize);
		memcpy(p->heap, p->bottom, p->itemsize);
		p->nitems--;
		p->bottom -= p->itemsize;
		reheap_down(p);
		}
	return slots_in_use;
	}

/*****************************************************************/

char *pq_look(register PQ *p)
	{
	return p->heap;
	}

/*****************************************************************/

int pq_numele(register PQ *p)
	{
	return p->nitems;
	}