# $Id: heap.m,v 1.2 2001/06/27 20:52:57 ksb Exp $
# the heap of misery -- files to be deleted

require "util_ppm.m"

%i
typedef struct THnode {
	char *pcdir;
	char *pcfile;
	int iweight;
} TRASH_HEAP;
static void HeapDump(FILE *);
extern int HeapInsert(char*, char*, int);
extern int HeapDequeue(char **, char **, int *);

#if !defined(TRASH_CAN_SIZE)
#define TRASH_CAN_SIZE	8192
#endif

%%

init 'util_ppm_init(& PPMTrash, sizeof(TRASH_HEAP), TRASH_CAN_SIZE);'


%c
static int iTrashCur = 0;
static PPM_BUF PPMTrash;

/* debug routine to output the heap					(ksb)
 */
static void
HeapOut(FILE *fp, int iDeep, int iDx, TRASH_HEAP *pTRCur)
{
	register int i;
	printf("%*.*s", iDeep, iDeep, " ");
	if (iDx >= iTrashCur) {
		printf(".\n");
		return;
	}
	fprintf(fp, "%s/%s <%d>\n", pTRCur[iDx].pcdir, pTRCur[iDx].pcfile, pTRCur[iDx].iweight);
	i = 2*(iDx+1)-1;
	if (i < iTrashCur) {
		HeapOut(fp, iDeep+1, i, pTRCur);
		HeapOut(fp, iDeep+1, i+1, pTRCur);
	}
}

static void
HeapDump(FILE *fp)
{
	HeapOut(fp, 0, 0, util_ppm_size(& PPMTrash, 0));
}


/* put the heap back in heap order					(ksb)
 */
int
HeapDrop(pTRHeap, iDrop)
TRASH_HEAP *pTRHeap;
int iDrop;
{
	register int iPar;
	auto TRASH_HEAP THSwap;

	for (/* param */; iDrop > 0; iDrop = iPar) {
		iPar = (iDrop-1)/2;
		if (pTRHeap[iDrop].iweight <= pTRHeap[iPar].iweight) {
			break;
		}
		THSwap = pTRHeap[iPar];
		pTRHeap[iPar] = pTRHeap[iDrop];
		pTRHeap[iDrop] = THSwap;
	}
	return 1;
}

/* put this in the heap of misery					(ksb)
 */
int
HeapInsert(pcDir, pcFile, iWeight)
char *pcDir, *pcFile;
int iWeight;
{
	register TRASH_HEAP *pTRList, *pTREnd;
	register int i;
	static char *pcLastDir = (char *)0;

	i = iTrashCur++;
	if ((TRASH_HEAP *)0 == (pTRList = util_ppm_size(& PPMTrash, iTrashCur))) {
		return 0;
	}
	pTREnd = & pTRList[i];
	if ((char *)0 == pcLastDir || 0 != strcmp(pcLastDir, pcDir)) {
		pcLastDir = strdup(pcDir);
	}
	pTREnd->pcdir = pcLastDir;
	pTREnd->pcfile = strdup(pcFile);
	pTREnd->iweight = iWeight;
	return HeapDrop(pTRList, i);
}

/* Find the next contestant						(ksb)
 * return false when we don't have one.
 */
int
HeapDequeue(ppcDir, ppcFile, piWeight)
char **ppcDir, **ppcFile;
int *piWeight;
{
	register TRASH_HEAP *pTRCur, *pTRList;
	register int iLeft, iRight;

	if (0 == iTrashCur || (TRASH_HEAP *)0 == (pTRList = util_ppm_size(& PPMTrash, 0))) {
		return 0;
	}

	pTRCur = pTRList;
	*ppcDir = pTRCur->pcdir;
	*ppcFile = pTRCur->pcfile;
	*piWeight = pTRCur->iweight;
	iLeft = 1, iRight = 2;
	pTRCur->iweight = -1;

	/* inv.: empty slot at pTRCur, kids at iLeft and maybe iRight
	 * fill this slot, find next slot.
	 */
	while (iLeft < iTrashCur) {
		if (iRight < iTrashCur && pTRList[iRight].iweight >= pTRList[iLeft].iweight) {
			iLeft = iRight;
		}
		pTRCur->pcdir = pTRList[iLeft].pcdir;
		pTRCur->pcfile = pTRList[iLeft].pcfile;
		pTRCur->iweight = pTRList[iLeft].iweight;
		pTRCur = & pTRList[iLeft];
		iRight = (iLeft + 1)*2;
		iLeft = iRight-1;
	}
	
	if (pTRCur == & pTRList[--iTrashCur]) {
		return 1;
	}
	pTRCur->pcdir = pTRList[iTrashCur].pcdir;
	pTRCur->pcfile = pTRList[iTrashCur].pcfile;
	pTRCur->iweight = pTRList[iTrashCur].iweight;

	return HeapDrop(pTRList, pTRCur-pTRList);
}
%%